Hierarchical Encoding of Sequential Data With Compact and Sub-Linear Storage Cost

Snapshot-based visual localization is an important problem in several computer vision and robotics applications such as Simultaneous Localization And Mapping (SLAM). To achieve real-time performance in very large-scale environments with massive amounts of training and map data, techniques such as approximate nearest neighbor search (ANN) algorithms are used. While several state-of-the-art variants of quantization and indexing techniques have been demonstrated to be efficient in practice, their theoretical memory cost still scales at least linearly with the training data (i.e., O(n) where n is the number of observations in the database), since each observation must be associated with at least one code vector. To address these limitations, we present a novel hierarchical encoding approach that enables sub-linear storage for sequential data, e.g. ordered frames in a video sequence commonly used in visual localization datasets. The algorithm exploits the widespread sequential nature of sensor information streams in robotics and autonomous vehicle applications and achieves, both theoretically and experimentally, sub-linear scalability in storage required for a given environment size. Furthermore, the associated query time of our algorithm is also of sub-linear complexity. We benchmark the performance of the proposed algorithm on several real-world benchmark datasets and experimentally validate the sub-linearity of our approach, while also showing that our approach yields competitive absolute storage performance as well.