Optimizing skyline queries over incomplete data

详细信息    查看全文

• 作者：Jongwuk Lee^a ; ^{julee@hufs.ac.kr" class="auth_mail" title="E-mail the corresponding author} ; Hyeonseung Im^b ; ^{hsim@kangwon.ac.kr" class="auth_mail" title="E-mail the corresponding author} ; Gae-won You ; ^c ; ^{gaewonyou@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Skyline queries ; Incomplete data ; Dominance ; Incomparability ; Intransitivity ; Cyclicity
• 刊名：Information Sciences
• 出版年：2016
• 出版时间：20 September 2016
• 年：2016
• 卷：361-362
• 期：Complete
• 页码：14-28
• 全文大小：749 K

文摘

Skyline queries have been widely used as an attractive operator in multi-criteria decision making applications. Because of the intuitive notion of skyline queries, many skyline algorithms have been developed in various data settings. However, most of the skyline algorithms rely on the assumption of completeness, i.e., all values of points are known. In many cases, because this assumption does not hold, conventional skyline algorithms cannot be applied. To handle incomplete data, existing work redefines the dominance notion by using the common subspace between points. However, it can incur too many pairwise comparisons over incomplete data. To address this problem, we first propose a new sorting-based bucket skyline algorithm using two optimization techniques: bucket- and point-level orders. In case that too few or no skyline points exist over incomplete data, we develop a novel skyline ranking method that adjusts two user-specific parameters for retrieving meaningful skyline points. Lastly, we empirically evaluate the efficiency and effectiveness of our proposed algorithms over both synthetic and real-life datasets.