Analysis of pre-computed partition top method for range top-k queries in OLAP data cubes

Abstract

In decision support systems, having knowledge on the top k values is more informative and crucial than the maximum value. Unfortunately, the naïve method involves high computational cost and the existing methods for range-max query are inefficient if applied directly. In this paper, we propose a Pre-computed Partition Top method (PPT) to partition the data cube and pre-store a number of top values for improving query performance. The main focus of this study is to find the optimum values for two parameters, i.e., the partition factor (b) and the number of pre-stored values (r), through analytical approach. A cost function based on Poisson distribution is used for the analysis. The analytical results obtained are verified against simulation results. It is shown that the PPT method outperforms other alternative methods significantly when proper b and r are used.