Efficient indexing for skyline queries with partially ordered domains

Abstract

Given a dataset containing multidimensional data points, a skyline query retrieves a set of data points that are not be dominated by any other points. Skyline queries are useful in multi-preference analysis and decision making applications, and there has been a lot of research interest in the efficient processing of skyline queries. While many skyline evaluation methods have been developed on totally ordered domains for numerical attributes, the efficient evaluation of skyline queries on a combination of totally ordered domains for numerical attributes and partially ordered domains for categorical attributes, which is a more general and challenging problem, is only beginning to be studied. The difficulty in handling skyline queries involving partially ordered domains mainly comes from the more complex dominance relationship among values in partially ordered domains. In this thesis, we present a new indexing method named ZINC (for Z-order Indexing with Nested Code) that supports efficient skyline computation for data with both totally and partially ordered attribute domains. The key innovation in ZINC is based on combining the strengths of the ZB-tree, which is the state-of-the-art index method for computing skylines involving totally ordered domains, with a novel, nested coding scheme that succinctly maps partial orders into total orders. An extensive performance evaluation demonstrates that ZINC significantly outperforms the state-of-the-art indexing schemes for skyline queries.