On the estimation of the number of desired records with respect to a given query

Abstract

The importance of the estimation of the number of desired records for a given query is outlined. Two algorithms for the estimation in the “closest neighbors problem” are presented. The numbers of operations of the algorithms are Ο ( ml 2 ) and Ο ( ml ), where m is the number of clusters and l is the “length” of the query.