Evaluation of top-k OLAP queries using aggregate R-trees

Nikos Mamoulis*, Spiridon Bakiras, Panos Kalnis

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

4 Scopus citations

Abstract

A top-κ OLAP query groups measures with respect to some abstraction level of interesting dimensions and selects the κ groups with the highest aggregate value. An example of such a query is "find the 10 combinations of product-type and month with the largest sum of sales". Such queries may also be applied in a spatial database context, where objects are augmented with some measures that must be aggregated according to a spatial division. For instance, consider a map of objects (e.g., restaurants), where each object carries some non-spatial measure (e.g., the number of customers served during the last month). Given a partitioning of the space into regions (e.g., by a regular grid), the goal is to find the regions with the highest number of served customers. A straightforward method to evaluate a top-κ OLAP query is to compute the aggregate value for each group and then select the groups with the highest aggregates. In this paper, we study the integration of the top-κ operator with the aggregate query processing module. For this, we make use of spatial indexes, augmented with aggregate information, like the aggregate R-tree. We device a branch-and-bound algorithm that accesses a minimal number of tree nodes in order to compute the top-κ groups. The efficiency of our approach is demonstrated by experimentation.

Original languageEnglish (US)
Pages (from-to)236-253
Number of pages18
JournalLecture Notes in Computer Science
Volume3633
DOIs
StatePublished - Jan 1 2005
Event9th International Symposium on Spatial and Temporal Databases, SSTD 2005 - Angra dos Reis, Brazil
Duration: Aug 22 2005Aug 24 2005

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Evaluation of top-k OLAP queries using aggregate R-trees'. Together they form a unique fingerprint.

Cite this