2015/09/11 by Luisa Verdoliva, Verdoliva, Luisa, Davide Cozzolino +3
Computer Science · #Advanced Image and Video Retrieval Techniques #Computer Vision and Pattern Recognition (cs.CV) #FOS: Computer and information sciences #Video Analysis and Summarization #Video Surveillance and Tracking Methods
paper · pdf · doi:10.48550/arxiv.1509.03453
openalex publication_date 2015/09/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We propose a new algorithm for fast approximate nearest neighbor search based\non the properties of ordered vectors. Data vectors are classified based on the\nindex and sign of their largest components, thereby partitioning the space in a\nnumber of cones centered in the origin. The query is itself classified, and the\nsearch starts from the selected cone and proceeds to neighboring ones. Overall,\nthe proposed algorithm corresponds to locality sensitive hashing in the space\nof directions, with hashing based on the order of components. Thanks to the\nstatistical features emerging through ordering, it deals very well with the\nchallenging case of unstructured data, and is a valuable building block for\nmore complex techniques dealing with structured data. Experiments on both\nsimulated and real-world data prove the proposed algorithm to provide a\nstate-of-the-art performance.\n