Leveraging discarded samples for tighter estimation of multiple-set aggregates

ABSTRACT

Many datasets, including market basket data, text or hypertext documents, and events recorded in different locations or time periods, can be modeled as a collection of sets over a ground set of keys. Common queries over such data, including similarity or association rules are represented as the weight or selectivity of keys that satisfy some selection predicate defined over keys' attributes and memberships in particular sets.

On massive data sets, exact computation of such aggregates can be inefficient or infeasible, and therefore, approximate queries are processed over sketches of the sets. Sketches based on coordinated random samples are scalable and flexible and well suited for many applications. Queries are resolved by producing a sketch of the union of sets used in the predicate from the sketches of these sets and then applying an estimator to this union-sketch.

We derive novel tighter (unbiased) estimators that leverage sampled keys that are present in the union of applicable sketches but excluded from the union sketch. We establish analytically that our estimators dominate estimators applied to the union-sketch for all queries and data sets. Empirical evaluation on synthetic and real data reveals that on typical applications we can expect a 25% 4 fold reduction in estimation error.

REFERENCES

• 1: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 2: Kevin Beyer , Peter J. Haas , Berthold Reinwald , Yannis Sismanis , Rainer Gemulla, On synopses for distinct-value estimation under multiset operations, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247504]
• 3: Krishna Bharat , Andrei Broder, Mirror, mirror on the Web: a study of host pairs with replicated content, Proceedings of the eighth international conference on World Wide Web, p.1579-1590, May 1999, Toronto, Canada
• 4: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 5: K.R.W. Brewer, L.J. Early, and S.F. Joyce. Selecting several samples from a single population. Australian Journal of Statistics, 14(3):231--239, 1972.
• 6: A. Broder, On the Resemblance and Containment of Documents, Proceedings of the Compression and Complexity of Sequences 1997, p.21, June 11-13, 1997
• 7: Andrei Z. Broder, Identifying and Filtering Near-Duplicate Documents, Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching, p.1-10, June 21-23, 2000
• 8: Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher, Min-wise independent permutations, Journal of Computer and System Sciences, v.60 n.3, p.630-659, June 2000 [doi>10.1006/jcss.1999.1690]
• 9: Moses Charikar , Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, Towards estimation error guarantees for distinct values, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.268-279, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335230]
• 10: Moses S. Charikar, Similarity estimation techniques from rounding algorithms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509965]
• 11: Abdur Chowdhury , Ophir Frieder , David Grossman , Mary Catherine McCabe, Collection statistics for fast duplicate document detection, ACM Transactions on Information Systems (TOIS), v.20 n.2, p.171-191, April 2002 [doi>10.1145/506309.506311]
• 12: Edith Cohen, Size-estimation framework with applications to transitive closure and reachability, Journal of Computer and System Sciences, v.55 n.3, p.441-453, Dec. 1997 [doi>10.1006/jcss.1997.1534]
• 13: Edith Cohen , Nick Duffield , Haim Kaplan , Carsten Lund , Mikkel Thorup, Stream sampling for variance-optimal estimation of subset sums, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1255-1264, January 04-06, 2009, New York, New York
• 14: E. Cohen, A. Fiat, and H. Kaplan. Associative search in Peer to Peer networks: Harnessing latent semantics. In Proceedings of the IEEE INFOCOM'03 Conference, 2003.
• 15: Edith Cohen , Haim Kaplan, Efficient estimation algorithms for neighborhood variance and other moments, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 16: Edith Cohen , Haim Kaplan, Spatially-decaying aggregation over a network, Journal of Computer and System Sciences, v.73 n.3, p.265-288, May, 2007 [doi>10.1016/j.jcss.2006.10.016]
• 17: Edith Cohen , Haim Kaplan, Summarizing data using bottom-k sketches, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281133]
• 18: Edith Cohen , Haim Kaplan, Estimating Aggregates over Multiple Sets, Proceedings of the 2008 Eighth IEEE International Conference on Data Mining, p.761-766, December 15-19, 2008 [doi>10.1109/ICDM.2008.110]
• 19: E. Cohen and H. Kaplan. Tighter estimation using bottom-k sketches. In Proceedings of the 34th VLDB Conference, 2008.
• 20: Edith Cohen , Martin J. Strauss, Maintaining time-decaying stream aggregates, Journal of Algorithms, v.59 n.1, p.19-36, April 2006 [doi>10.1016/j.jalgor.2005.01.006]
• 21: E. Cohen, Y.-M. Wang, and G. Suri. When piecewise determinism is almost true. In Proc. Pacific Rim International Symposium on Fault-Tolerant Systems, pages 66--71, Dec. 1995.
• 22: Jack G. Conrad , Cindy P. Schriber, Constructing a text corpus for inexact duplicate detection, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009131]
• 23: Tamraparni Dasu , Theodore Johnson , S. Muthukrishnan , Vladislav Shkapenyuk, Mining database structure; or, how to build a data quality browser, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564719]
• 24: Nick Duffield , Carsten Lund , Mikkel Thorup, Priority sampling for estimation of arbitrary subset sums, Journal of the ACM (JACM), v.54 n.6, p.32-es, December 2007 [doi>10.1145/1314690.1314696]
• 25: Li Fan , Pei Cao , Jussara Almeida , Andrei Z. Broder, Summary cache: a scalable wide-area web cache sharing protocol, IEEE/ACM Transactions on Networking (TON), v.8 n.3, p.281-293, June 2000 [doi>10.1109/90.851975]
• 26: J. Feigenbaum , S. Kannan , M. Strauss , M. Viswanathan, An Approximate L1-Difference Algorithm for Massive Data Streams, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.501, October 17-18, 1999
• 27: Phillip B. Gibbons , Srikanta Tirthapura, Estimating simple functions on the union of data streams, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.281-291, July 2001, Crete Island, Greece [doi>10.1145/378580.378687]
• 28: Phillip B. Gibbons, Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports, Proceedings of the 27th International Conference on Very Large Data Bases, p.541-550, September 11-14, 2001
• 29: M. Hadjieleftheriou, X. Yu, N. Koudas, and D. Srivastava. Hashed samples: Selectivity estimators for set similarity selection queries. In Proceedings of the 34th VLDB Conference, 2008.
• 30: J. Hájek. Sampling from a finite population. Marcel Dekker, New York, 1981.
• 31: Monika Henzinger, Finding near-duplicate web pages: a large-scale evaluation of algorithms, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148222]
• 32: D.G. Horvitz and D.J. Thompson. A generalization of sampling without replacement from a finite universe. Journal of the American Statistical Association, 47(260):663--685, 1952.
• 33: Haim Kaplan , Micha Sharir, Randomized incremental constructions of three-dimensional convex hulls and planar voronoi diagrams, and approximate range counting, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.484-493, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109611]
• 34: Aleksander Kołcz , Abdur Chowdhury , Joshua Alspector, Improved robustness of signature-based near-replica detection via lexicon randomization, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014127]
• 35: Ping Li , Kenneth W. Church, A Sketch Algorithm for Estimating Two-Way and Multi-Way Associations, Computational Linguistics, v.33 n.3, p.305-354, September 2007 [doi>10.1162/coli.2007.33.3.305]
• 36: Udi Manber, Finding similar files in a large file system, Proceedings of the USENIX Winter 1994 Technical Conference on USENIX Winter 1994 Technical Conference, p.2-2, January 17-21, 1994, San Francisco, California
• 37: Gurmeet Singh Manku , Arvind Jain , Anish Das Sarma, Detecting near-duplicates for web crawling, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242592]
• 38: Damon Mosk-Aoyama , Devavrat Shah, Computing separable functions via gossip, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA [doi>10.1145/1146381.1146401]
• 39: Edith Cohen , Mayur Datar , Shinji Fujiwara , Aristides Gionis , Piotr Indyk , Rajeev Motwani , Jeffrey D. Ullman , Cheng Yang, Finding Interesting Associations without Support Pruning, IEEE Transactions on Knowledge and Data Engineering, v.13 n.1, p.64-78, January 2001 [doi>10.1109/69.908981]
• 40: The Netflix Prize. http://www.netflixprize.com/
• 41: E. Ohlsson. Sequential poisson sampling. J. Official Statistics, 14(2):149--162, 1998.
• 42: B. Rosén. Asymptotic theory for successive sampling with varying probabilities without replacement, I. The Annals of Mathematical Statistics, 43(2):373--397, 1972.
• 43: B. Rosén. Asymptotic theory for order sampling. J. Statistical Planning and Inference, 62(2):135--158, 1997.
• 44: B. Rosén. On sampling with probability proportional to size. J. Statistical Planning and Inference, 62(2):159--191, 1997.
• 45: Saul Schleimer , Daniel S. Wilkerson , Alex Aiken, Winnowing: local algorithms for document fingerprinting, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872770]
• 46: Neil T. Spring , David Wetherall, A protocol-independent technique for eliminating redundant network traffic, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.87-95, August 28-September 01, 2000, Stockholm, Sweden
• 47: K. Sripanidkulchai, B. Maggs, and H. Zhang. Efficient content location using interest-based locality in peer-to-peer systems. In Proceedings of the IEEE Infocom '03 Conference, 2003.
• 48: Mario Szegedy, The DLT priority sampling is essentially optimal, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132539]
• 49: M. Szegedy and M. Thorup. On the variance of subset sum estimation. In Proc. 15th ESA, 2007.
• 50: Chunqiang Tang , Zhichen Xu , Sandhya Dwarkadas, Peer-to-peer information retrieval using self-organizing semantic overlay networks, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863976]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Measurement, Performance

Keywords:
approximate query processing, bottom-k sampling, coordinated sampling, multiple-set aggregates, order sampling, sketches