DROLAP - A Dense-Region Based Approach to On-Line Analytical Processing

Abstract

ROLAP (Relational OLAP) and MOLAP (Multidimensional OLAP) are two opposing techniques for building On-line Analytical Processing (OLAP) systems. MOLAP has good query performance while ROLAP is based on mature RDBMS technologies. Many data warehouses contain sparse but clustered multidimensional data which neither ROLAP or MOLAP handles efficiently and scalably.We propose a denseregion-based OLAP (DROLAP) approach which surpasses both ROLAP and MOLAP in space efficiency and query performance. DROLAP takes the bests of ROLAP and MOLAP and combines them to support fast queries and high storage utilization. The core of building a DROLAP system lies in the mining of dense regions in a data cube, for which we have developed an efficient index-based algorithm EDEM to handle. Extensive performance studies consistently show that the DROLAP approach is superior to both MOLAP and ROLAP in handling sparse but clustered multidimensional data. Moreover, our EDEM algorithm is efficient and effective in identifying dense regions.