P-Cube: Answering Preference Queries in Multi-Dimensional Space
Dong Xin, Jiawei Han · 2008
Many new applications that involve decision making need online (i.e., OLAP-styled) preference analysis with multidimensional Boolean selections. Typical preference queries includes top-kqueries 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, neitherBoolean-then-preferencenorpreference-then-Booleanapproach is satisfactory. To integrate Boolean pruning and preference pruning in a unified framework, we proposesignature,a new materialization measure for multi-dimensional group-bys. Based on this, we proposeP-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.