On Nonlinear Learned String Indexing

Paolo Ferragina

doi:10.1109/ACCESS.2023.3295434

On Nonlinear Learned String Indexing

2023-01-01

6

OA

AI

Giosuè Cataldo Marinò

G

Giorgio Vinciguerra *

DOI：10.1109/ACCESS.2023.3295434

Original

Original request for help

Save

Abstract

En 中文

We investigate the potential of several artificial neural network architectures to be used as an index on a sorted set of strings, namely, as a mapping from a query string to (an estimate of) its lexicographic rank in the set, which allows solving some interesting string-search operations such as range and prefix searches. Our evaluation on a variety of real and synthetic datasets shows that learned models can beat the space vs error trade-off of the classic (possibly compressed) trie-based solutions for relatively dense datasets only, while being slower to be trained and queried. This leads us to conclude that learned models are not yet competitive with classic trie-based solutions, and thus cannot completely replace them, but possibly only integrate them. Although our study does not settle the question conclusively, it highlights appropriate methods, provides a baseline for comparison, and introduces several open problems, thereby serving as a starting point for future research.

Keywords:

String dictionaries

string search

prefix search

tries

neural networks

machine learning

data structures

learned indexes

On Nonlinear Learned String Indexing

Abstract

Journal

Organization