On efficient mutual nearest neighbor query processing in spatial databases

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

15 Scopus Citations
View graph of relations

Author(s)

  • Yunjun Gao
  • Baihua Zheng
  • Gencai Chen
  • Qing Li

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)705-727
Journal / PublicationData and Knowledge Engineering
Volume68
Issue number8
Publication statusPublished - Aug 2009

Abstract

This paper studies a new form of nearest neighbor queries in spatial databases, namely, mutual nearest neighbor (MNN) search. Given a set D of objects and a query object q, an MNN query returns from D, the set of objects that are among the k1 (≥1) nearest neighbors (NNs) of q; meanwhile, have q as one of their k2 (≥1) NNs. Although MNN queries are useful in many applications involving decision making, data mining, and pattern recognition, it cannot be efficiently handled by existing spatial query processing approaches. In this paper, we present the first piece of work for tackling MNN queries efficiently. Our methods utilize a conventional data-partitioning index (e.g., R-tree, etc.) on the dataset, employ the state-of-the-art database techniques including best-first based k nearest neighbor (kNN) retrieval and reverse kNN search with TPL pruning, and make use of the advantages of batch processing and reusing technique. An extensive empirical study, based on experiments performed using both real and synthetic datasets, has been conducted to demonstrate the efficiency and effectiveness of our proposed algorithms under various experimental settings. © 2009 Elsevier B.V. All rights reserved.

Research Area(s)

  • Algorithm, Nearest neighbor, Query processing, Spatial databases

Citation Format(s)

On efficient mutual nearest neighbor query processing in spatial databases. / Gao, Yunjun; Zheng, Baihua; Chen, Gencai et al.

In: Data and Knowledge Engineering, Vol. 68, No. 8, 08.2009, p. 705-727.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review