Dht-based Index Structure Study

With the recent advent of Distributed Hash Tables(or DHTs for short),various highly-scalable and fault-tolerant distributed systems(e.g.,P2P networks) start to thrive in practice. What comes along is the increasing need for various applications based on DHTs,in particular, for complex query processing(e.g.,range queries and k-nearest-neighbor queries).However, as DHTs destroy data locality by its hashing,it is a non-trivial task to support complex queries in DHT-based P2P systems.Among existing solutions,while there are several from-scratch designs that need changing DHTs' internal structures,others adopt a more practical way,that is,to build a P2P index on top of DHTs.In this thesis,we followed the latter design philosophy and explored the problem of how to better utilize the interface of generic DHTs and to build an efficient distributed query processing systems.We proposed a holistic suite of solutions,called(m)-LIGHT(including LIGHT and m-LIGHT),for over-DHT indexing and query processing.First,we focused on the one-dimensional case and proposed LIGhtweight Hash Tree (LIGHT).By a novel naming mechanism that gracefully distributes index over DHTs,LIGHT achieves efficiency in query processing yet with low maintenance overhead.More specifically, LIGHT can support several complex queries(including range queries,k-NN queries and Min/Max queries) with optimal performance.Furthermore,we studied the problem of multi-dimensional indexing over DHTs.m-LIGHT is proposed to achieve high querying efficiency and to significantly relief load imbalance among peers,which is often the case for multi-dimensional indexing.Specifically, m-LIGHT achieves its high efficiency by employing a more general naming mechanism,m-LIGHT leverages a new data-aware index splitting strategy to achieve optimal load balance among peer nodes.For performance evaluation on(m)-LIGHT,we conduct extensive experiments based on real-world implementation.Compared to the state-of-the-art over-DHT indexing schemes, (m)-LIGHT substantially saves the index maintenance overhead,achieves a more balanced load distribution,and improves the complex query performance in both bandwidth consumption and response latency.