Design of a next generation sampling service for large scale data analysis applications

ABSTRACT

Advances in data collection and storage technologies have resulted in large and dynamically growing data sets at many organizations. Database and data mining researchers often use sampling with great effect to scale up performance on these data sets with small cost to accuracy. However, existing techniques often ignore the cost of computing a sample. This cost is often linear in the size of the data set, not the sample, which is expensive. Furthermore, for data mining applications that leverage progressive sampling or bootstrapping-based techniques, this cost can be prohibitive, since they require the generation of multiple samples.To address this problem, we present a solution in the context of a state-of-the-art data analysis center. Specifically, we propose a scalable service that supports sample generation with cost linear in the size of the sample. We then present an efficient parallelization of this service. Our solution leverages high speed interconnects (e.g. Myrinet, Infini-band) for parallel I/O operations with pipelined data transfers. We export an interface that supports both ad-hoc SQL-like querying for database applications, as well as a stand-alone service for data mining applications. We then evaluate our work using queries abstracted from a network monitoring and analysis application, which uses both database and progressive sampling queries. We demonstrate that our implementation achieves good load balance and realizes up to an order of magnitude speedup when compared with extant approaches.

REFERENCES

• 1: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 2: Mario Cannataro , Domenico Talia, The knowledge grid, Communications of the ACM, v.46 n.1, p.89-93, January 2003 [doi>10.1145/602421.602425]
• 3: P. Carns, W. Ligon, R. Ross, and R. Thakur. Pvfs: A parallel file system for linux clusters. In Proceedings of the Annual Linux Showcase and Conference, 2000.
• 4: Ling Tony Chen , Doron Rotem, Declustering Objects for Visualization, Proceedings of the 19th International Conference on Very Large Data Bases, p.85-96, August 24-27, 1993
• 5: A. Chervenak, I. Foster, C. Kesselman, C. Salisbury, and S. Tuecke. The Data Grid: Towards an Architecture For the Distributed Management and Analysis of Large Scientific Datasets, 2001.
• 6: Peter F. Corbett , Dror G. Feitelson, The Vesta parallel file system, ACM Transactions on Computer Systems (TOCS), v.14 n.3, p.225-264, Aug. 1996 [doi>10.1145/233557.233558]
• 7: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 8: David DeWitt , Jim Gray, Parallel database systems: the future of high performance database systems, Communications of the ACM, v.35 n.6, p.85-98, June 1992 [doi>10.1145/129888.129894]
• 9: Thomas G. Dietterich, An Experimental Comparison of Three Methods for Constructing Ensembles of Decision Trees: Bagging, Boosting, and Randomization, Machine Learning, v.40 n.2, p.139-157, Aug. 2000 [doi>10.1023/A:1007607513941]
• 10: Pedro Domingos , Geoff Hulten, A General Method for Scaling Up Machine Learning Algorithms and its Application to Clustering, Proceedings of the Eighteenth International Conference on Machine Learning, p.106-113, June 28-July 01, 2001
• 11: H. C. Du , J. S. Sobolewski, Disk allocation for Cartesian product files on multiple-disk systems, ACM Transactions on Database Systems (TODS), v.7 n.1, p.82-101, March 1982 [doi>10.1145/319682.319698]
• 12: Christos Faloutsos , Pravin Bhagwat, Declustering using fractals, Proceedings of the second international conference on Parallel and distributed information systems, p.18-25, January 1993, San Diego, California, United States
• 13: M. T. Fang , Richard C. T. Lee , C. C. Chang, The Idea of De-Clustering and its Applications, Proceedings of the 12th International Conference on Very Large Data Bases, p.181-188, August 25-28, 1986
• 14: Jiawei Han , Micheline Kamber, Data mining: concepts and techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 15: Christopher Jermaine , Abhijit Pol , Subramanian Arumugam, Online maintenance of very large random samples, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007603]
• 16: G. John and P. Langley. Static versus dynamic sampling for data mining. In Proceedings of the International Conference on Knowledge Discovery and Data Mining, 1996.
• 17: David Kotz. Disk-directed I/O for MIMD multiprocessors. In Proceedings of the 1994 Symposium on Operating Systems Design and Implementation, pages 61--74. ACM Press, November 1994.
• 18: Duen-Ren Liu , Shashi Shekhar, A Similarity Graph-Based Approach to Declustering Problems and Its Application towards Paralleling Grid Files, Proceedings of the Eleventh International Conference on Data Engineering, p.373-381, March 06-10, 1995
• 19: Matthew V. Mahoney , Philip K. Chan, Learning Rules for Anomaly Detection of Hostile Network Traffic, Proceedings of the Third IEEE International Conference on Data Mining, p.601, November 19-22, 2003
• 20: John M. May, Parallel I/O for high performance computing, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 21: Bongki Moon , Anurag Acharya , Joel H. Saltz, Study of Scalable Declustering Algorithms for Parallel Grid Files, Proceedings of the 10th International Parallel Processing Symposium, p.434-440, April 15-19, 1996
• 22: Nils Nieuwejaar , David Kotz, The galley parallel file system, Proceedings of the 10th international conference on Supercomputing, p.374-381, May 25-28, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237578.237639]
• 23: Frank Olken , Doron Rotem, Random sampling from database files: a survey, Proceedings of the fifth international conference on Statistical and scientific database management, p.92-111, March 1990, Charlotte, North Carolina, United States
• 24: J. Pan, C. Faloutsos, and S. Seshan. Fastcars: Fast, correlation-aware sampling for network data mining. In Proceeding of the IEEE GlobeCom Global Internet Symposium, 2002.
• 25: Srinivasan Parthasarathy, Efficient Progressive Sampling for Association Rules, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.354, December 09-12, 2002
• 26: Jean-Pierre Prost , Richard Treumann , Richard Hedges , Bin Jia , Alice Koniges, MPI-IO/GPFS, an optimized implementation of MPI-IO on top of GPFS, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.17-17, November 10-16, 2001, Denver, Colorado [doi>10.1145/582034.582051]
• 27: Foster Provost , David Jensen , Tim Oates, Efficient progressive sampling, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.23-32, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312188]
• 28: Foster Provost , Venkateswarlu Kolluri, A Survey of Methods for Scaling Up Inductive Algorithms, Data Mining and Knowledge Discovery, v.3 n.2, p.131-169, June 1999 [doi>10.1023/A:1009876119989]
• 29: K. E. Seamons , Y. Chen , P. Jones , J. Jozwiak , M. Winslett, Server-directed collective I/O in Panda, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.57-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224371]
• 30: Xiaohui Shen , Alok Choudhary, MS-I/O: A Distributed Multi-Storage I/O System, Proceedings of the 2nd IEEE/ACM International Symposium on Cluster Computing and the Grid, p.163, May 21-24, 2002
• 31: Rajeev Thakur , Alok Choudhary , Rajesh Bordawekar , Sachin More , Sivaramakrishna Kuditipudi, Passion: Optimized I/O for Parallel Applications, Computer, v.29 n.6, p.70-78, June 1996
• 32: Hannu Toivonen, Sampling Large Databases for Association Rules, Proceedings of the 22th International Conference on Very Large Data Bases, p.134-145, September 03-06, 1996
• 33: 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]
• 34: M. Zaki, S. Parthasarathy, M. Ogihara, and W. Li. New algorithms for fast discovery of association rules. In Proceedings of the International Conference on Knowledge Discovery and Data Mining, 1997.

INDEX TERMS

Keywords:
data centers, data mining, parallel I/O, sampling