A prefix hash tree is a distributed data structure

Data structure

In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...

 that enables more sophisticated queries over a distributed hash table

Distributed hash table

A distributed hash table is a class of a decentralized distributed system that provides a lookup service similar to a hash table; pairs are stored in a DHT, and any participating node can efficiently retrieve the value associated with a given key...

 (DHT). The prefix hash tree uses the lookup interface of a DHT to construct a trie

Trie

In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the...

-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 - PHT was developed as part of work on the PIER project.