NON LINEAR K-VECTOR Conference Paper uri icon


  • The k-vector search technique is a general purpose search method that is capable of locating entries in a sorted array with complexity independent from the database size. It is based on an m-long vector of integers, called the k-vector, that keeps record of the sorted database nonlinearities. The traditional k-vector best performs for almost linear sorted databases. In this paper we extend the k-vector technique by the use of non-linear mapping functions, and show how this approach can potentially solve performance and memory limitations of the traditional k-vector for searches in arrays with strongly non-uniform distributions.

author list (cited authors)

  • Fialho, M., & Mortari, D.

publication date

  • January 2017