D-AVTree: DHT-Based Search System to Support Scalable Multi-Attribute Queries

Hoaison NGUYEN; Yasuo TAN; Yoichi SHINODA

doi:10.1587/transcom.E97.B.1898

D-AVTree: DHT-Based Search System to Support Scalable Multi-Attribute Queries

Hoaison NGUYEN, Yasuo TAN, Yoichi SHINODA

Full Text Views

0

Share
Cite this

Summary :

At present, vast numbers of information resources are available on the Internet. However, one emerging issue is how to search and exploit these information resources in an efficient and flexible manner with high scalability. In this study, we focused our attention on the design of a distributed hash table (DHT)-based search system that supports efficient scalable multi-attribute queries of information resources in a distributed manner. Our proposed system, named D-AVTree, is built on top of a ring-based DHT, which partitions a one-dimensional key space across nodes in the system. It utilizes a descriptive naming scheme, which names each resource using an attribute-value (AV) tree, and the resource names are mapped to d-bit keys in order to distribute the resource information to responsible nodes based on a DHT routing algorithm. Our mapping scheme maps each AV branch of a resource name to a d-bit key where AV branches that share a subsequence of AV pairs are mapped to a continuous portion of the key space. Therefore, our mapping scheme ensures that the number of resources distributed to a node is small and it facilitates efficient multi-attribute queries by querying only a small number of nodes. Further, the scheme has good compatibility with key-based load balancing algorithms for DHT-based networks. Our system can achieve both efficiency and a good degree of load balancing even when the distribution of AV pairs in the resource names is skewed. Our simulation results demonstrated the efficiency of our solution in terms of the distribution cost, query hit ratio, and the degree of load balancing compared with conventional approaches.

Publication: IEICE TRANSACTIONS on Communications Vol.E97-B No.9 pp.1898-1909

Publication Date: 2014/09/01

Publicized

Online ISSN: 1745-1345

DOI: 10.1587/transcom.E97.B.1898

Type of Manuscript: PAPER

Category: Network

Authors

Hoaison NGUYEN
  VNU-University of Engineering and Technology,Japan Advanced Institute of Science and Technology
Yasuo TAN
  Japan Advanced Institute of Science and Technology
Yoichi SHINODA
  Japan Advanced Institute of Science and Technology

Keyword

attribute-value tree, distributed hash table (DHT), load balancing, multi-attribute query

Cite this

Copy

Hoaison NGUYEN, Yasuo TAN, Yoichi SHINODA, "D-AVTree: DHT-Based Search System to Support Scalable Multi-Attribute Queries" in IEICE TRANSACTIONS on Communications, vol. E97-B, no. 9, pp. 1898-1909, September 2014, doi: 10.1587/transcom.E97.B.1898.
Abstract: At present, vast numbers of information resources are available on the Internet. However, one emerging issue is how to search and exploit these information resources in an efficient and flexible manner with high scalability. In this study, we focused our attention on the design of a distributed hash table (DHT)-based search system that supports efficient scalable multi-attribute queries of information resources in a distributed manner. Our proposed system, named D-AVTree, is built on top of a ring-based DHT, which partitions a one-dimensional key space across nodes in the system. It utilizes a descriptive naming scheme, which names each resource using an attribute-value (AV) tree, and the resource names are mapped to d-bit keys in order to distribute the resource information to responsible nodes based on a DHT routing algorithm. Our mapping scheme maps each AV branch of a resource name to a d-bit key where AV branches that share a subsequence of AV pairs are mapped to a continuous portion of the key space. Therefore, our mapping scheme ensures that the number of resources distributed to a node is small and it facilitates efficient multi-attribute queries by querying only a small number of nodes. Further, the scheme has good compatibility with key-based load balancing algorithms for DHT-based networks. Our system can achieve both efficiency and a good degree of load balancing even when the distribution of AV pairs in the resource names is skewed. Our simulation results demonstrated the efficiency of our solution in terms of the distribution cost, query hit ratio, and the degree of load balancing compared with conventional approaches.
URL: https://globals.ieice.org/en_transactions/communications/10.1587/transcom.E97.B.1898/_p

Copy

@ARTICLE{e97-b_9_1898,
author={Hoaison NGUYEN, Yasuo TAN, Yoichi SHINODA, },
journal={IEICE TRANSACTIONS on Communications},
title={D-AVTree: DHT-Based Search System to Support Scalable Multi-Attribute Queries},
year={2014},
volume={E97-B},
number={9},
pages={1898-1909},
abstract={At present, vast numbers of information resources are available on the Internet. However, one emerging issue is how to search and exploit these information resources in an efficient and flexible manner with high scalability. In this study, we focused our attention on the design of a distributed hash table (DHT)-based search system that supports efficient scalable multi-attribute queries of information resources in a distributed manner. Our proposed system, named D-AVTree, is built on top of a ring-based DHT, which partitions a one-dimensional key space across nodes in the system. It utilizes a descriptive naming scheme, which names each resource using an attribute-value (AV) tree, and the resource names are mapped to d-bit keys in order to distribute the resource information to responsible nodes based on a DHT routing algorithm. Our mapping scheme maps each AV branch of a resource name to a d-bit key where AV branches that share a subsequence of AV pairs are mapped to a continuous portion of the key space. Therefore, our mapping scheme ensures that the number of resources distributed to a node is small and it facilitates efficient multi-attribute queries by querying only a small number of nodes. Further, the scheme has good compatibility with key-based load balancing algorithms for DHT-based networks. Our system can achieve both efficiency and a good degree of load balancing even when the distribution of AV pairs in the resource names is skewed. Our simulation results demonstrated the efficiency of our solution in terms of the distribution cost, query hit ratio, and the degree of load balancing compared with conventional approaches.},
keywords={},
doi={10.1587/transcom.E97.B.1898},
ISSN={1745-1345},
month={September},}

Copy

TY - JOUR
TI - D-AVTree: DHT-Based Search System to Support Scalable Multi-Attribute Queries
T2 - IEICE TRANSACTIONS on Communications
SP - 1898
EP - 1909
AU - Hoaison NGUYEN
AU - Yasuo TAN
AU - Yoichi SHINODA
PY - 2014
DO - 10.1587/transcom.E97.B.1898
JO - IEICE TRANSACTIONS on Communications
SN - 1745-1345
VL - E97-B
IS - 9
JA - IEICE TRANSACTIONS on Communications
Y1 - September 2014
AB - At present, vast numbers of information resources are available on the Internet. However, one emerging issue is how to search and exploit these information resources in an efficient and flexible manner with high scalability. In this study, we focused our attention on the design of a distributed hash table (DHT)-based search system that supports efficient scalable multi-attribute queries of information resources in a distributed manner. Our proposed system, named D-AVTree, is built on top of a ring-based DHT, which partitions a one-dimensional key space across nodes in the system. It utilizes a descriptive naming scheme, which names each resource using an attribute-value (AV) tree, and the resource names are mapped to d-bit keys in order to distribute the resource information to responsible nodes based on a DHT routing algorithm. Our mapping scheme maps each AV branch of a resource name to a d-bit key where AV branches that share a subsequence of AV pairs are mapped to a continuous portion of the key space. Therefore, our mapping scheme ensures that the number of resources distributed to a node is small and it facilitates efficient multi-attribute queries by querying only a small number of nodes. Further, the scheme has good compatibility with key-based load balancing algorithms for DHT-based networks. Our system can achieve both efficiency and a good degree of load balancing even when the distribution of AV pairs in the resource names is skewed. Our simulation results demonstrated the efficiency of our solution in terms of the distribution cost, query hit ratio, and the degree of load balancing compared with conventional approaches.
ER -