AN INDEXING METHOD FOR SUPPORTING SPATIAL QUERIES IN STRUCTURED PEER-TO-PEER SYSTEMS

摘要

To provide the efficient supporting spatial data queries in peer-to-peer systems has recently received much attention. Most proposed methods tried to use hop count to represent the transmission delay, and the total message count to estimate the cost of query processing. For the ignorance of the differences between DHT lookups and spatial queries, and distinction between physical networks and overlay networks, the efficiency and cost of their query processing can't be indicated properly. In addition, their experimental results are achieved by using point data sets, while the fact that the overlap of spatial objects usually exists in real applications is not considered, and it may cause multi path query processing and then results in plenty of peers visiting and routing messages. In this paper, we propose an indexing method which efficiently supports spatial queries in structured peer-to-peer systems. It adopts an overlap minimization algorithm which takes the query rate of data into account to reasonably reduce the holistic cost of queries. We also introduce a dynamically adaptive distributed optimization scheme that dynamically adapting to the time-varying overlay architecture and data usage concerns. Theoretical analysis and simulation results both indicate that our method is efficient and effective.