Fast data stream algorithms using associative memories

ABSTRACT

The primary goal of data stream research is to develop space and time efficient solutions for answering continuous on-line summarization queries. Research efforts over the last decade have resulted in a number of efficient algorithms with varying degrees of space and time complexities. While these techniques are developed in a standard CPU setting, many of their applications such as click-fraud detection and network-traffic summarization typically execute on special networking architectures called Network Processing Units (NPUs). These NPUs interface with special associative memories known as Ternary Content Addressable Memories (TCAMs) to provide gigabit rate forwarding at network routers. In this paper, we describe how the integrated architecture of NPU and TCAMs can be exploited towards achieving the goal of developing high-speed stream summarization solutions. We propose two TCAM-conscious solutions for the frequent elements problem in data streams and present a comprehensive evaluation of these techniques on a state-of-the-art networking platform.

REFERENCES

• 1: Intel network processing units. http://www.intel.com/, 2006.
• 2: Teja networking systems. http://www.teja.com, 2006.
• 3: Daniel J. Abadi , Don Carney , Ugur Çetintemel , Mitch Cherniack , Christian Convey , Sangdon Lee , Michael Stonebraker , Nesime Tatbul , Stan Zdonik, Aurora: a new model and architecture for data stream management, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.2, p.120-139, August 2003 [doi>10.1007/s00778-003-0095-z]
• 4: Nagender Bandi , Divyakant Agrawal , Amr El Abbadi, Fast Algorithms for Heavy Distinct Hitters using Associative Memories, Proceedings of the 27th International Conference on Distributed Computing Systems, p.6, June 25-27, 2007 [doi>10.1109/ICDCS.2007.110]
• 5: N. Bandi, S. Schnieder, D. Agrawal, and A. E. Abbadi. Hardware acceleration of database operations using content-addressable memories. In DaMoN, 2005.
• 6: S. Chandrasekaran. Telegraphcq: Continuous dataflow processing for an uncertain world, 2003.
• 7: 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
• 8: Graham Cormode , S. Muthukrishnan, What's hot and what's not: tracking most frequent items dynamically, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.296-306, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773182]
• 9: Chuck Cranor , Theodore Johnson , Oliver Spataschek , Vladislav Shkapenyuk, Gigascope: a stream database for network applications, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872838]
• 10: 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
• 11: Cristian Estan , George Varghese, New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice, ACM Transactions on Computer Systems (TOCS), v.21 n.3, p.270-313, August 2003 [doi>10.1145/859716.859719]
• 12: R. H. K. Fang Yu. Efficient Multi-Match Packet Classification with TCAM. In IEEE Hot Interconnects, 2004.
• 13: B. T. Gold, A. Ailamaki, L. Huston, and B. Falsafi. Accelerating database operations using a network processor. In DaMoN, 2005.
• 14: M. Greenwald and S. Khanna. Space-efficient online computation of quantile summaries. In SIGMOD Conference, 2001.
• 15: J. Hershberger, N. Shrivastava, S. Suri, and C. D. Tóth. Adaptive spatial partitioning for multidimensional data streams. In ISAAC, pages 522--533, 2004.
• 16: 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]
• 17: K. Lakshminarayanan, A. Rangarajan, and S. Venkatachary. Algorithms for advanced packet classification with ternary cams. In SIGCOMM '05, pages 193--204, New York, NY, USA, 2005. ACM Press.
• 18: G. S. Manku and R. Motwani. Approximate frequency counts over data streams, 2002.
• 19: Gurmeet Singh Manku , Sridhar Rajagopalan , Bruce G. Lindsay, Approximate medians and other quantiles in one pass and with limited memory, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.426-435, June 01-04, 1998, Seattle, Washington, United States
• 20: A. Metwally, D. Agrawal, and A. E. Abbadi. Efficient computation of frequent and top-k elements in data streams. In ICDT, pages 398--412, 2005.
• 21: J. Misra and D. Gries. Finding repeated elements. Sci. Comput. Program., 2(2):143--152, 1982.
• 22: Shashidhar Mysore , Banit Agrawal , Timothy Sherwood , Nisheeth Shrivastava , Subhash Suri, Profiling over Adaptive Ranges, Proceedings of the International Symposium on Code Generation and Optimization, p.147-158, March 26-29, 2006 [doi>10.1109/CGO.2006.30]
• 23: G. J. Narlikar, A. Basu, and F. Zane. Coolcams: Power-efficient tcams for forwarding engines. In INFOCOM, 2003.
• 24: R. Panigrahy and S. Sharma. Sorting and Searching using Ternary CAMs. In IEEE Micro., 2003.
• 25: J. Widom and R. Motwani. Query processing, resource management, and approximation in a data stream management system, 2003.
• 26: Fang Yu , Randy H. Katz , T. V. Lakshman, Gigabit Rate Packet Pattern-Matching Using TCAM, Proceedings of the Network Protocols, 12th IEEE International Conference on (ICNP'04), p.174-183, October 05-08, 2004

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance

Keywords:
TCAMS, data streams, hardware