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|
|Keywords:||Multi-way tree structure|
|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|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Dec 11, 2017
checked on Dec 9, 2017
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.