Prefix hash tree

A Prefix Hash Tree (PHT) is a distributed data structure that enables more sophisticated queries over a Distributed Hash Table (DHT). The Prefix Hash Tree uses the lookup interface of a DHT to construct a trie-based data structure that is both efficient (updates are doubly logarithmic in the size of the domain being indexed), and resilient (the failure of any given node in a Prefix Hash Tree does not affect the availability of data stored at other nodes).

External links

• http://berkeley.intel-research.net/sylvia/pht.pdf - Prefix Hash Tree: An Indexing Data Structure over Distributed Hash Tables
• http://pier.cs.berkeley.edu - The PIER project implements a PHT

See also

• Distributed Hash Table (DHT)
• Prefix tree