The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Jan. 04, 2000
Filed:
Aug. 21, 1997
Phillip B Gibbons, Westfield, NJ (US);
Yossi Matias, Tel Aviv, IL;
Viswanath Poosala, Highland Park, NJ (US);
Lucent Technologies Inc., Murray Hill, NJ (US);
Abstract
Techniques for maintaining a random sample of a relation in a database in the presence of updates to the relation. The random sample of the relation is referred to as a 'backing sample,' and it is maintained in the presence of insert, modify and delete operations involving the relation. When a new tuple is inserted into the relation, a sample of the given tuple is added to the backing sample if the size of the backing sample is below an upper bound. Otherwise, a randomly-selected tuple of the backing sample is replaced with the new tuple if a sample of the new tuple must be inserted into the backing sample to maintain randomness or another characteristic. When a tuple in the relation is the subject of a modify operation, the backing sample is left unchanged if the modify operation does not affect an attribute of interest to an application which uses the backing sample. Otherwise, a value field in a sample of the tuple in the backing sample is updated. When a tuple is deleted from the relation, any sample of that tuple in the backing sample is removed. A new backing sample may be computed if this removal causes the size of the backing sample to fall below a prespecified lower bound. The backing sample can be of a size which is negligible in comparison to the relation, and need only be modified very infrequently. As a result, its overhead in terms of computation time and storage space is minimal.