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: 9306
Venue: VLDB
Year: 2005
Pagerank: 0.0001181903
Overall Rank: 1,471 | 89.78%
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
913	Finding k-Dominant Skylines in High Dimensional Space	2006	SIGMOD	0.00015372758
1,181	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00013447487
1,576	Efficient Computation of the Skyline Cube	2005	VLDB	0.00011278557
1,830	Relaxing Join and Selection Queries	2006	VLDB	0.0001037611
2,371	Efficient Processing of Top-k Dominating Queries on Multi-Dimensional Data	2007	VLDB	8.9443366e-05
2,502	Efficient Skyline Computation over Low-Cardinality Domains	2007	VLDB	8.631993e-05
3,454	Refreshing the Sky: The Compressed Skycube with Efficient Support for Frequent Updates	2006	SIGMOD	7.0770352e-05
4,141	Approaching the Skyline in Z Order	2007	VLDB	6.4110324e-05
4,555	Creating Competitive Products	2009	VLDB	6.0818278e-05
5,591	Efficient Skyline Querying with Variable User Preferences on Nominal Attributes	2008	VLDB	5.4181199e-05
5,708	Scalable Skyline Computation Using Object-based Space Partitioning	2009	SIGMOD	5.3629476e-05
5,988	Call to Order: A Hierarchical Browsing Approach to Eliciting Users' Preference	2010	SIGMOD	5.2394981e-05
6,568	Efficient Parallel Skyline Processing using Hyperplane Projections	2011	SIGMOD	5.0020592e-05
6,680	Categorical Skylines for Streaming Data	2008	SIGMOD	4.960978e-05
9,207	FHL-Cube: Multi-Constraint Shortest Path Querying with Flexible Combination of Constraints	2022	VLDB	4.3694476e-05
9,376	Output-sensitive Evaluation of Prioritized Skyline Queries	2015	SIGMOD	4.344689e-05
12,085	eSkyline: Processing Skyline Queries over Encrypted Data	2013	VLDB	4.1905499e-05
12,312	Minimizing the Communication Cost for Continuous Skyline Maintenance	2009	SIGMOD	4.1905499e-05
12,359	A Fair Assignment Algorithm for Multiple Preference Queries	2009	VLDB	4.1905499e-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.00029962961
386	Shooting Stars in the Sky: An Online Algorithm for Skyline Queries	2002	VLDB	0.00024740283
746	An Optimal and Progressive Algorithm for Skyline Queries	2003	SIGMOD	0.00017212135
2,351	Multi-objective Query Processing for Database Systems	2004	VLDB	8.9836468e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
746	An Optimal and Progressive Algorithm for Skyline Queries	2003	SIGMOD	0.00017212135
10,925	Optimal (Multiway) Spatial Joins	2024	PODS	4.1905499e-05
2,351	Multi-objective Query Processing for Database Systems	2004	VLDB	8.9836468e-05
6,568	Efficient Parallel Skyline Processing using Hyperplane Projections	2011	SIGMOD	5.0020592e-05
1,499	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00011643887
2,911	A Scalable Algorithm for Maximizing Range Sum in Spatial Databases	2012	VLDB	7.9273624e-05
5,708	Scalable Skyline Computation Using Object-based Space Partitioning	2009	SIGMOD	5.3629476e-05
9,753	Minimum Coresets for Maxima Representation of Multidimensional Data	2021	PODS	4.2856385e-05
5,113	Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative	2017	SIGMOD	5.6827696e-05
5,320	On Finding Skylines in External Memory	2011	PODS	5.5677544e-05