NDLI: Supporting Multi-dimensional Range Query in HD Tree

Content Provider	IEEE Xplore Digital Library
Author	Yunfeng Gu Boukerche, A. Xun Ye Araujo, R.B.
Copyright Year	2010
Abstract	There are two basic concerns for supporting multi-dimensional range query in P2P overlay networks. The first is to preserve data locality in the process of data space partitioning, and the second is the maintenance of data locality among data items with an exponentially expanding rate and an exponentially extending rate. The first problem has been well addressed by using recursive decomposition schemes, such as Quad tree, K-d tree, Z-order, and Hilbert curve. While the second problem was recently identified by our novel data structure: HD Tree. This paper is a follow-up to our previous work in HD Tree. In this paper, we explore how data locality can be easily maintained, and how range query can be efficiently supported in HD Tree. This is done by introducing two basic routing strategies, hierarchical routing and distributed routing. Although hierarchical routing can be applied to any two nodes in the system, it generates high volume traffic towards nodes near the root, and has very limited options to cope with a node failure. On the other hand, distributed routing concerns source and destination pairs only at the same depth, but traffic load is bound to some nodes at two neighboring depths, and multiple options can be found to redirect a routing request. Because HD Tree supports multiple routes between any two nodes in the system, routing in HD Tree is very flexible, and can be designed for many purposes, like fault tolerance, or dynamic load balancing. Distributed Routing Oriented Combined Routing algorithm is one such routing strategies implemented so far. It is a hybrid algorithm combining advantages from both the hierarchical routing and the distributed routing. The experimental results show that the DROCR algorithm achieves considerable performance gain over the equivalent tree routing at the highest depth examined. In the experiment of supporting multi-dimensional range query, we employ the Z-order space filling curve over the HD Tree overlay layer. We are expecting that the performance of range query will vary proportionally with the change of range size, and reasonably with the increase of dimensionality.
Starting Page	71
Ending Page	78
File Size	423321
Page Count	8
File Format	PDF
ISBN	9781424486519
ISSN	15506525
DOI	10.1109/DS-RT.2010.17
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2010-10-17
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Routing High definition video Peer to peer computing Pattern matching Distributed databases Algorithm design and analysis Data structures DDM HD Tree peer-to-peer P2P overlay data structures distributed associative searching range query multi-dimensional data space partitioning
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Supporting Multi-dimensional Range Query in HD Tree

Error-Resilient Routing for Supporting Multi-dimensional Range Query in HD Tree

Error-Resilient Routing for Supporting Multi-dimensional Range Query in HD Tree

Hierarchically distributed tree

Binary Search Tree: An Efficient Overlay Structure to Support Range Query

A grid structure support multi-dimensional range query for P2P networks

Supporting Multi-dimensional Range Queries in Peer-to-Peer Systems (2005)

A scalable index architecture for supporting multidimensional range queries in peer-to-peer networks (2006)

Towards Robust Routing in HD Tree

Supporting Multi-dimensional Range Query in HD Tree

Similar Documents

Supporting Multi-dimensional Range Query in HD Tree

Error-Resilient Routing for Supporting Multi-dimensional Range Query in HD Tree

Error-Resilient Routing for Supporting Multi-dimensional Range Query in HD Tree

Hierarchically distributed tree

Binary Search Tree: An Efficient Overlay Structure to Support Range Query

A grid structure support multi-dimensional range query for P2P networks

Supporting Multi-dimensional Range Queries in Peer-to-Peer Systems (2005)

A scalable index architecture for supporting multidimensional range queries in peer-to-peer networks (2006)

Towards Robust Routing in HD Tree

Supporting Multi-dimensional Range Query in HD Tree