Counting unique search results

Details Counting unique search results Counting unique search results

2008-04-21

2011-11-22

Tony, Mahmoudi (Department: 2169)

Data processing: database and file management or data structures

Database and file access

Preparing data for information retrieval

C711S216000

Reexamination Certificate

active

08065309

ABSTRACT:
The subject matter of this specification can be embodied in, among other things, a computer-implemented method for counting one or more unique search results within a plurality of search results includes creating hash values for information in each of the search results using a first hash function. The first hash function has a predetermined hash value range size. The method further includes identifying a predetermined number of smallest hash values within the created hash values. The method further includes estimating a first number of unique search results based on the predetermined hash value range size, the predetermined number, and a largest hash value in the smallest hash values.

REFERENCES:
patent: 6038561 (2000-03-01), Snyder et al.
patent: 2003/0055813 (2003-03-01), Chaudhuri et al.
patent: 2004/0049492 (2004-03-01), Gibbons
patent: 2005/0251510 (2005-11-01), Billingsley et al.
patent: 2007/0106666 (2007-05-01), Beckerle et al.
patent: 2007/0239663 (2007-10-01), Dyskant
patent: 2007/0255702 (2007-11-01), Orme
patent: 2009/0192980 (2009-07-01), Beyer et al.
Noga Alon et al., “The space complexity of approximating the frequency moments,”Symposium on Theory of Computing '96, pp. 20-29, 1996.
Ziv Bar-Yossef et al., “Counting distinct elements in a data stream,”RANDOM '02 Proceedings of the 6th International Workshop on Randomization and Approximation Techniques, pp. 1-10, 2002.
Ziv Bar-Yossef et al., “Reductions in Streaming Algorithms, with an Application to Counting Triangles in Graphs,”Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 623-632, 2002.
Kevin Beyer et al., “On Synopses for Distinct-Value Estimation Under Multiset Operations,”Proceedings of the 2007 ACM SIGMOD international conference on Management of data, pp. 199-210, Jun. 12, 2007.
J. Lawrence Carter et al., “Universal Classes of Hash Functions,”STOC '77 Proceedings of the ninth annual ACM symposium on Theory of computing, pp. 106-112, 1977.
Edith Cohen, “Size-Estimation Framework with Applications to Transitive Closure and Reachability,”Journal of Computer and System Sciences, vol. 55 Issue 3, Dec. 1997.
Philippe Flajolet, “Probabilistic Counting Algorithms for Data Base Applications,”Journal of Computer and System Sciences, vol. 31(2), pp. 182-209, Oct. 1985.
Phillip B. Gibbons, “Estimating Simple Functions on the Union of Data Streams,”Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, pp. 281-290, 2001.
Haas et al., “Fixed-Precision Estimation of Join Selectivity,”Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGARD symposium on Principles of database systems, pp. 190-201, 1993.
Kyu-Young Whang et al., “A Linear-Time Probabilistic Counting Algorithm for Database Applications,”Journal of ACM Transactions on Database Systems, vol. 15(2), pp. 208-229, Jun. 1990.

Affiliated with

Also associated with

Rating

Counting unique search results does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Counting unique search results, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting unique search results will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4266560