Efficient Skyline Evaluation over Partially Ordered Domains

Summary: Introduces two skyline methods for partially ordered domains that avoid false positives and costly dominance checks: lattice-inspired total-order mapping and column-store-style indexing for incompatibility verification. Up to 10× faster than prior approaches. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 10251
Venue: VLDB
Year: 2010
Pagerank: 5.093636e-05
Overall Rank: 12,464 | 14.49%
DOI: 10.14778/1920841.1920996

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Shiming Zhang (University of Hong Kong)
2. Nikos Mamoulis (University of Hong Kong)
3. David W. Cheung (University of Hong Kong)
4. Ben Kao (University of Hong Kong)

BibTeX Citation

@article{zhang_vldb10,
        title = {{Efficient Skyline Evaluation over Partially Ordered Domains}},
        author = {Zhang, Shiming and Mamoulis, Nikos and Cheung, David W. and Kao, Ben},
        journal = {PVLDB},
        series = {{VLDB} '10},
        volume = {3},
        number = {1},
        pages = {1255--1268},
        doi = {10.14778/1920841.1920996},
        url = {https://doi.org/10.14778/1920841.1920996},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 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.001157935
12	C-Store: A Column-oriented DBMS	2005	VLDB	0.00069513174
243	Efficient Progressive Skyline Computation	2001	VLDB	0.00023495903
308	Shooting Stars in the Sky: An Online Algorithm for Skyline Queries	2002	VLDB	0.00021787597
966	A Common Database Approach for OLTP and OLAP Using an In-Memory Column Database	2009	SIGMOD	0.00012920281
1,097	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00012181027
1,847	Efficient Computation of Reverse Skyline Queries	2007	VLDB	9.6252055e-05
1,938	Discovering Relative Importance of Skyline Attributes	2009	VLDB	9.4514785e-05
2,516	Stratified Computation of Skylines with Partially-Ordered Domains	2005	SIGMOD	8.4773324e-05
3,139	Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Databases	2008	SIGMOD	7.7188328e-05
3,224	Kernel-Based Skyline Cardinality Estimation	2009	SIGMOD	7.6249441e-05
3,409	Approaching the Skyline in Z Order	2007	VLDB	7.4368546e-05
5,455	Scalable Skyline Computation Using Object-based Space Partitioning	2009	SIGMOD	6.2133548e-05
6,616	Categorical Skylines for Streaming Data	2008	SIGMOD	5.8214223e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,938	Discovering Relative Importance of Skyline Attributes	2009	VLDB
2	5,496	Reconciling Skyline and Ranking Queries	2017	VLDB
3	12,672	On Dominating Your Neighborhood Profitably	2007	VLDB
4	5,409	Efficient Skyline Querying with Variable User Preferences on Nominal Attributes	2008	VLDB
5	3,409	Approaching the Skyline in Z Order	2007	VLDB
6	243	Efficient Progressive Skyline Computation	2001	VLDB
7	6,616	Categorical Skylines for Streaming Data	2008	SIGMOD
8	5,455	Scalable Skyline Computation Using Object-based Space Partitioning	2009	SIGMOD
9	2,434	Efficient Skyline Computation over Low-Cardinality Domains	2007	VLDB
10	2,516	Stratified Computation of Skylines with Partially-Ordered Domains	2005	SIGMOD