for i in 1..m
{
     p = Ci(vq)
     lookup (i,p) in Index
     fetch (i,p',j)
     while p' "close to" p on curve i
     {
          collect next (i,p',j) as candidate
     }
}
for each candidate j
{
     lookup j in Db
     fetch (j,vj)
     d = D(vj , vq)
     include j in k-NN if d small enough
}

Cost   =   2T_open  +  mT_sel  +  NfT_P  +  NfT_D

where

• T_sel is the cost of Index lookup using e.g. B-tree

• f is the filtering factor