Exact and Deterministic Patch Descriptor Retrieval via Hierarchical Normalization

Koichi Sato · 2026

Read Exact and Deterministic Patch Descriptor Retrieval via Hierarchical Normalization by Koichi Sato (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-27280.txt.

Description

Sato presents a patch descriptor search that returns provably exact nearest neighbours while checking only a sliver of the database. Image patches are matched by descriptor vectors, and exhaustive search over every vector is slow. Approximate indexes run faster but can return different answers across runs. Hierarchical Normalization splits each feature vector into a major part and a minor part with prescribed sizes. The minor part's contribution is bounded, giving a safe upper bound on full similarity, in a retrieval paper published in 2026.

Search scans the cheap major part for all entries, then fully scores only entries that cannot be pruned. A layout tuned for processor caches adds practical speed. Speed-ups pass thirteenfold on one benchmark split, with under half a percent of entries needing full scoring in the reported setting. The recommended gentler setting still prunes nearly everything while barely moving error rates.

Catalog record

CREATORKoichi Sato
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE34 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.27280

Browse the full library · About the Tower of Babel