US5689696A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for maintaining information in a database used to generate high biased histograms using a probability function, counter and threshold values
Assignee: Nokia of America Corp
•
Filing: 1995-12-28
•
Granted: 1997-11-18
•
Expires: 2015-12-28
Abstract
Abstract A method maintains information associated with items in a database of limited memory which information is used to generate representations of the information such as high-biased histograms. In a first embodiment of the inventive method, information associated with all items with sales above a threshold, together with approximate counts of the items, is maintained. Appropriate choice of a threshold limits the amount of information required to be maintained so as to generate accurate representations of the information with high probability. In a second embodiment of the inventive method, information used to generate a high-biased histogram is maintained within a fixed allotment of memory by dynamic adjusting a threshold which threshold is used to determine a probability with which information is retained in the database.
Inventors
- 👤 Phillip B. Gibbons
- 👤 Yossi Matias
- 👤 Andrew Witkowski
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 13:30
CPC Classifications
G; G06; G06Q; G06Q30/00; G06Q30/02
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
70 words
A method comprising the steps of: receiving information associated with an item for entry into a database, and if said database comprises other information associated with said item, then updating said other information based on the received information, and if said database does not comprise other information associated with said item, then adding said information to said database based upon a probability that is a function of a threshold value.
Claim 2
Independent Claim
70 words
A method comprising the steps of: receiving information associated with an item for entry into a database, and if said database comprises other information associated with said item, then updating said other information based on the received information, and if said database does not comprise other information associated with said item, then adding said information to said database based upon a probability that is a function of a threshold value.
Claim 3
Dependent Claim
21 words
The method of claim 1 wherein said probability is a probability of success that said information is added to said database.
Claim 4
Dependent Claim
47 words
The method of claim 1, wherein the information associated with said item added to said database comprises a count associated with said item, said method further comprising the step of: establishing said count associated with said item in said database as a function of said threshold value.
Claim 5
Dependent Claim
13 words
The method of claim 1 wherein said threshold value is a fixed value.
Claim 6
Dependent Claim
43 words
The method of claim 1, wherein said database is characterized by a size limit, which size limit determines a maximum amount of information in said database, further comprising the step of: adjusting said threshold value if said database is of said size limit.
Claim 7
Dependent Claim
42 words
The method of claim 5 further comprising the step of: for information associated with each item in said database, retaining information associated with said each item in said database based upon a probability that is a function of the adjusted threshold value.
Claim 8
Dependent Claim
44 words
The method of claim 1 further comprising the step of: generating a high-biased histogram based on said information in said database, wherein said information comprises count values associated with items in said database, wherein said count value is a function of the threshold value.
Claim 9
Independent Claim
123 words
A method of maintaining information in a database wherein said database can store a maximum amount of information, said method comprising the steps of: receiving information associated with an item for entry into a database, and if said database comprise other information associated with said item, then updating said other information based on the received information; if said database does not comprise said maximum amount of information, then adding said information to said database; if said database does comprise said maximum amount of information, then a) adjusting a threshold value, and b) for information associated with each item in said database, retaining information associated with said each item in said database with a probability that is a function of the adjusted threshold value.
Claim 10
Independent Claim
123 words
A method of maintaining information in a database wherein said database can store a maximum amount of information, said method comprising the steps of: receiving information associated with an item for entry into a database, and if said database comprise other information associated with said item, then updating said other information based on the received information; if said database does not comprise said maximum amount of information, then adding said information to said database; if said database does comprise said maximum amount of information, then a) adjusting a threshold value, and b) for information associated with each item in said database, retaining information associated with said each item in said database with a probability that is a function of the adjusted threshold value.
Claim 11
Dependent Claim
44 words
The method of claim 8 further comprising the step of: generating a high-biased histogram based on said information in said database, wherein said information comprises a count value associated with an item, wherein said count value is a function of the adjusted threshold value.
References Cited (Backward Citations)
US4620286A
Cited
US4774681A
Cited
US4910772A
Cited
US5058158A
Cited
US5563982A
Cited
US5257206A
Cited
US5596493A
Cited
US5251131A
Cited
US5361379A
Cited
US5488725A
Cited
US5404509A
Cited
US5583950A
Cited
US5546502A
Cited
US5581704A
Cited
US5519840A
Cited
US5524240A
Cited
US5475813A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-11-17 | 2001-05-19 | 2001-11-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-11-17 | 2005-05-19 | 2005-11-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-11-17 | 2009-05-19 | 2009-11-18 | $7700.00 | Window Closed / Lapsed |