What's hot and what's not: tracking most frequent items dynamically

ABSTRACT

Most database management systems maintain statistics on the underlying relation. One of the important statistics is that of the "hot items" in the relation: those that appear many times (most frequently, or more than some threshold). For example, end-biased histograms keep the hot items as part of the histogram and are used in selectivity estimation. Hot items are used as simple outliers in data mining, and in anomaly detection in networking applications.We present a new algorithm for dynamically determining the hot items at any time in the relation that is undergoing deletion operations as well as inserts. Our algorithm maintains a small space data structure that monitors the transactions on the relation, and when required, quickly outputs all hot items, without rescanning the relation in the database. With user-specified probability, it is able to report all hot items. Our algorithm relies on the idea of "group testing", is simple to implement, and has provable quality, space and time guarantees. Previously known algorithms for this problem that make similar quality and performance guarantees can not handle deletions, and those that handle deletions can not make similar guarantees without rescanning the database. Our experiments with real and synthetic data shows that our algorithm is remarkably accurate in dynamically tracking the hot items independent of the rate of insertions and deletions.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman , J. D. Ullman , J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 2: Noga Alon , Phillip B. Gibbons , Yossi Matias , Mario Szegedy, Tracking join and self-join sizes in limited storage, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.10-20, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303978]
• 3: 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]
• 4: Brian Babcock , Chris Olston, Distributed top-k monitoring, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872764]
• 5: D. Barbara, N. Wu, and S. Jajodia. Detecting novel network intrusions using bayes estimators. In Proceedings of the first SIAM International Conference on Data Mining, 2001.
• 6: B. Boyer and J. Moore. A fast majority vote algorithm. Technical Report 35, Institute for Computer Science, University of Texas, 1982.
• 7: J. L. Carter and M. N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18(2):143--154, 1979.
• 8: Moses Charikar , Kevin Chen , Martin Farach-Colton, Finding Frequent Items in Data Streams, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.693-703, July 08-13, 2002
• 9: Erik D. Demaine , Alejandro López-Ortiz , J. Ian Munro, Frequency Estimation of Internet Packet Streams with Limited Space, Proceedings of the 10th Annual European Symposium on Algorithms, p.348-360, September 17-21, 2002
• 10: D.-Z. Du and F. Hwang. Combinatorial Group Testing and Its Applications, volume 3 of Series on Applied Mathematics. World Scientific, 1993.
• 11: Min Fang , Narayanan Shivakumar , Hector Garcia-Molina , Rajeev Motwani , Jeffrey D. Ullman, Computing Iceberg Queries Efficiently, Proceedings of the 24rd International Conference on Very Large Data Bases, p.299-310, August 24-27, 1998
• 12: M. Fischer and S. Salzberg. Finding a majority among n votes: Solution to problem 81--5. Journal of Algorithms, 3(4):376--379, 1982.
• 13: Phillip B. Gibbons , Yossi Matias, New sampling-based summary statistics for improving approximate query answers, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.331-342, June 01-04, 1998, Seattle, Washington, United States
• 14: P. Gibbons and Y. Matias. Synopsis structures for massive data sets. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, A, 1999.
• 15: Phillip B. Gibbons , Yossi Matias , Viswanath Poosala, Fast Incremental Maintenance of Approximate Histograms, Proceedings of the 23rd International Conference on Very Large Data Bases, p.466-475, August 25-29, 1997
• 16: Anna C. Gilbert , Sudipto Guha , Piotr Indyk , Yannis Kotidis , S. Muthukrishnan , Martin J. Strauss, Fast, small-space algorithms for approximate histogram maintenance, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509966]
• 17: A. Gilbert, Y. Kotidis, S. Muthukrishnan, and M. Strauss. QuickSAND: Quick summary and analysis of network data. Technical Report 2001--43, DIMACS, 2001.
• 18: A. C. Gilbert, Y. Kotidis, S. Muthukrishnan, and M. Strauss. How to summarize the universe: Dynamic maintenance of quantiles. In Proceedings of 28th International Conference on Very Large Data Bases, 2002.
• 19: Yannis E. Ioannidis , Stavros Christodoulakis, Optimal histograms for limiting worst-case error propagation in the size of join results, ACM Transactions on Database Systems (TODS), v.18 n.4, p.709-748, Dec. 1993 [doi>10.1145/169725.169708]
• 20: Yannis E. Ioannidis , Viswanath Poosala, Balancing histogram optimality and practicality for query result size estimation, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.233-244, May 22-25, 1995, San Jose, California, United States
• 21: Richard M. Karp , Scott Shenker , Christos H. Papadimitriou, A simple algorithm for finding frequent elements in streams and bags, ACM Transactions on Database Systems (TODS), v.28 n.1, p.51-55, March 2003 [doi>10.1145/762471.762473]
• 22: W. Kautz and R. Singleton. Nonrandom binary superimposed codes. IEEE Transactions on on Information Theory, 10:363--377, 1964.
• 23: G. Manku and R. Motwani. Approximate frequency counts over data streams. In Proceedings of 28th International Conference on Very Large Data Bases, pages 346--357, 2002.
• 24: J. Misra and D. Gries. Finding repeated elements. Science of Computer Programming, 2:143--152, 1982.
• 25: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 26: Online Data Mining for Co-Evolving Time Sequences, Proceedings of the 16th International Conference on Data Engineering, p.13, February 28-March 03, 2000

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Statistical databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Human Factors, Standardization, Theory