Fast thresholding of high dimensional Euclidean distances using binary squaring

摘要

This paper presents a new approximative method to threshold Euclidean distances. The procedure utilizes so called binary squares, which will be introduced and formally put into relation to conventional square computations. The proposed method can significantly speed up distance matching. The speed gain depends on several parameters, like dimension count (the higher the better), total distances and the percentage of distances outside of the desired thresholded area. In the worst case its running time degenerates to the running time of conventional square based computation. The method is essentially presented for integer coordinates, but can - to a certain degree - be applied to floating point coordinates as well. Though being an approximation method the results diverge from the correct results only by a small margin in most cases.