New Techniques for Best-Match Retrieval

Dennis Shasha, Tsong Li Wang

Research output: Contribution to journalArticlepeer-review

58 Scopus citations


A scheme to answer best-match queries from a file containing a collection of objects is described. A best-match query is to find the objects in the file that are closest 1990similarity measure) to a given target. Previous work [5, 331] suggests that one can reduce the number of comparisons required to achieve the desired results using the triangle inequality, starting with a data structure for the file that reflects some precomputed intrafile distances. We generalize the technique to allow the optimum use of any given set of precomputed intrafile distances. Some empirical results are presented which illustrate the effectiveness of our scheme, and its performance relative to previous algorithms.

Original languageEnglish (US)
Pages (from-to)140-158
Number of pages19
JournalACM Transactions on Information Systems (TOIS)
Issue number2
StatePublished - Jan 4 1990
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Information Systems
  • General Business, Management and Accounting
  • Computer Science Applications


Dive into the research topics of 'New Techniques for Best-Match Retrieval'. Together they form a unique fingerprint.

Cite this