Stratified Graph Indexing for Efficient Search in Deep Descriptor Databases

Abstract Searching for unseen objects in extensive visual archives is challenging, demanding efficient indexing methods that can support meaningful similarity retrievals. This research paper presents the Stratified Graph (SG) approach for indexing similar deep descriptors by sorting them into distance-sensitive layers. The indexing algorithm incrementally constructs a bi-directional m-nearest neighbor graph within each layer, with additional 1-nearest neighbor links from outer layers, providing a distant scaling property in the graph structure. The search process starts from the innermost layer, and the same layer neighbors enhance Average Recall (AR), while the distant scaling property enhances search speed, maintaining logarithmic complexity scaling. We compare and contrast SG with six state-of-the-art retrieval methods in four deep-descriptor and two classical-descriptor databases, and we show that the SG indexing and search has smaller memory usage (up to four times) and the Mean Average Precision and AR improve up to 8% over state-of-art for all six datasets at five retrieval depths.