Apparatus and method for approximating frequency moments

Details Apparatus and method for approximating frequency moments Apparatus and method for approximating frequency moments

1997-05-21

1999-09-07

Amsbury, Wayne

Data processing: database and file management or data structures

Database design

Data structure types

707 2, G06F 1700

Patent

active

059501855

ABSTRACT:
A method for estimating frequency moments of a database, the frequency moments F.sub.k of a sequence containing m.sub.i elements of type i, for 1<i<n, being ##EQU1## for each k.gtoreq.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.

REFERENCES:
patent: 4956774 (1990-09-01), Shibamiya et al.
patent: 5251131 (1993-10-01), Masand et al.
patent: 5404509 (1995-04-01), Klein
patent: 5542089 (1996-07-01), Lindsay et al.
patent: 5675786 (1997-10-01), McKee et al.
patent: 5675789 (1997-10-01), Ishii et al.
patent: 5689696 (1997-11-01), Gibbons et al.
patent: 5721896 (1998-02-01), Ganguly et al.
patent: 5758338 (1998-05-01), Faloutsos et al.
Salem et al., "Probabilistic Diagnosis of Hot Spots", IEEE Comput. Soc. Press , pp. 30-39, 1992.

Affiliated with

Also associated with

Rating

Apparatus and method for approximating frequency moments does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Apparatus and method for approximating frequency moments, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for approximating frequency moments will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1815394