As a hyper-parameter, alter_ratio can be enumerated and tuned for applications to achieve the best performance. It is also common to have no prior knowledge of the query constraints, i.e., no pre-tuning can be applied. In this section, we derive a low-overhead heuristic algorithm to estimate alter_ratio. Intuitively, alter_ratio should be positively correlated with the clusterness of satisfied vectors: The more clustered satisfied vectors, the larger alter_ratio should be. In the extreme case when all satisfied vectors are distributed in the same region and no unsatisfied vectors are within this region, alter_ratio should be 1 to obtain the optimal performance, as we do not need to explore unsatisfied vectors. Here, we adapt the concept of k-nearest-neighbor statistics [1]} as the estimation of alter_ratio. With a given constraint \(f\)  and a collection of satisfied vectors from the samples (\(SSV\) ), our estimation of alter_ratio is:
\(\frac{1}{|SSV|}\sum _{v \in SSV}{ \frac{|{\lbrace v^{\prime } | f(v^{\prime })=\texttt {true} \hspace{2.84544pt} \forall v^{\prime } \in \textit {top-k\_neighbor}(v)\rbrace }|}{k} }\) 
