Replicated declustering of spatial data

ABSTRACT

The problem of disk declustering is to distribute data among multiple disks to reduce query response times through parallel I/O. A strictly optimal declustering technique is one that achieves optimal parallel I/O for all possible queries. In this paper, we focus on techniques that are optimized for spatial range queries. Current declustering techniques, which have single copies of the data, have been shown to be suboptimal for range queries. The lower bound on extra disk accesses is proved to be Ω(log N) for N disks even in the restricted case of an N-by-N grid, and all current approaches have been trying to achieve this bound. Replication is a well-known and effective solution for several problems in databases, especially for availability and load balancing. In this paper, we explore the idea of replication in the context of declustering and propose a framework where strictly optimal parallel I/O is achievable using a small amount of replication. We provide some theoretical foundations for replicated declustering, e.g., a bound for number of copies for strict optimality on any number of disks, and propose a class of replicated declustering schemes, periodic allocations, which are shown to be strictly optimal. The results for optimal disk allocation are extended for larger number of disks by increasing replication. Our techniques and results are valid for any arbitrary a-by-b grids, and any declustering scheme can be further improved using our replication framework. Using the framework, we perform experiments to identify a strictly optimal disk access schedule for any given arbitrary range query. In addition to the theoretical bounds, we compare the proposed replication based scheme to other existing techniques by performing experiments on real datasets.

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: R. Bose and S. Shrikhande. On the construction of sets of mutually orthogonal latin squares and the falsity of a conjecture of euler. Euler. Trans. Am. Math. Sm., 95:191--209, 1960.
• 7: Declustering Using Golden Ratio Sequences, Proceedings of the 16th International Conference on Data Engineering, p.271, February 28-March 03, 2000
• 8: 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]
• 9: Ling Tony Chen , Doron Rotem, Optimal response time retrieval of replicated data (extended abstract), Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.36-44, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182596]
• 10: Ming-Syan Chen , Hui-I Hsiao , Chung-Sheng Li , Philip S. Yu, Using rotational mirrored declustering for replica placement in a disk-array-based video server, Proceedings of the third ACM international conference on Multimedia, p.121-130, November 05-09, 1995, San Francisco, California, United States [doi>10.1145/217279.215257]
• 11: Paolo Ciaccia , Arianna Veronesi, Dynamic Declustering Methods for Parallel Grid Files, Proceedings of the Third International ACPC Conference with Special Emphasis on Parallel Databases and Parallel I/O: Parallel Computation, p.110-123, September 23-25, 1996
• 12: 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]
• 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: 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]
• 15: 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
• 16: H. Ferhatosmanoglu, A. S. Tosun, and A. Ramachandran. Replicated declustering of spatial data: A technical report. http://www.cse.ohiostate.edu/~hakan/repdec-report.pdf, 2003.
• 17: 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]
• 18: Shahram Ghandeharizadeh , David J. DeWitt, Hybrid-range partitioning strategy: a new declustering strategy for multiprocessor databases machines, Proceedings of the sixteenth international conference on Very large databases, p.481-492, September 1990, Brisbane, Australia
• 19: 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
• 20: L. Golubchik , S. Khanna , S. Khuller , R. Thurimella , A. Zhu, Approximation algorithms for data placement on parallel disks, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.223-232, January 09-11, 2000, San Francisco, California, United States
• 21: Jim Gray , Bob Horst , Mark Walker, Parity striping of disc arrays: low-cost reliable storage with acceptable throughput, Proceedings of the sixteenth international conference on Very large databases, p.148-161, September 1990, Brisbane, Australia
• 22: 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
• 23: Yu-long Lo , Kien A. Hua , Honesty C. Young, A General Multidimensional Data Allocation Method for Multicomputer Database Systems, Proceedings of the 8th International Conference on Database and Expert Systems Applications, p.357-366, September 01-05, 1997
• 24: 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
• 25: 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
• 26: 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
• 27: R. Muntz, J. Santos, and S. Berson. A parallel disk storage system for real-time multimedia applications. International Journal of Intelligent Systems, Special Issue on Multimedia Computing System, 13(12):1137--74, December 1998.
• 28: 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
• 29: Sunil Prabhakar , Divyakant Agrawal , Amr El Abbadi, Efficient disk allocation for fast similarity searching, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.78-87, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277651.277674]
• 30: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 31: Peter Sanders , Sebastian Egner , Jan Korst, Fast concurrent access to parallel disks, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.849-858, January 09-11, 2000, San Francisco, California, United States
• 32: J. Santos and R. Muntz. Design of the RIO (randomized I/O) storage server. Technical Report TR970032, UCLA Computer Science Department, 1997. http://mml.cs.ucla.edu/publications/papers/cstech970032.ps.
• 33: Seagate. Seagate specifications. http://www.seagate.com/pdf/datasheets/, December 2003.
• 34: 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
• 35: 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]
• 36: Optimal Parallel I/O Using Replication, Proceedings of the 2002 International Conference on Parallel Processing Workshops, p.506, August 18-21, 2002