Multiple choice tries and distributed hash tables

DOI10.1002/rsa.20234zbMath1172.68067OpenAlexW4230636836MaRDI QIDQ3633017

Gahyun Park, Wojciech Szpankowski, Luc P. Devroye, Gábor Lugosi

Publication date: 16 June 2009

Published in: Random Structures and Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20234

zbMATH Keywords

probabilistic analysis of algorithmsdistributed hash tablesalgorithms on sequencesrandom triesrandom data structures

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05)

Uses Software

• PATRICIA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Simple efficient load-balancing algorithms for peer-to-peer systems
• Asymptotical growth of a class of random trees
• A study of trie-like structures under the density model
• Concentration inequalities using the entropy method
• Laws of large numbers and tail inequalities for random tries and PATRICIA trees
• A note on growing binary trees
• Randomized allocation processes
• On the number of full levels in tries
• Novel architectures for P2P applications
• A stochastic process on the hypercube with applications to peer-to-peer networks
• Paths in a random digital tree: limiting distributions
• Some results on V-ary asymmetric tries
• Balanced Allocations
• New results on the size of tries
• On Representatives of Subsets
• Viceroy
• Balanced binary trees for ID management and load balance in distributed hash tables
• An inequality involving multinomial probabilities
• File structures using hashing functions
• On the Application of the Borel-Cantelli Lemma