Cost Models for Learned Index with Insertions
Authors
Nielsen, Per Hedegaard ; Bilgram, Rasmus Vraa
Term
4. term
Education
Publication year
2019
Abstract
This thesis examines how insertions affect learned index structures that use machine learning models for lookups. We develop cost models that estimate when models in a Recursive Model Index (RMI) should be retrained and whether a learned index is suitable in a given setting, including a threshold on how many insertions can be tolerated before binary search is expected to offer faster lookups. Drawing on ideas from query optimization, we pair estimates with continuously updated statistics and assume a standalone system with a growing dataset. We also analyze the structure and implement optimizations to improve both insertion and lookup efficiency. Finally, we evaluate using synthetic data distributions to study distribution shifts and training effects, and we argue that overfitting can make learned indexes less susceptible to insertions—an observation that contrasts with conventional machine learning goals of generalization. Deletions and updates are out of scope.
Dette speciale undersøger, hvordan indsættelser påvirker learned index-strukturer, der anvender maskinlæringsmodeller til opslag. Vi udvikler omkostningsmodeller, som estimerer, hvornår modeller i et Recursive Model Index (RMI) bør retrænes, og om en learned index-løsning er hensigtsmæssig i et givent miljø, herunder en tærskel for, hvor mange indsættelser der kan håndteres, før binær søgning forventes at være hurtigere ved opslag. Med inspiration fra forespørgselsoptimering kobler vi estimater med løbende statistikopdateringer og antager et standalone-system med et voksende datasæt. Vi analyserer også strukturen og implementerer optimeringer, der forbedrer effektiviteten for både indsættelser og opslag. Endelig evaluerer vi med syntetiske datadistributioner for at undersøge fordelingens ændringer og træningseffekter, og vi argumenterer for, at overfitting kan gøre learned indexes mindre følsomme over for indsættelser—en observation, der står i kontrast til gængse mål om generalisering i maskinlæring. Sletninger og opdateringer behandles ikke.
[This apstract has been generated with the help of AI directly from the project full text]