SDI: a swift tree structure for multi-dimensional data indexing in peer-to-peer networks

ABSTRACT

Efficient multi-dimensional data search has received much attention in centralized systems. However, its implementation in large-scale distributed systems is not a trivial job and remains to be a challenge. In this paper, SDI, a new succinct multi-dimensional balanced tree structure based on peer-to-peer technology, is presented. With SDI structure, the query efficiency can be bounded by O(log N). Compared with previous tree-based methods, SDI has extremely low maintenance cost. This is due to the carefully chosen finger links. Furthermore, new algorithms are designed for both point query and range query processing, which make SDI free from the root-bottleneck problem. Experimental results validate the efficiency and effectiveness of the proposed approach.

REFERENCES

• 1: Artur Andrzejak , Zhichen Xu, Scalable, Efficient Range Queries for Grid Information Services, Proceedings of the Second International Conference on Peer-to-Peer Computing, p.33, September 05-07, 2002
• 2: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, ACM SIGMOD Record, v.14 n.2, June 1984
• 3: Cristina Schmidt , Manish Parashar, Flexible Information Discovery in Decentralized Distributed Systems, Proceedings of the 12th IEEE International Symposium on High Performance Distributed Computing, p.226, June 22-24, 2003
• 4: Chunqiang Tang , Zhichen Xu , Sandhya Dwarkadas, Peer-to-peer information retrieval using self-organizing semantic overlay networks, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863976]
• 5: C. Zhang, A. Krishnamurthy, and R. Wang. Skipindex: Towards a scalable peer-to-peer index service for high-dimensional data. Technical Report Tr-703-04, Princeton University, 2004.
• 6: Elisa Bertino , C , Kian-Lee Tan , Beng Chin Ooi , Ron Sacks-Davis , Justin Zobel , Boris Shidlovsky, Indexing Techniques for Advanced Database Systems, Kluwer Academic Publishers, Norwell, MA, 1997
• 7: G.-H. Cha, X. Zhu, D. Petkovic, and C.-W. Chung. An efficient indexing method for nearest neighbor searches in high-dimensional image databases. IEEE Transactions on Multimedia, 4(1):76--87, 2002.
• 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: Jonathan K. Lawder , Peter J. H. King, Using Space-Filling Curves for Multi-dimensional Indexing, Proceedings of the 17th British National Conferenc on Databases: Advances in Databases, p.20-35, July 03-05, 2000
• 11: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 12: J. Lee, H. Lee, S. Kang, S. Choe, and J. Song. Ciss:an efficient object clustering framework for dht-based peer-to-peer applications. In DBISP2P, pages 215--229, 2004.
• 13: 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
• 14: O. D. Sahin , A. Gupta , D. Agrawal , A. El Abbadi, A Peer-to-peer Framework for Caching Range Queries, Proceedings of the 20th International Conference on Data Engineering, p.165, March 30-April 02, 2004
• 15: Paolo Ciaccia , Marco Patella , Pavel Zezula, M-tree: An Efficient Access Method for Similarity Search in Metric Spaces, Proceedings of the 23rd International Conference on Very Large Data Bases, p.426-435, August 25-29, 1997
• 16: Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998
• 17: Xin Li , Young Jin Kim , Ramesh Govindan , Wei Hong, Multi-dimensional range queries in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958500]
• 18: Y. Shu, K.-L. Tan, and A. Zhou. Adapting the content native space for load balanced indexing. In DBISP2P, pages 122--135, 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
      H.2.m Miscellaneous

General Terms:
Algorithms, Design, Experimentation

Keywords:
multi-dimensional data, peer-to-peer, point query, range query