A general technique for top-κ geometric intersection query problems

Saladi Rahul, Ravi Janardan

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

In a top-κ Geometric Intersection Query (top-κ GIQ) problem, a set of n weighted, geometric objects in Rd is to be preprocessed into a compact data structure so that for any query geometric object, q, and integerk > 0, the k largest-weight objects intersected by q can be reported efficiently. While the top-κ problem has been studied extensively for non-geometric problems (e.g., recommender systems), the geometric version has received little attention. This paper gives a general technique to solve any top-κ GIQ problem efficiently. The technique relies only on the availability of an efficient solution for the underlying (non-top-κ) GIQ problem, which is often the case. Using this, asymptotically efficient solutions are derived for several top-κ GIQ problems, including top-κ orthogonal and circular range search, point enclosure search, halfspace range search, etc. Implementations of some of these solutions, using practical data structures, show that they are quite efficient in practice. This paper also does a formal investigation of the hardness of the top-κ GIQ problem, which reveals interesting connections between the top-κ GIQ problem and the underlying (non-top-κ) GIQ problem.

Original languageEnglish (US)
Article number6945935
Pages (from-to)2859-2871
Number of pages13
JournalIEEE Transactions on Knowledge and Data Engineering
Volume26
Issue number12
DOIs
StatePublished - Dec 1 2014

Bibliographical note

Publisher Copyright:
© 1989-2012 IEEE.

Keywords

  • Range search
  • Top-κ
  • aggregation
  • geometric algorithms and data structures
  • query processing and optimization

Fingerprint

Dive into the research topics of 'A general technique for top-κ geometric intersection query problems'. Together they form a unique fingerprint.

Cite this