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 multidimensional Boolean selections. Typical preference queries includes top-k queries and skyline queries. An analytical query often comes with a set of Boolean predicates that constrain a target subset 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 at least one order of magnitude speed-up over existing approaches.