FILTERING SEARCH: A NEW APPROACH TO QUERY-ANSWERING.

Research output: Contribution to journalArticlepeer-review

235 Scopus citations

Abstract

We introduce a new technique for solving problems of the following form: preprocess a set of objects so that those satisfying a given property with respect to a query object can be listed very effectively. Well-known problems that fall into this category include range search, point enclosure, intersection, and near-neighbor problems. The approach which we take is very general and rests on a new concept called filtering search. We show on a number of examples how it can be used to improve the complexity of known algorithms and simplify their implementations as well. In particular, filtering search allows us to improve on the worst-case complexity of the best algorithms known so far for solving the problems mentioned above.

Original languageEnglish (US)
Pages (from-to)703-724
Number of pages22
JournalSIAM Journal on Computing
Volume15
Issue number3
DOIs
StatePublished - 1986
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics

Fingerprint

Dive into the research topics of 'FILTERING SEARCH: A NEW APPROACH TO QUERY-ANSWERING.'. Together they form a unique fingerprint.

Cite this