US6081805A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Pass-through architecture via hash techniques to remove duplicate query results
Assignee: Meta Platforms Inc
•
Filing: 1997-09-10
•
Granted: 2000-06-27
•
Expires: 2017-09-10
Abstract
Abstract A method and system for removing duplicate query results in a database system comprising a plurality of data sources. The method and system includes issuing a query from a user to a first data source. In response to receiving a first query result from the data source, a first hash index is computed for the first query result and the first query result is passed on to the user. The method and system further includes receiving a second query result and computing a second hash index for the second query result. The first hash index is then compared with the second hash index to cheek for a hash collision. If the first, and second hash indexes match, the first data source is queried for data corresponding to the second query result. And if the first data source contains the data, then the second query result is considered a duplicate and is discarded.
Inventors
- 👤 Ramanathan V. Guha
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 04:16
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2455; G06F16/24553; G06F16/24554; G06F16/24556; G06F16/22; G06F16/2228; G06F16/2255; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99934; Y10S707/99935
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
168 words
A computer-readable medium containing program instructions for removing duplicate query results in a system comprising a plurality of data sources, the program instructions for: a) issuing a query from a user to a first data source; b) receiving a first query result; c) computing a first index for the first query result; d) passing the first query result to the user; e) issuing said query to a second data source: f) receiving a second query result; g) computing a second index for the second query result; h) comparing the first index with the second index to check for an index collision; i) if the first and second indexes match, querying the first data source for data corresponding to the second query result; j) discarding the second query result if the first data source contains the data; and wherein queries are issued to one data source at a time, allowing the results from each data source to be processed before the results from the next data source are received.
Claim 2
Dependent Claim
168 words
A computer-readable medium containing program instructions for removing duplicate query results in a system comprising a plurality of data sources, the program instructions for: a) issuing a query from a user to a first data source; b) receiving a first query result; c) computing a first index for the first query result; d) passing the first query result to the user; e) issuing said query to a second data source: f) receiving a second query result; g) computing a second index for the second query result; h) comparing the first index with the second index to check for an index collision; i) if the first and second indexes match, querying the first data source for data corresponding to the second query result; j) discarding the second query result if the first data source contains the data; and wherein queries are issued to one data source at a time, allowing the results from each data source to be processed before the results from the next data source are received.
Claim 3
Dependent Claim
37 words
The computer-readable medium of claim 1 wherein instruction c) further includes an instruction for: c1) storing the first index and a pointer to the first data source that produced the first query result in a hash table.
Claim 4
Dependent Claim
30 words
The computer-readable medium of claim 1 further including an instruction for: p1 k) if the first and second indexes do not match, passing the second query result to the user.
Claim 5
Dependent Claim
46 words
The computer-readable medium of claim 1 wherein program instruction k) further induces an instruction for: k1) storing the second index and a pointer to the data source that produced the second query result in a hash table if the first and second indexes do not match.
Claim 6
Dependent Claim
22 words
The computer-readable medium of claim 1 wherein each index is a hash index that Is computed using a highly discriminating hash algorithm.
Claim 7
Dependent Claim
15 words
The computer-readable medium of claim 5 wherein the hash algorithm is a Knuth Hashing Algorithm.
Claim 8
Dependent Claim
161 words
A process for removing duplicate query results in a system comprising a plurality of data sources in a computer environment, comprising the steps of: issuing a query from a user to a first data source; receiving a first query result; computing a first index for the first query result; passing said first query result to the user; sending said query to a second data source; receiving a second query result; computing a second index for said second query result; comparing said first index with said second index to check for an index collision; wherein if said first and second indexes match, then said first data source is queried for data corresponding to said second query result; discarding said second query result if said first data source contains said data; and wherein queries are issued to one data source at a time, allowing the results from each data source to be processed before the results from the next data source are received.
Claim 9
Dependent Claim
161 words
A process for removing duplicate query results in a system comprising a plurality of data sources in a computer environment, comprising the steps of: issuing a query from a user to a first data source; receiving a first query result; computing a first index for the first query result; passing said first query result to the user; sending said query to a second data source; receiving a second query result; computing a second index for said second query result; comparing said first index with said second index to check for an index collision; wherein if said first and second indexes match, then said first data source is queried for data corresponding to said second query result; discarding said second query result if said first data source contains said data; and wherein queries are issued to one data source at a time, allowing the results from each data source to be processed before the results from the next data source are received.
Claim 10
Dependent Claim
26 words
The process of claim 7, further comprising the step of: storing said first index and a pointer to said first data source in a hash table.
Claim 11
Dependent Claim
27 words
The process of claim 7, further comprising the step of: passing said second query result to said user if said first and second indexes do not match.
Claim 12
Dependent Claim
35 words
The process of claim 7, further comprising the step of: storing said second index and a pointer to said second data source in a hash table if said first and second indexes do not match.
Claim 13
Dependent Claim
21 words
The process of claim 7, wherein each index is a hash index that is computed using a highly discriminating hash algorithm.
Claim 14
Dependent Claim
14 words
The process of claim 11, wherein said hash algorithm is a Knuth Hashing Algorithm.
Claim 15
Independent Claim
185 words
An apparatus for removing duplicate query results in a system comprising a plurality of data sources in a computer environment, comprising: a module for issuing a query from a user to a first data source; a module for receiving a first query result; a module for computing a first index for the first query result; a module for passing said first query result to the user; a module for sending said query to a second data source; a module for receiving a second query result; a module for computing a second index for said second query result; a module for comparing said first index with said second index to check for an index collision; wherein if said first and second indexes match, then said first data source is queried for data corresponding to said second query result; a module for discarding said second query result if said first data source contains said data; and wherein queries are issued to one data source at a time, allowing the results from each data source to be processed before the results from the next data source are received.
Claim 16
Independent Claim
185 words
An apparatus for removing duplicate query results in a system comprising a plurality of data sources in a computer environment, comprising: a module for issuing a query from a user to a first data source; a module for receiving a first query result; a module for computing a first index for the first query result; a module for passing said first query result to the user; a module for sending said query to a second data source; a module for receiving a second query result; a module for computing a second index for said second query result; a module for comparing said first index with said second index to check for an index collision; wherein if said first and second indexes match, then said first data source is queried for data corresponding to said second query result; a module for discarding said second query result if said first data source contains said data; and wherein queries are issued to one data source at a time, allowing the results from each data source to be processed before the results from the next data source are received.
Claim 17
Dependent Claim
26 words
The apparatus of claim 13, further comprising: a module for storing said first index and a pointer to said first data source in a hash table.
Claim 18
Dependent Claim
27 words
The apparatus of claim 13, further comprising: a module for passing said second query result to said user if said first and second indexes do not match.
Claim 19
Dependent Claim
35 words
The apparatus of claim 13, further comprising: a module for storing said second index and a pointer to said second data source in a hash table if said first and second indexes do not match.
Claim 20
Dependent Claim
21 words
The apparatus of claim 13, wherein each index is a hash index that is computed using a highly discriminating hash algorithm.
Claim 21
Dependent Claim
14 words
The apparatus of claim 17, wherein said hash algorithm is a Knuth Hashing Algorithm.
References Cited (Backward Citations)
US4879648A
Cited
US4961139A
Cited
US5488725A
Cited
US5727196A
Cited
US5555405A
Cited
US5598559A
Cited
US5659737A
Cited
US5768532A
Cited
US5873080A
Cited
US5895465A
Cited
US5943665A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-06-27 | 2003-12-27 | 2004-06-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-06-27 | 2007-12-27 | 2008-06-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-06-27 | 2011-12-27 | 2012-06-27 | $7700.00 | Window Closed / Lapsed |