Patent US2544743A successfully refreshed from Google Patents.
Patent US2562740A successfully refreshed from Google Patents.
Patent US5950189A successfully refreshed from Google Patents.
US5950189A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Retrieval system and method
Assignee: AT&T Inc
•
Filing: 1997-01-02
•
Granted: 1999-09-07
•
Expires: 2017-01-02
Abstract
Abstract The invention is an improved retrieval system and method. Many pattern recognition tasks, including estimation, classification, and the finding of similar objects, make use of linear models. For example, many text retrieval systems represent queries as linear functions, and retrieve documents whose vector representation has a high dot product with the query. The fundamental operation in such tasks is the computation of the dot product between a query vector and a large database of instance vectors. Often instance vectors which have high dot products with the query are of interest. The invention relates to a random sampling based retrieval system that can identify, for any given query vector, those instance vectors which have large dot products, while avoiding explicit computation of all dot products.
Inventors
- 👤 Edith Cohen
- 👤 David Dolan Lewis
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 19:36
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/33; G06F16/3331; G06F16/334; G06F16/3347; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99934; Y10S707/99935
Claims Analysis
Total Claims: 10
Claim 1
Independent Claim
145 words
A retrieval system for retrieving data from a database, the database comprising records each having a set of attribute values and a record identifier, comprising: a database sampling unit, for sampling from the records in the database and generating a sampled representation of the database according to a probability distribution over the records of the database, the probability distribution being constructed as a function of the attribute values in the records, and the database sampling unit being constructed to generate a weighted, directed graph representing the database, the database sampling unit determining the probability distribution by random walks on the weighted, directed graph; a query input unit, for receiving a database query; and a query processing unit, operatively connected to the query input unit and to the database sampling unit, which applies the database query to the sampled representation of the database to return results.
Claim 2
Dependent Claim
145 words
A retrieval system for retrieving data from a database, the database comprising records each having a set of attribute values and a record identifier, comprising: a database sampling unit, for sampling from the records in the database and generating a sampled representation of the database according to a probability distribution over the records of the database, the probability distribution being constructed as a function of the attribute values in the records, and the database sampling unit being constructed to generate a weighted, directed graph representing the database, the database sampling unit determining the probability distribution by random walks on the weighted, directed graph; a query input unit, for receiving a database query; and a query processing unit, operatively connected to the query input unit and to the database sampling unit, which applies the database query to the sampled representation of the database to return results.
Claim 3
Dependent Claim
27 words
A retrieval system according to claim 1, wherein the database sampling unit is constructed to output a set of lists of record identifiers, as the sampled representation.
Claim 4
Dependent Claim
41 words
A retrieval system according to claim 2, wherein the query processing unit uses the sampled representation of the database to compute an approximation of the dot product between the database query and each database record, and return the resulting approximate values.
Claim 5
Dependent Claim
31 words
A retrieval system according to claim 3, wherein the query processing unit is constructed to return results only on records whose approximated dot product with the query exceeds a predetermined threshold.
Claim 6
Independent Claim
119 words
A method of retrieving information from a database, the database comprising records each having a set of attribute values and a record identifier, comprising the steps of: (a) sampling from records of a database, to generate a sampled representation of the database according to a probability distribution over the records and attributes of the database, i) the probability distribution being constructed as a function of the attribute values in the records, the construction being done by a weighted, directed graph representing the database, and ii) the database sampling unit determining the probability distribution by random walks on the weighted, directed graph; (b) receiving a query input; and (c) applying the query input to the sampled representation to return results.
Claim 7
Independent Claim
119 words
A method of retrieving information from a database, the database comprising records each having a set of attribute values and a record identifier, comprising the steps of: (a) sampling from records of a database, to generate a sampled representation of the database according to a probability distribution over the records and attributes of the database, i) the probability distribution being constructed as a function of the attribute values in the records, the construction being done by a weighted, directed graph representing the database, and ii) the database sampling unit determining the probability distribution by random walks on the weighted, directed graph; (b) receiving a query input; and (c) applying the query input to the sampled representation to return results.
Claim 8
Dependent Claim
24 words
A method according to claim 5, further comprising the step of: (d) outputting a set of lists of record identifiers as the sampled representation.
Claim 9
Dependent Claim
31 words
A method according to claim 6, further comprising the step of: (e) calculating an approximation of the dot product between the query input and each database record, to return the results.
Claim 10
Dependent Claim
29 words
A method according to claim 7, further comprising the step of: (f) returning results only on entries whose approximated dot product with the query input exceeds a predetermined threshold.
References Cited (Backward Citations)
US4831550A
Cited
US5212765A
Cited
US5408586A
Cited
US5488725A
Cited
WO1993023818A1
Cited
US5586197A
Cited
US5675786A
Cited
US5713016A
Cited
US5696964A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-09-06 | 2003-03-08 | 2003-09-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-09-06 | 2007-03-08 | 2007-09-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-09-06 | 2011-03-08 | 2011-09-07 | $7700.00 | Window Closed / Lapsed |