Efficient Indexing Scheme over DHT

Abstract

Range query processing is an essential role in many P2P applications including database indexing, distributed computing and location aware computing and commercial services based on current user’s location. Most of P2P applications are running over DHT overlay network. But most of DHT can only provide for exact match queries. If there is no an efficient indexing scheme over DHTs, complex queries such as range queries may be major challenge. So in recent years, there are many indexing schemes over DHTs are proposed for range query processing. In this paper, an efficient indexing scheme is proposed for multidimensional range query processing. For building the proposed scheme, data are firstly distributed over peer nodes. For fairly distributing of data, k-dimensional tree (kd-tree) is used. While partitioning data on kd-tree, splitting points with each dimension are generated. Leave nodes of kd-tree store data records with tree information including splitting points. The proposed indexing scheme is built using these stored tree information. By using the proposed system, bandwidth and time consuming in range query processing over DHTs can reduce.