Spatial Skyline Queries: An Efficient Geometric Algorithm

Wanbin Son, Mu-Woong Lee, Hee-Kap Ahn, Seung-won Hwang

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.

The relationship between spatial locations (left) and the resulting distance-based skyline space (right).

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.

Illustration of geometric dominance using perpendicular bisectors between points relative to the query space.

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

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.
BibTeX
@inproceedings{son2009spatial,
  author = {Wanbin Son and Mu-Woong Lee and Hee-Kap Ahn and Seung-won Hwang},
  title = {{Spatial Skyline Queries: An Efficient Geometric Algorithm}},
  booktitle = {SSTD},
  year = {2009},
  url = {https://openreview.net/forum?id=-ETkMzs2LS7},
}
Figure