Answering Constrained k-NN Queries in Unstructured P2P Systems

Bin Wang, Xiaochun Yang, Guoren Wang, Lei Chen, Xiaoyang Sean Wang, Xuemin Lin, Ge Yu

Abstract

The processing of k-NN queries has been studied extensively both in a centralized computing environment and in a structured P2P environment. However, the problem over an unstructured P2P system is not well studied despite of their popularity. Communication-efficient processing of k-NN queries in such an environment is a unique challenge due to the distribution, dynamics and large scale of the system. In this paper, we investigate the problem of efficiently computing k-NN queries over unstructured P2P systems. We first propose a location-based domination model to determine a search space. We then present two types of probing strategies, radius-convergence and radius-expanding. A comprehensive performance study demonstrates that our techniques are efficient and scalable.
BibTeX
@inproceedings{wang2006answering,
  author = {Bin Wang and Xiaochun Yang and Guoren Wang and Lei Chen and Xiaoyang Sean Wang and Xuemin Lin and Ge Yu},
  title = {{Answering Constrained k-NN Queries in Unstructured P2P Systems}},
  booktitle = {DBISP2P},
  year = {2006},
  doi = {10.1007/978-3-540-71661-7\_38},
}

Loading related content...

Figure