Efficient top-k queries for orthogonal ranges

Saladi Rahul, Prosenjit Gupta, Ravi Janardan, K. S. Rajan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations


Advances in sensing and data gathering technologies have resulted in an explosion in the volume of data that is being generated, processed, and archived. In particular, this information overload calls for new methods for querying large spatial datasets, since users are often not interested in merely retrieving a list of all data items satisfying a query, but would, instead, like a more informative "summary" of the retrieved items. An example is the so-called top-k problem, where the goal is to retrieve from a set of n weighted points in IRd the k most significant points, ranked by their weights, that lie in an orthogonal query box in IRd (rather than get a list of all points lying in the query box). In this paper, efficient and output-sensitive solutions are presented for this problem in two settings. In the first setting, the k points are reported in arbitrary order and the underlying set can be updated dynamically through insertions and deletions of points. In the second setting, the k points are reported in sorted order of their weights.

Original languageEnglish (US)
Title of host publicationWALCOM
Subtitle of host publicationAlgorithms and Computation - 5th International Workshop, WALCOM 2011, Proceedings
Number of pages12
StatePublished - Mar 10 2011
Event5th Annual Workshop on Algorithms and Computation, WALCOM 2011 - New Delhi, India
Duration: Feb 18 2011Feb 20 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6552 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other5th Annual Workshop on Algorithms and Computation, WALCOM 2011
CityNew Delhi

Fingerprint Dive into the research topics of 'Efficient top-k queries for orthogonal ranges'. Together they form a unique fingerprint.

Cite this