Discovering Relative Importance of Skyline Attributes

Summary: Proposes p-skylines that inject relative attribute importance into skyline queries to shrink result sets. A discovery framework uses user-provided superior/inferior examples; existence NP-complete and optimal discovery FNP-complete, but a polynomial-time restricted version using only superior examples is tractable; experiments show accuracy and scalability. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h1e31c5cf16b191f3
Venue: VLDB
Year: 2009
Pagerank: 9.2454758e-05
Overall Rank: 1,990 | 86.63%
DOI: 10.14778/1687627.1687697

Incoming Non-self Citations Over Time

Authors

1. Denis Mindolin (State University of New York at Buffalo)
2. Jan Chomicki (State University of New York at Buffalo)

BibTeX Citation

@article{mindolin_vldb09,
        title = {{Discovering Relative Importance of Skyline Attributes}},
        author = {Mindolin, Denis and Chomicki, Jan},
        journal = {PVLDB},
        series = {{VLDB} '09},
        doi = {10.14778/1687627.1687697},
        url = {https://doi.org/10.14778/1687627.1687697},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,087	Regret-Minimizing Representative Databases	2010	VLDB	0.00012097722
2,545	Interactive Regret Minimization	2012	SIGMOD	8.3178501e-05
5,068	Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality	2018	SIGMOD	6.2893698e-05
6,012	Call to Order: A Hierarchical Browsing Approach to Eliciting Users' Preference	2010	SIGMOD	5.9143092e-05
6,065	k-Hit Query: Top-k Query with Probabilistic Utility Function	2015	SIGMOD	5.8978409e-05
6,176	Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings	2018	VLDB	5.8609559e-05
6,756	Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size	2021	SIGMOD	5.6900378e-05
7,452	Strongly Truthful Interactive Regret Minimization	2019	SIGMOD	5.5235226e-05
11,582	Robust Best Point Selection under Unreliable User Feedback	2024	VLDB	4.9793485e-05
12,497	Generating Top-k Packages via Preference Elicitation	2014	VLDB	4.9793485e-05
12,567	IPS: An Interactive Package Configuration System for Trip Planning	2013	VLDB	4.9793485e-05
12,755	Efficient Skyline Evaluation over Partially Ordered Domains	2010	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
671	Foundations of Preferences in Database Systems	2002	VLDB	0.00014929237
1,377	Preference SQL - Design, Implementation, Experiences	2002	VLDB	0.00010871114
2,491	Efficient Skyline Computation over Low-Cardinality Domains	2007	VLDB	8.3921786e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,502	Computing All Skyline Probabilities for Uncertain Data	2009	PODS
2	256	Efficient Progressive Skyline Computation	2001	VLDB
3	2,996	Multi-objective Query Processing for Database Systems	2004	VLDB
4	12,755	Efficient Skyline Evaluation over Partially Ordered Domains	2010	VLDB
5	12,962	On Dominating Your Neighborhood Profitably	2007	VLDB
6	2,566	Stratified Computation of Skylines with Partially-Ordered Domains	2005	SIGMOD
7	5,626	Reconciling Skyline and Ranking Queries	2017	VLDB
8	8,547	Discovering the Skyline of Web Databases	2016	VLDB
9	5,548	Efficient Skyline Querying with Variable User Preferences on Nominal Attributes	2008	VLDB
10	9,701	Output-sensitive Evaluation of Prioritized Skyline Queries	2015	SIGMOD