Efficient routing in non-uniform dhts for range query support

By randomly mapping items and nodes to a common address space, most P2P index structures based on DHTs provide only exact match data lookups. This compromises their use in data-oriented applications where more advanced query facilities, such as range queries, are needed. We have previously proposed a P2P index structure that refines the Chord DHT by mapping data items to the Chord address space in an order-preserving way. Load balancing of skewed data is then achieved deterministically by pulling nodes to zones where too many data items reside. However, based on Chord's underlying routing infrastructure, our previous solution can no longer ensure logarithmic routing cost when the node distribution over the address space becomes highly skewed. In this paper, we push our previous study one step further and propose a simple yet efficient refinement to Chord's routing component. By offering nodes more flexibility in the choice of their neighbors, our solution ensures logarithmic routing cost, with high probability. Most importantly, our solution is dynamic in the sense that it adapts to any node distribution, including highly adversarial ones.