Abstract
As more data-intensive applications emerge, advanced retrieval semantics, such as ranking or skylines, have attracted attention. Geographic information systems are such an application with massive spatial data. Our goal is to efficiently support skyline queries over massive spatial data. To achieve this goal, we first observe that the best known algorithm VS2, despite its claim, may fail to deliver correct results. In contrast, we present a simple and efficient algorithm that computes the correct results. To validate the effectiveness and efficiency of our algorithm, we provide an extensive empirical comparison of our algorithm and VS2 in several aspects.
Introduction
Imagine you are traveling to a new city and want to book a hotel. You prioritize proximity to two specific locations: the airport and your conference venue. A "spatial skyline query" identifies all hotels that are not "spatially dominated" by any other hotel. A hotel is dominated if there is another candidate that is closer to both the airport and the venue.
While algorithms exist for general skyline queries, spatial data possesses unique geometric properties. The previously established state-of-the-art for this problem was the Voronoi-based Spatial Skyline Algorithm ($VS^2$). However, this research identifies a critical flaw in $VS^2$: its pruning heuristic incorrectly assumes that if all of a point's Voronoi neighbors are dominated, the point itself must be dominated. This paper provides a geometric counter-example proving this assumption false, meaning $VS^2$ can fail to return valid skyline points.
The EnhancedSpatialSkyline (ES) Algorithm
To address the inaccuracies of the baseline, we propose the EnhancedSpatialSkyline (ES) algorithm. This approach shifts the problem from algebraic distance comparisons to purely geometric tests, utilizing the Convex Hull of the query points ($CH(Q)$) and the Voronoi diagram of the data points ($P$).
Geometric Dominance Test
Instead of calculating numerical distances to every query point, the ES algorithm utilizes a geometric property: two data points do not dominate each other if and only if their perpendicular bisector intersects the interior of the Convex Hull of the query points ($CH(Q)$). This allows for a fast binary search for line intersections, significantly reducing computational overhead.
Seed Skylines and Search Pruning
The algorithm leverages "seed skylines"—data points whose Voronoi cells intersect or are contained within $CH(Q)$. These points are mathematically guaranteed to be part of the skyline. By traversing the Delaunay graph around $CH(Q)$, the ES algorithm can identify these seeds immediately without expensive dominance tests. These seeds then define a bounding box that drastically prunes the remaining search space.
Experimental Evaluation
The algorithm was evaluated using both synthetic datasets (up to 1 million points) and a real-world dataset of 104,770 Points of Interest in California.
Key results include:
- Accuracy: ES is mathematically proven to return the complete set of spatial skyline points, correcting the omissions found in $VS^2$.
- Performance: ES outperforms a corrected version of $VS^2$ by an order of magnitude in response time.
- Efficiency: By finding seed skylines "for free" and using the fast bisector test, ES minimizes both CPU cycles and I/O operations (random accesses to the R*-tree index).
Conclusion and Future Work
By translating algebraic dominance into geometric intersection tests, the ES algorithm achieves superior efficiency and guaranteed accuracy. While currently optimized for 2D Euclidean space, the underlying theorems generalize to higher dimensions. Future research will focus on adapting these geometric principles to urban road networks, where distances are constrained by routing and infrastructure rather than straight-line Euclidean geometry.
Summary updated