Brief Announcement: Hashed Predecessor Patricia Trie - A Data Structure for Efficient Predecessor Queries in Peer-to-Peer Systems

S. Kniesburges, C. Scheideler, in: Proceedings of the 26th International Symposium on Distributed Computing (DISC), 2012, pp. 435–436.

Download
Restricted 626-Predecessor-Kniesburges_Scheideler.pdf 184.09 KB
Conference Paper
Author
Kniesburges, Sebastian; Scheideler, ChristianLibreCat
Abstract
The design of ecient search structures for peer-to-peer systems has attracted a lot of attention in recent years. In this announcement we address the problem of nding the predecessor in a key set and present an ecient data structure called hashed Predecessor Patricia trie. Our hashed Predecessor Patricia trie supports PredecessorSearch(x) and Insert(x) and Delete(x) in O(log log u) hash table accesses when u is the size of the universe of the keys. That is the costs only depend on u and not the size of the data structure. One feature of our approach is that it only uses the lookup interface of the hash table and therefore hash table accesses may be realized by any distributed hash table (DHT).
Publishing Year
Proceedings Title
Proceedings of the 26th International Symposium on Distributed Computing (DISC)
forms.conference.field.series_title_volume.label
LNCS
Page
435-436
LibreCat-ID
626

Cite this

Kniesburges S, Scheideler C. Brief Announcement: Hashed Predecessor Patricia Trie - A Data Structure for Efficient Predecessor Queries in Peer-to-Peer Systems. In: Proceedings of the 26th International Symposium on Distributed Computing (DISC). LNCS. ; 2012:435-436. doi:10.1007/978-3-642-33651-5_45
Kniesburges, S., & Scheideler, C. (2012). Brief Announcement: Hashed Predecessor Patricia Trie - A Data Structure for Efficient Predecessor Queries in Peer-to-Peer Systems. In Proceedings of the 26th International Symposium on Distributed Computing (DISC) (pp. 435–436). https://doi.org/10.1007/978-3-642-33651-5_45
@inproceedings{Kniesburges_Scheideler_2012, series={LNCS}, title={Brief Announcement: Hashed Predecessor Patricia Trie - A Data Structure for Efficient Predecessor Queries in Peer-to-Peer Systems}, DOI={10.1007/978-3-642-33651-5_45}, booktitle={Proceedings of the 26th International Symposium on Distributed Computing (DISC)}, author={Kniesburges, Sebastian and Scheideler, Christian}, year={2012}, pages={435–436}, collection={LNCS} }
Kniesburges, Sebastian, and Christian Scheideler. “Brief Announcement: Hashed Predecessor Patricia Trie - A Data Structure for Efficient Predecessor Queries in Peer-to-Peer Systems.” In Proceedings of the 26th International Symposium on Distributed Computing (DISC), 435–36. LNCS, 2012. https://doi.org/10.1007/978-3-642-33651-5_45.
S. Kniesburges and C. Scheideler, “Brief Announcement: Hashed Predecessor Patricia Trie - A Data Structure for Efficient Predecessor Queries in Peer-to-Peer Systems,” in Proceedings of the 26th International Symposium on Distributed Computing (DISC), 2012, pp. 435–436.
Kniesburges, Sebastian, and Christian Scheideler. “Brief Announcement: Hashed Predecessor Patricia Trie - A Data Structure for Efficient Predecessor Queries in Peer-to-Peer Systems.” Proceedings of the 26th International Symposium on Distributed Computing (DISC), 2012, pp. 435–36, doi:10.1007/978-3-642-33651-5_45.
Main File(s)
File Name
626-Predecessor-Kniesburges_Scheideler.pdf 184.09 KB
Access Level
Restricted Closed Access
Last Uploaded
2018-03-15T06:42:40Z


Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar