Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size

Summary: ORD and ORU marry skyline with top-k to relax preferences while delivering controllable output sizes. Qualitative study and benchmarks against baselines show improved personalization, flexible preferences, predictable cardinality, and efficiency. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hb2e77668a3570bba
Venue: SIGMOD
Year: 2021
Pagerank: 5.6873442e-05
Overall Rank: 6,761 | 54.56%
DOI: 10.1145/3448016.3457299

Incoming Non-self Citations Over Time

Authors

1. Kyriakos Mouratidis (Singapore Management University)
2. Keming Li (Southern University of Science and Technology)
3. Bo Tang (Southern University of Science and Technology)

BibTeX Citation

@inproceedings{mouratidis_sigmod21,
        title = {{Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size}},
        author = {Mouratidis, Kyriakos and Li, Keming and Tang, Bo},
        series = {{SIGMOD} '21},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3448016.3457299},
        url = {https://dl.acm.org/doi/10.1145/3448016.3457299},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,921	GTI: Graph-based Tree Index with Logarithm Updates for Nearest Neighbor Search in High-Dimensional Spaces	2025	VLDB	5.641565e-05
10,261	Accelerating Skyline Path Enumeration with a Core Attribute Index on Multi-attribute Graphs	2025	SIGMOD	5.0480912e-05
11,547	Directional Queries: Making Top-k Queries More Effective in Discovering Relevant Results	2024	SIGMOD	4.9769913e-05
11,588	Robust Best Point Selection under Unreliable User Feedback	2024	VLDB	4.9769913e-05
11,718	rkHit: Representative Query with Uncertain Preference	2023	SIGMOD	4.9769913e-05
11,880	tau-LevelIndex: Towards Efficient Query Processing in Continuous Preference Space	2022	SIGMOD	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 22 of 22 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011402175
44	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00045319457
342	The Onion Technique: Indexing for Linear Optimization Queries	2000	SIGMOD	0.00020520649
418	PREFER: A System for the Efficient Execution of Multiparametric Ranked Queries	2001	SIGMOD	0.00018609134
672	Foundations of Preferences in Database Systems	2002	VLDB	0.00014922272
818	Finding k-Dominant Skylines in High Dimensional Space	2006	SIGMOD	0.00013666302
1,087	Regret-Minimizing Representative Databases	2010	VLDB	0.00012092041
1,992	Discovering Relative Importance of Skyline Attributes	2009	VLDB	9.2411032e-05
2,106	Computing k-Regret Minimizing Sets	2014	VLDB	9.0287481e-05
2,498	FEXIPRO: Fast and Exact Inner Product Retrieval in Recommender Systems	2017	SIGMOD	8.3800917e-05
2,545	Interactive Regret Minimization	2012	SIGMOD	8.3139128e-05
2,621	Ranking with Uncertain Scoring Functions: Semantics and Sensitivity Measures	2011	SIGMOD	8.2130891e-05
3,380	Ad-hoc Top-k Query Answering for Data Streams	2007	VLDB	7.353368e-05
4,083	Learning User Preferences By Adaptive Pairwise Comparison	2015	VLDB	6.8143727e-05
4,833	Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative	2017	SIGMOD	6.3867086e-05
5,071	Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality	2018	SIGMOD	6.2863925e-05
5,627	Reconciling Skyline and Ranking Queries	2017	VLDB	6.0578274e-05
6,178	Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings	2018	VLDB	5.8581814e-05
6,382	Maximum Rank Query	2015	VLDB	5.805942e-05
6,721	RRR: Rank-Regret Representative	2019	SIGMOD	5.6966108e-05
6,972	Global Immutable Region Computation	2014	SIGMOD	5.6281923e-05
7,456	Strongly Truthful Interactive Regret Minimization	2019	SIGMOD	5.5209079e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,547	Directional Queries: Making Top-k Queries More Effective in Discovering Relevant Results	2024	SIGMOD
2	6,522	Query Refinement for Diverse Top-k Selection	2024	SIGMOD
3	2,999	Multi-objective Query Processing for Database Systems	2004	VLDB
4	1,087	Regret-Minimizing Representative Databases	2010	VLDB
5	5,071	Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality	2018	SIGMOD
6	6,178	Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings	2018	VLDB
7	2,485	Processing a Large Number of Continuous Preference Top-k Queries	2012	SIGMOD
8	9,706	Output-sensitive Evaluation of Prioritized Skyline Queries	2015	SIGMOD
9	5,627	Reconciling Skyline and Ranking Queries	2017	VLDB
10	2,893	Efficient Processing of Top-k Dominating Queries on Multi-Dimensional Data	2007	VLDB