US6295533B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for accessing heterogeneous databases
Assignee: Rutgers, The State University of New Jersey
•
Filing: 1998-02-24
•
Granted: 2001-09-25
•
Expires: 2018-02-24
Abstract
Abstract A system and method are provided for answering queries concerning information stored in a set of collections. Each collection includes a structured entity, and each structured entity includes a field. A query is received that specifies a subset of the set of collections and a logical constraint between fields that includes a requirement that a first field match a second field. The probability that the first field matches the second field is determined automatically based upon the contents of the fields. A collection of lists is generated in response to the query, where each list includes members of the subset of collections specified in the query, and where each list has an estimate of the probability that the members of the list satisfies the logical constraint specified in the query.
Inventors
- 👤 William W. Cohen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 17:39
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/25; G06F16/256; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99935
Claims Analysis
Total Claims: 34
Claim 1
Independent Claim
143 words
A method for answering a query containing a join operation, the method comprising: representing each entry in a column of a first relation by a vector; representing each entry in a column of a second relation by a vector; selecting a subset of rows of the first relation; for each of the entries in the column of the first relation that is part of a row from the subset of rows: determining the value of a similarity metric function that is based upon the vector representing the entry in the column of the first relation and a vector representing an entry from the column of the second relation, for each entry in the column of the second relation; joining the first relation with the second relation based upon the set of similanty metric function values determined; and outputting the result of the joining.
Claim 2
Independent Claim
143 words
A method for answering a query containing a join operation, the method comprising: representing each entry in a column of a first relation by a vector; representing each entry in a column of a second relation by a vector; selecting a subset of rows of the first relation; for each of the entries in the column of the first relation that is part of a row from the subset of rows: determining the value of a similarity metric function that is based upon the vector representing the entry in the column of the first relation and a vector representing an entry from the column of the second relation, for each entry in the column of the second relation; joining the first relation with the second relation based upon the set of similanty metric function values determined; and outputting the result of the joining.
Claim 3
Independent Claim
143 words
A method for answering a query containing a join operation, the method comprising: representing each entry in a field of a first relation by a vector; representing each entry in a field of a second relation by a vector; selecting a subset of tuples of the first relation; for each of the entries in the field of the first relation that is part of a tuple from the subset of tuples: determining the value of a similarity metric function that is based upon the vector representing the entry in the field of the first relation and a vector representing an entry from the field of the second relation, for each entry in the field of the second relation; joining the first relation with the second relation based upon the set of similarity metric function values determined; and outputting the result of the joining.
Claim 4
Independent Claim
143 words
A method for answering a query containing a join operation, the method comprising: representing each entry in a field of a first relation by a vector; representing each entry in a field of a second relation by a vector; selecting a subset of tuples of the first relation; for each of the entries in the field of the first relation that is part of a tuple from the subset of tuples: determining the value of a similarity metric function that is based upon the vector representing the entry in the field of the first relation and a vector representing an entry from the field of the second relation, for each entry in the field of the second relation; joining the first relation with the second relation based upon the set of similarity metric function values determined; and outputting the result of the joining.
Claim 5
Dependent Claim
32 words
The method of claim 2 wherein the joining is based on the N highest values in a subset of the set of similarity metric function values determined, where N is an integer.
Claim 6
Dependent Claim
32 words
The method of claim 2 wherein the joining is based on the N lowest values in a subset of the set of similarity metric function values determined, where N is an integer.
Claim 7
Dependent Claim
22 words
The method of claim 2 wherein an estimate of probability for correct matching of each tuple of the result is additionally output.
Claim 8
Dependent Claim
27 words
The method of claim 5 wherein the estimate of probability for a tuple is based on the value of the similarity metric function associated with that tuple.
Claim 9
Dependent Claim
27 words
The method of claim 2 wherein the first relation and the second relation are heterogeneous relations that are maintained separately and in locations remote to one another.
Claim 10
Dependent Claim
35 words
The method of claim 2 wherein each component of each vector corresponds to at least one of the following terms in the corresponding entry: a word, a word prefix, a word suffix, and a phrase.
Claim 11
Dependent Claim
33 words
The method of claim 8 wherein the value of each component of each vector is based on the frequency of the term corresponding to the component in the entry corresponding to the vector.
Claim 12
Dependent Claim
40 words
The method of claim 9 wherein the value of a component of each vector is additionally based on the frequency of occurrence of the term corresponding to the component, in all of the entries in a field including the vector.
Claim 13
Dependent Claim
13 words
The method of claim 2 wherein each vector is normalized to unit length.
Claim 14
Dependent Claim
66 words
The method of claim 2 wherein the similarity metric function is given by ∑ i v i · w i wherein v i is the i th component of a vector v corresponding to an entry in the field from the first relation, and w i is the i th component of vector w corresponding to an entry in the field from the second relation.
Claim 15
Dependent Claim
16 words
The method of claim 2 wherein the query is probabilistically answered using the A* search algorithm.
Claim 16
Independent Claim
154 words
A medium storing instructions for answering a query containing a join operation, the instructions adapted to be executed by a processor, the instructions including: representing each entry in a field of a first relation by a vector; representing each entry in a field of a second relation by a vector; selecting a subset of tuples of the first relation; for each of the entries in the field of the first relation that is part of a tuple from the subset of tuples: determining the value of a similarity metric function that is based upon the vector representing the entry in the field of the first relation and a vector representing an entry from the field of the second relation, for each entry in the field of the second relation; joining the first relation with the second relation based upon the set of similarity metric function values determined; and outputting the result of the joining.
Claim 17
Independent Claim
154 words
A medium storing instructions for answering a query containing a join operation, the instructions adapted to be executed by a processor, the instructions including: representing each entry in a field of a first relation by a vector; representing each entry in a field of a second relation by a vector; selecting a subset of tuples of the first relation; for each of the entries in the field of the first relation that is part of a tuple from the subset of tuples: determining the value of a similarity metric function that is based upon the vector representing the entry in the field of the first relation and a vector representing an entry from the field of the second relation, for each entry in the field of the second relation; joining the first relation with the second relation based upon the set of similarity metric function values determined; and outputting the result of the joining.
Claim 18
Independent Claim
30 words
The medium 14 wherein the joining is based on the N highest values in a subset of the set of similarity metric function values determined, where N is an integer.
Claim 19
Independent Claim
30 words
The medium 14 wherein the joining is based on the N highest values in a subset of the set of similarity metric function values determined, where N is an integer.
Claim 20
Dependent Claim
32 words
The medium of claim 14 wherein the joining is based on the N lowest values in a subset of the set of similarity metric function values determined, where N is an integer.
Claim 21
Dependent Claim
22 words
The medium of claim 14 wherein an estimate of probability for correct matching of each tuple of the result is additionally output.
Claim 22
Dependent Claim
27 words
The medium of claim 17 wherein the estimate of probability for a tuple is based on the value of the similarity metric function associated with that tuple.
Claim 23
Dependent Claim
27 words
The medium of claim 14 wherein the first relation and the second relation are heterogeneous relations that are maintained separately and in locations remote to one another.
Claim 24
Dependent Claim
35 words
The medium of claim 14 wherein each component of each vector corresponds to at least one of the following terms in the corresponding entry: a word, a word prefix, a word suffix, and a phrase.
Claim 25
Dependent Claim
33 words
The medium of claim 14 wherein the value of each component of each vector is based on the frequency of the term corresponding to the component in the entry corresponding to the vector.
Claim 26
Dependent Claim
40 words
The medium of claim 21 wherein the value of a component of each vector is additionally based on the frequency of occurrence of the term corresponding to the component, in all of the entries in a field including the vector.
Claim 27
Dependent Claim
13 words
The medium of claim 14 wherein each vector is normalized to unit length.
Claim 28
Dependent Claim
66 words
The medium of claim 14 wherein the similarity metric function is given by ∑ i v i · w i wherein v i is the i th component of a vector v corresponding to an entry in the field from the first relation, and w i is the i th component of vector w corresponding to an entry in the field from the second relation.
Claim 29
Dependent Claim
16 words
The medium of claim 14 wherein the query is probabilistically answered using the A* search algorithm.
Claim 30
Independent Claim
161 words
An apparatus for answering a query containing a join operation, the apparatus comprising: a processor; and a memory that stores instructions adapted to be executed by a processor, the instructions including: representing each entry in a field of a first relation by a vector; representing each entry in a field of a second relation by a vector; selecting a subset of tuples of the first relation; for each of the entries in the field of the first relation that is part of a tuple from the subset of tuples; determining the value of a similarity metric function that is based upon the vector representing the entry in the field of the first relation and a vector representing an entry from the field of the second relation, for each entry in the field of the second relation; joining the first relation with the second relation based upon the set of similarity metric function values determined; and outputting the result of the joining.
Claim 31
Independent Claim
161 words
An apparatus for answering a query containing a join operation, the apparatus comprising: a processor; and a memory that stores instructions adapted to be executed by a processor, the instructions including: representing each entry in a field of a first relation by a vector; representing each entry in a field of a second relation by a vector; selecting a subset of tuples of the first relation; for each of the entries in the field of the first relation that is part of a tuple from the subset of tuples; determining the value of a similarity metric function that is based upon the vector representing the entry in the field of the first relation and a vector representing an entry from the field of the second relation, for each entry in the field of the second relation; joining the first relation with the second relation based upon the set of similarity metric function values determined; and outputting the result of the joining.
Claim 32
Independent Claim
182 words
A method for performing a join operation, the method comprising the steps of: representing each entry in a field of a first relation and a field of a second relation as a vector; evaluating a similarity metric function on a plurality of pairs of vectors, wherein each pair from the plurality of pairs of vectors includes a vector from the field of the first relation and a vector from the field of the second relation; determining whether to join a tuple from the first relation and a tuple from the second relation based on i) the value of the similarity function evaluated on the vector corresponding to the entry that is in the tuple from the first relation and the field of the first relation, and the vector corresponding to the entry that is in the tuple from the second relation and the field of the second relation; and ii) the values for the similarity metric function obtained in the evaluation step; and outputting the tuple obtained by joining the tuple from the first relation and the tuple from the second relation.
Claim 33
Independent Claim
182 words
A method for performing a join operation, the method comprising the steps of: representing each entry in a field of a first relation and a field of a second relation as a vector; evaluating a similarity metric function on a plurality of pairs of vectors, wherein each pair from the plurality of pairs of vectors includes a vector from the field of the first relation and a vector from the field of the second relation; determining whether to join a tuple from the first relation and a tuple from the second relation based on i) the value of the similarity function evaluated on the vector corresponding to the entry that is in the tuple from the first relation and the field of the first relation, and the vector corresponding to the entry that is in the tuple from the second relation and the field of the second relation; and ii) the values for the similarity metric function obtained in the evaluation step; and outputting the tuple obtained by joining the tuple from the first relation and the tuple from the second relation.
Claim 34
Dependent Claim
89 words
The method of claim 27 wherein a probability estimate for correct joining of the tuple from the first relation and the tuple from the second relation is also output, wherein the probability estimate is based on the value of the similarity function evaluated on the vector corresponding to the entry that is in the tuple from the first relation and the field of the first relation, and the vector corresponding to the entry that is in the tuple from the second relation and the field of the second relation.
References Cited (Backward Citations)
US5237678A
Cited
US5454106A
Cited
US5701453A
Cited
US5577241A
Cited
US5694559A
Cited
US5701400A
Cited
US5819291A
Cited
US5960430A
Cited
US5884304A
Cited
US5920859A
Cited
US5924090A
Cited
US5999928A
Cited
US5895465A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-09-24 | 2005-03-26 | 2005-09-25 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-09-24 | 2009-03-26 | 2009-09-25 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-09-24 | 2013-03-26 | 2013-09-25 | $7700.00 | Window Closed / Lapsed |