CAM conscious integrated answering of frequent elements and top-k queries over data streams

ABSTRACT

Frequent elements and top-k queries constitute an important class of queries for data stream analysis applications. Certain applications require answers for both frequent elements and top-k queries on the same stream. In addition, the ever increasing data rates call for providing fast answers to the queries, and researchers have been looking towards exploiting specialized hardware for this purpose. Content Addressable Memory(CAM) provides an efficient way of looking up elements and hence are well suited for the class of algorithms that involve lookups. In this paper, we present a fast and efficient CAM conscious integrated solution for answering both frequent elements and top-k queries on the same stream. We call our scheme CAM conscious Space Saving with Stream Summary (CSSwSS), and it can efficiently answer continuous queries. We provide an implementation of the proposed scheme using commodity CAM chips, and the experimental evaluation demonstrates that not only does the proposed scheme outperforms existing CAM conscious techniques by an order of magnitude at query loads of about 10%, but the proposed scheme can also efficiently answer continuous queries.

REFERENCES

• 1: Nagender Bandi , Ahmed Metwally , Divyakant Agrawal , Amr El Abbadi, Fast data stream algorithms using associative memories, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247510]
• 2: N. Bandi, S. Schnieder, D. Agrawal, and A. E. Abbadi. Hardware Acceleration of Database operations using Content Addressable Memories. In DaMoN, 2005.
• 3: Bishwaranjan Bhattacharjee , Naoki Abe , Kenneth Goldman , Bianca Zadrozny , Vamsavardhana R. Chillakuru , Marysabel del Carpio , Chid Apte, Using secure coprocessors for privacy preserving collaborative data mining and analysis, Proceedings of the 2nd international workshop on Data management on new hardware, June 25-25, 2006, Chicago, Illinois [doi>10.1145/1140402.1140404]
• 4: 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
• 5: John Cieslewicz , Kenneth A. Ross, Adaptive aggregation on chip multiprocessors, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 6: Gautam Das , Dimitrios Gunopulos , Nick Koudas , Nikos Sarkas, Ad-hoc top-k query answering for data streams, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 7: 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
• 8: Rui Fang , Bingsheng He , Mian Lu , Ke Yang , Naga K. Govindaraju , Qiong Luo , Pedro V. Sander, GPUQP: query co-processing using graphics processors, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247606]
• 9: M. Fischer and S. Salzberg. Finding a majority among n votes: Solution to problem 81--5. In Journal of Algorithms 3(4), pages 376--379, 1982.
• 10: Brian Gold , Anastassia Ailamaki , Larry Huston , Babak Falsafi, Accelerating database operators using a network processor, Proceedings of the 1st international workshop on Data management on new hardware, June 12-12, 2005, Baltimore, Maryland [doi>10.1145/1114252.1114260]
• 11: Michael Greenwald , Sanjeev Khanna, Space-efficient online computation of quantile summaries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.58-66, May 21-24, 2001, Santa Barbara, California, United States
• 12: N. Hardavellas, I. Pandis, R. Johnson, N. G. Mancheril, A. Ailamaki, and B. Falsafi. Database Servers on Chip Multiprocessors: Limitations and Opportunities. In CIDR, pages 79--87, 2007.
• 13: Integrated Devices Technologies, Integrated IP Co-processor IDT 75K62134. http://idt.com/?genID=75K62134&source=products_genericPart_75K62134, 2006.
• 14: Intel Internet Exchange Architecture for Network Processors. Technical report, Intel Corp., 2002.
• 15: Intel IXP 2800 Network Processor Product Brief. http://www.intel.com/design/network/prodbrf/279054.htm, 2006.
• 16: Gurmeet Singh Manku , Rajeev Motwani, Approximate frequency counts over data streams, Proceedings of the 28th international conference on Very Large Data Bases, p.346-357, August 20-23, 2002, Hong Kong, China
• 17: Ahmed Metwally , Divyakant Agrawal , Amr El Abbadi, An integrated efficient solution for computing frequent and top-k elements in data streams, ACM Transactions on Database Systems (TODS), v.31 n.3, p.1095-1133, September 2006 [doi>10.1145/1166074.1166084]
• 18: Kyriakos Mouratidis , Spiridon Bakiras , Dimitris Papadias, Continuous monitoring of top-k queries over sliding windows, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142544]
• 19: R. Panigrahy and D. Thomas. Finding Frequent Elements in Non-Bursty Streams. In ESA, pages 53--62, October 2007.
• 20: Devavrat Shah , Pankaj Gupta, Fast Updating Algorithms for TCAMs, IEEE Micro, v.21 n.1, p.36-47, January 2001 [doi>10.1109/40.903060]
• 21: Teja networking systems and teja np application development platform. http://www.teja.com, 2006.
• 22: S. Venkataraman, D. Song, P. Gibbons, and A. Blum. New streaming algorithms for fast detection of superspreaders. In NDSS, 2005.
• 23: Jingren Zhou , John Cieslewicz , Kenneth A. Ross , Mihir Shah, Improving database performance on simultaneous multithreading processors, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 24: G. K. Zipf. Human Behavior and The Principle of Least Effort. Addison-Wesley, Cambridge, MA, 1949.
• 25: Marcin Zukowski , Sándor Héman , Peter Boncz, Architecture-conscious hashing, Proceedings of the 2nd international workshop on Data management on new hardware, June 25-25, 2006, Chicago, Illinois [doi>10.1145/1140402.1140410]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

General Terms:
Design, Performance

Keywords:
content addressable memory, data streams, frequent elements queries, network processor, stream algorithms, top-k queries