IP Library › Granted Patent US 12,242,796
Granted Patent B2
US 12,242,796 · App. 17/807,461 · Granted Mar 4, 2025

Permutation invariance for representing linearized tabular data

Inventors: Sarthak Dash (Jersey City, NY); Sugato Bagchi (White Plains, NY); Nandana Mihindukulasooriya (Cambridge, MA); Alfio Massimiliano Gliozzo (Brooklyn, NY)
Assignee: INTERNATIONAL BUSINESS MACHINES CORPORATION
G06F40/157G06F40/284
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,242,796
App. No.
17/807,461
Granted
Mar 4, 2025
Kind
B2
Abstract

An embodiment for encoding permutation-invariant representations of linearized tabular data. The embodiment may receive input including tabular data and linearize a column or row within the received tabular data. The embodiment may automatically assign an increasing sequence of position identifiers to each non-delimiting tokenized cell in the linearized column or row until a header delimiter is reached. The embodiment may, in response to reaching the header delimiter, automatically assign a monotonically increasing sequence of position identifiers for each non-delimiting tokenized cell positioned after the header delimiter, restarting from an integer corresponding to 1 greater than the position identifier assigned to the header delimiter for each non-delimiting tokenized cell positioned after cell delimiters. The embodiment may automatically assign a static position identifier for each of the cell delimiters in the linearized column or row and output an encoded permutation-invariant representation of the linearized column or row.

Claims (37)

1. A computer-based method of encoding tabular data with permutation invariance, the method comprising:

receiving input including tabular data and linearizing a column or row within the received tabular data;

automatically assigning an increasing sequence of position identifiers to each non-delimiting tokenized cell in the linearized column or row until a header delimiter is reached;

in response to reaching the header delimiter, automatically assigning a monotonically increasing sequence of position identifiers for each non-delimiting tokenized cell positioned after the header delimiter, restarting from an integer corresponding to 1 greater than the position identifier assigned to the header delimiter for each non-delimiting tokenized cell positioned after cell delimiters;

automatically assigning a static position identifier for each of the cell delimiters in the linearized column or row, the static position identifier being 1 greater than a highest position identifier assigned to the non-delimiting tokenized cells; and

automatically outputting an encoded permutation-invariant representation of the linearized column or row.

2. The computer-based method of claim 1 , further comprising inputting the encoded permutation invariant representation into a pretrained transformer model to generate a final vector.

3. The computer-based method of claim 2 , further comprising using the generated final vector as an input for performing table search functions.

4. The computer-based method of claim 2 , further comprising using the final vector as an input for performing for table question-answering functions.

5. The computer-based method of claim 2 , further comprising using the final vector as an input for performing table interpretation functions.

6. The computer-based method of claim 2 , further comprising using the final vector as an input in a down-stream table analytics function carried out in a supervised setup.

7. The computer-based method of claim 2 , further comprising using the final vector as an input for performing a down-stream table analytics function carried out in a zero-shot setting.

8. A computer system, the computer system comprising:

one or more processors, one or more computer-readable memories, one or more computer-readable tangible storage medium, and program instructions stored on at least one of the one or more computer-readable tangible storage medium for execution by at least one of the one or more processors via at least one of the one or more computer-readable memories, wherein the computer system is capable of performing a method comprising:

receiving input including tabular data and linearizing a column or row within the received tabular data;

automatically assigning an increasing sequence of position identifiers to each non-delimiting tokenized cell in the linearized column or row until a header delimiter is reached;

in response to reaching the header delimiter, automatically assigning a monotonically increasing sequence of position identifiers for each non-delimiting tokenized cell positioned after the header delimiter, restarting from an integer corresponding to 1 greater than the position identifier assigned to the header delimiter for each non-delimiting tokenized cell positioned after cell delimiters;

automatically assigning a static position identifier for each of the cell delimiters in the linearized column or row, the static position identifier being 1 greater than a highest position identifier assigned to the non-delimiting tokenized cells; and

automatically outputting an encoded permutation-invariant representation of the linearized column or row.

9. The computer system of claim 8 , further comprising inputting the encoded permutation invariant representation into a pretrained transformer model to generate a final vector.

10. The computer system of claim 9 , further comprising using the generated final vector as an input for performing table search functions.

11. The computer system of claim 9 , further comprising using the final vector as an input for performing for table question-answering functions.

12. The computer system of claim 9 , further comprising using the final vector as an input for performing table interpretation functions.

13. The computer system of claim 9 , further comprising using the final vector as an input in a down-stream table analytics function carried out in a supervised setup.

14. The computer system of claim 9 , further comprising using the final vector as an input for performing a down-stream table analytics function carried out in a zero-shot setting.

15. A computer program product, the computer program product comprising:

one or more computer-readable tangible storage medium and program instructions stored on at least one of the one or more computer-readable tangible storage medium, the program instructions executable by a processor capable of performing a method, the method comprising:

receiving input including tabular data and linearizing a column or row within the received tabular data;

automatically assigning an increasing sequence of position identifiers to each non-delimiting tokenized cell in the linearized column or row until a header delimiter is reached;

in response to reaching the header delimiter, automatically assigning a monotonically increasing sequence of position identifiers for each non-delimiting tokenized cell positioned after the header delimiter, restarting from an integer corresponding to 1 greater than the position identifier assigned to the header delimiter for each non-delimiting tokenized cell positioned after cell delimiters;

automatically assigning a static position identifier for each of the cell delimiters in the linearized column or row, the static position identifier being 1 greater than a highest position identifier assigned to the non-delimiting tokenized cells; and

automatically outputting an encoded permutation-invariant representation of the linearized column or row.

16. The computer program product of claim 15 , further comprising inputting the encoded permutation invariant representation into a pretrained transformer model to generate a final vector.

17. The computer program product of claim 16 , further comprising using the generated final vector as an input for performing table search functions.

18. The computer program product of claim 16 , further comprising using the final vector as an input for performing for table question-answering functions.

19. The computer program product of claim 16 , further comprising using the final vector as an input for performing table interpretation functions.

20. The computer program product of claim 16 , further comprising using the final vector as an input in a down-stream table analytics function carried out in a supervised setup.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 17, 2022
From: DASH, SARTHAK; BAGCHI, SUGATO; MIHINDUKULASOORIYA, NANDANA; GLIOZZO, ALFIO MASSIMILIANO
To: INTERNATIONAL BUSINESS MACHINES CORPORATION
Reel/Frame 060236/0765 →
Continuity (1)
Related Publication 20230409806A1 · Dec 21, 2023
References Cited (49)
US 8099382B2 · Liu et al. · 2012 [cited by applicant]
US 8214378B2 · Kohlhammer et al. · 2012 [cited by applicant]
US 11080607B1 · Demtchenko · 2021 [cited by applicant]
US 11188585B2 · Yanosy et al. · 2021 [cited by applicant]
US 11256995B1 · Bucher · 2022 [cited by applicant]
US 11263534B1 · Prat · 2022 [cited by applicant]
US 20170230171A1 · Gadepally · 2017 [cited by examiner]
US 20210090692A1 · Schmeink et al. · 2021 [cited by applicant]
US 20210286942A1 · Benson · 2021 [cited by applicant]
US 20220051126A1 · Quader et al. · 2022 [cited by applicant]
US 20230316147A1 · Dias et al. · 2023 [cited by applicant]
US 20230418848A1 · Clinchant et al. · 2023 [cited by applicant]
KR 100842263B1 · 2008 [cited by applicant]
KR 1020220004574A · 2022 [cited by applicant]
KR 102385983B1 · 2022 [cited by applicant]
Cohen-Karlik, et al., “Regularizing Towards Permutation Invariance in Recurrent Models”, 34th Conference on Neural Information Processing Systems, NeurIPS, 2020, 11 pages. [cited by applicant]
Deng, et al. “TURL: Table Understanding through Representation Learning.” Proceedings of the VLDB Endowment, 2021, vol. 14, No. 3, pp. 307-319. https://doi.org/10.14778/3430915.3430921. [cited by applicant]
Disclosed Anonymously, “Spatial-Temporal Skeleton Transformers for Action Recognition”, IP.com, IPCOM000266923D, Sep. 1, 2021, 8 Pages. https://ip.com/IPCOM/000266923. [cited by applicant]
Habibi, et al., “DeepTable: a permutation invariant neural network for table orientation classification”, Springer, Data Mining and Knowledge Discovery, Sep. 8, 2020, 21 Pages. https://link.springer.com/article/10.1007/… [cited by applicant]
Hulsebos, et al., “Sherlock: A deep learning approach to semantic data type detection”, Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. Aug. 4-8, 2019, 9 Pages. https://… [cited by applicant]
Disclosed Anonymously, “Explainability of Automatically Trained ML Models”, IP.com IPCOM000268322D; Jan. 24, 2022, 4 Pages. https://ip.com/IPCOM/000268322. [cited by applicant]
Disclosed Anonymously, “Optimize Agile Project Execution Plans by Mining User Story Interdependencies via Machine Learning Techniques”, IP.com, IPCOM000268697D, Feb. 16, 2022, 10 Pages. https://ip.com/IPCOM/000268697. [cited by applicant]
Jimenez-Ruiz, et al., “Results of SemTab 2020”, CEUR Workshop Proceedings, 2775, 2020, 9 Pages. https://openaccess.city.ac.uk/id/eprint/25441/1/. [cited by applicant]
Kalra, et al., “Learning Permutation Invariant Representations Using Memory Networks”, ArXiv, Jul. 3, 2020, 17 pages. arXiv:1911.07984v2[cs.LG]. [cited by applicant]
Lee, et al., “Set Transformer: A Framework for Attention-based Permutation-Invariant Neural Networks”, Proceedings of the 36th International Conference on Machine Learning, PMLR 97, 2019, 10 Pages. http://proceedings.ml… [cited by applicant]
Mell et al., “The NIST Definition of Cloud Computing”, Recommendations of the National Institute of Standards and Technology, NIST Special Publication 800-145, Sep. 2011, 7 pages. [cited by applicant]
Pang, et al., “SetRank: Learning a Permutation-Invariant Ranking Model for Information Retrieval,” arXiv:1912.05891v1 [cs.IR], Dec. 12, 2019, Proceedings of ACM Conference (Conference '17), Jul. 2017, ACM, 11 pgs., http… [cited by applicant]
Santoro, et al., “A simple neural network module for relational reasoning”, 31st Conference on Neural Information Processing Systems, NIPS, 2017, 10 pages. https://proceedings.neurips.cc/paper/2017/file/e6acf4b0f69f6f6e… [cited by applicant]
Vinyals, et al., “Order Matters: Sequence to Sequence for Sets”, ICLR, Feb. 23, 2016, 11 pages. arXiv:1511.06391v4[stat.ML]. [cited by applicant]
Yang, et al. “Robust attentional aggregation of deep feature sets for multi-view 3D reconstruction.” International Journal of Computer Vision 128.1 (2020), pp. 53-73. https://link.springer.com/content/pdf/10.1007/s11263… [cited by applicant]
Zaheer, et al., “Deep Sets”, 31st Conference on Neural Information Processing System, NIPS, 2017, 11 pages. https://papers.nips.cc/paper/2017/file/f22e4747da1aa27e363d86d40ff442fe-Paper.pdf. [cited by applicant]
Zhang, et al., “Web table extraction, retrieval, and augmentation: A survey,” ACM Transactions on Intelligent Systems and Technology, Feb. 2020, ResearchGate, 36 pgs. [cited by applicant]
Chen, et al.. “Learning Semantic Annotations for Tabular Data”, Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI, 2019 , pp. 2088-2094. https://www.ijcai.org/Proceedings/… [cited by applicant]
Abdelmageed, et al., “JenTab Meets SemTab 2021's New Challenges”, SemTab@ISWC 2021, https://paperswithcode.com/paper/jentab-meets-semtab-2021-s-new-challenges, Accessed on May 18, 2023, 15 Pages. [cited by applicant]
Cutrona, et al., “Tough Tables: Carefully Evaluating Entity Linking for Tabular Data”, Springer International Publishing, The Semantic Web—ISWC 2020, Lecture Notes in Computer Science, 18 pages. [cited by applicant]
Dash, et al., “Permutation Invariant Strategy Using Transformer Encoders for Table Understanding”, Findings of the Association for Computational Linguistics, NAACL 2022, 14 Pages. [cited by applicant]
Hendrycks, et al., “Gaussian Error Linear Units (GELUs)”, arXiv:1606.08415v4 [cs.LG], Jul. 8, 2020, 9 Pages. [cited by applicant]
Hu, et al., “VizNet: Towards A Large-Scale Visualization Learning and Benchmarking Repository”, CHI 2019, May 4-9, 2019, ACM, pp. 1-12. [cited by applicant]
IBM: List of IBM Patents or Patent Applications Treated as Related (Appendix P), Jun. 1, 2023, 2 pages. [cited by applicant]
Iida, et al., “Tabbie: Pretrained Representations of Tabular Data”, Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Jun. 6-… [cited by applicant]
Jimenez-Ruiz, “SemTab 2019: Resources to Benchmark Tabular Data to Knowledge Graph Matching Systems”, ResearchGate, Conference Extended Semantic Web Conference (ESWC), Jun. 2020, 17 Pages. https://www.researchgate.net/p… [cited by applicant]
Johnson, et al., “Billion-scale similarity search with GPUs”, arXiv:1702.08734v1 [cs.CV], Feb. 28, 2017, 12 Pages. [cited by applicant]
Khattab, et al., “ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT”, arXiv:2004.12832v2 [cs.IR] Jun. 4, 2020, 10 Pages. [cited by applicant]
McCray, “An upper-level ontology for the biomedical domain”, Comparative and Functional Genomics, Comp Funct Genom 2003; pp. 80-84. [cited by applicant]
Mulwad, et al., “Using linked data to interpret tables”, ResearchGate, Nov. 2010, 13 Pages. https://www.researchgate.net/publication/228806432_Using_linked_data_to_interpret_tables. [cited by applicant]
Ritze, et al., “Matching HTML Tables to DBpedia”, Wims, 2015, ACM, 6 Pages. [cited by applicant]
Suhara, et al., “Annotating Columns with Pre-trained Language Models”, arXiv:2104.01785v2 [cs.DB], Mar. 1, 2022, 15 pages. [cited by applicant]
Zhang, et al., “Sato: Contextual Semantic Type Detection in Tables”, Proceedings of the VLDB Endowment, vol. 13, No. 11, 2020, pp. 1835-1848. [cited by applicant]
Zhu et al., Permutation-Invariant Tabular Data Synthesis. 2022 IEEE International Conference on Big Data (Big Data), Osaka, Japan, 2022 pp. 5855-5864. [retrieved online Jun. 5, 2024], Retrieved from the Internet: doi: 1… [cited by applicant]