Please use this identifier to cite or link to this item: https://doi.org/10.1145/1142473.1142475
Title: Speeding up search in peer-to-peer networks with a multi-way tree structure
Authors: Jagadish, H.V.
Ooi, B.C. 
Tan, K.-L. 
Vu, Q.H.
Zhang, R.
Keywords: Multi-way tree structure
Peer-to-peer
System architecture
Issue Date: 2006
Source: Jagadish, H.V.,Ooi, B.C.,Tan, K.-L.,Vu, Q.H.,Zhang, R. (2006). Speeding up search in peer-to-peer networks with a multi-way tree structure. Proceedings of the ACM SIGMOD International Conference on Management of Data : 1-12. ScholarBank@NUS Repository. https://doi.org/10.1145/1142473.1142475
Abstract: Peer-to-Peer systems have recently become a popular means to share resources. Effective search is a critical requirement in such systems, and a number of distributed search structures have been proposed in the literature. Most of these structures provide "log time search" capability, where the logarithm is taken base 2. That is, in a system with N nodes, the cost of the search is O(log2N).In database systems, the importance of large fanout index structures has been well recognized. In P2P search too, the cost could be reduced considerably if this logarithm were taken to a larger base. In this paper, we propose a multi-way tree search structure, which reduces the cost of search to O(logmN), where m is the fanout. The penalty paid is a larger update cost, but we show how to keep this penalty to be no worse than linear in m. We experimentally explore this tradeoff between search and update cost as a function of m, and suggest how to find a good trade-off point.The multi-way tree structure we propose, BATON*, is derived from the BATON structure that has recently been suggested. In addition to multi-way fanout, BATON*also adds support for multi-attribute queries to BATON. Copyright 2006 ACM.
Source Title: Proceedings of the ACM SIGMOD International Conference on Management of Data
URI: http://scholarbank.nus.edu.sg/handle/10635/42011
ISBN: 1595934340
ISSN: 07308078
DOI: 10.1145/1142473.1142475
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

59
checked on Dec 11, 2017

Page view(s)

44
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.