Fast and approximate stream mining of quantiles and frequencies using graphics processors

ABSTRACT

We present algorithms for fast quantile and frequency estimation in large data streams using graphics processors (GPUs). We exploit the high computation power and memory bandwidth of graphics processors and present a new sorting algorithm that performs rasterization operations on the GPUs. We use sorting as the main computational component for histogram approximation and construction of ε-approximate quantile and frequency summaries. Our algorithms for numerical statistics computation on data streams are deterministic, applicable to fixed or variable-sized sliding windows and use a limited memory footprint. We use GPU as a co-processor and minimize the data transmission between the CPU and GPU by taking into account the low bus bandwidth. We implemented our algorithms on a PC with a NVIDIA GeForce FX 6800 Ultra GPU and a 3.4 GHz Pentium IV CPU and applied them to large data streams consisting of more than 100 million values. We also compared the performance of our GPU-based algorithms with optimized implementations of prior CPU-based algorithms. Overall, our results demonstrate that the graphics processors available on a commodity computer system are efficient stream-processor and useful co-processors for mining data streams.

REFERENCES

• 1: P. Agarwal, S. Krishnan, N. Mustafa, and S. Venkatasubramanian. Streaming geometric optimization using graphics hardware. 11 European Symposium on Algorithms, 2003.
• 2: Ramesh C. Agarwal, A super scalar sort algorithm for RISC processors, ACM SIGMOD Record, v.25 n.2, p.240-246, June 1996
• 3: Gagan Aggarwal , Mayur Datar , Sridhar Rajagopalan , Matthias Ruhl, On the Streaming Model Augmented with a Sorting Primitive, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.540-549, October 17-19, 2004 [doi>10.1109/FOCS.2004.48]
• 4: Rohit Ananthakrishna , Abhinandan Das , Johannes Gehrke , Flip Korn , S. Muthukrishnan , Divesh Srivastava, Efficient Approximation of Correlated Sums on Data Streams, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.569-572, March 2003 [doi>10.1109/TKDE.2003.1198391]
• 5: A. Arasu, B. Babcock, S. Babu, J. Cieslewicz, M. Datar, K. Ito, R. Motwani, U. Srivastava, and J. Widom. Stanford data stream management system. Data Stream Management, 2004. To appear.
• 6: Arvind Arasu , Gurmeet Singh Manku, Approximate counts and quantiles over sliding windows, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055598]
• 7: N. Bandi, C. Sun, D. Agrawal, and A. El Abbadi. Hardware acceleration in commercial databases: A case study of spatial operations. VLDB, 2004.
• 8: K. E. Batcher. Sorting networks and their applications. In Proc. 1968 Spring Joint Computer Conf., pages 307--314, Reston, VA, 1968. AFIPS Press.
• 9: I. Buck, T. Foley, D. Horn, J. Sugerman, K. Fatahalian, M. Houston, and P. Hanrahan. Brook for gpus: Stream computation on graphics hardware. Proc. of ACM SIGGRAPH, 2004.
• 10: 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
• 11: Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, Random sampling for histogram construction: how much is enough?, ACM SIGMOD Record, v.27 n.2, p.436-447, June 1998
• 12: 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]
• 13: 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
• 14: 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
• 15: Michael Doggett. Programmability features of graphics hardware. ACM SIGGRAPH Course Notes # 11, 2003.
• 16: Martin Dowd , Yehoshua Perl , Larry Rudolph , Michael Saks, The periodic balanced sorting network, Journal of the ACM (JACM), v.36 n.4, p.738-757, Oct. 1989 [doi>10.1145/76359.76362]
• 17: Alain Fournier , Donald Fussell, On the power of the frame buffer, ACM Transactions on Graphics (TOG), v.7 n.2, p.103-128, April 1988 [doi>10.1145/42458.42460]
• 18: C. Giannella, J. Han, J. Pei, X. Yan, and P. S. Yu. Mining frequent patterns in data streams at multiple time granularities. Proc. of NSF Workshop on Next Generation Data Mining, 2002.
• 19: Naga K. Govindaraju , Michael Henson , Ming C. Lin , Dinesh Manocha, Interactive visibility ordering and transparency computations among geometric primitives in complex environments, Proceedings of the 2005 symposium on Interactive 3D graphics and games, April 03-06, 2005, Washington, District of Columbia [doi>10.1145/1053427.1053435]
• 20: Naga K. Govindaraju , Brandon Lloyd , Wei Wang , Ming Lin , Dinesh Manocha, Fast computation of database operations using graphics processors, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007594]
• 21: N. Govindaraju, N. Raghuvanshi, M. Henson, and D. Manocha. A cache-efficient sorting algorithm for database and data mining computations using graphics processors. Technical report, University of North Carolina-Chapel Hill, 2005.
• 22: Michael B. Greenwald , Sanjeev Khanna, Power-conserving computation of order-statistics over sensor networks, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055597]
• 23: Michael Greenwald , Sanjeev Khanna, Space-efficient online computation of quantile summaries, ACM SIGMOD Record, v.30 n.2, p.58-66, June 2001
• 24: Approximating a Data Stream for Querying and Estimation: Algorithms and Performance Evaluation, Proceedings of the 18th International Conference on Data Engineering, p.567, February 26-March 01, 2002
• 25: Piotr Indyk, Algorithms for dynamic geometric problems over data streams, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007413]
• 26: Cheqing Jin , Weining Qian , Chaofeng Sha , Jeffrey X. Yu , Aoying Zhou, Dynamically maintaining frequent items over a data stream, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956918]
• 27: R. Jin and G. Agrawal. An algorithm for in-core frequent itemset mining on streaming data. Submitted for Publication, 2004.
• 28: 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]
• 29: Peter Kipfer , Mark Segal , Rüdiger Westermann, UberFlow: a GPU-based particle engine, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, August 29-30, 2004, Grenoble, France [doi>10.1145/1058129.1058146]
• 30: Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 31: Anthony LaMarca , Richard E. Ladner, The influence of caches on the performance of sorting, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.370-379, January 05-07, 1997, New Orleans, Louisiana, United States
• 32: A. Lastra, M. Lin, and D. Manocha. GPGP: General purpose computation using graphics processors. http://www.cs.unc.edu/Events/Conferences/GP2, 2004.
• 33: Xuemin Lin , Hongjun Lu , Jian Xu , Jeffrey Xu Yu, Continuously Maintaining Quantile Summaries of the Most Recent N Elements over a Data Stream, Proceedings of the 20th International Conference on Data Engineering, p.362, March 30-April 02, 2004
• 34: Gurmeet Singh Manku and Rajeev Motwani. Approximate frequency counts over data streams. In Philip A. Bernstein et al., editórs, VLDB 2002: proceedings of the Twenty-Eighth International Conference on Very Large Data Bases, Hong Kong, pages 346--357, 2002.
• 35: Gurmeet Singh Manku , Sridhar Rajagopalan , Bruce G. Lindsay, Approximate medians and other quantiles in one pass and with limited memory, ACM SIGMOD Record, v.27 n.2, p.426-435, June 1998
• 36: Gurmeet Singh Manku , Sridhar Rajagopalan , Bruce G. Lindsay, Random sampling techniques for space efficient online computation of order statistics of large datasets, ACM SIGMOD Record, v.28 n.2, p.251-262, June 1999
• 37: D. Manocha. Interactive Geometric and Scientific Computations using Graphics Hardware. SIGGRAPH Course Notes # 11, 2003.
• 38: J. Misra and D. Gries. Finding repeated elements. Sc. Comp. Prog., 2:143--152, 1982.
• 39: Rajeev Motwani , Dilys Thomas, Caching queues in memory buffers, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 40: J. Munro and M. Paterson. Selection and sorting with limited storage. Theoretical Computer Science, pages 315--323, 1980.
• 41: S. Muthukrishnan, Data streams: algorithms and applications, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 42: Timothy J. Purcell , Craig Donner , Mike Cammarano , Henrik Wann Jensen , Pat Hanrahan, Photon mapping on programmable graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
• 43: Chengyu Sun , Divyakant Agrawal , Amr El Abbadi, Hardware acceleration for spatial selections and joins, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872813]
• 44: Nitin Thaper , Sudipto Guha , Piotr Indyk , Nick Koudas, Dynamic multidimensional histograms, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564741]
• 45: S. Venkatasubramanian. The graphics card as a stream computer. Workshop on Management and Processing of Data Streams, 2003.
• 46: J. Xu, X. Lin, and X. Zhou. Space efficient quantile summary for constrained sliding windows on a data stream. Proceedings of WAIM (LNCS 3129), pages 34--44, 2004.
• 47: Jingren Zhou , Kenneth A. Ross, Implementing database operations using SIMD instructions, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564709]

INDEX TERMS

Keywords:
data streams, frequencies, graphics processors, memory bandwidth, quantiles, sliding windows, sorting