Efficient Sub-Window Nearest Neighbor Search On Matrix

Keywords

Nearest neighbor; similarity search

Abstract

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.

Publication Date

4-1-2017

Publication Title

IEEE Transactions on Knowledge and Data Engineering

Volume

29

Issue

4

Number of Pages

784-797

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/TKDE.2016.2633357

Socpus ID

85015802699 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/85015802699

This document is currently not available here.

Share

COinS