A progressive approach for similarity search on matrix

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

Research output: Journal article publicationConference articleAcademic researchpeer-review

5 Citations (Scopus)


We study a similarity search problem on a raw image by its pixel values. We call this problem as matrix similarity search; it has several applications, e.g., object detection, motion estimation, and superresolution. Given a data image D and a query q, the best match refers to a sub-window of D that is the most similar to q. The state-of-theart solution applies a sequence of lower bound functions to filter subwindows and reduce the response time. Unfortunately, it suffers from two drawbacks: (i) its lower bound functions cannot support arbitrary query size, and (ii) it may invoke a large number of lower bound functions, which may incur high cost in the worst-case. In this paper, we propose an efficient solution that overcomes the above drawbacks. First, we present a generic approach to build lower bound functions that are applicable to arbitrary query size and enable trade-offs between bound tightness and computation time. We provide performance guarantee even in the worst-case. Second, to further reduce the number of calls to lower bound functions, we develop a lower bound function for a group of sub-windows. Experimental results on image data demonstrate the efficiency of our proposed methods.
Original languageEnglish
Pages (from-to)373-390
Number of pages18
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publication statusPublished - 1 Jan 2015
Event14th International on Symposium on Spatial and Temporal Databases, SSTD 2015 - Hong Kong, Hong Kong
Duration: 26 Aug 201528 Aug 2015

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'A progressive approach for similarity search on matrix'. Together they form a unique fingerprint.

Cite this