New Techniques for Best-Match Retrieval

Dennis Shasha, Tsong Li Wang

Research output: Contribution to journalArticle

Abstract

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)
Volume8
Issue number2
DOIs
StatePublished - Jan 4 1990

ASJC Scopus subject areas

  • Information Systems
  • Business, Management and Accounting(all)
  • Computer Science Applications

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

  • Cite this