Efficient Sub-Window Nearest Neighbor Search on Matrix

Tsz Nam Chan, Man Lung Yiu, Kien A. Hua

Research output: Journal article publicationJournal articleAcademic researchpeer-review

4 Citations (Scopus)


Personal use is permitted, but republication/redistribution requires IEEE permission. We study a nearest neighbor search problem on a matrix by its element values. Given a data matrix D and a query matrix q, the sub-window nearest neighbor search problem finds a sub-window of D that is the most similar to q. This problem has a wide range of applications, e.g., geospatial data integration, object detection, and motion estimation. In this paper, we propose an efficient progressive search solution that overcomes the drawbacks of existing solutions. First, we present a generic approach to build level-based lower bound functions on top of basic lower bound functions. Second, we develop a novel lower bound function for a group of sub-windows, in order to boost the efficiency of our solution. Furthermore, we extend our solution to support irregular-shaped queries. Experimental results on real data demonstrate the efficiency of our proposed methods.
Original languageEnglish
Article number7776935
Pages (from-to)784-797
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number4
Publication statusPublished - 1 Apr 2017


  • Nearest neighbor
  • similarity search

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Cite this