Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces a patch descriptor retrieval method that achieves exact nearest neighbor search while significantly reducing the number of evaluations needed, utilizing a deterministic approach that guarantees consistent results across different runs. The method leverages Hierarchical Normalization (HN) to decompose feature vectors, allowing for efficient pruning of the search space and maintaining high accuracy with minimal full evaluations. Experimental results demonstrate impressive speed-ups of up to 13.7x over traditional brute-force methods, with only a small fraction of entries requiring complete evaluation, showcasing the method's practicality for large-scale applications.
Achieving exact nearest neighbor retrieval with 13.7x speed-up over brute-force methods while ensuring deterministic results could revolutionize how we approach large-scale search tasks.
We present a patch descriptor retrieval method that returns the exact nearest neighbour -- provably identical to exhaustive full-vector search -- while evaluating only a small fraction of the database, and does so deterministically: the same (database, query) pair always produces the same result, independent of run order, thread count, or hardware. This contrasts with approximate nearest-neighbour (ANN) approaches such as HNSW and IVF-PQ, which trade exactness for speed and may return different results across runs. The enabling mechanism is Hierarchical Normalization (HN): a normalisation scheme that splits the pre-normalisation feature vector into a K-dim major component (norm sqrt(1-alpha)) and a (128-K)-dim minor component (norm sqrt(alpha)). Since the minor inner product is bounded by alpha (Cauchy-Schwarz on the prescribed norms), the major similarity plus alpha is an admissible upper bound on the full similarity: the search scans the K-dim major component for all entries, then applies full 128-dim evaluation only to entries that cannot be pruned -- a provably exact branch-and-bound scan. We train HN-modified HardNet on the notredame split of the UBC patch dataset and evaluate on trevi and halfdome. With a cache-optimised Structure-of-Arrays layout and K=8, alpha=1/32, the search achieves 13.7x (trevi) / 12.7x (halfdome) speed-up over brute-force 128-dim search, with only 0.4% of entries requiring full evaluation. At K=16, alpha=1/8, FPR@95 rises from 0.0062 to 0.0064 on trevi at 7.2x speed-up, with 98.8% of entries bypassing full evaluation.