Please use this identifier to cite or link to this item:
|Title:||Stratified computation of skylines with partially-ordered domains||Authors:||Chan, C.-Y.
|Issue Date:||2005||Citation:||Chan, C.-Y.,Eng, P.-K.,Tan, K.-L. (2005). Stratified computation of skylines with partially-ordered domains. Proceedings of the ACM SIGMOD International Conference on Management of Data : 203-214. ScholarBank@NUS Repository.||Abstract:||In this paper, we study the evaluation of skyline queries with partially-ordered attributes. Because such attributes lack a total ordering, traditional index-based evaluation algorithms (e.g., NN and BBS) that are designed for totally-ordered attributes can no longer prune the space as effectively. Our solution is- to transform each partially-ordered attribute into a. two-integer domain that allows us to exploit index-based algorthms to- compute skyline; queries, on the transformed space. Based', on this framework, we propose three novel algorithms: BBS+ is a straight forward adaptation of BBS using the framework, and SDC+ (Stratification by Dominance Classification) and SDC+ are optimized to handle false positives and support progressive evaluation. Both SDC and SDC+ exploit a dominance relationship to organize the data into strata. While SDC generates its strata at runtime, SDC+ partitions the data into strata offline. We also design two dominance classification strategies (MinPC and MaxPC) to further optimize the performance of SDC and SDC+. We implemented the proposed schemes and evaluated their efficiency. Our results show that our proposed techniques outperform existing approaches by a wide margin, with SDC+-MinPC giving the best performance in terms of both response time as well as progressiveness. To the best of our knowledge, this is the first paper to address the problem of skyline query evaluation involving partially-ordered attribute domains. Copyright 2005 ACM.||Source Title:||Proceedings of the ACM SIGMOD International Conference on Management of Data||URI:||http://scholarbank.nus.edu.sg/handle/10635/40184||ISSN:||07308078|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Sep 9, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.