Efficient incremental query processing via vantage point filtering in dynamic multi-dimensional index structures

Efficient query processing in multi-dimensional indexing structures is an i mportant issue for multimedia data applications. In this paper, we propose incremental k-nearest neighbor query (k-NNQ) and range query algorithms for R-tree based structures. The novel aspect of these algorithms is that they make use of the notion of VP filtering, a concept borrowed from the MVP-tr ee. The filtering notion allows for delaying of computational overhead unti l absolutely necessary. By so doing, we attain considerable performance ben efits while paying insignificant overhead during the construction of the in dex structure. We implemented our algorithms and carried out experiments to demonstrate the capability and usefulness of our method. Results show that improvements range from 8% to 23% in response time for the experimental en vironment that we considered.