DDT: a distributed data structure for the support of P2P range query

This paper defines and evaluates a hierarchical distributed data structure, Distributed Digest Trie, supporting range queries in P2P systems. Providing efficient support for these queries is currently a challenging research issue in the P2P field, as classical approaches based on Distributed Hash Tables (DHT) are often not suitable for this kind of queries, due to the loss of locality introduced by the hashing function. Distributed Digest Trie exploits the DHT only to define a uniform assignment of logical identifiers to peers while each key is managed by the peer publishing it. Each peer is paired with the leaf of the trie corresponding to its logical identifier. An internal node of the trie stores a digest summarizing the keys published by the peers paired with the leaves of the tree rooted at that node. A proper mapping function is defined to map the internal nodes of the trie to the peers. The digests stored at the internal nodes are exploited to guide the search process for the resolution of the range query. Different aggregation techniques are proposed. A set of experimental results compare these techniques, evaluate the cost of dynamic updates of the data structure and the network traffic generated by the method.