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.00011469322
Overall Rank: 1,216 | 91.86%
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
820	Finding k-Dominant Skylines in High Dimensional Space	2006	SIGMOD	0.00013621724
1,126	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00011888563
1,401	Efficient Computation of the Skyline Cube	2005	VLDB	0.0001075604
1,649	Relaxing Join and Selection Queries	2006	VLDB	9.9699016e-05
2,499	Efficient Skyline Computation over Low-Cardinality Domains	2007	VLDB	8.3611036e-05
2,904	Efficient Processing of Top-k Dominating Queries on Multi-Dimensional Data	2007	VLDB	7.8723013e-05
3,346	Refreshing the Sky: The Compressed Skycube with Efficient Support for Frequent Updates	2006	SIGMOD	7.3804433e-05
3,487	Approaching the Skyline in Z Order	2007	VLDB	7.2428454e-05
4,258	Creating Competitive Products	2009	VLDB	6.683217e-05
5,565	Efficient Skyline Querying with Variable User Preferences on Nominal Attributes	2008	VLDB	6.0652619e-05
5,606	Scalable Skyline Computation Using Object-based Space Partitioning	2009	SIGMOD	6.0509937e-05
6,024	Call to Order: A Hierarchical Browsing Approach to Eliciting Users' Preference	2010	SIGMOD	5.8919629e-05
6,609	Efficient Parallel Skyline Processing using Hyperplane Projections	2011	SIGMOD	5.718077e-05
6,770	Categorical Skylines for Streaming Data	2008	SIGMOD	5.6693028e-05
9,578	FHL-Cube: Multi-Constraint Shortest Path Querying with Flexible Combination of Constraints	2022	VLDB	5.1419143e-05
9,738	Output-sensitive Evaluation of Prioritized Skyline Queries	2015	SIGMOD	5.1187707e-05
10,502	Causal Search for Skylines (CSS): Causally-Informed Selective Data De-Correlation	2026	SIGMOD	4.9605343e-05
12,614	eSkyline: Processing Skyline Queries over Encrypted Data	2013	VLDB	4.9605343e-05
12,837	Minimizing the Communication Cost for Continuous Skyline Maintenance	2009	SIGMOD	4.9605343e-05
12,883	A Fair Assignment Algorithm for Multiple Preference Queries	2009	VLDB	4.9605343e-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
258	Efficient Progressive Skyline Computation	2001	VLDB	0.00022896896
317	Shooting Stars in the Sky: An Online Algorithm for Skyline Queries	2002	VLDB	0.00021232519
640	An Optimal and Progressive Algorithm for Skyline Queries	2003	SIGMOD	0.00015286314
3,014	Multi-objective Query Processing for Database Systems	2004	VLDB	7.740485e-05

Semantically Similar Papers

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