Skyline Operator on Anti-correlated Distributions

Summary: Cardinality model for anti-correlated distributions with a polynomial estimator for skyline size. A determination-elimination framework extends pruning to anti-correlated data, delivering gains over state-of-the-art on real and synthetic benchmarks. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10916
Venue: VLDB
Year: 2013
Pagerank: 5.4556836e-05
Overall Rank: 8,312 | 42.98%
DOI: 10.14778/2733004.2733007

Incoming Non-self Citations Over Time

Authors

1. Haichuan Shang (University of Tokyo)
2. Masaru Kitsuregawa (National Institute of Informatics; University of Tokyo)

BibTeX Citation

@article{shang_vldb13,
        title = {{Skyline Operator on Anti-correlated Distributions}},
        author = {Shang, Haichuan and Kitsuregawa, Masaru},
        journal = {PVLDB},
        series = {{VLDB} '13},
        volume = {6},
        number = {9},
        pages = {649--660},
        doi = {10.14778/2733004.2733007},
        url = {https://doi.org/10.14778/2733004.2733007},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,208	Causal Search for Skylines (CSS): Causally-Informed Selective Data De-Correlation	2026	SIGMOD	5.093636e-05
10,551	APEROL: Adaptive Parallel Edge-to-cloud Runtime Optimization for Layered Workflow Execution	2026	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
308	Shooting Stars in the Sky: An Online Algorithm for Skyline Queries	2002	VLDB	0.00021787597
623	An Optimal and Progressive Algorithm for Skyline Queries	2003	SIGMOD	0.00015684963
3,224	Kernel-Based Skyline Cardinality Estimation	2009	SIGMOD	7.6249441e-05
4,941	Randomized Multi-pass Streaming Skyline Algorithms	2009	VLDB	6.4333573e-05
5,016	On Finding Skylines in External Memory	2011	PODS	6.3998091e-05
5,455	Scalable Skyline Computation Using Object-based Space Partitioning	2009	SIGMOD	6.2133548e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,496	Reconciling Skyline and Ranking Queries	2017	VLDB
2	6,467	Efficient Parallel Skyline Processing using Hyperplane Projections	2011	SIGMOD
3	10,030	Skyline Queries with Noisy Comparisons	2015	PODS
4	9,192	Efficient and Effective Cardinality Estimation for Skyline Family	2023	SIGMOD
5	6,473	Parallel Computation of Skyline and Reverse Skyline Queries Using MapReduce	2013	VLDB
6	10,208	Causal Search for Skylines (CSS): Causally-Informed Selective Data De-Correlation	2026	SIGMOD
7	5,455	Scalable Skyline Computation Using Object-based Space Partitioning	2009	SIGMOD
8	792	Finding k-Dominant Skylines in High Dimensional Space	2006	SIGMOD
9	2,434	Efficient Skyline Computation over Low-Cardinality Domains	2007	VLDB
10	3,224	Kernel-Based Skyline Cardinality Estimation	2009	SIGMOD