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: hc282196e33efa123
Venue: VLDB
Year: 2013
Pagerank: 5.3332727e-05
Overall Rank: 8,479 | 43.00%
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,424	Causal Search for Skylines (CSS): Causally-Informed Selective Data De-Correlation	2026	SIGMOD	4.9793485e-05
10,733	APEROL: Adaptive Parallel Edge-to-cloud Runtime Optimization for Layered Workflow Execution	2026	VLDB	4.9793485e-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
313	Shooting Stars in the Sky: An Online Algorithm for Skyline Queries	2002	VLDB	0.00021311041
638	An Optimal and Progressive Algorithm for Skyline Queries	2003	SIGMOD	0.00015338893
3,281	Kernel-Based Skyline Cardinality Estimation	2009	SIGMOD	7.4583561e-05
5,070	Randomized Multi-pass Streaming Skyline Algorithms	2009	VLDB	6.2890477e-05
5,144	On Finding Skylines in External Memory	2011	PODS	6.2566665e-05
5,590	Scalable Skyline Computation Using Object-based Space Partitioning	2009	SIGMOD	6.0739438e-05

Semantically Similar Papers

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