Maximal Vector Computation in Large Data Sets

Summary: Revisits maximal-vector/skyline computation, showing classic divide-and-conquer methods externalize poorly and degrade with dimension. Introduces LESS, an external algorithm combining prior strengths, with average-case O(kn) time and strong empirical performance. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h09fd26d3cd5c9c8c
Venue: VLDB
Year: 2005
Pagerank: 0.00011512468
Overall Rank: 1,213 | 91.85%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Parke Godfrey (York University)
2. Ryan Shipley (The College of William and Mary)
3. Jarek Gryz (York University)

BibTeX Citation

@article{godfrey_vldb05,
        title = {{Maximal Vector Computation in Large Data Sets}},
        author = {Godfrey, Parke and Shipley, Ryan and Gryz, Jarek},
        journal = {PVLDB},
        series = {{VLDB} '05},
        pages = {229},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 20 of 20 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
817	Finding k-Dominant Skylines in High Dimensional Space	2006	SIGMOD	0.00013672764
1,124	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00011927351
1,394	Efficient Computation of the Skyline Cube	2005	VLDB	0.00010796403
1,643	Relaxing Join and Selection Queries	2006	VLDB	0.00010006399
2,491	Efficient Skyline Computation over Low-Cardinality Domains	2007	VLDB	8.3921786e-05
2,893	Efficient Processing of Top-k Dominating Queries on Multi-Dimensional Data	2007	VLDB	7.9019071e-05
3,340	Refreshing the Sky: The Compressed Skycube with Efficient Support for Frequent Updates	2006	SIGMOD	7.4080086e-05
3,478	Approaching the Skyline in Z Order	2007	VLDB	7.2700866e-05
4,241	Creating Competitive Products	2009	VLDB	6.7085648e-05
5,548	Efficient Skyline Querying with Variable User Preferences on Nominal Attributes	2008	VLDB	6.0882467e-05
5,590	Scalable Skyline Computation Using Object-based Space Partitioning	2009	SIGMOD	6.0739438e-05
6,012	Call to Order: A Hierarchical Browsing Approach to Eliciting Users' Preference	2010	SIGMOD	5.9143092e-05
6,601	Efficient Parallel Skyline Processing using Hyperplane Projections	2011	SIGMOD	5.7397409e-05
6,745	Categorical Skylines for Streaming Data	2008	SIGMOD	5.6908052e-05
9,543	FHL-Cube: Multi-Constraint Shortest Path Querying with Flexible Combination of Constraints	2022	VLDB	5.1614165e-05
9,701	Output-sensitive Evaluation of Prioritized Skyline Queries	2015	SIGMOD	5.1381851e-05
10,424	Causal Search for Skylines (CSS): Causally-Informed Selective Data De-Correlation	2026	SIGMOD	4.9793485e-05
12,565	eSkyline: Processing Skyline Queries over Encrypted Data	2013	VLDB	4.9793485e-05
12,788	Minimizing the Communication Cost for Continuous Skyline Maintenance	2009	SIGMOD	4.9793485e-05
12,834	A Fair Assignment Algorithm for Multiple Preference Queries	2009	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
256	Efficient Progressive Skyline Computation	2001	VLDB	0.00022981799
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
2,996	Multi-objective Query Processing for Database Systems	2004	VLDB	7.7697801e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	638	An Optimal and Progressive Algorithm for Skyline Queries	2003	SIGMOD
2	11,489	Optimal (Multiway) Spatial Joins	2024	PODS
3	2,996	Multi-objective Query Processing for Database Systems	2004	VLDB
4	6,601	Efficient Parallel Skyline Processing using Hyperplane Projections	2011	SIGMOD
5	1,589	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS
6	3,085	A Scalable Algorithm for Maximizing Range Sum in Spatial Databases	2012	VLDB
7	5,590	Scalable Skyline Computation Using Object-based Space Partitioning	2009	SIGMOD
8	10,085	Minimum Coresets for Maxima Representation of Multidimensional Data	2021	PODS
9	4,831	Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative	2017	SIGMOD
10	5,144	On Finding Skylines in External Memory	2011	PODS