Patent US5950185A successfully refreshed from Google Patents.
US5950185A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus and method for approximating frequency moments
Assignee: Nokia of America Corp
•
Filing: 1997-05-21
•
Granted: 1999-09-07
•
Expires: 2017-05-21
Abstract
Abstract A method for estimating frequency moments of a database, the frequency moments F k of a sequence containing m i elements of type i, for 1<i<n, being ##EQU1## for each k≧0. The method entails receiving a sequence of data elements for input to the database; selecting a subset of the sequence of data elements; initializing a counter corresponding to each data element of the subset; comparing data elements input to the database with each data element in the subset and incrementing counters of subset elements which correspond to the input data elements; computing a random variable for each data item in the subset, which depends on the counter of this subset item; and, processing the plurality of random variables to determine an estimate of the frequency moment. The estimated frequency moment is optimized to be accurate with a high degree of confidence.
Inventors
- 👤 Noga Alon
- 👤 Yossi Matias
- 👤 Mario Szegedy
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 23:50
CPC Classifications
G; G06; G06Q; G06Q30/00; G06Q30/02; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932
Claims Analysis
Total Claims: 9
Claim 1
Independent Claim
190 words
A method for estimating frequency moments of a database, F k , the frequency moments being of the order k, with k equal to the degree of the frequency moment and k≧1, said method comprising the steps of: receiving data elements for input to said database, each said data element being of a type; choosing a subset of quantity M of said data elements, each said data element in said subset chosen randomly; providing M counters, one counter for each said data element in said subset; initializing said counters; for each said data element input to said database, comparing said data element input to said database with each said data element in said subset and incrementing counters that correspond to those of said elements in said subset whose type is identical to the type of said data element input to said database; computing a random variable ##EQU5## for each said data element in said subset, where r u is a current count of said counter corresponding to said data element in said subset; and processing each said random variable to determine an estimate of said frequency moment F k .
Claim 2
Independent Claim
190 words
A method for estimating frequency moments of a database, F k , the frequency moments being of the order k, with k equal to the degree of the frequency moment and k≧1, said method comprising the steps of: receiving data elements for input to said database, each said data element being of a type; choosing a subset of quantity M of said data elements, each said data element in said subset chosen randomly; providing M counters, one counter for each said data element in said subset; initializing said counters; for each said data element input to said database, comparing said data element input to said database with each said data element in said subset and incrementing counters that correspond to those of said elements in said subset whose type is identical to the type of said data element input to said database; computing a random variable ##EQU5## for each said data element in said subset, where r u is a current count of said counter corresponding to said data element in said subset; and processing each said random variable to determine an estimate of said frequency moment F k .
Claim 3
Dependent Claim
87 words
A method for estimating frequency moments according to claim 1, wherein said database is of size m and said processing step includes the steps of: grouping said variables f u '(r u ) into M 2 groups of M 1 elements each; for each of said M 2 groups, computing an average value f v " for the M 1 variables; computing a median value f* for M 2 quantities of f v " values obtained; and computing an estimate for F k as a value mf*.
Claim 4
Dependent Claim
17 words
A method for estimating frequency moments according to claim 1, wherein said database is of size m.
Claim 5
Dependent Claim
31 words
A method for estimating frequency moments according to claim 3, wherein an estimate of a second frequency moment having k=2 is performed using on the order of √n(log(n+m )) memory locations.
Claim 6
Dependent Claim
24 words
A method for estimating frequency moments according to claim 1, wherein each of said quantity M data elements are selected in a probabilistic manner.
Claim 7
Dependent Claim
22 words
A method for estimating frequency moments according to claim 1, wherein each of said quantity M data elements are selected a priori.
Claim 8
Dependent Claim
43 words
A method for estimating frequency moments according to claim 1, further including the step of determining when said database size increases, and replacing a previous data element of said small subset with a new database item received in accordance with a calculated probability.
Claim 9
Dependent Claim
41 words
A method for estimating frequency moments according to claim 7, wherein a plurality of identical data items are received by said database, said method further including the step of incrementing the counter for that data item a corresponding number of times.
References Cited (Backward Citations)
US4956774A
Cited
US5251131A
Cited
US5404509A
Cited
US5675789A
Cited
US5675786A
Cited
US5542089A
Cited
US5689696A
Cited
US5721896A
Cited
US5758338A
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 |