Please use this identifier to cite or link to this item:
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
System architecture
Issue Date: 2006
Citation: 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.
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
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.


checked on Nov 16, 2018

Page view(s)

checked on Sep 22, 2018

Google ScholarTM



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