From discrepancy to declustering: near-optimal multidimensional declustering strategies for range queries

ABSTRACT

Declustering schemes allocate data blocks among multiple disks to enable parallel retrieval. Given a declustering scheme D, its response time with respect to a query Q, rt(Q), is defined to be the maximum number of disk blocks of the query stored by the scheme in any one of the disks. If |Q| is the number of data blocks in Q and M is the number of disks then rt(Q) is at least |Q|/M. One way to evaluate the performance of D with respect to a set of queries 𝑄 is to measure its additive error - the maximum difference between rt(Q) from |Q|/M over all range queries Q ε 𝑄.In this paper, we consider the problem of designing declustering schemes for uniform multidimensional data arranged in a d-dimensional grid so that their additive errors with respect to range queries are as small as possible. It has been shown that such declustering schemes will have an additive error of Ω(log M) when d = 2 and Ω(log d-1/2 M) when d > 2 with respect to range queries.Asymptotically optimal declustering schemes exist for 2-dimensional data. For data in larger dimensions, however, the best bound for additive errors is O(M^d-1), which is extremely large. In this paper, we propose the two declustering schemes based on low discrepancy points in d-dimensions. When d is fixed, both schemes have an additive error of O(log^d-1 M) with respect to range queries provided certain conditions are satisfied: the first scheme requires d ≥ 3 and M to be a power of a prime where the prime is at least d while the second scheme requires the size of the data to grow within some polynomial of M, with no restriction on M. These are the first known multidimensional declustering schemes with additive errors near optimal.

REFERENCES

• 1: NCR WorldMark/Teradata 1 TB TPC-D Executive Summary. www.tpc.org.
• 2: Sun Fire 6800 midframe server with Sun Storedge arrays. www.sun.com/smi/Press/sunflash/2002-05/sunflash.20020514.2.html.
• 3: Khaled A. S. Abdel-Ghaffar , Amr El Abbadi, Optimal Allocation of Two-Dimensional Data, Proceedings of the 6th International Conference on Database Theory, p.409-418, January 08-10, 1997
• 4: Mikhail J. Atallah , Sunil Prabhakar, (Almost) optimal parallel block access to range queries, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.205-215, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335224]
• 5: Declustering Using Golden Ratio Sequences, Proceedings of the 16th International Conference on Data Engineering, p.271, February 28-March 03, 2000
• 6: Randeep Bhatia , Rakesh K. Sinha , Chung-Min Chen, Hierarchical Declustering Schemes for Range Queries, Proceedings of the 7th International Conference on Extending Database Technology: Advances in Database Technology, p.525-537, March 27-31, 2000
• 7: Chialin Chang , Bongki Moon , Anurag Acharya , Carter Shock , Alan Sussman , Joel H. Saltz, Titan: A High-Performance Remote Sensing Database, Proceedings of the Thirteenth International Conference on Data Engineering, p.375-384, April 07-11, 1997
• 8: Chung-Min Chen , Rakesh K. Sinha, Analysis and Comparison of Declustering Schemes for Interactive Navigation Queries, IEEE Transactions on Knowledge and Data Engineering, v.12 n.5, p.763-778, September 2000 [doi>10.1109/69.877507]
• 9: Chung-Min Chen , Rakesh K. Sinha , Randeep Bhatia, Efficient Disk Allocation Schemes for Parallel Retrieval of Multidimensional Grid Data, Proceedings of the 13th International Conference on Scientific and Statistical Database Management, p.213-222, July 18-20, 2001
• 10: 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
• 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: C. Faloutsos, Gray Codes for Partial Match and Range Queries, IEEE Transactions on Software Engineering, v.14 n.10, p.1381-1393, October 1988 [doi>10.1109/32.6184]
• 13: 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
• 14: 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
• 15: H. Faure. Discrepancy of sequences associated with a number system (in dimension s) (in french). Acta Arithmetica, 41(4):337-351, 1982.
• 16: Nahum D. Gershon , C. Grant Miller, Dealing with the data deluge, IEEE Spectrum, v.30 n.7, p.28-32, July 1993 [doi>10.1109/6.222224]
• 17: J. H. Halton. On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals. Numerische Mathematik, 2:84-90, 1960.
• 18: B. Himatsingka, J. Srivastava, J.-Z. Li, and D. Rotem. Latin hypercubes: A class of multidimensional declustering techniques, 1994. Technical Report TR94-05, Department of Computer Science, University of Minnesota.
• 19: John A. Richards , Xiuping Jia , D. E. Ricken , W. Gessner, Remote Sensing Digital Image Analysis: An Introduction, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 20: Myoung Ho Kim , Sakti Pramanik, Optimal file distribution for partial match retrieval, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.173-182, June 01-03, 1988, Chicago, Illinois, United States
• 21: S. Kuo , M. Winslett , Y. Cho , J. Lee, New GDM-Based Declustering Methods for Parallel Range Queries, Proceedings of the 1999 International Symposium on Database Engineering & Applications, p.119, August 02-04, 1999
• 22: Jianzhong Li , Jaideep Srivastava , Doron Rotem, CMD: A Multidimensional Declustering Method for Parallel Data Systems, Proceedings of the 18th International Conference on Very Large Data Bases, p.3-14, August 23-27, 1992
• 23: Duen-Ren Liu , Shashi Shekhar, Partitioning similarity graphs: a framework for declustering problems, Information Systems, v.21 n.6, p.475-496, Sept. 1996 [doi>10.1016/0306-4379(96)00024-5]
• 24: J. Matousek. Geometric discrepancy, an illustrated guide. Springer-Verlag, 1999.
• 25: John M. May, Parallel I/O for high performance computing, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 26: Bongki Moon , Joel H. Saltz, Scalability Analysis of Declustering Methods for Multidimensional Range Queries, IEEE Transactions on Knowledge and Data Engineering, v.10 n.2, p.310-327, March 1998 [doi>10.1109/69.683759]
• 27: H. Niederreiter. Nets, (t, s) sequences, and algebraic curves over finite fields with many rational points. Documenta Math. J. DMV, 3:377-386, 1998.
• 28: S. Prabhakar , K. Abdel-Ghaffar , D. Agrawal , A. El Abbadi, Efficient Retrieval of Multidimensional Datasets through Parallel I/O, Proceedings of the Fifth International Conference on High Performance Computing, p.375, December 17-20, 1998
• 29: Sunil Prabhakar , Khaled A. S. Abdel-Ghaffar , Divyakant Agrawal , Amr El Abbadi, Cyclic Allocation of Two-Dimensional Data, Proceedings of the Fourteenth International Conference on Data Engineering, p.94-101, February 23-27, 1998
• 30: H. E. Rose. A course in number theory. Oxford University Press, Walton Street, Oxford, 1988.
• 31: K. F. Roth. On irregularities of distribution. Mathematika, 1:73-79, 1954.
• 32: W. Schmidt. On irregularities of distribution vii. Acta Arithmetica, 21:45-50, 1972.
• 33: Rakesh K. Sinha , Randeep Bhatia , Chung-Min Chen, Asymptotically Optimal Declustering Schemes for Range Queries, Proceedings of the 8th International Conference on Database Theory, p.144-158, January 04-06, 2001
• 34: J. Srivastava, T. Niccum, and B. Himatsingka. Data declustering in PADMA: A parallel database manager. Bulletin of Technical Communication on Data Engineering, 17(3):3-13, 1994.
• 35: Yvonne Zhou , Shashi Shekhar , Mark Coyle, Disk Allocation Methods for Parallelizing Grid Files, Proceedings of the Tenth International Conference on Data Engineering, p.243-252, February 14-18, 1994

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Parallel databases

Keywords:
declustering schemes, disk allocations, parallel database, range query