Scalable skyline evaluation in multidimensional and partially ordered domains

摘要: of thesis entitled Scalable Skyline Evaluation in Multidimensional and Partially Ordered Domains Submitted by Shiming ZHANG for the degree Doctor Philosophy Computer Science at The University Hong Kong August 2011 skyline query, as an elegant sophisticated paradigm flexible multicritera data analysis, has attracted a lot attention advanced database applications. Specifically, given d-dimensional D set multidimensional preferences P, which involve partial or total orders attributes, w.r.t. P is superior subset contains points that are not dominated any others on all dimensions. Here, object o dominates another o′, if only better than good o′ dimensions least one dimension. present scale-free choice worthy further consideration many contexts. problem high dimensional spaces easily becomes CPU-intensive due to large number dominance tests. We focus such problems propose dynamic indexing technique organize tree, integrated into state-of-the-art sort-based algorithms boost their computational performance magnitude. novel checking approach supported theoretical scales well with dimensionality cardinality tremendous savings unnecessary tests but also efficiency help bitwise operations. partially ordered attributes seldom considered literature. A few prior methods partial-to-total mapping scheme adapt stronger notions dominance, generate false positives require expensive checks. this two (i.e., CPS SCL) do have these drawbacks. Our first method uses appropriate embedding order chain products follows off-the-shelf algorithm. second column-wise storage approach, facilitates efficient incomparability verification. empirical