Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2006-05-16
2006-05-16
Alam, Shahid (Department: 2162)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C717S141000
Reexamination Certificate
active
07047230
ABSTRACT:
For use with a database that accommodates distinct value queries having predicates, a distinct sampling system and a method of distinct sampling. In one embodiment, the distinct sampling system includes a scanning subsystem that is configured to scan each row in the database for a distinct target attribute, employ a hash function to map the distinct target attribute to an attribute priority level, maintain random samples of each row based on a sample priority level and a sample size, and produce a distinct sample therefrom. The distinct sampling system further includes a distinct query estimator that is configured to receive the distinct value queries, cause the distinct value queries to be executed on the distinct sample to retrieve a result, and adjust the result to produce a distinct estimate therefrom.
REFERENCES:
patent: 6012064 (2000-01-01), Gibbons et al.
patent: 6044370 (2000-03-01), Anfindsen
patent: 6092065 (2000-07-01), Floratos et al.
patent: 6108647 (2000-08-01), Poosala et al.
patent: 6108666 (2000-08-01), Floratos et al.
patent: 6122644 (2000-09-01), Graefe et al.
patent: 6226629 (2001-05-01), Cossock
patent: 6289334 (2001-09-01), Reiner et al.
patent: 6292804 (2001-09-01), Ardoin et al.
patent: 6373971 (2002-04-01), Floratos et al.
patent: 6714874 (2004-03-01), Myers et al.
patent: 6865567 (2005-03-01), Oommen et al.
patent: 6961930 (2005-11-01), Waldspurger et al.
patent: 2002/0083067 (2002-06-01), Tamayo et al.
Smith, Bradley J. et al., “The Exponential Hash Function”, The ACM Journal of Experimental Algorithmics, vol. 2, Article 3, 1997, pp. 1-18.
Vitter, Jeffrey Scott, “Random Sampling with a Reservoir”, ACM Transactions on Mathematical Software, vol. 11, No. 1, Mar. 1985, pp. 37-57.
Gibbons, Phillip B.; Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports;Proceedings of the 27th VLDB Conference; Roma, Italy; Sep. 2001.
Alam Shahid
Lucent Technologies - Inc.
LandOfFree
Distinct sampling system and a method of distinct sampling... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Distinct sampling system and a method of distinct sampling..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distinct sampling system and a method of distinct sampling... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3596830