Efficient group-by reverse skyline computation

Z. Wang, Y. Gao, Q. Liu, X. Miao, Qing Li, C. Li

Research output: Journal article publicationJournal articleAcademic researchpeer-review

2 Citations (Scopus)

Abstract

© 2015, Springer Science+Business Media New York.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.
Original languageEnglish
Pages (from-to)1023-1049
Number of pages27
JournalWorld Wide Web
Volume19
Issue number6
DOIs
Publication statusPublished - 1 Nov 2016
Externally publishedYes

Keywords

  • Algorithm
  • Group-by reverse skyline
  • Query processing
  • Reverse skyline

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this