Progressive ranking of range aggregates

摘要

Ranking-aware queries have been gaining much attention recently in many applications such as multimedia databases, search engines and data streams. They are, however, not only restricted to such applications but are also very useful in On-Line Analytical Processing (OLAP) applications. In this paper, we introduce aggregation ranking queries in OLAP data cubes motivated by an online advertisement tracking data warehouse application. These queries aggregate information over a specified range and then return the ranked order of the aggregated values. For instance, an advertiser might be interested in the top-k publishers over the last three months in terms of sales obtained through the online advertisements placed on the publishers. They differ from range aggregate queries in that range aggregate queries are mainly concerned with an aggregate operator such as SUM and MIN/MAX over the selected ranges of all dimensions in the data cubes. Existing techniques for range aggregate queries are not able to process aggregation ranking queries efficiently. Hence, in this paper we propose new algorithms to handle this problem. The essence of the proposed algorithms is based on both ranking and cumulative information to progressively rank aggregation results. Furthermore we empirically evaluate our techniques and the experimental results show that the query cost is improved significantly.