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: 9496
Venue: VLDB
Year: 2005
Pagerank: 0.00011772712
Overall Rank: 1,185 | 91.88%
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
792	Finding k-Dominant Skylines in High Dimensional Space	2006	SIGMOD	0.00013979615
1,097	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00012181027
1,360	Efficient Computation of the Skyline Cube	2005	VLDB	0.00011040203
1,636	Relaxing Join and Selection Queries	2006	VLDB	0.00010156479
2,434	Efficient Skyline Computation over Low-Cardinality Domains	2007	VLDB	8.5839844e-05
2,827	Efficient Processing of Top-k Dominating Queries on Multi-Dimensional Data	2007	VLDB	8.0831263e-05
3,273	Refreshing the Sky: The Compressed Skycube with Efficient Support for Frequent Updates	2006	SIGMOD	7.5768045e-05
3,409	Approaching the Skyline in Z Order	2007	VLDB	7.4368546e-05
4,170	Creating Competitive Products	2009	VLDB	6.8543709e-05
5,409	Efficient Skyline Querying with Variable User Preferences on Nominal Attributes	2008	VLDB	6.2279841e-05
5,455	Scalable Skyline Computation Using Object-based Space Partitioning	2009	SIGMOD	6.2133548e-05
5,887	Call to Order: A Hierarchical Browsing Approach to Eliciting Users' Preference	2010	SIGMOD	6.0500409e-05
6,467	Efficient Parallel Skyline Processing using Hyperplane Projections	2011	SIGMOD	5.8712039e-05
6,616	Categorical Skylines for Streaming Data	2008	SIGMOD	5.8214223e-05
9,364	FHL-Cube: Multi-Constraint Shortest Path Querying with Flexible Combination of Constraints	2022	VLDB	5.2798829e-05
9,524	Output-sensitive Evaluation of Prioritized Skyline Queries	2015	SIGMOD	5.2555551e-05
10,208	Causal Search for Skylines (CSS): Causally-Informed Selective Data De-Correlation	2026	SIGMOD	5.093636e-05
12,274	eSkyline: Processing Skyline Queries over Encrypted Data	2013	VLDB	5.093636e-05
12,498	Minimizing the Communication Cost for Continuous Skyline Maintenance	2009	SIGMOD	5.093636e-05
12,544	A Fair Assignment Algorithm for Multiple Preference Queries	2009	VLDB	5.093636e-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
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
2,932	Multi-objective Query Processing for Database Systems	2004	VLDB	7.9475864e-05

Semantically Similar Papers

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