2016/05/19 by Kimmo Fredriksson, Fredriksson, Kimmo
Computer Science · #68P05 #68P20 #Advanced Image and Video Retrieval Techniques #Computational Geometry (cs.CG) #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Retrieval (cs.IR) #Video Analysis and Summarization #cs.CG #cs.DS #cs.IR #msc:68P05 #msc:68P20
paper · pdf · doi:10.48550/arxiv.1605.05944
Minor changes, submitted to Pattern Recognition Letters
openalex publication_date 2016/05/19 · arxiv created 2016/05/20 · arxiv updated 2016/05/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Geometric Near-neighbor Access Tree (GNAT) is a metric space indexing method based on hierarchical hyperplane partitioning of the space. While GNAT is very efficient in proximity searching, it has a bad reputation of being a memory hog. We show that this is partially based on too coarse analysis, and that the memory requirements can be lowered while at the same time improving the search efficiency. We also show how to make GNAT memory adaptive in a smooth way, and that the hyperplane partitioning can be replaced with ball partitioning, which can further improve the search performance. We conclude with experimental results showing the new methods can give significant performance boost.