Inverse Queries For Multidimensional Spaces
Lists
Only you see this
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 {\em 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.
BibTeX
@misc{bernecker2011inverse,
author = {Thomas Bernecker and Tobias Emrich and Hans-Peter Kriegel and Nikos Mamoulis and Matthias Renz and Shiming Zhang and Andreas Züfle},
title = {{Inverse Queries For Multidimensional Spaces}},
year = {2011},
eprint = {1103.0172},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/1103.0172},
}| Indexing Reverse Top-k Queries | arXiv · 2012 |
| Reverse k-skyband query based on reuse technology | Proceedings of the 2nd International Conference on Computer Science and Electronics Engineering (iccsee 2013) · 2013 |
| Grid-Index Algorithm for Reverse Rank Queries | Edbt · 2017 |
| A Unified Framework for Efficiently Processing Ranking Related Queries | Edbt · 2014 |
| Eclipse: Practicability Beyond 1NN and Skyline | arXiv · 2017 |
| Reverse Nearest Neighbors Search in High Dimensions using Locality-Sensitive Hashing | arXiv · 2010 |