×

zbMATH — the first resource for mathematics

Hashed Patricia trie: efficient longest prefix matching in peer-to-peer systems. (English) Zbl 1317.68288
Katoh, Naoki (ed.) et al., WALCOM: Algorithms and computation. 5th international workshop, WALCOM 2011, New Delhi, India, February 18–20, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-19093-3/pbk). Lecture Notes in Computer Science 6552, 170-181 (2011).
Summary: The design of efficient search structures for peer-to-peer systems has attracted a lot of attention in recent years. In this paper we address the problem of longest prefix matching and present an efficient data structure called hashed Patricia trie. Our hashed Patricia trie supports \(\mathit{Prefixsearch}(x)\) and \(\mathit{Insert}(x)\) in \(\mathcal O(\log \left|x\right|)\) hash table accesses and \(\mathit{Delete}(x)\) in \(\mathcal O(1)\) hash table accesses when \(|x|\) is the number of bits used to encode \(x\). That is the costs only depend on \(|x|\) and not the size of the data structure. The hash table accesses may be realized by any distributed hash table (DHT).
For the entire collection see [Zbl 1206.68014].
MSC:
68W32 Algorithms on strings
68P05 Data structures
Software:
Chord; Pastry; PATRICIA
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aspnes, J., Shah, G.: Skip graphs. In: Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, USA, January 12-14, pp. 384–393 (2003) · Zbl 1094.68545
[2] Awerbuch, B., Scheideler, C.: Peer-to-peer systems for prefix search. In: Proceedings of the Twenty-second Annual Symposium on Principles of Distributed Computing, PODC 2003, pp. 123–132. ACM, New York (2003), http://doi.acm.org/10.1145/872035.872053 · Zbl 1321.68060 · doi:10.1145/872035.872053
[3] Bayer, R., Unterauer, K.: Prefix b-trees. ACM Trans. Database Syst. 2(1), 11–26 (1977), doi:10.1145/320521.320530 · doi:10.1145/320521.320530
[4] Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press/McGraw-Hill (2001) · Zbl 1047.68161
[5] van Emde Boas, P., Kaas, R., Zijlstra, E.: Design and implementation of an efficient priority queue. Mathematical Systems Theory 10, 99–127 (1977) · Zbl 0363.60104 · doi:10.1007/BF01683268
[6] Knuth, D.E.: The Art of Computer Programming: Sorting and Searching, 2nd edn., vol. 3. Addison Wesley, Reading (1997) · Zbl 0883.68015
[7] Kumar, S., Turner, J.S., Crowley, P., Mitzenmacher, M.: Hexa: Compact data structures for faster packet processing. In: ICNP, pp. 246–255 (2007)
[8] Litwin, W.: Trie hashing. In: Lien, Y.E. (ed.) SIGMOD Conference, pp. 19–29. ACM Press, New York (1981)
[9] Litwin, W., Roussopoulos, N., Lévy, G., Hong, W.: Trie hashing with controlled load. IEEE Trans. Software Eng. 17(7), 678–691 (1991) · Zbl 05114108 · doi:10.1109/32.83904
[10] Morrison, D.R.: Patricia–practical algorithm to retrieve information coded in alphanumeric. J. ACM 15(4), 514–534 (1968) · doi:10.1145/321479.321481
[11] Patrascu, M., Thorup, M.: Time-space trade-offs for predecessor search. CoRR abs/cs/0603043 (2006) · Zbl 1301.68150
[12] Ramabhadran, S., Hellerstein, J., Ratnasamy, S., Shenker, S.: Prefix hash tree - an indexing data structure over distributed hash tables, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.58.617
[13] Rowstron, A.I.T., Druschel, P.: Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In: Liu, H. (ed.) Middleware 2001. LNCS, vol. 2218, pp. 329–350. Springer, Heidelberg (2001), http://portal.acm.org/citation.cfm?id=646591.697650 · Zbl 1051.68788 · doi:10.1007/3-540-45518-3_18
[14] Stoica, I., Morris, R., Karger, D., Kaashoek, M.F., Balakrishnan, H.: Chord: A scalable peer-to-peer lookup service for internet applications. In: SIGCOMM 2001: Proceedings of the 2001 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, pp. 149–160. ACM, New York (2001) · doi:10.1145/383059.383071
[15] Waldvogel, M., Varghese, G., Turner, J., Plattner, B.: Scalable best matching prefix lookups. In: PODC 1998: Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, p. 312. ACM, New York (1998) · Zbl 06548969 · doi:10.1145/277697.277765
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.