Efficient allocation algorithms for OLAP over imprecise data

Abstract

Recent work proposed extending the OLAP data model to support data ambiguity, specifically imprecision and uncertainty. A process called allocation was proposed to transform a given imprecise fact table into a form, called the Extended Database, that can be readily used to answer OLAP aggregation queries. In this work, we present scalable, efficient algorithms for creating the Extended Database (i.e., performing allocation) for a given imnprecise fact table. Many allocation policies require multiple iterations over the imprecise fact table, and the straightforward evaluation approaches introduced earlier can be highly inefficient. Optimizing iterative allocation policies for large datasets presents novel challenges, and has not been considered previously to the best of our knowledge. In addition to developing scalable allocation algorithms, we present a performance evaluation that demonstrates their efficiency and compares their performance with respect to straight-foward approaches. Copyright 2006 VLDB Endowment, ACM.