E = MC3: managing uncertain enterprise data in a cluster-computing environment

ABSTRACT

Modern enterprises must manage uncertain data for purposes of risk assessment and decisionmaking under uncertainty. The Monte Carlo approach embodied in the MCDB system of Jampani et al. is well suited for such a task. MCDB can support industrial strength business-intelligence queries over uncertain warehouse data. Moreover, MCDB's extensible approach to specifying uncertainty can also capture complex stochastic prediction models, allowing sophisticated ``what-if'' analyses within the DBMS. The MCDB computations can be highly CPU intensive, but offer the potential for massive parallelization. To realize this potential, we provide a new system, called MC<sup>3</sup> (Monte Carlo Computation on a Cluster), that extends the MCDB approach to the map-reduce processing framework. MC<sup>3</sup> can exploit the robustness and scalability of map-reduce, and can handle data stored in non-relational formats. We show how MCDB query plans over ``tuple bundles'' can be translated to sequences of map-reduce operations over nested data, and describe different parallelization schemes. We also provide and analyze several novel distributed algorithms for adding pseudorandom number seeds to tuple bundles. These algorithms ensure statistical correctness of the Monte-Carlo computations while minimizing the seed length. Our experiments show that MC³ can scale well for a variety of workloads.

REFERENCES

• 1: Parag Agrawal , Omar Benjelloun , Anish Das Sarma , Chris Hayworth , Shubha Nabar , Tomoe Sugihara , Jennifer Widom, Trio: a system for data, uncertainty, and lineage, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 2: L. Antova, C. Koch, andD. Olteanu. MayBMS: Managing incomplete information with probabilistic world-set decompositions. In ICDE, pages 1479--1480, 2007.
• 3: Jihad Boulos , Nilesh Dalvi , Bhushan Mandhani , Shobhit Mathur , Chris Re , Dan Suciu, MYSTIQ: a system for finding more answers by using probabilities, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066277]
• 4: Fay Chang , Jeffrey Dean , Sanjay Ghemawat , Wilson C. Hsieh , Deborah A. Wallach , Mike Burrows , Tushar Chandra , Andrew Fikes , Robert E. Gruber, Bigtable: a distributed storage system for structured data, Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation, p.15-15, November 06-08, 2006, Seattle, WA
• 5: Hung-chih Yang , Ali Dasdan , Ruey-Lung Hsiao , D. Stott Parker, Map-reduce-merge: simplified relational data processing on large clusters, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247602]
• 6: P. D. Coddington. Random number generators for parallel computers. The NHSE Review, 2, 1996.
• 7: Brian F. Cooper , Raghu Ramakrishnan , Utkarsh Srivastava , Adam Silberstein , Philip Bohannon , Hans-Arno Jacobsen , Nick Puz , Daniel Weaver , Ramana Yerneni, PNUTS: Yahoo!'s hosted data serving platform, Proceedings of the VLDB Endowment, v.1 n.2, August 2008 [doi>10.1145/1454159.1454167]
• 8: Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.10-10, December 06-08, 2004, San Francisco, CA
• 9: L. Devroye. Non-Uniform Random Variate Generation. Springer, 1986.
• 10: 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]
• 11: P. W. Glynn and S. Asmussen. Stochastic Simulation: Algorithms and Analysis. Springer, 2007.
• 12: Hadoop. http://hadoop.apache.org/core/.
• 13: Hiroshi Haramoto , Makoto Matsumoto , Pierre L'Ecuyer, A Fast Jump Ahead Algorithm for Linear Recurrences in a Polynomial Space, Proceedings of the 5th international conference on Sequences and Their Applications, September 14-18, 2008, Lexington, KY, USA [doi>10.1007/978-3-540-85912-3_26]
• 14: Hiroshi Haramoto , Makoto Matsumoto , Takuji Nishimura , François Panneton , Pierre L'Ecuyer, Efficient Jump Ahead for F2-Linear Random Number Generators, INFORMS Journal on Computing, v.20 n.3, p.385-390, Summer 2008 [doi>10.1287/ijoc.1070.0251]
• 15: S. G. Henderson and B. L. Nelson, editors. Simulation. North-Holland, 2006.
• 16: Ravi Jampani , Fei Xu , Mingxi Wu , Luis Leopoldo Perez , Christopher Jermaine , Peter J. Haas, MCDB: a monte carlo approach to managing uncertain data, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376686]
• 17: JAQL. http://code.google.com/p/jaql/.
• 18: JSON. http://www.json.org.
• 19: Benny Kimelfeld , Yehoshua Sagiv, Modeling and querying probabilistic XML data, ACM SIGMOD Record, v.37 n.4, December 2008 [doi>10.1145/1519103.1519115]
• 20: Pierre L'Ecuyer, Random numbers for simulation, Communications of the ACM, v.33 n.10, p.85-97, Oct. 1990 [doi>10.1145/84537.84555]
• 21: Gregory W. Fischer , Ziv Carmon , Dan Ariely , Gal Zauberman , Pierre L'Ecuyer, Good Parameters and Implementations for Combined Multiple Recursive Random Number Generators, Operations Research, v.47 n.1, p.159-164, January 1999 [doi>10.1287/opre.47.1.159]
• 22: Pierre L'Ecuyer , Terry H. Andres, A random number generator based on the combination of four LCGs, Mathematics and Computers in Simulation, v.44 n.1, p.99-107, May 1997 [doi>10.1016/S0378-4754(97)00052-9]
• 23: M. Mascagni. Some methods of parallel pseudorandom number generation. In R. Schreiber, M. Heath, and A. Ranade, editors, Algorithms for Parallel Processing, pages 277--288. Springer, 1997.
• 24: François Panneton , Pierre L'Ecuyer , Makoto Matsumoto, Improved long-period generators based on linear recurrences modulo 2, ACM Transactions on Mathematical Software (TOMS), v.32 n.1, p.1-16, March 2006 [doi>10.1145/1132973.1132974]
• 25: S. K. Park , K. W. Miller, Random number generators: good ones are hard to find, Communications of the ACM, v.31 n.10, p.1192-1201, Oct. 1988 [doi>10.1145/63039.63042]
• 26: Christopher Re , Dan Suciu, Managing Probabilistic Data with MystiQ: The Can-Do, the Could-Do, and the Can't-Do, Proceedings of the 2nd international conference on Scalable Uncertainty Management, p.5-18, October 01-03, 2008, Naples, Italy [doi>10.1007/978-3-540-87993-0_3]
• 27: SimpleDB. http://aws.amazon.com.
• 28: Sarvjeet Singh , Chris Mayfield , Sagar Mittal , Sunil Prabhakar , Susanne Hambrusch , Rahul Shah, Orion 2.0: native support for uncertain data, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376744]
• 29: SQLServer Data Services. http://www.microsoft.com/sql/dataservices/default.mspx.
• 30: A. Srinivasan, D. M. Ceperley, and M. Mascagni. Random number generators for parallel applications. In Monte Carlo Methods in Chemical Physics, pages 13--36. Wiley, 1997.
• 31: C. J. K. Tan. The PLFG parallel pseudo-random number generator. Future Generation Computer Systems, 18:693--698, 2002.
• 32: D. Z. Wang, E. Michelakis, M. N. Garofalakis, and J. M. Hellerstein. BayesStore:managing large, uncertain data repositories with probabilistic graphical models. Proc. VLDB, pages 340--351, 2008.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General

General Terms:
Algorithms, Design, Languages, Performance

Keywords:
jaql, json, map-reduce, monte carlo, uncertain data