Apparatus and method for approximating frequency moments

摘要

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≧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.