IP Library › Granted Patent US 12,346,297
Granted Patent B2
US 12,346,297 · App. 17/888,560 · Granted Jul 1, 2025

Database record lineage and vector search

Inventors: Oded Shmueli (Haifa, IL); Michael Leybovich (Haifa, IL)
Assignee: Technion Research & Development Foundation Limited
G06F16/2237G06F16/24537G06F16/258G06F16/285
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,346,297
App. No.
17/888,560
Granted
Jul 1, 2025
Kind
B2
Abstract

There is provided a method of computing lineage, comprising: managing a dataset of records, each record associated with set(s) of vectors of real numbers that encode an approximation of lineage of the respective record, the set(s) of vectors computed by an encoding process, obtaining result record(s) in response to executing a query on the dataset, computing set(s) of vectors for the result record(s), searching the set(s) of vectors on the records of the dataset to identify a record associated with a subset of vectors that are statistically similar to the set(s) of vectors for the result record(s), and providing a subset of the records corresponding to the identified subset of records, the subset of the records having a likelihood of contributing to the existence of the result record(s) in response to execution of the query.

Claims (74)

1. A computer implemented method for reducing processing time of at least one hardware processor searching a dataset by executing a search engine based on computing lineage for result records of a query for execution on the dataset, comprising:

managing a dataset of a plurality of records stored on at least one a data server, each record associated with at least one set of vectors of real numbers that encode an approximation of lineage of the respective record, the at least one set of vectors computed by an encoding process,

wherein the lineage of a certain record includes a plurality of records of the dataset whose existence led to the existence of the certain record by a sequence of database operations;

by the at least one hardware processor:

receiving said query transmitted from at least one client terminal over a communication network;

accessing, through said communication network, at least one data server storing said dataset;

conducting a two-phase search, wherein:

in a first phase:

instructing the search engine to execute the query on the dataset to identify at least one result record;

computing at least one set of result vectors comprising lineage for the at least one result record using the encoding process and/or by executing operations on sets, of vectors, of records according to the query;

in a second phase:

instructing the search engine to execute a search, using the at least one set of result vectors, on the plurality of sets of vectors of records of the dataset to identify a subset of target records such that each is associated with a target set of vectors that is statistically similar to the at least one set of result vectors of the at least one result record, wherein said searching based on said statistical similarity reduces execution time of said searching;

wherein the statistical similarity is computed between a target set of vectors and a set of result vectors by considering each of the target set of vectors and the set of result vectors as a respective single unit;

outputting a subset of the plurality of target records of the dataset corresponding to the identified subset of target records, the subset of the plurality of target records having a likelihood of contributing to the existence of the at least one result record in response to execution of the query by the search engine,

wherein each set of the target set of vectors and the set of result vectors includes at least two members; and

feeding the outputted subset to at least one of an automated alert generation process and an automated analysis process for detection and/or corrections of errors of the records.

2. The computer implemented method of claim 1 , further comprising:

converting, for each dataset record, the at least one set of vectors to a single long vector;

converting the at least one set of vectors computed for the at least one result record to a single long vector;

wherein searching comprises searching a plurality of single long vector of the plurality of records to identify a subset of long vectors associated with the plurality of records such that each long vector is statistically similar to the single long vector computed for the at least one result record.

3. The method of claim 1 , wherein the query comprises insertion of a new record into the dataset, computing comprises computing at least one set of vectors for the new record formed by an encoding process, annotating the new record with the at least one set of vectors computed for the new record, and inserting the annotated new record into the dataset.

4. The method of claim 1 , wherein the query comprises at least one operation executed on the plurality of records to generate at least one result record, computing comprises computing the at least one set of vectors for the at least one result record by executing the at least one operation on the at least one set of vectors of the plurality of dataset records according to the query.

5. The method of claim 4 , wherein the at least one operation comprises an OR operator indicating alternative use of data, and computing the at least one set of vectors for the at least one result record comprises computation of a lineage embedding of two records using the OR operator.

6. The method of claim 5 , wherein the lineage embedding of two records using the OR operator is computed by:

computing a union vector set by a union operation between the at least one set of vectors of the first record and the at least one set of vectors of the second record;

when the number of vector members of the union vector set is greater than a maximum allowed number of vectors,

clustering the vector members of the union vector set into clusters, wherein the number of clusters is set according to the maximum allowed number of vectors,

and setting the lineage embedding as at least one set of vectors that includes vectors of centroids of the clusters, wherein the number of vectors of centroids matches the maximum allowed number of vectors.

7. The method of claim 4 , wherein the at least one operation comprises an AND operator indicating joint use of data, and computing the at least one set of vectors for the at least one new record comprises computation of a lineage embedding of two records using the AND operator.

8. The method of claim 7 , wherein the lineage embedding of two records using the AND operator is computed by:

computing a Cartesian product of the at least one set of vectors of the first record and the at least one set of vectors of the second record, to obtain a set of pairs of vectors;

computing a respective average vector for each pair of vectors of the Cartesian product, and

setting the lineage embedding as at least one set of vectors that includes a plurality of average vectors.

9. The method of claim 1 , wherein the at least one set of vectors for each of the plurality of records of the dataset is computed by:

obtaining a corpus of the dataset;

converting words of records of the corpus into a single text unit; and

training a word embedding model on the single text unit, wherein the encoding process comprises the word embedding model that is trained.

10. The method of claim 9 , further comprising:

for each respective record:

feeding each of a plurality of words of the respective record into the word embedding model to obtain a plurality of word vectors;

computing an intra and inter-field weighted average over the word vectors of each word of the respective record, and

setting the at least one set of vectors as the intra and inter-field weighted average.

11. The method of claim 1 , wherein each column of each record is associated with at least one set of vectors.

12. The method of claim 1 , further comprising verifying the subset of the plurality of records, by applying the query to the subset of the plurality of records in the identified subset of records, the subset of the plurality of records having a likelihood of contributing to the existence of the at least one result record in response to execution of the query.

13. The method of claim 1 , wherein a respective record of the plurality of dataset records is associated with a respective timestamp indicating when the respective record was created, and further comprising at least one of: (i) filtering out from the identified subset of records, records which are non-lineage records according to their later timestamps, and (ii) filtering out, from the identified subset of records, records which fall outside the target time interval from the searching.

14. The method of claim 1 , further comprising:

analyzing the query to identify at least one column of interest, and

wherein the searching is performed by assigning larger weights to records having the at least one column of interest.

15. The method of claim 1 , further comprising:

storing for each respective record, at least one previous query where the respective record was involved in the evaluation of the at least one previous query and/or where the at least one previous query inserted the respective record; and

using the stored at least one previous query for filtering out records that are similar to the identified subset of records but that were not involved in the evaluation of the query.

16. The method of claim 1 , further comprising:

tracking dependencies between queries in a directed acyclic graph (DAG) structure, wherein during searching, weights assigned to the identified subset of records are inversely proportional to a distance on the DAG between the query and other queries that created records corresponding to the identified subset.

17. The method of claim 1 , wherein the searching is performed by balancing a minimum squared Euclidean distance between a vector from the set of vectors associated with a record of the dataset and a vector from the set of vectors associated with the at least one result record, and an average of squared Euclidean distances for pairs of vectors including one vector from the set of vectors associated with a record of the dataset and one vector from the set of vectors associated with the at least one result record.

18. The method of claim 1 , wherein the searching is performed by balancing between a maximum cosine similarity between a vector from the set of vectors associated with a record of the dataset and a vector from the set of vectors associated with the at least one result record, and an average of pair-wise cosine similarities for pairs of vectors including one vector from the set of vectors associated with a record of the dataset and one vector from the set of vectors associated with the at least one result record.

19. A method for reducing processing time of at least one hardware processor searching a dataset by executing a search engine, comprising:

by the at least one hardware processor executing said search engine:

receiving a search query transmitted from at least one client terminal over a communication network, said search query comprising at least one set of result vectors for searching on a dataset of a plurality of records, each record including at least one target set of vectors of real numbers that encode an approximation of lineage of the respective record, wherein the lineage of a certain record includes a plurality of records of the dataset whose existence led to the existence of the certain record by a sequence of database operations;

accessing, through said communication network, at least one data server storing said dataset;

converting, for each record, the at least one set of vectors to single long vector;

conducting a two-phase search, wherein:

in a first phase:

instructing the search engine to execute the query on the dataset to identify at least one result record;

converting the at least one set of result vectors computed for a database query's at least one output record comprising a lineage encoding set of vectors to a single long vector;

in a second phase:

instructing the search engine to execute a search on a plurality of single long vectors of the plurality of records to identify a subset in which each long vector is statistically similar to the single long vector computed for the database query, wherein the statistical similarity is computed between a target set of vectors and a set of result vectors by considering each of the target set and the set of result vectors as a respective single unit in the form of the single long vector, wherein said searching based on said statistical similarity reduces execution time of said searching;

outputting the at least one set of vectors and the associated records of the identified subset being statistically similar to the at least one set of vectors of the search query,

wherein each set of the target set of vectors and the set of result vectors includes at least two members; and

feeding the outputted subset to at least one of an automated alert generation process and an automated analysis process for detection and/or corrections of errors of the records.

20. The method of claim 19 , wherein each one of the vectors of a set of vectors is of a same dimension, and a dot product between a first single long vector computed from a first set of vectors and a second single long vector computed from a second set of vectors computes similarities between two sets corresponding to the first set of vectors and the second set of vectors.

21. The method of claim 20 , wherein each single long vector includes a first component used for computation of the average of pair-wise similarities between the two sets and a second component used for computation of the maximum of the pair-wise similarities used for the searching.

22. The method of claim 21 , wherein the pair-wise similarities is at least one of: (i) balancing a minimum squared Euclidean distance between a single long vector of the dataset and the single long vector of the at least one output record, and an average of squared Euclidean distances for pairs of single long vectors including one single long vector from the dataset and one single long vector from the at least one output record, and (ii) balancing between a maximum cosine similarity amongst pairs of single long vectors of the dataset, including one single long vector from the dataset and one single long vector from the at least one output record, and an average of the pair-wise cosine similarities between the pairs of single long vectors.

23. The method of claim 19 , further comprising normalizing vectors in each set of vectors.

24. The method of claim 19 , wherein each one of the vectors of one set of vectors is of a same dimension, and wherein the single long vector is created by concatenating a number of copies of each normalized one of the vectors of the one set of vectors, where the number of copies equals the number of vectors in the one set of vectors, wherein each vector that is concatenated is a normalized vector of the one set of vectors repeated a number of times equal to the number of vectors.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Sep 7, 2022
From: SHMUELI, ODED; LEYBOVICH, MICHAEL
To: TECHNION RESEARCH & DEVELOPMENT FOUNDATION LIMITED
Reel/Frame 061008/0161 →
Continuity (2)
Provisional Application 63238167 · Aug 29, 2021
Related Publication 20230061341A1 · Mar 2, 2023
References Cited (69)
US 8005817B1 · Amer-Yahia · 2011 [cited by examiner]
US 10255323B1 · Guo et al. · 2019 [cited by applicant]
US 10984030B2 · Bordawekar et al. · 2021 [cited by applicant]
US 20180075095A1 · Srivastava · 2018 [cited by examiner]
US 20180365579A1 · Wan · 2018 [cited by examiner]
US 20190220471A1 · Mota Toledo · 2019 [cited by examiner]
US 20200074274A1 · Fan · 2020 [cited by examiner]
US 20210158918A1 · Neumann · 2021 [cited by examiner]
US 20210182293A1 · Zhang · 2021 [cited by examiner]
US 20210192282A1 · Goodsitt · 2021 [cited by examiner]
US 20210294780A1 · Lifsches · 2021 [cited by examiner]
US 20210326400A1 · Qiu · 2021 [cited by examiner]
US 20220012538A1 · Mizoguchi · 2022 [cited by examiner]
US 20220121636A1 · Zheng · 2022 [cited by examiner]
US 20240152495A1 · Joyce · 2024 [cited by examiner]
Ainy et al. “Approximated Summarization of Data Provenance”, Proceedings of the 24th ACM International Conference on Information and Knowledge Management, CIKM '15, Melbourne, Australia, Oct. 19-23, 2015, p. 483-492, Oc… [cited by applicant]
Almeida et al. “Scalable Bloom Filters”, Information Processing Letters, 101(6): 255-261, Available Online Nov. 22, 2006. [cited by applicant]
Andoni et al. “Practical and Optimal LSH for Angular Distance”, Advances in Neural Information Processing Systems, NIPS 2015, 28: 1225-1233, Dec. 7, 2015. [cited by applicant]
Arora et al. “On Embeddings in Relational Databases”, ArXiv Preprint ArXiv:2005.06437v1, p. 1-9, May 13, 2020. [cited by applicant]
Arya et al. “Approximate Nearest Neighbor Queries in Fixed Dimensions”, Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '93, Chap.30: 271-280, Jan. 1993. [cited by applicant]
Bordawekar et al. “Cognitive Database: A Step Towards Endowing Relational Databases With Artificial Intelligence Capabilities”, ArXiv Preprint ArXiv:1712.07199v1, p. 1-14, Dec. 19, 2017. [cited by applicant]
Bordawekar et al. “Enabling Cognitive Intelligence Queries in Relational Databases Using Low-Dimensional Word Embeddings”, ArXiv Preprint ArXiv: 1603.07185v1, p. 1-12, Mar. 23, 2016. [cited by applicant]
Bordawekar et al. “Using Word Embedding to Enable Semantic Queries in Relational Databases”, Proceedings of the 1st Workshop on Data Management for End-to-End Machine Learning, DEEM '17, Chicago, IL, USA, May 14, 2017, … [cited by applicant]
Brecheisen et al. “Efficient Similarity Search on Vector Sets”, Datenbanksysteme in Business, Technologie und Web, 11. Fachtagung des GIFachbereichs Datenbanken und Informationssysteme, DBIS, p. 1-19, 2005. [cited by applicant]
Buneman et al. “Provenance in Databases (Tutorial Outline)”, Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data, SIGMOD '07, Beijing, China, Jun. 12-14, 2007, p. 1171-1173, Jun. 12, 2007. [cited by applicant]
Buneman et al. “Why and Where: A Characterization of Data Provenance”, Proceedings of the 8th International Conference on Database Theory, ICDT '01, LNCS 1973: 316-330, Jan. 4, 2001. [cited by applicant]
Cappuzzo et al. “Creating Embeddings of Heterogeneous Relational Datasets for Data Integration Tasks”, Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, SIGMOD '20, Portland, Oregon, USA… [cited by applicant]
Cer et al. “Universal Sentence Encoder”, ArXiv Preprint ArXiv:1803.11175v2, p. 1-7, Apr. 12, 2018. [cited by applicant]
Cui et al. “Tracing the Lineage of View Data in a Warehousing Environment”, ACM Transactions on Database Systems, TODS, 25(2): 179-227, Jun. 1, 2000. [cited by applicant]
Deutch et al. “Circuit for Dialog Provenance”, Proceedings of the 17th International Conference on Database Theory, ICDT, Athens, Greece, Mar. 24-28, 2014, p. 201-212, Mar. 24, 2014. [cited by applicant]
Deutch et al. “Provenance for Natural Language Queries”, Proceedings of the VLDB Endowment, 10(5); 577-588, Jan. 1, 2017. [cited by applicant]
Deutch et al. “Selective Provenance for Datalog Programs Using Top-K Queries”, Proceedings of the VLDB Endowment, 8(12): 1394-1405, Aug. 1, 2015. [cited by applicant]
Devlin et al. “BERT: Pre-Training of Deep Bidirectional Transformers for Language Understanding”, Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human … [cited by applicant]
Gillick et al. “Multilingual Language Processing From Bytes”, ArXiv Preprint ArXiv:1512.00103v2, p. 1-11, Apr. 2, 2016. [cited by applicant]
Gionis et al. “Similarity Search in High Dimensions Via Hashing”, Proceedings of the 25th International Conference on Very Large Data Bases, VLDB' 99, Edinburgh, Scotland, UK, Sep. 7, 1999, 99(6): 518-529, Sep. 7, 1999. [cited by applicant]
Green et al. “Provenance Semirings”, Proceedings of the Twenty-Sixth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS '07, Beijing, China, Jun. 11-13, 2007, p. 31-40, Jun. 11, 2007. [cited by applicant]
Guenther et al. “Pre-Trained Web Table Embeddings for Table Discovery”, Fourth Workshop in Exploiting AI Techniques for Data Management, aiDM'21, Virtual Event, China, Jun. 20-25, 2021, p. 24-31, Jun. 20, 2021. [cited by applicant]
Guo et al. “Quantization Based Fast Inner Product Search”, Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, AISTATS 2016, Cadiz, Spain, May 9-11, 2016, 41: 482-490, May 9, 2016. [cited by applicant]
Harper et al. “The MovieLens Datasets: History and Context”, ACM Transactions on Interactive Intelligent Systems, 5(4): Art.19-1-19-19, Dec. 2015. [cited by applicant]
Houle et al. “Rank-Based Similarity Search: Reducing the Dimensional Dependence”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 37(1): 136-150, Published Online Jul. 25, 2014. [cited by applicant]
Ives et al. “Dataset Relationship Management”, Proceedings of Conference on Innovative Database Systems Research, CIDR '19, Asilomar, CA, USA, Jan. 2019, p. 1-7, Jan. 2019. [cited by applicant]
Ives et al. “The Orchestra Collaborative Data Sharing System”, SIGMOD Recvord, 37(3): 26-32, Sep. 2008. [cited by applicant]
Jegou et al. “Product Quantization for Nearest Neighbor Search”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(1): 117-128, Pubished Online Feb. 25, 2010. [cited by applicant]
Karvounarakis et al. “Querying Data Provenance”, Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, SIGMOD '10, Indianapolis, Indiana, USA, Jun. 6-11, 2010, p. 951-962, Jun. 6, 2010. [cited by applicant]
Karvounarakis et al. “Semiring-Annotated Data: Queries and Provenance”, SIGMOD Record, 41(3): 5-14, Sep. 2012. [cited by applicant]
Klein et al. “Corpus-Based Induction of Syntactic Structure: Models of Dependency and Constituency”, Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics, ACL '04, p. 478-1-478-8, Jul. 21,… [cited by applicant]
Kretser et al. “A Partnership for Public Health: USDA Branded Food Products Database”, Journal of Food Composition and Analysis, 64: 10-12, Dec. 1, 2017. [cited by applicant]
Lee et al. “Integrating Approximate Summarization With Provenance Capture”, Proceedings of the 9th USENIX Conference on Theory and Practice of Provenance, TaPP '17, Seattle, Washington, USA, Jun. 22-23, 2017, p. 2-1-2-6… [cited by applicant]
Lee et al. “Provenance Summaries for Answers and Non-Answers”, Proceedings of the VLDB Endowment, 11(12): 1954-1957, Aug. 1, 2018. [cited by applicant]
Lelarge et al. “Hooks in PostgreSQL”, Dalibo, Blog, p. 1-56, Feb. 2012. [cited by applicant]
Leybovich et al. “Efficient Approximate Search for Sets of Vectors”, ArXiv Preprint ArXiv:2107.06817v2, p. 1-8, Aug. 30, 2021. [cited by applicant]
Leybovich et al. “ML Based Lineage in Databases [Regular Papers]”, Proceedings of the 2nd International Workshop on Applied AI for Database Systems and Applications, AIDB '20, Tokyo, Japan, Aug. 31, 2020, p. 1-12, Aug. … [cited by applicant]
Maas et al. “Learning Word Vectors for Sentiment Analysis”, Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, Portland, Oregon, USA, Jun. 19-24, 2011, p. 142-150, Jun. 19, 2011. [cited by applicant]
Malkov et al. “Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4): 824-836, Published Online … [cited by applicant]
Mel'cuk “Dependency Syntax: Theory and Practice”, SUNY Series in Linguistics, State University of New York Press, p. 1-430, 1988. (Part 1). [cited by applicant]
Mel'cuk “Dependency Syntax: Theory and Practice”, SUNY Series in Linguistics, State University of New York Press, p. 1-430, 1988. (Part 2). [cited by applicant]
Mel'cuk “Dependency Syntax: Theory and Practice”, SUNY Series in Linguistics, State University of New York Press, p. 1-430, 1988. (Part 3). [cited by applicant]
Mel'cuk “Dependency Syntax: Theory and Practice”, SUNY Series in Linguistics, State University of New York Press, p. 1-430, 1988. (Part 4). [cited by applicant]
Mikolov et al. “Distributed Representations of Words and Phrases and Their Compositionality”, Proceedings of the 26th International Conference on Neural Information Processing Systems, NIPS '13, 2: 3111-3119, Dec. 5, 20… [cited by applicant]
Mikolov et al. “Efficient Estimation of Word Representations in Vector Space”, Workshop Track Proceedings of the 1st International Conference on Learning Representations, ICLR 2013, Scottsdale, Arizona, USA, May 2-4, 20… [cited by applicant]
Mikolov et al. “Linguistic Regularities in Continuous Space Word Representations”, Proceedings of NAACL-HLT 2013, Atlanta, Georgia, USA, Jun. 9-14, 2013, p. 746-751, Jun. 9, 2013. [cited by applicant]
Muja et al. “Scalable Nearest Neighbor Algorithms for High Dimensional Data”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(11): 2227-2240, Published Online Apr. 30, 2014. [cited by applicant]
Pennington et al. “GloVe: Global Vectors for Word Representation”, Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, EMNLP '14, Doha, Quatar, Oct. 25-29, 2014, p. 1532-1543, Oct. 25… [cited by applicant]
Re et al. “Approximate Lineage for Probabilistic Databases”, Proceedings of the VLDB Endowment, PVLSB '08, Auckland, New Zealand, Aug. 23-28, 2008, 1(1): 797-808, Aug. 23, 2008. [cited by applicant]
Rehurek et al. “Software Framework for Topic Modelling With Large Corpora”, Proceedings of the LREC 2010 Workshop on New Challenges for NLP Frameworks, La Valetta, Malta, May 22, 2010, p. 46-50, May 22, 2010. [cited by applicant]
Senellart “Provenance and Probabilities in Relational Databases: From Theory to Practice”, ACM SIGMOD Record, 46(4): 5-15, Dec. 2017. [cited by applicant]
Senellart et al. “ProvSQL: Provenance and Probability Management in PostgreSQL”, Proceedings of the VLDB Endowment, 11(12): 2034-2037, Aug. 2018. [cited by applicant]
Sugawara et al. “On Approximately Searching for Similar Word Embeddings”, Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, Berlin, Germany, Aug. 7-12, 2016, p. 2265-2275, Aug. 7, … [cited by applicant]
Wu et al. “Google's Neural Machine Translation System: Bridging the Gap Between Human and Machine Translation”, ArXiv Preprint ArXiv:1609.08144v2, p. 1-23, Oct. 8, 2016. [cited by applicant]