In many situations, users would readily accept an aporximate query result if evaluation of the query becomes faster. In this article, we investigate approximate evaluation techniques based o nthe VA-File for Nearest-neighbor Search (NN-Search). The VA-file contains approximations of feature points. These paproximations frequently suffice to eliminate the vast majority of points in a first phase. Then, a second phase identifes the NN by computing exact distances of all remaining points. To develop approximate query-evaluation techniques, we proceed in two steps: first, we derive an analytic model for VA-File based NN-search. This is to investigate the relationship between approximation granularity, effectiveness of the filtering step and search performance. In more detail, we develop formulae for the distribution of the error of the bounds and the duration of the different phases of query evalaution. Based on these results, we develop differnet approximate query evaluation techniques. The first one adapts the bounds to have a more rigid filtering, the second one skips computation of the exact distances. Experiments show that these techniques have the desired effect: for instance, when allowing for a small but specific reduction of result quality, we observed a speedup of 7 in 50-NN search.
展开▼
