Why go logarithmic if we can go linear?: Towards effective distinct counting of search traffic

ABSTRACT

Estimating the number of distinct elements in a large multiset has several applications, and hence has attracted active research in the past two decades. Several sampling and sketching algorithms have been proposed to accurately solve this problem. The goal of the literature has always been to estimate the number of distinct elements while using minimal resources. However, in some modern applications, the accuracy of the estimate is of primal importance, and businesses are willing to trade more resources for better accuracy. Throughout our experience with building a distinct count system at a major search engine, Ask.com, we reviewed the literature of approximating distinct counts, and compared most algorithms in the literature. We deduced that Linear Counting, one of the least used algorithms, has unique and impressive advantages when the accuracy of the distinct count is critical to the business. For other estimators to attain comparable accuracy, they need more space than Linear Counting. We have supported our analytical results through comprehensive experiments. The experimental results highly favor Linear Counting when the number of distinct elements is large and the error tolerance is low.

REFERENCES

• 1: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.20-29, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237823]
• 2: Morton M. Astrahan , Mario Schkolnick , Kyu-Young Whang, Approximating the number of unique values of an attribute without sorting, Information Systems, v.12 n.1, p.11-15, Jan. 1987 [doi>10.1016/0306-4379(87)90014-7]
• 3: Ziv Bar-Yossef , T. S. Jayram , Ravi Kumar , D. Sivakumar , Luca Trevisan, Counting Distinct Elements in a Data Stream, Proceedings of the 6th International Workshop on Randomization and Approximation Techniques, p.1-10, September 13-15, 2002
• 4: Ziv Bar-Yossef , Ravi Kumar , D. Sivakumar, Reductions in streaming algorithms, with an application to counting triangles in graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.623-632, January 06-08, 2002, San Francisco, California
• 5: Kevin Beyer , Raghu Ramakrishnan, Bottom-up computation of sparse and Iceberg CUBE, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.359-370, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 6: T. Bohman, C. Cooper, and A. Frieze. Min-Wise Independent Linear Permutations. Electronic Journal of Combinatorics, 7:R26, 2000.
• 7: Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher, Min-wise independent permutations (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.327-336, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276781]
• 8: 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]
• 9: 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]
• 10: Graham Cormode , Mayur Datar , Piotr Indyk , S. Muthukrishnan, Comparing data streams using Hamming norms (how to zero in), Proceedings of the 28th international conference on Very Large Data Bases, p.335-345, August 20-23, 2002, Hong Kong, China
• 11: Graham Cormode , Flip Korn , S. Muthukrishnan , Divesh Srivastava, Diamond in the rough: finding Hierarchical Heavy Hitters in multi-dimensional data, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007588]
• 12: Mayur Datar , Aristides Gionis , Piotr Indyk , Rajeev Motwani, Maintaining stream statistics over sliding windows: (extended abstract), Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.635-644, January 06-08, 2002, San Francisco, California
• 13: M. Durand and P. Flajolet. Loglog Counting of Large Cardinalities (extended abstract). In Proceedings of the 11th ESA European Symposium on Algorithms, pages 605--617, 2003.
• 14: Cristian Estan , George Varghese , Mike Fisk, Bitmap algorithms for counting active flows on high speed links, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948225]
• 15: Ying Feng , Divyakant Agrawal , Amr El Abbadi , Ahmed Metwally, Range CUBE: Efficient Cube Computation by Exploiting Data Correlation, Proceedings of the 20th International Conference on Data Engineering, p.658, March 30-April 02, 2004
• 16: Philippe Flajolet , G. Nigel Martin, Probabilistic counting algorithms for data base applications, Journal of Computer and System Sciences, v.31 n.2, p.182-209, Sept. 1985 [doi>10.1016/0022-0000(85)90041-8]
• 17: É. Fusy and F. Giroire. Estimating the Number of Active Flows in a Data Stream over a Sliding Window. In Proceedings of the 4th SIAM Workshop on Analytic Algorithmics and Combinatorics, 2007.
• 18: S. Ganguly. Counting Distinct Items over Update Streams. In Proceedings of the 16th ISAAC International Symposium on Algorithms and Computation, pages 505--514, 2005.
• 19: Sumit Ganguly , Minos Garofalakis , Rajeev Rastogi, Processing set expressions over continuous update streams, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872790]
• 20: 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
• 21: 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]
• 22: Phillip B. Gibbons , Srikanta Tirthapura, Distributed streams algorithms for sliding windows, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564880]
• 23: F. Giroire. Order Statistics and Estimating Cardinalities of Massive Datasets. In Proceedings of the 6th DMTCS Discrete Mathematics and Theoretical Computer Science, pages 157--166, 2005.
• 24: Jim Gray , Surajit Chaudhuri , Adam Bosworth , Andrew Layman , Don Reichart , Murali Venkatrao , Frank Pellow , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals, Data Mining and Knowledge Discovery, v.1 n.1, p.29-53, 1997 [doi>10.1023/A:1009726021843]
• 25: Peter J. Haas , Jeffrey F. Naughton , S. Seshadri , Lynne Stokes, Sampling-Based Estimation of the Number of Distinct Values of an Attribute, Proceedings of the 21th International Conference on Very Large Data Bases, p.311-322, September 11-15, 1995
• 26: P. Haas and L. Stokes. Estimating the Number of Classes in a Finite Population. Journal of the American Statistical Association, 93:1475--1487, 1998.
• 27: Jiawei Han , Yixin Chen , Guozhu Dong , Jian Pei , Benjamin W. Wah , Jianyong Wang , Y. Dora Cai, Stream Cube: An Architecture for Multi-Dimensional Analysis of Data Streams, Distributed and Parallel Databases, v.18 n.2, p.173-197, September 2005 [doi>10.1007/s10619-005-3296-1]
• 28: Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Implementing data cubes efficiently, ACM SIGMOD Record, v.25 n.2, p.205-216, June 1996
• 29: Wen-Chi Hou , Gultekin Ozsoyoglu , Erdogan Dogdu, Error-constrained COUNT query evaluation in relational databases, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.278-287, May 29-31, 1991, Denver, Colorado, United States
• 30: Wen-Chi Hou , Gultekin Ozsoyoglu , Baldeo K. Taneja, Statistical estimators for relational algebra expressions, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.276-287, March 1988, Austin, Texas, United States [doi>10.1145/308386.308455]
• 31: Wen-Chi Hou , Gultekin Ozsoyoglu , Baldeo K. Taneja, Processing aggregate relational queries with hard time constraints, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.68-77, June 1989, Portland, Oregon, United States
• 32: Laks V. S. Lakshmanan , Jian Pei , Jiawei Han, Quotient cube: how to summarize the semantics of a data cube, Proceedings of the 28th international conference on Very Large Data Bases, p.778-789, August 20-23, 2002, Hong Kong, China
• 33: Laks V. S. Lakshmanan , Jian Pei , Yan Zhao, QC-trees: an efficient summary structure for semantic OLAP, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872768]
• 34: Xiaolei Li , Jiawei Han , Hector Gonzalez, High-dimensional OLAP: a minimal cubing approach, Proceedings of the Thirtieth international conference on Very large data bases, p.528-539, August 31-September 03, 2004, Toronto, Canada
• 35: Ahmed Metwally , Divyakant Agrawal , Amr El Abbad , Qi Zheng, On Hit Inflation Techniques and Detection in Streams of Web Advertising Networks, Proceedings of the 27th International Conference on Distributed Computing Systems, p.52, June 25-27, 2007 [doi>10.1109/ICDCS.2007.124]
• 36: Konstantinos Morfonios , Yannis Ioannidis, CURE for cubes: cubing using a ROLAP engine, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 37: Jeffrey F. Naughton , S. Seshadri, On Estimating the Size of Projections, Proceedings of the Third International Conference on Database Theory, p.499-513, December 12-14, 1990
• 38: F. Olken and D. Rotem. Random Sampling from Databases: A Survey. Journal of Statistics and Computing, 5:25--42, 1995.
• 39: G. Özsoyoglu, K. Du, A. Tjahjana, W.-C. Hou, and D. Y. Rowland. On Estimating COUNT, SUM, and AVERAGE Relational Algebra Queries. In Proceedings of the 2nd DEXA International Conference on Database and Expert Systems Applications, pages 406--412, 1991.
• 40: Yannis Sismanis , Antonios Deligiannakis , Nick Roussopoulos , Yannis Kotidis, Dwarf: shrinking the PetaCube, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564745]
• 41: Jeffrey S. Vitter, Random sampling with a reservoir, ACM Transactions on Mathematical Software (TOMS), v.11 n.1, p.37-57, March 1985 [doi>10.1145/3147.3165]
• 42: Kyu-Young Whang , Brad T. Vander-Zanden , Howard M. Taylor, A linear-time probabilistic counting algorithm for database applications, ACM Transactions on Database Systems (TODS), v.15 n.2, p.208-229, June 1990 [doi>10.1145/78922.78925]
• 43: David Woodruff, Optimal space lower bounds for all frequency moments, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems