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

Dong Xin, Jiawei Han

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 2008 IEEE 24th International Conference on Data Engineering, ICDE'08
Pages1092-1100
Number of pages9
DOIs
StatePublished - 2008
Event2008 IEEE 24th International Conference on Data Engineering, ICDE'08 - Cancun, Mexico
Duration: Apr 7 2008Apr 12 2008

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1084-4627

Other

Other2008 IEEE 24th International Conference on Data Engineering, ICDE'08
Country/TerritoryMexico
CityCancun
Period4/7/084/12/08

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Information Systems

Fingerprint

Dive into the research topics of 'P-Cube: Answering preference queries in multi-dimensional space'. Together they form a unique fingerprint.

Cite this