Hierarchical bin buffering: Online local moments for dynamic external memory arrays

ABSTRACT

For a massive I/O array of size n, we want to compute the first N local moments, for some constant N. Our simpler algorithms partition the array into consecutive ranges called bins, and apply not only to local-moment queries, but also to algebraic queries. With N buffers of size &sqrt;n, time complexity drops to O(&sqrt;n). A more sophisticated approach uses hierarchical buffering and has a logarithmic time complexity (O(b log_b n)), when using N hierarchical buffers of size n/b. Using overlapped bin buffering, we show that only one buffer is needed, as with wavelet-based algorithms, but using much less storage.

REFERENCES

• 1: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.20-29, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237823]
• 2: S. Browne , J. Dongarra , N. Garner , G. Ho , P. Mucci, A Portable Programming Interface for Performance Evaluation on Modern Processors, International Journal of High Performance Computing Applications, v.14 n.3, p.189-204, August 2000 [doi>10.1177/109434200001400303]
• 3: Kaushik Chakrabarti , Minos Garofalakis , Rajeev Rastogi , Kyuseok Shim, Approximate query processing using wavelets, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.2-3, p.199-223, September 2001
• 4: Cleveland, W., and Loader, C. 1995. Smoothing by local regression: Principles and methods. Tech. Rep., AT&T Bell Laboratories.
• 5: Codd, E. F., Codd, S., and Salley, C. 1993. Providing OLAP (on-line analytical processing) to user-analysts: An IT mandate. Tech. Rep., E. F. Codd and Associates.
• 6: Antonios Deligiannakis , Nick Roussopoulos, Extended wavelets for multiple measures, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872786]
• 7: Relative Prefix Sums: An Efficient Approach for Querying Dynamic OLAP Data Cubes, Proceedings of the 15th International Conference on Data Engineering, p.328, March 23-26, 1999
• 8: Jim Gray , Adam Bosworth , Andrew Layman , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Total, Proceedings of the Twelfth International Conference on Data Engineering, p.152-159, February 26-March 01, 1996
• 9: Ching-Tien Ho , Rakesh Agrawal , Nimrod Megiddo , Ramakrishnan Srikant, Range queries in OLAP data cubes, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.73-88, May 11-15, 1997, Tucson, Arizona, United States
• 10: IEC. 1999. Letter symbols to be used in electrical technology---Part 2: Telecommunications and electronics. Tech. Rep. IEC 60027-2 Second ed. International Electrotechnical Commission.
• 11: Mehrdad Jahangiri , Dimitris Sacharidis , Cyrus Shahabi, SHIFT-SPLIT: I/O efficient maintenance of wavelet-transformed multidimensional data, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066189]
• 12: Daniel Lemire, Wavelet-based relative prefix sum methods for range sum queries in data cubes, Proceedings of the 2002 conference of the Centre for Advanced Studies on Collaborative research, p.6, September 30-October 03, 2002, Toronto, Ontario, Canada
• 13: Lemire, D. 2007. A better alternative to piecewise linear time series segmentation. In Proceedings of the SIAM International Conference on Data Mining (SDM).
• 14: Lemire, D., and Kaser, O. 2007. Hierarchical bin buffering library in C++. http://code.google.com/p/hierarchicalbinbuffering/. Last checked on 15-7-2007.
• 15: Li, B.-C., and Shen, J. 1992. Fast calculation of local moments and application to range image segmentation. In Proceedings of the International Conference on Pattern Recognition, 298--301.
• 16: Guido Moerkotte, Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing, Proceedings of the 24rd International Conference on Very Large Data Bases, p.476-487, August 24-27, 1998
• 17: Interview: A Conversation with Jim Gray, Queue, v.1 n.4, June 2003 [doi>10.1145/864056.864078]
• 18: Chung Keung Poon, Dynamic orthogonal range queries in OLAP, Theoretical Computer Science, v.296 n.3, p.487-510, 14 March 2003 [doi>10.1016/S0304-3975(02)00741-7]
• 19: Singiresu S. Rao, Applied Numerical Methods for Engineers and Scientists, Prentice Hall Professional Technical Reference, 2001
• 20: Rolfe R. Schmidt , Cyrus Shahabi, ProPolyne: A Fast Wavelet-Based Algorithm for Progressive Evaluation of Polynomial Range-Sum Queries, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.664-681, March 25-27, 2002
• 21: Scott, D., and Sagae, M. 1997. Adaptive density estimation with massive data sets. In Proceedings of the Statistical Computing Section, ASA, 104--108.
• 22: Silva, C., Chiang, Y., El-Sana, J., and Lindstrom, P. 2002. Out-of-Core algorithms for scientific visualization and computer graphics. In Visualization Course Notes, Tutorial.
• 23: Jeffrey Scott Vitter, External memory algorithms, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
• 24: Jeffrey Scott Vitter , Min Wang , Bala Iyer, Data cube approximation and histograms via wavelets, Proceedings of the seventh international conference on Information and knowledge management, p.96-104, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288645]
• 25: Feng Zhou , Peter Kornerup, Computing Moments by Prefix Sums, University of Southern Denmark, 1995

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.1 Interpolation

General Terms:
Algorithms, Experimentation, Theory

Keywords:
Very large arrays, hierarchical buffers, polynomial fitting, statistical queries