Patent · US Active

System and method for maintaining and utilizing Bernoulli samples over evolving multisets

US8140466B2 · kind B2 · utility

0Cited by

7References

20Claims

0Family size

Assignee

International Business Machines Corporation · US

Inventors

Rainer Gemulla · Riegelsberg, DE
Peter J. Haas · San Jose, US
Wolfgang Lehner · Dresden, DE

Key dates

Filing date	Apr 24, 2008
Grant date	Mar 20, 2012
Priority date	—
Expiry date	Jan 17, 2031

Classification

Technology area (CPC Y)Emerging Cross-Sectional Technologies
CPC primaryY10S707/99942
WIPO fieldComputer technology
WIPO sectorElectrical engineering

Abstract

One embodiment of the present invention provides a method for incrementally maintaining a Bernoulli sample S with sampling rate q over a multiset R in the presence of update, delete, and insert transactions. The method includes processing items inserted into R using Bernoulli sampling and augmenting S with tracking counters during this processing. Items deleted from R are processed by using the tracking counters and by removing newly deleted items from S using a calculated probability while maintaining a degree of uniformity in S.

Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.