Please use this identifier to cite or link to this item:
Title: Efficient indexing for skyline queries with partially ordered domains
Authors: LIU BIN
Keywords: Skyline Query, Partially Ordered Domain, Nested Encoding
Issue Date: 14-Jul-2010
Citation: LIU BIN (2010-07-14). Efficient indexing for skyline queries with partially ordered domains. ScholarBank@NUS Repository.
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.
Appears in Collections:Master's Theses (Open)

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
LiuB.pdf1.31 MBAdobe PDF



Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.