A Partial Match Retrieval Method on P2P Networks using Skip Graph and Suffix Array
-
- BANNO Ryohei
- Graduate School of Information Science and Technology, Hokkaido University (Presently with NTT Network Innovation Laboratories, Nippon Telegraph and Telephone Corporation)
-
- SATO Haruhiko
- Graduate School of Information Science and Technology, Hokkaido University
-
- OYAMA Satoshi
- Graduate School of Information Science and Technology, Hokkaido University
-
- KURIHARA Masahito
- Graduate School of Information Science and Technology, Hokkaido University
Bibliographic Information
- Other Title
-
- P2Pネットワークにおけるスキップグラフと接尾辞配列を用いた部分一致検索手法
Abstract
Structured overlay networks, known for the application to distributed hash tables, provide searching for nodes without any centralized indexes in large scale networks. However it is hard to handle complex queries represented by partial match queries. There are past studies trying to realize partial match retrieval on structured overlay networks such as dividing keys into n-grams. However, those studies have serious problems e.g. affected by the bias of the n-gram frequency. In this paper, we propose a new partial match retrieval method which combines Skip Graph, a structured overlay network supporting range queries, and Suffix Array, a useful data structure in string manipulation. We report on the results of simulation experiments and describe that the proposed method can handle partial match queries within O(log N) overlay routing hops for a network of N nodes. We also show that the proposed method is free from various problems including load imbalance among nodes.
Journal
-
- Computer Software
-
Computer Software 29 (3), 3_164-3_180, 2012
Japan Society for Software Science and Technology
- Tweet
Details 詳細情報について
-
- CRID
- 1390001204738560000
-
- NII Article ID
- 130004549275
-
- ISSN
- 02896540
-
- Text Lang
- ja
-
- Data Source
-
- JaLC
- CiNii Articles
-
- Abstract License Flag
- Disallowed