Dynamic storage balancing in a distributed spatial index

ABSTRACT

We propose a general framework to index very large datasets of spatial data in a distributed system. Our proposal is built on the recently proposed Scalable Distributed Rtree (SD-Rtree) [4] and addresses specifically the server allocation problem. In SD-Rtree, a new server is assigned to the network whenever a split of a full node is required. We describe a more flexible allocation protocol which copes with a temporary shortage of storage resources. Our algorithm is especially based on k-NN query processing we introduce as well. We analyze the cost of this protocol, describe its features, and propose practical hints to use it. We also present experiments validating our approach.

REFERENCES

• 1: Lars Arge , David Eppstein , Michael T. Goodrich, Skip-webs: efficient distributed data structures for multi-dimensional data sets, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073827]
• 2: Adina Crainiceanu , Prakash Linga , Johannes Gehrke , Jayavel Shanmugasundaram, Querying peer-to-peer networks using P-trees, Proceedings of the 7th International Workshop on the Web and Databases: colocated with ACM SIGMOD/PODS 2004, June 17-18, 2004, Paris, France [doi>10.1145/1017074.1017082]
• 3: Robert Devine, Design and Implementation of DDH: A Distributed Dynamic Hashing Algorithm, Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, p.101-114, October 13-15, 1993
• 4: C. du Mouza, W. Litwin, and P. Rigaux. SD-Rtre: A Scalable Distributed Rtree. In ICDE, pages 296--305, 2007.
• 5: 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]
• 6: U. C. B. Geography Division. Tiger/Line files, 2007. URL:http://www.census.gov/geo/www/tiger/.
• 7: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, ACM SIGMOD Record, v.14 n.2, June 1984
• 8: H. V. Jagadish , Beng Chin Ooi , Quang Hieu Vu, BATON: a balanced tree structure for peer-to-peer networks, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 9: H. V. Jagadish , Beng Chin Ooi , Quang Hieu Vu , Rong Zhang , Aoying Zhou, VBI-Tree: A Peer-to-Peer Framework for Supporting Multi-Dimensional Indexing Schemes, Proceedings of the 22nd International Conference on Data Engineering, p.34, April 03-07, 2006 [doi>10.1109/ICDE.2006.169]
• 10: J. S. Karlsson. hQT*: A Scalable Distributed Data Structure for High-Performance Spatial Accesses. In FODO, 1998.
• 11: V. Kriakov, A. Delis, and G. Kollios. Management of Highly Dynamic Multidimensional Data in a Cluster of Workstations. In EDBT, pages 748--764, 2004.
• 12: Witold Litwin , Marie-Anna Neimat , Donovan A. Schneider, LH*—a scalable, distributed data structure, ACM Transactions on Database Systems (TODS), v.21 n.4, p.480-525, Dec. 1996 [doi>10.1145/236711.236713]
• 13: Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, ACM SIGMOD Record, v.24 n.2, p.71-79, May 1995
• 14: Hanan Samet, Foundations of Multidimensional and Metric Data Structures (The Morgan Kaufmann Series in Computer Graphics and Geometric Modeling), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 15: Yannis Theodoridis , Jefferson R. O. Silva , Mario A. Nascimento, On the Generation of Spatiotemporal Datasets, Proceedings of the 6th International Symposium on Advances in Spatial Databases, p.147-164, July 20-23, 1999

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

General Terms:
Performance

Keywords:
distributed index, kNN-query, storage balancing