Abstract
Traditional spatial queries return, for a given query object $q$, all database objects that satisfy a given predicate, such as epsilon range and $k$-nearest neighbors. This paper defines and studies inverse spatial queries, which, given a subset of database objects $Q$ and a query predicate, return all objects which, if used as query objects with the predicate, contain $Q$ in their result. We first show a straightforward solution for answering inverse spatial queries for any query predicate. Then, we propose a filter-and-refinement framework that can be used to improve efficiency. We show how to apply this framework on a variety of inverse queries, using appropriate space pruning strategies. In particular, we propose solutions for inverse epsilon range queries, inverse $k$-nearest neighbor queries, and inverse skyline queries. Our experiments show that our framework is significantly more efficient than naive approaches.
Introduction
In traditional spatial databases, queries are typically centered around a single point of interest. For example, a user might ask for all restaurants within a 5-mile radius (an $\epsilon$-range query) or the three closest gas stations (a $k$-nearest neighbor query). Reverse queries flip this perspective, identifying which query points would include a specific object in their results.
This paper introduces Inverse Spatial Queries (IQ), a powerful generalization of reverse queries. Instead of a single object, an IQ takes a set of objects $Q$ as input and finds all locations in space that, if used as a query point, would return the entire set $Q$ in their result set. This has significant applications in market analysis, recommendation systems, and logistics, where one might want to find potential customer locations for a specific bundle of products.
The Inverse Query Framework
Solving inverse queries by simply intersecting the results of multiple reverse queries is computationally expensive and redundant. To address this, the authors propose a high-performance filter-and-refinement framework designed to prune the search space efficiently:
- Query-Based Validation: A preliminary check to see if a solution is even possible. For instance, in an Inverse $k$-NN query, if the size of the target set $Q$ is greater than $k$, the result set is immediately known to be empty.
- Query-Based Pruning: This stage uses the geometric properties of the set $Q$ to define a candidate region. For example, in an Inverse $\epsilon$-Range query, any valid query point must lie within the intersection of spheres of radius $\epsilon$ centered at each object in $Q$.
- Object-Based Pruning: This stage leverages other objects in the database to further narrow down candidates. For Inverse $k$-NN, the authors utilize the convex hull of $Q$ to dismiss distant points quickly.
- Refinement: The final stage where candidate points are verified against the full database to ensure they meet the query criteria.
Specific Inverse Query Types
Inverse $\epsilon$-Range Queries (I$\epsilon$-RQ)
In an I$\epsilon$-RQ, we seek all points $p$ such that every object $q \in Q$ is within distance $\epsilon$ of $p$. Geometrically, this means $p$ must reside in the intersection of all circles (or hyperspheres) of radius $\epsilon$ centered at each $q \in Q$.
Inverse $k$-Nearest Neighbor Queries (I$k$-NNQ)
An I$k$-NNQ finds all points $p$ for which the set $Q$ is a subset of $p$'s $k$ nearest neighbors. This is more complex than range queries because the "boundary" for inclusion depends on the density of other objects in the database.
Experimental Evaluation
The framework was tested against synthetic datasets (up to 5D) and a real-world dataset of the North American road network. The researchers compared their Multi-Query Filtering (MQF) approach against a "Naive" approach (intersecting separate reverse queries).
Key findings include:
- Efficiency: MQF consistently required 50% to 80% fewer page accesses than the Naive method, as it avoids redundant index traversals.
- Scalability: Unlike the Naive approach, which slows down linearly as the size of $Q$ increases, MQF often becomes faster because a larger $Q$ creates tighter geometric constraints, allowing for more aggressive pruning.
- Dimensionality: The framework remains robust in higher dimensions, where the volume of valid result intersections typically shrinks, aiding the pruning process.
Conclusion
The Inverse Query framework provides a robust and efficient method for complex spatial searches. By shifting from individual object analysis to set-based geometric pruning, the authors demonstrate significant performance gains over traditional intersection methods. Future work may extend these concepts to top-$k$ preference queries and scenarios involving negative constraints.
Summary updated