Parallel Computation of Skyline and Reverse Skyline Queries Using MapReduce

Summary: Parallel MapReduce algorithms for skyline and reverse-skyline queries. Histograms prune non-skyline points, region-based partitioning enables independent candidate computation, and final region-wise verification guarantees correctness; results show scalability. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10873
Venue: VLDB
Year: 2013
Pagerank: 5.8698599e-05
Overall Rank: 6,473 | 55.60%
DOI: 10.14778/2556549.2556580

Incoming Non-self Citations Over Time

Authors

1. Yoonjae Park (Seoul National University)
2. Jun-Ki Min (Korea University)
3. Kyuseok Shim (Seoul National University)

BibTeX Citation

@article{park_vldb13,
        title = {{Parallel Computation of Skyline and Reverse Skyline Queries Using MapReduce}},
        author = {Park, Yoonjae and Min, Jun-Ki and Shim, Kyuseok},
        journal = {PVLDB},
        series = {{VLDB} '13},
        volume = {6},
        number = {14},
        pages = {2002--2013},
        doi = {10.14778/2556549.2556580},
        url = {https://doi.org/10.14778/2556549.2556580},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,356	Reverse k Nearest Neighbors Query Processing: Experiments and Analysis	2015	VLDB	5.282937e-05
10,621	Scalable Grid-based Computation of Kendall's tau Correlation	2026	VLDB	5.093636e-05
12,127	Processing of Probabilistic Skyline Queries Using MapReduce	2015	VLDB	5.093636e-05
12,162	Work-Efficient Parallel Skyline Computation for the GPU	2015	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 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
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
623	An Optimal and Progressive Algorithm for Skyline Queries	2003	SIGMOD	0.00015684963
1,097	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00012181027
1,847	Efficient Computation of Reverse Skyline Queries	2007	VLDB	9.6252055e-05
2,312	Online Aggregation and Continuous Query support in MapReduce	2010	SIGMOD	8.7642158e-05
2,689	The Spatial Skyline Queries	2006	VLDB	8.2559825e-05
3,139	Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Databases	2008	SIGMOD	7.7188328e-05
6,467	Efficient Parallel Skyline Processing using Hyperplane Projections	2011	SIGMOD	5.8712039e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,616	Categorical Skylines for Streaming Data	2008	SIGMOD
2	243	Efficient Progressive Skyline Computation	2001	VLDB
3	5,496	Reconciling Skyline and Ranking Queries	2017	VLDB
4	1,847	Efficient Computation of Reverse Skyline Queries	2007	VLDB
5	12,162	Work-Efficient Parallel Skyline Computation for the GPU	2015	VLDB
6	1,360	Efficient Computation of the Skyline Cube	2005	VLDB
7	5,455	Scalable Skyline Computation Using Object-based Space Partitioning	2009	SIGMOD
8	3,429	Angle-based Space Partitioning for Efficient Parallel Skyline Computation	2008	SIGMOD
9	6,467	Efficient Parallel Skyline Processing using Hyperplane Projections	2011	SIGMOD
10	12,127	Processing of Probabilistic Skyline Queries Using MapReduce	2015	VLDB