Cost Estimation of Spatial k-Nearest-Neighbor Operators
Ahmed M. Aly, Walid G. Aref, Mourad Ouzzani · Movebank · 2015
Advances in geo-sensing technology have led to an unprecedented spread of location-aware devices. In turn, this has resulted into a plethora of location-based services in which huge amounts of spa- tial data need to be efficiently consumed by spatial query proces- sors. For a spatial query processor to properly choose among the various query processing strategies, the cost of the spatial operators has to be estimated. In this paper, we study the problem of estimat- ing the cost of the spatialk-nearest-neighbor (k-NN, for short) op- erators, namely,k-NN-Select andk-NN-Join. Given a query that has ak-NN operator, the objective is to estimate the number of blocks that are going to be scanned during the processing of this operator. Estimating the cost of ak-NN operator is challenging for several reasons. For instance, the cost of ak-NN-Select operator is directly affected by the value ofk, the location of the query focal point, and the distribution of the data. Hence, a cost model that captures these factors is relatively hard to realize. This paper in- troduces cost estimation techniques that maintain a compact set of cataloginformation that can be kept in main-memory to enable fast estimation via lookups. A detailed study of the performance and accuracy trade-off of each proposed technique is presented. Ex- perimental results using real spatial datasets from OpenStreetMap demonstrate the robustness of the proposed estimation techniques.