More Web Proxy on the site http://driver.im/

research-article

Reconciling skyline and ranking queries

Authors:

Davide MartinenghiAuthors Info & Claims

Proceedings of the VLDB Endowment, Volume 10, Issue 11

Pages 1454 - 1465

https://doi.org/10.14778/3137628.3137653

Published: 01 August 2017 Publication History

Abstract

Traditionally, skyline and ranking queries have been treated separately as alternative ways of discovering interesting data in potentially large datasets. While ranking queries adopt a specific scoring function to rank tuples, skyline queries return the set of non-dominated tuples and are independent of attribute scales and scoring functions. Ranking queries are thus less general, but usually cheaper to compute and widely used in data management systems.

We propose a framework to seamlessly integrate these two approaches by introducing the notion of restricted skyline queries (R-skylines). We propose R-skyline operators that generalize both skyline and ranking queries by applying the notion of dominance to a set of scoring functions of interest. Such sets can be characterized, e.g., by imposing constraints on the function's parameters, such as the weights in a linear scoring function. We discuss the formal properties of these new operators, show how to implement them efficiently, and evaluate them on both synthetic and real datasets.

References

[1]

S. Börzsönyi, D. Kossmann, and K. Stocker. The skyline operator. In ICDE, pages 421--430, 2001.

Digital Library

[2]

M. J. Carey and D. Kossmann. On saying "enough already!" in SQL. In SIGMOD, pages 219--230, 1997.

Digital Library

[3]

J. Chomicki, P. Ciaccia, and N. Meneghetti. Skyline queries, front and back. SIGMOD Record, 42(3):6--18, 2013.

Digital Library

[4]

J. Chomicki et al. Skyline with presorting. In ICDE, pages 717--719, 2003.

[5]

E. Ciceri et al. Crowdsourcing for top-k query processing over uncertain data. TKDE, 28(1):41--53, 2016.

Digital Library

[6]

Y. S. Eum, K. S. Park, and S. H. Kim. Establishing dominance and potential optimality in multi-criteria analysis with imprecise weight and value. Computers & Operations Research, 28:397--409, 2001.

Digital Library

[7]

A. A. Freitas. A critical review of multi-objective optimization in data mining: a position paper. SIGKDD Explorations, 6(2):77--86, 2004.

Digital Library

[8]

P. Godfrey. Skyline cardinality for relational processing. In FoIKS, pages 78--97, 2004.

[9]

P. Godfrey et al. Algorithms and analyses for maximal vector computation. VLDB J., 16(1):5--28, 2007.

Digital Library

[10]

V. Kaibel and M. E. Pfetsch. Some algorithmic problems in polytope theory. In Algebra, Geometry, and Software Systems, pages 23--47, 2003.

[11]

X. Lin et al. Selecting stars: The k most representative skyline operator. In ICDE, pages 86--95, 2007.

[12]

C. Lofi and W. Balke. On skyline queries and how to choose from pareto sets. In Advanced Query Processing, Volume 1: Issues and Trends, pages 15--36. 2013.

[13]

C. Lofi, U. Güntzer, and W. Balke. Efficient computation of trade-off skylines. In EDBT, pages 597--608, 2010.

Digital Library

[14]

N. Meneghetti et al. Output-sensitive evaluation of prioritized skyline queries. In SIGMOD, pages 1955--1967, 2015.

Digital Library

[15]

D. Mindolin and J. Chomicki. Preference elicitation in prioritized skyline queries. VLDB J., 20(2):157--182, 2011.

Digital Library

[16]

K. Mouratidis, J. Zhang, and H. Pang. Maximum rank query. PVLDB, 8(12):1554--1565, 2015.

Digital Library

[17]

D. Papadias et al. Progressive skyline computation in database systems. TODS, 30(1):41--82, 2005.

Digital Library

[18]

A. Salo and R. P. Hämäläinen. Preference programming multicriteria weighting models under incomplete information. In Handbook of Multicriteria Analysis, chapter 4, pages 167--187. Springer, 2010.

[19]

Y. Siskos, E. Grigoroudis, and N. F. Matsatsinis. UTA Methods, pages 297--334. Springer New York, 2005.

[20]

M. A. Soliman et al. Ranking with uncertain scoring functions: semantics and sensitivity measures. In SIGMOD, pages 805--816, 2011.

Digital Library

[21]

Y. Tao et al. Distance-based representative skyline. In ICDE, pages 892--903, 2009.

Digital Library

[22]

M. L. Yiu and N. Mamoulis. Efficient processing of top-k dominating queries on multi-dimensional data. In VLDB, pages 483--494, 2007.

Digital Library

[23]

H. Yu et al. Enabling ad-hoc ranking for data retrieval. In ICDE, pages 514--515, 2005.

[24]

J. Zhang, K. Mouratidis, and H. Pang. Global immutable region computation. In SIGMOD, pages 1151--1162, 2014.

Digital Library

Cited By

Chen QWong R(2024)Robust Best Point Selection under Unreliable User FeedbackProceedings of the VLDB Endowment10.14778/3681954.368195517:11(2681-2693)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681955
Mouratidis KLi KTang B(2024)Marrying Top-k with Skyline Queries: Operators with Relaxed Preference Input and Controllable Output SizeACM Transactions on Database Systems10.1145/3705726Online publication date: 22-Nov-2024
https://doi.org/10.1145/3705726
Xiao XLi J(2023)rkHit: Representative Query with Uncertain PreferenceProceedings of the ACM on Management of Data10.1145/35892711:2(1-26)Online publication date: 20-Jun-2023
https://dl.acm.org/doi/10.1145/3589271
Show More Cited By

Reconciling skyline and ranking queries
1. Information systems
  1. Data management systems
    1. Database management system engines
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory

Recommendations

Combination skyline queries
Transactions on Large-Scale Data- and Knowledge-Centered Systems VI

Given a collection of data objects, the skyline problem is to select the objects which are not dominated by any others. In this paper, we propose a new variation of the skyline problem, called the combination skyline problem. The goal is to find the ...
U-Skyline: A New Skyline Query for Uncertain Databases

The skyline query, aiming at identifying a set of skyline tuples that are not dominated by any other tuple, is particularly useful for multicriteria data analysis and decision making. For uncertain databases, a probabilistic skyline query, called P-...
Skyline Diagram: Efficient Space Partitioning for Skyline Queries
Skyline queries are important in many application domains. In this paper, we propose a novel structure <italic>Skyline Diagram</italic>, which given a set of points, partitions the plane into a set of regions, referred to as skyline polyominos. All query ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the VLDB Endowment

Proceedings of the VLDB Endowment Volume 10, Issue 11

August 2017

432 pages

ISSN:2150-8097

Editors:
Peter Boncz
CWI
,
Ken Salem
University of Waterloo

Issue’s Table of Contents

Publisher

VLDB Endowment

Publication History

Published: 01 August 2017

Published in PVLDB Volume 10, Issue 11

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
166
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen QWong R(2024)Robust Best Point Selection under Unreliable User FeedbackProceedings of the VLDB Endowment10.14778/3681954.368195517:11(2681-2693)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681955
Mouratidis KLi KTang B(2024)Marrying Top-k with Skyline Queries: Operators with Relaxed Preference Input and Controllable Output SizeACM Transactions on Database Systems10.1145/3705726Online publication date: 22-Nov-2024
https://doi.org/10.1145/3705726
Xiao XLi J(2023)rkHit: Representative Query with Uncertain PreferenceProceedings of the ACM on Management of Data10.1145/35892711:2(1-26)Online publication date: 20-Jun-2023
https://dl.acm.org/doi/10.1145/3589271
Yin BZeng WWei X(2023)Efficient crowdsourced best objects finding via superiority probability based ordering for decision support systemsExpert Systems with Applications: An International Journal10.1016/j.eswa.2023.119893223:COnline publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1016/j.eswa.2023.119893
Zhang JTang BYiu MYan XLi KIves ZBonifati AEl Abbadi A(2022)T-LevelIndex: Towards Efficient Query Processing in Continuous Preference SpaceProceedings of the 2022 International Conference on Management of Data10.1145/3514221.3526182(2149-2162)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3526182
Vlachou ADoulkeridis CRocha-Junior JNørvåg K(2022)On Decisive Skyline QueriesBig Data Analytics and Knowledge Discovery10.1007/978-3-031-12670-3_6(61-73)Online publication date: 22-Aug-2022
https://dl.acm.org/doi/10.1007/978-3-031-12670-3_6
Mouratidis KLi KTang BLi GLi ZIdreos SSrivastava D(2021)Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable SizeProceedings of the 2021 International Conference on Management of Data10.1145/3448016.3457299(1317-1330)Online publication date: 9-Jun-2021
https://dl.acm.org/doi/10.1145/3448016.3457299
Tang BMouratidis KHan MLi GLi ZIdreos SSrivastava D(2021)On m-Impact Regions and Standing Top-k Influence ProblemsProceedings of the 2021 International Conference on Management of Data10.1145/3448016.3452832(1784-1796)Online publication date: 9-Jun-2021
https://dl.acm.org/doi/10.1145/3448016.3452832
Ciaccia PMartinenghi D(2020)Flexible SkylinesACM Transactions on Database Systems10.1145/340611345:4(1-45)Online publication date: 10-Dec-2020
https://dl.acm.org/doi/10.1145/3406113
Ciaccia PMartinenghi DTorlone R(2020)Foundations of Context-aware Preference PropagationJournal of the ACM10.1145/337571367:1(1-43)Online publication date: 15-Jan-2020
https://dl.acm.org/doi/10.1145/3375713
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents