Efficient group-by reverse skyline computation

详细信息    查看全文

• 作者：Zonghui Wang ; Yunjun Gao ; Qing Liu ; Xiaoye Miao ; Qing Li ; Chuan Li
• 关键词：Reverse skyline ; Group ; by reverse skyline ; Query processing ; Algorithm
• 刊名：World Wide Web
• 出版年：2016
• 出版时间：November 2016
• 年：2016
• 卷：19
• 期：6
• 页码：1023-1049
• 全文大小：3,495 KB
• 刊物类别：Computer Science
• 刊物主题：Information Systems Applications and The Internet
  Database Management
  Operating Systems
  
• 出版者：Springer Netherlands
• ISSN：1573-1413
• 卷排序：19

文摘

The reverse skyline query is very useful in many decision making applications. Given a multi-dimensional dataset P and a query point q, the reverse skyline query returns all the points in P whose dynamic skyline contains q. Although the reverse skyline retrieval has been well-studied in the literature, there is, to the best of our knowledge, no prior work on one of the most intuitive and practical types of reverse skyline queries, namely, group-by reverse skyline (GRS) query, which retrieves the reverse skyline for each group in a specified dataset. We formalize the GRS query including monochromatic and bichromatic versions, and identify its properties, and then propose a set of efficient algorithms for computing the group-by reverse skyline. Extensive experimental evaluation using both real and synthetic datasets demonstrates the performance of our proposed algorithms in terms of effectiveness and efficiency under a variety of experimental settings.