Learned Metric Index — Proposition of learned indexing for unstructured data. Issue 100 (September 2021)

• Record Type: Journal Article
• Authors: Antol, Matej; Ol'ha, Jaroslav; Slanináková, Terézia; Dohnal, Vlastislav
• Is Part Of: Information systems. Issue 100(2021)
• Publication Date: 2021-09
• Subjects: Index structures -- Learned index -- Unstructured data -- Content-based search -- Metric space; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2021.101774
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: The main paradigm of similarity searching in metric spaces has remained mostly unchanged for decades — data objects are organized into a hierarchical structure according to their mutual distances, using representative pivots to reduce the number of distance computations needed to efficiently search the data. We propose an alternative to this paradigm, using machine learning models to replace pivots, thus posing similarity search as a classification problem, which stands in for numerous expensive distance computations. Even a relatively naïve implementation of this idea is more than competitive with state-of-the-art methods in terms of speed and recall, proving the concept as viable and showing great potential for its future development. Graphical abstract: Highlights: A novel approach for searching in unstructured data which exploits machine learning. Proposal interconnects learned models into a single index structure. Searching is re-framed as a classification problem instead of computing distances. The proof-of-concept implementation shows more than competitive performance. Numerous promising directions for the future enhancements are outlined.