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: 10080
Venue: VLDB
Year: 2009
Pagerank: 9.4514785e-05
Overall Rank: 1,938 | 86.71%
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,072	Regret-Minimizing Representative Databases	2010	VLDB	0.0001230281
2,491	Interactive Regret Minimization	2012	SIGMOD	8.5086491e-05
4,939	Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality	2018	SIGMOD	6.4336325e-05
5,887	Call to Order: A Hierarchical Browsing Approach to Eliciting Users' Preference	2010	SIGMOD	6.0500409e-05
5,944	k-Hit Query: Top-k Query with Probabilistic Utility Function	2015	SIGMOD	6.0328749e-05
6,052	Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings	2018	VLDB	5.9941393e-05
6,636	Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size	2021	SIGMOD	5.8172769e-05
7,305	Strongly Truthful Interactive Regret Minimization	2019	SIGMOD	5.6501646e-05
11,250	Robust Best Point Selection under Unreliable User Feedback	2024	VLDB	5.093636e-05
12,206	Generating Top-k Packages via Preference Elicitation	2014	VLDB	5.093636e-05
12,276	IPS: An Interactive Package Configuration System for Trip Planning	2013	VLDB	5.093636e-05
12,464	Efficient Skyline Evaluation over Partially Ordered Domains	2010	VLDB	5.093636e-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
656	Foundations of Preferences in Database Systems	2002	VLDB	0.00015258172
1,338	Preference SQL - Design, Implementation, Experiences	2002	VLDB	0.00011117197
2,434	Efficient Skyline Computation over Low-Cardinality Domains	2007	VLDB	8.5839844e-05

Semantically Similar Papers

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