On Efficient Processing of Subspace Skyline Queries on High Dimensional Data

摘要: Recent studies on efficiently answering subspace skyline queries can be separated into two approaches. The first focused pre-materializing a set of skylines points in various subspaces while the second focus dynamically by using anchors to prune off through spatial reasoning. Despite effort compress pre-materialized removal redundancy, storage space for approach remain exponential number dimensions. query time other hand also grow substantially data with higher dimensionality where pruning power become much weaker. In this paper, we propose methods high dimensional such that both prematerialization and moderated. We novel notions maximal partial-dominating space, partial-dominated equality between pairs objects full use these concepts as foundation data. Query processing involves mostly simple operations computation is done only small subset candidate subspace. develop random sampling method compute an on-line fashion. Extensive experiments have been conducted demonstrated efficiency effectiveness our methods.