Multiple choice tries and distributed hash tables

DOI10.1002/RSA.20234MaRDI QIDQ3633017zbMATH OpenOpenAlexFDO

Authors Gahyun Park, Wojciech Szpankowski, Luc Devroye, Gábor Lugosi

Publication date 16 June 2009

Published in Random Structures \& 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)

Recommendations

• Multiple choice tries and distributed hash tables
• An Analysis of the Height of Tries with Random Weights on the Edges
• Improved behaviour of tries by adaptive branching
• On the number of full levels in tries
• Publication:4508387

Cites work

• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 53861 (Why is no real title available?)
• scientific article; zbMATH DE number 1875412 (Why is no real title available?)
• A note on growing binary trees
• A stochastic process on the hypercube with applications to peer-to-peer networks
• A study of trie-like structures under the density model
• An inequality involving multinomial probabilities
• Asymptotical growth of a class of random trees
• Average case analysis of algorithms on sequences. With a foreword by Philippe Flajolet
• Balanced Allocations
• Balanced binary trees for ID management and load balance in distributed hash tables
• Concentration inequalities using the entropy method
• File structures using hashing functions
• Graph theory with applications
• Laws of large numbers and tail inequalities for random tries and PATRICIA trees
• New results on the size of tries
• Novel architectures for P2P applications: the continuous-discrete approach
• On Representatives of Subsets
• On the Application of the Borel-Cantelli Lemma
• On the number of full levels in tries
• Paths in a random digital tree: limiting distributions
• Randomized allocation processes
• Simple efficient load-balancing algorithms for peer-to-peer systems
• Some results on V-ary asymmetric tries
• Viceroy, a scalable and dynamic emulation of the butterfly

Cited in

(1)

• Multiple choice tries and distributed hash tables

Describes a project that uses

Uses Software

• PATRICIA

This page was built for publication: Multiple choice tries and distributed hash tables

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3633017)