A Cost Model for Reverse Nearest Neighbor Query Processing on R-trees Using Self Pruning
Felix Borutta, Peer Kröger and Matthias Renz
In this short paper, we propose the first cost model for a class of index structures designed for reverse nearest neighbor (RNN) search, so-called self pruning approaches. These approaches use estimations of the nearest neighbor distances of database objects for pruning. We will particularly detail our cost model for R-Trees but our concepts can easily applied to any tree-like index structure that implements a self pruning strategy. Our cost model estimates the number of disk accesses of a given RNN query and, thus, allows to predict the required I/O costs in any hardware environment. We further explore three variants regarding the trade-off between estimation accuracy and model efficiency/storage overhead. Preliminary experiments on synthetic data confirm that the estimations are accurate compared to the exact query costs.
