Patent ID: 7937388

Claim:
A method for finding the elements of an input stream with frequency above a threshold, the method comprising: splitting the input stream of elements into a plurality of fixed-size windows; and processing each of the plurality of windows sequentially by performing the following: for each element in a current window, determining whether an entry corresponding to a current element is present in a table; in the event an entry corresponding to the current element is present in the table, incrementing a frequency counter associated with the current element; in the event the entry corresponding to the current element is not present in the table, inserting an entry into a table corresponding to the current element, wherein inserting an entry comprises: calculating a probabilistic error bound Δ corresponding to the current element based on an index i of the current window; and inserting the probabilistic error bound Δ and a frequency counter corresponding to the current element into an entry corresponding to the current element in the table; and at the end of the current window, removing all elements from the table wherein the sum of the frequency counter and probabilistic error bound Δ associated with the element is less than or equal to the index of the current window; wherein computing the probabilistic error bound Δ comprises applying one of the following formulas: Δ=β√{square root over (δ(1−(i−1) β )+(i−1) β )}{square root over (δ(1−(i−1) β )+(i−1) β )}, where Δ is the probabilistic error bound, β is a parameter of the power law distribution, δ is a small probability, and i is an index of the current window, or Δ˜k*i, where k is a measure of aggression and i is an index of the current window.