0
$\begingroup$

Ilya R provides the following query complexity of ANN for Hamming distance based on coordinate sampling

https://www.ilyaraz.org/static/class_2018/files/20181023.pdf

When he says k point locations in #3 (see pic) does it mean the time for computing the hash of the query $q$? If yes then why does it say k point locations instead of k coordinates? Because I think the steps are :

  1. Using the sampled coordinates (pre-determined) hash the incoming query
  2. Scan through each point $p$ in the indexed hash bucket
  3. Perform an exact comparison to see if $p$ is an ANN

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.