P-Cube: Answering preference queries in multi-dimensional space

Many new applications that involve decision making need online (i.e., OLAP-styled) preference analysis with multi-dimensional boolean selections. Typical preference queries includes lop-k queries and skyline queries. An analytical query often comes with a set of boolean predicates that constrain a largel subsel of data, which, may also vary incrementally by drilling/rolling operators. To efficiently support preference queries with multiple boolean predicates, neither boolean-then-preference nor preference-then-boolean approach is satisfactory. To integrate boolean pruning and preference pruning in a unified framework, we propose signature, a new materialization measure for multi-dimensional group-bys. Based on this, we propose P-Cube (i.e., data cube for preference queries) and study its complete life cycle, including signature generation, compression, decomposition, incremental maintenance and usage for efficient on-line analytical query processing. We present a signature-based progressive algorithm that is able to simultaneously push boolean and preference constraints deep into the database search. Our performance study shows that the proposed method achieves al least one order of magnitude speed-up over existing approaches.