On the estimation of the number of desired records with respect to a given query
C. Yu, Wo-Shun Luk, Man‐Keung Siu · ACM Transactions on Database Systems · 1978
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.