Efficient Top-k Queries for Orthogonal Ranges

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 a 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.