Learned indexing in high-dimensional data

Computers model the human ability to compare objects by applying mathematical measures to their digital representations. This provides the foundation for similarity search, a process that identifies objects most closely resembling a given search example. Current large and complex data places huge demands on similarity search systems. Somewhat counterintuitively, the more details the description of objects includes (that is, the more features they have), the less reliable similarity measures become. Additionally, these methods are forced to sacrifice the quality of the answers due to speed and memory constraints. For several decades, similarity search systems have addressed these challenges using advancements in fields such as statistics, signal processing, and graph theory. These techniques power similarity search indexes that organize data and quickly locate relevant objects. Despite the possibility for optimization toward various objectives and the ability to capture complex patterns, machine learning has not contributed significantly to indexing yet. This thesis explores the potential of applying machine learning to similarity searching through a standalone learned index. The research presented in this work focuses on redefining indexing and retrieval through machine learning operations, comparing this index with state-of-the-art similarity indexes in two conference competitions, and crucially, addressing its scalability and dynamicity to reflect the needs of modern data collections. The subsequent line of work examines the index under production-level needs of a real-world scientific similarity task: identifying similar proteins in the PDB and AlphaFold Database. Finally, the thesis highlights other promising directions of integrating machine learning into searching that remain open for further exploration.

Paper