US5519840A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for implementing approximate data structures using operations on machine words
Assignee: AT&T Inc
•
Filing: 1994-01-24
•
Granted: 1996-05-21
•
Expires: 2014-01-24
Abstract
Abstract A method of implementing approximate data structures is disclosed. The method recognizes that an approximate data structure can be implemented using a mapping of elements in the data strucure and using an exact data strucure on the mapped elements.
Inventors
- 👤 Yossi Matias
- 👤 Jeffrey S. Vitter
- 👤 Neal E. Young
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 06:26
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/30; G06F9/30003; G06F9/3004; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99942
Claims Analysis
Total Claims: 9
Claim 1
Independent Claim
107 words
A method of executing a first operation on a first data structure comprising a set of items to generate an output, the method comprising the steps of: executing a second operation on machine words to generate respective outputs, the machine words representing respective second data structures comprising items, the items of each respective second data structure having a universe size no larger than the size of the machine word, each item in said set of items in said first data structure being represented by an item in at least one of said respective second data structures, and generating said output as a function of said respective outputs.
Claim 2
Independent Claim
107 words
A method of executing a first operation on a first data structure comprising a set of items to generate an output, the method comprising the steps of: executing a second operation on machine words to generate respective outputs, the machine words representing respective second data structures comprising items, the items of each respective second data structure having a universe size no larger than the size of the machine word, each item in said set of items in said first data structure being represented by an item in at least one of said respective second data structures, and generating said output as a function of said respective outputs.
Claim 3
Dependent Claim
18 words
The method of claim 1 wherein said second operation executed on the machine words is a successor operation.
Claim 4
Dependent Claim
18 words
The method of claim 1 wherein said second operation executed on the machine words is a predecessor operation.
Claim 5
Dependent Claim
18 words
The method of claim 1 wherein said second operation executed on the machine words is a look-up operation.
Claim 6
Dependent Claim
18 words
The method of claim 1 wherein said second operation executed on the machine words is an insertion operation.
Claim 7
Dependent Claim
18 words
The method of claim 1 wherein said second operation executed on the machine words is a deletion operation.
Claim 8
Dependent Claim
82 words
The method of claim 1 wherein a primary data structure comprises a plurality of items having an associated universe and wherein said first data structure is generated by mapping each item in said plurality of items in said primary data structure into an item in said set of items in said first data structure, said set of items in said first data structure having an associated universe smaller than the universe associated with the plurality of items in said primary data structure.
Claim 9
Dependent Claim
30 words
The method of claim 1 wherein the items in said second data structure are determined based on groups of items in said set of items in said first data structure.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-05-21 | 1999-11-20 | 2000-05-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-05-21 | 2003-11-20 | 2004-05-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-05-21 | 2007-11-20 | 2008-05-21 | $7700.00 | Window Closed / Lapsed |