k-vector range searching techniques
Academic Article
Overview
Additional Document Info
View All
Overview
abstract
Various k-vector range searching techniques are presented here. These methods accomplish the range search by taking advantage of an n-long vector of integers, called the k-vector, to avoid the search phase and, thus, to minimize the search time. The price is increased memory requirement for the k-vector allocation. However, it is possible to balance the extra memory required and the speed attained by choosing a step parameter h which samples the k-vector. The proposed method is compared with the well known "binary search" technique, and demonstrates a high speed gain rate (from 10 to more than 50 times). The application of the k-vector technique to dynamic databases (when entries can be deleted or inserted), is also presented. Then, the general two-level k-vector technique, for piecewise linear data distributions, is presented. Finally, just to show one of the wide-range possible applications, a two-level k-vector technique is applied to compute the arcsin function, by means of a look-up table approach.
