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


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


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.