Equivalent disk allocations

ABSTRACT

Declustering techniques reduce query response times through parallel I/O by distributing data among multiple devices. Except for a few cases it is not possible to find declustering schemes that are optimal for all spatial range queries. As a result of this, most of the research on declustering have focused on finding schemes with low worst case additive error. Number-theoretic declustering techniques provide low additive error and high threshold. In this paper, we investigate equivalent disk allocations and focus on number-theoretic declustering. Most of the disk allocations are equivalent and provide the same additive error and threshold. Investigation of equivalent allocations offer many advantages. By keeping one of the equivalent disk allocations, we can reduce the complexity of search for good disk allocations under various criteria such as additive error and threshold. Probabilistic approaches to finding good declustering schemes is feasible using equivalent allocations.

REFERENCES

• 1: 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
• 2: 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]
• 3: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 4: Stefan Berchtold , Christian Böhm , Bernhard Braunmüller , Daniel A. Keim , Hans-Peter Kriegel, Fast parallel similarity search in multimedia databases, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.1-12, May 11-15, 1997, Tucson, Arizona, United States
• 5: 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
• 6: Declustering Using Golden Ratio Sequences, Proceedings of the 16th International Conference on Data Engineering, p.271, February 28-March 03, 2000
• 7: Chung-Min Chen , Christine T. Cheng, From discrepancy to declustering: near-optimal multidimensional declustering strategies for range queries, 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.543618]
• 8: Chung-Min Chen , Christine T. Cheng, Replication and retrieval strategies of multidimensional data on parallel disks, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956871]
• 9: 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]
• 10: C. Faloutsos , D. Metaxas, Declustering using error correcting codes, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.253-258, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73747]
• 11: H. Ferhatosmanoglu, Concentric Hyperspaces and Disk Allocation for Fast Parallel Range Searching, Proceedings of the 15th International Conference on Data Engineering, p.608, March 23-26, 1999
• 12: Hakan Ferhatosmanoǧlu , Ali Şaman Tosun , Aravind Ramachandran, Replicated declustering of spatial data, 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.1055577]
• 13: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
• 14: Shahram Ghandeharizadeh , David J. DeWitt, Hybrid-Range Partitioning Strategy: A New Declustering Strategy for Multiprocessor Database Machines, Proceedings of the 16th International Conference on Very Large Data Bases, p.481-492, August 13-16, 1990
• 15: Shahram Ghandeharizadeh , David J. DeWitt , Waheed Qureshi, A performance analysis of alternative multi-attribute declustering strategies, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.29-38, June 02-05, 1992, San Diego, California, United States
• 16: Jim Gray , Bob Horst , Mark Walker, Parity Striping of Disk Arrays: Low-Cost Reliable Storage with Acceptable Throughput, Proceedings of the 16th International Conference on Very Large Data Bases, p.148-161, August 13-16, 1990
• 17: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 18: 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
• 19: 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
• 20: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 21: Harold Shapiro. Introduction to the Theory of Numbers. John Wiley and Sons, 1983.
• 22: Optimal Parallel I/O Using Replication, Proceedings of the 2002 International Conference on Parallel Processing Workshops, p.506, August 18-21, 2002
• 23: Ali Şaman Tosun. Threshold based declustering in high dimensions. In DEXA 2005.
• 24: Ali Şaman Tosun, Replicated declustering for arbitrary queries, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus [doi>10.1145/967900.968054]
• 25: Ali Saman Tosun, Constrained Declustering, Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC'05) - Volume I, p.232-237, April 04-06, 2005 [doi>10.1109/ITCC.2005.112]
• 26: Ali Saman Tosun, Design Theoretic Approach to Replicated Declustering, Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC'05) - Volume I, p.226-231, April 04-06, 2005 [doi>10.1109/ITCC.2005.124]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management

General Terms:
Algorithms, Design

Keywords:
declustering, number theory, parallel I/O, range query