Maximal Vector Computation in Large Data Sets

Summary: Maximal vector computation ties skyline queries to convex hulls; externalization hampers divide-and-conquer methods. Proposes LESS, an external algorithm blending skyline-strategy strengths with externalization-friendly design, giving average-case O(kn). (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9305
Venue: VLDB
Year: 2005
Pagerank: 0.00011828508
Overall Rank: 1,473 | 89.76%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
914	Finding k-Dominant Skylines in High Dimensional Space	2006	SIGMOD	0.00015387584
1,179	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00013457451
1,575	Efficient Computation of the Skyline Cube	2005	VLDB	0.00011286884
1,830	Relaxing Join and Selection Queries	2006	VLDB	0.000103862
2,366	Efficient Processing of Top-k Dominating Queries on Multi-Dimensional Data	2007	VLDB	8.9523637e-05
2,500	Efficient Skyline Computation over Low-Cardinality Domains	2007	VLDB	8.6457563e-05
3,452	Refreshing the Sky: The Compressed Skycube with Efficient Support for Frequent Updates	2006	SIGMOD	7.0821774e-05
4,142	Approaching the Skyline in Z Order	2007	VLDB	6.4138475e-05
4,559	Creating Competitive Products	2009	VLDB	6.0857166e-05
5,583	Efficient Skyline Querying with Variable User Preferences on Nominal Attributes	2008	VLDB	5.4237646e-05
5,695	Scalable Skyline Computation Using Object-based Space Partitioning	2009	SIGMOD	5.3681018e-05
5,985	Call to Order: A Hierarchical Browsing Approach to Eliciting Users' Preference	2010	SIGMOD	5.2442779e-05
6,568	Efficient Parallel Skyline Processing using Hyperplane Projections	2011	SIGMOD	5.0068521e-05
6,677	Categorical Skylines for Streaming Data	2008	SIGMOD	4.9657435e-05
9,205	FHL-Cube: Multi-Constraint Shortest Path Querying with Flexible Combination of Constraints	2022	VLDB	4.3736393e-05
9,452	Output-sensitive Evaluation of Prioritized Skyline Queries	2015	SIGMOD	4.339214e-05
12,077	eSkyline: Processing Skyline Queries over Encrypted Data	2013	VLDB	4.1945683e-05
12,304	Minimizing the Communication Cost for Continuous Skyline Maintenance	2009	SIGMOD	4.1945683e-05
12,351	A Fair Assignment Algorithm for Multiple Preference Queries	2009	VLDB	4.1945683e-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
262	Efficient Progressive Skyline Computation	2001	VLDB	0.00029987552
386	Shooting Stars in the Sky: An Online Algorithm for Skyline Queries	2002	VLDB	0.00024768022
749	An Optimal and Progressive Algorithm for Skyline Queries	2003	SIGMOD	0.00017228334
2,346	Multi-objective Query Processing for Database Systems	2004	VLDB	8.9919258e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
749	An Optimal and Progressive Algorithm for Skyline Queries	2003	SIGMOD	0.00017228334
10,921	Optimal (Multiway) Spatial Joins	2024	PODS	4.1945683e-05
2,346	Multi-objective Query Processing for Database Systems	2004	VLDB	8.9919258e-05
6,568	Efficient Parallel Skyline Processing using Hyperplane Projections	2011	SIGMOD	5.0068521e-05
1,502	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00011643406
2,906	A Scalable Algorithm for Maximizing Range Sum in Spatial Databases	2012	VLDB	7.9350108e-05
5,695	Scalable Skyline Computation Using Object-based Space Partitioning	2009	SIGMOD	5.3681018e-05
9,772	Minimum Coresets for Maxima Representation of Multidimensional Data	2021	PODS	4.2856106e-05
5,116	Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative	2017	SIGMOD	5.6830089e-05
5,240	On Finding Skylines in External Memory	2011	PODS	5.6104868e-05