Article

BATON: a balanced tree structure for peer-to-peer networks

Authors:

H. V. Jagadish,

Quang Hieu VuAuthors Info & Claims

VLDB '05: Proceedings of the 31st international conference on Very large data bases

Pages 661 - 672

Published: 30 August 2005 Publication History

Abstract

We propose a balanced tree structure overlay on a peer-to-peer network capable of supporting both exact queries and range queries efficiently. In spite of the tree structure causing distinctions to be made between nodes at different levels in the tree, we show that the load at each node is approximately equal. In spite of the tree structure providing precisely one path between any pair of nodes, we show that sideways routing tables maintained at each node provide sufficient fault tolerance to permit efficient repair. Specifically, in a network with N nodes, we guarantee that both exact queries and range queries can be answered in O(log N) steps and also that update operations (to both data and network) have an amortized cost of O(log N). An experimental assessment validates the practicality of our proposal.

References

[1]

K. Aberer. P-Grid: A self-organizing access structure for p2p information systems. In Proceedings of the 6th International Conference on Cooperative Information Systems, 2001.]]

Digital Library

[2]

J. Aspnes and G. Shah. Skip graphs. In Proceeding of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 384--393, 2003.]]

Digital Library

[3]

A. Crainiceanu, P. Linga, J. Gehrke, and J. Shanmugasundaram. Querying peer-to-peer networks using P-Trees. In WebDB '04: Proceedings of the 7th International Workshop on the Web and Databases, pages 25--30, 2004.]]

Digital Library

[4]

P. Ganesan, M. Bawa, and H. Garcia-Molina. Online balancing of range-partitioned data with applications to peer-to-peer systems. In Proceedings of the 30th VLDB Conference, 2004.]]

[5]

A. Gupta, D. Agrawal, and A. El Abbadi. Approximate range selection queries in peer-to-peer systems. In Proceedings of the First Biennial Conference on Innovative Data Systems Research, 2003.]]

[6]

N. J. A. Harvey, M. B. Jones, S. Saroiu, M. Theimer, and A. Wolman. Skipnet: A scalable overlay network with practical locality properties. In USENIX Symposium on Internet Technologies and Systems, 2003.]]

Digital Library

[7]

D. Karger, F. Kaashoek, I. Stoica, R. Morris, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In Proceedings of the 2001 ACM SIGCOMM Conference, pages 149--160, 2001.]]

Digital Library

[8]

D. E. Knuth. The Art of Computer Programming, volume 3. Addison-Wesley Professional, 1998.]]

Digital Library

[9]

M. L. Lee, M. Kitsuregawa, B. C. Ooi, K.-L. Tan, and A. Mondal. Towards self-tuning data placement in parallel database systems. In Proceedings of the 2000 ACM SIGMOD International Conference on the Management of Data, pages 225--236, 2000.]]

Digital Library

[10]

T. J. Lehman and M. J. Carey. A study of index structures for main memory database management systems. In Proceedings of the 12th VLDB Conference, pages 294--303, 1986.]]

Digital Library

[11]

C. Y. Liau, W. S. Ng, Y. Shu, K.-L. Tan, and S. Bressan. Efficient range queries and fast lookup services for scalable p2p networks. In Proceedings of 2nd International Workshop On Databases, Information Systems and Peer-to-Peer Computing, pages 78--92, 2004.]]

[12]

W. Litwin, M.-A. Neimat, and D. A. Schneider. Rp*: A family of order preserving scalable distributed data structures. In Proceedings of the 20th VLDB Conference, 1994.]]

Digital Library

[13]

S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker. A scalable contentaddressable network. In Proceedings of the 2001 ACM Annual Conference of the Special Interest Group on Data Communication, pages 161--172, 2001.]]

Digital Library

[14]

A. Rowstron and P. Druschel. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In Proceedings of the 18th IFIP/ACM International Conference of Distributed Systems Platforms, pages 329--350, 2001.]]

Digital Library

[15]

O. D. Sahin, A. Gupta, D. Agrawal, and A. El Abbadi. A peer-to-peer framework for caching range queries. In Proceedings of the 20th International Conference on Data Engineering, 2004.]]

Digital Library

[16]

B. Y. Zhao, J. D. Kubiatowicz, and A. D. Joseph. Tapestry: An infrastructure for fault-tolerant wide-area location and routing. Technical Report CSD-01-1141, Univ. California, Berkeley, CA, Apr. 2001.]]

Digital Library

Cited By

Chen GVo HWu SOoi BÖzsu M(2020)A Framework for supporting DBMS-like indexes in the cloudProceedings of the VLDB Endowment10.14778/3402707.34027114:11(702-713)Online publication date: 3-Jun-2020
https://dl.acm.org/doi/10.14778/3402707.3402711
(2019)Improving multidimensional point query search using multi-way peer-to-peer tree networkInternational Journal of Information and Communication Technology10.5555/3319273.331927414:2(125-138)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.5555/3319273.3319274
Zhou MZhang RQian WZhou A(2018)Distribution-free data density estimation in large-scale networksFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-016-6194-y12:6(1220-1240)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.1007/s11704-016-6194-y
Show More Cited By

Recommendations

Dynamics of hot-potato routing in IP networks

Despite the architectural separation between intradomain and interdomain routing in the Internet, intradomain protocols do influence the path-selection process in the Border Gateway Protocol (BGP). When choosing between multiple equally-good BGP routes, ...
Dynamics of hot-potato routing in IP networks
SIGMETRICS '04/Performance '04: Proceedings of the joint international conference on Measurement and modeling of computer systems

Despite the architectural separation between intradomain and interdomain routing in the Internet, intradomain protocols do influence the path-selection process in the Border Gateway Protocol (BGP). When choosing between multiple equally-good BGP routes, ...
Designing optimal iBGP route-reflection topologies
NETWORKING'08: Proceedings of the 7th international IFIP-TC6 networking conference on AdHoc and sensor networks, wireless networks, next generation internet

The Border Gateway Protocol (BGP) is used today by all Autonomous Systems (AS) in the Internet. Inside each AS, iBGP sessions distribute the external routes among the routers. In large ASs, relying on a full-mesh of iBGP sessions between routers is not ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image DL Hosted proceedings

VLDB '05: Proceedings of the 31st international conference on Very large data bases

August 2005

1392 pages

ISBN:1595931546

General Chair:
Kjell Bratbergsengen
Norwegian University of Science & Technology, Trondheim, Norway

Publisher

VLDB Endowment

Publication History

Published: 30 August 2005

Qualifiers

Article

Conference

ICMI05

ICMI05: Seventh International Conference on Multimodal Interfaces 2005

August 30 - September 2, 2005

Trondheim, Norway

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

80
Total Citations
View Citations
1,001
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen GVo HWu SOoi BÖzsu M(2020)A Framework for supporting DBMS-like indexes in the cloudProceedings of the VLDB Endowment10.14778/3402707.34027114:11(702-713)Online publication date: 3-Jun-2020
https://dl.acm.org/doi/10.14778/3402707.3402711
(2019)Improving multidimensional point query search using multi-way peer-to-peer tree networkInternational Journal of Information and Communication Technology10.5555/3319273.331927414:2(125-138)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.5555/3319273.3319274
Zhou MZhang RQian WZhou A(2018)Distribution-free data density estimation in large-scale networksFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-016-6194-y12:6(1220-1240)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.1007/s11704-016-6194-y
Kargar SMohammad-Khanli L(2017)FractalJournal of Network and Computer Applications10.1016/j.jnca.2017.03.02187:C(147-168)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1016/j.jnca.2017.03.021
Zhu YXu QShi HSamsudin J(2017)An efficient distributed search solution for federated cloudDistributed and Parallel Databases10.1007/s10619-017-7201-535:3-4(411-433)Online publication date: 1-Dec-2017
https://dl.acm.org/doi/10.1007/s10619-017-7201-5
Kaur RSangal AKumar K(2016)A Persistent Structured Hierarchical Overlay Network to Counter Intentional Churn AttackJournal of Computer Networks and Communications10.1155/2016/51914052016(4)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1155/2016/5191405
Liao JYang DLi TQi QWang JSun H(2016)Fusion feature for LSH-based image retrieval in a cloud datacenterMultimedia Tools and Applications10.1007/s11042-015-2892-y75:23(15405-15427)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1007/s11042-015-2892-y
Sioutas SSourla ETsichlas KZaroliagis C(2015)ART$$^+$$+Revised Selected Papers of the First International Workshop on Algorithmic Aspects of Cloud Computing - Volume 951110.1007/978-3-319-29919-8_10(126-137)Online publication date: 14-Sep-2015
https://dl.acm.org/doi/10.1007/978-3-319-29919-8_10
Xiang WTan GReed DSun XFoster I(2014)Elastic MapReduce executionProceedings of the 14th IEEE/ACM International Symposium on Cluster, Cloud, and Grid Computing10.1109/CCGrid.2014.14(216-225)Online publication date: 26-May-2014
https://dl.acm.org/doi/10.1109/CCGrid.2014.14
Bressan SChan CHsu WLee MLing TOoi BTan KTung A(2013)Database research at the National University of SingaporeACM SIGMOD Record10.1145/2503792.250380342:2(46-51)Online publication date: 16-Jul-2013
https://dl.acm.org/doi/10.1145/2503792.2503803
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents