Article

Brief announcement: prefix hash tree

Authors:

Sriram Ramabhadran,

Sylvia Ratnasamy,

Joseph M. Hellerstein,

Scott ShenkerAuthors Info & Claims

PODC '04: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing

Page 368

https://doi.org/10.1145/1011767.1011823

Published: 25 July 2004 Publication History

Get Access

Abstract

This paper describes the Prefix Hash Tree, a distributed data structure that enables range queries over Distributed Hash Tables.

References

[1]

S. Ratnasamy P. Francis M. Handley R. Karp and S. Shenker, A Scalable Content Addressable Network, In ACM SIGCOMM 2001.

Digital Library

Google Scholar

[2]

M. Ruhl and D. Karger, Simple and Efficient Load Balancing Algorithms for Peer-to-Peer Systems, In ACM SPAA 2004.

Digital Library

Google Scholar

[3]

J. Aspnes and G. Shah, Skip Graphs In ACM-SIAM SODA 2003.

Digital Library

Google Scholar

[4]

P. Yalagandula and J. Browne, UT CS Tech. Report TR-04-18.

Google Scholar

Cited By

View all

Zaarour TBhattacharya ACurry E(2022)OpenPubSub: Supporting Large Semantic Content Spaces in Peer-to-Peer Publish/Subscribe Systems for the Internet of Multimedia ThingsIEEE Internet of Things Journal10.1109/JIOT.2022.31580889:18(17640-17659)Online publication date: 15-Sep-2022
https://doi.org/10.1109/JIOT.2022.3158088
Masinde NKhitman LDlikman IGraffi K(2020)Systematic Evaluation of LibreSocial—A Peer-to-Peer Framework for Online Social NetworksFuture Internet10.3390/fi1209014012:9(140)Online publication date: 20-Aug-2020
https://doi.org/10.3390/fi12090140
Freitag MBandle MSchmidt TKemper ANeumann T(2020)Adopting worst-case optimal joins in relational database systemsProceedings of the VLDB Endowment10.14778/3407790.340779713:12(1891-1904)Online publication date: 14-Sep-2020
https://dl.acm.org/doi/10.14778/3407790.3407797
Show More Cited By

Recommendations

Range queries on uncertain data

Given a set P of n uncertain points on the real line, each represented by its one-dimensional probability density function, we consider the problem of building data structures on P to answer range queries of the following three types for any query ...
Dynamic range majority data structures

Given a set P of n coloured points on the real line, we study the problem of answering range α-majority (or "heavy hitter") queries on P . More specifically, for a query range Q , we want to return each colour that is assigned to more than an α-fraction ...
Brief announcement: hashed predecessor patricia trie - a data structure for efficient predecessor queries in peer-to-peer systems
DISC'12: Proceedings of the 26th international conference on Distributed Computing

The design of efficient search structures for peer-to-peer systems has attracted a lot of attention in recent years. In this announcement we address the problem of finding the predecessor in a key set and present an efficient data structure called ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODC '04: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing

July 2004

422 pages

ISBN:1581138024

DOI:10.1145/1011767

General Chair:
Soma Chaudhuri
Iowa State University
,
Program Chair:
Shay Kutten
Technion

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 July 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PODC04

Sponsor:

PODC04: Principles of Distributed Computing 2004

July 25 - 28, 2004

Newfoundland, St. John's, Canada

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

83
Total Citations
View Citations
812
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)4

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zaarour TBhattacharya ACurry E(2022)OpenPubSub: Supporting Large Semantic Content Spaces in Peer-to-Peer Publish/Subscribe Systems for the Internet of Multimedia ThingsIEEE Internet of Things Journal10.1109/JIOT.2022.31580889:18(17640-17659)Online publication date: 15-Sep-2022
https://doi.org/10.1109/JIOT.2022.3158088
Masinde NKhitman LDlikman IGraffi K(2020)Systematic Evaluation of LibreSocial—A Peer-to-Peer Framework for Online Social NetworksFuture Internet10.3390/fi1209014012:9(140)Online publication date: 20-Aug-2020
https://doi.org/10.3390/fi12090140
Freitag MBandle MSchmidt TKemper ANeumann T(2020)Adopting worst-case optimal joins in relational database systemsProceedings of the VLDB Endowment10.14778/3407790.340779713:12(1891-1904)Online publication date: 14-Sep-2020
https://dl.acm.org/doi/10.14778/3407790.3407797
Graffi KMasinde N(2020)LibreSocial: A peer‐to‐peer framework for online social networksConcurrency and Computation: Practice and Experience10.1002/cpe.615033:8Online publication date: 13-Dec-2020
https://doi.org/10.1002/cpe.6150
Papadopoulos ASioutas SZaroliagis CZacharatos N(2019)Efficient Distributed Range Query Processing in Apache Spark2019 19th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGRID)10.1109/CCGRID.2019.00073(569-575)Online publication date: May-2019
https://doi.org/10.1109/CCGRID.2019.00073
Zhang WTang HByna SChen YEvripidou SStenström PO'Boyle M(2018)DARTProceedings of the 27th International Conference on Parallel Architectures and Compilation Techniques10.1145/3243176.3243207(1-12)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1145/3243176.3243207
Fathy YBarnaghi PTafazolli R(2018)Large-Scale Indexing, Discovery, and Ranking for the Internet of Things (IoT)ACM Computing Surveys10.1145/315452551:2(1-53)Online publication date: 12-Mar-2018
https://dl.acm.org/doi/10.1145/3154525
Ngom BMakpangou M(2017)Summary prefix tree: An over DHT indexing data structure for efficient superset search2017 IEEE 16th International Symposium on Network Computing and Applications (NCA)10.1109/NCA.2017.8171372(1-5)Online publication date: Oct-2017
https://doi.org/10.1109/NCA.2017.8171372
Hidalgo NArantes LSens PBonnaire X(2016)ECHOJournal of Parallel and Distributed Computing10.1016/j.jpdc.2015.10.00788:C(31-45)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1016/j.jpdc.2015.10.007
Yuan HCrowley PBrebner GBachmutsky ADas C(2015)Reliably Scalable Name Prefix LookupProceedings of the Eleventh ACM/IEEE Symposium on Architectures for networking and communications systems10.5555/2772722.2772739(111-121)Online publication date: 7-May-2015
https://dl.acm.org/doi/10.5555/2772722.2772739
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.

Cited By

Recommendations

Range queries on uncertain data

Dynamic range majority data structures

Brief announcement: hashed predecessor patricia trie - a data structure for efficient predecessor queries in peer-to-peer systems