{"id":26982,"date":"2026-09-27T20:02:12","date_gmt":"2026-09-27T18:02:12","guid":{"rendered":"https:\/\/www.itspy.cz\/thesis\/temporally-dynamic-learned-index-for-similarity-search-overcomplex-data\/"},"modified":"2026-09-27T20:04:54","modified_gmt":"2026-09-27T18:04:54","slug":"temporally-dynamic-learned-index-for-similarity-search-overcomplex-data","status":"publish","type":"thesis","link":"https:\/\/www.itspy.cz\/en\/thesis\/temporally-dynamic-learned-index-for-similarity-search-overcomplex-data\/","title":{"rendered":"Temporally Dynamic Learned Index for Similarity Search over\nComplex Data"},"content":{"rendered":"<p>Approximate nearest neighbor (ANN) search over<br \/>\nhigh-dimensional vectors underpins modern retrieval,<br \/>\nrecommendation systems, and retrieval-augmented generation<br \/>\nfor large language models. In learned indexing, small<br \/>\nneural models direct each query to the relevant region of<br \/>\nthe dataset. On static collections, learned indexes are<br \/>\ncompetitive with other established methods. However, their<br \/>\nadvantage disappears in dynamic settings. As inserts and<br \/>\ndeletes accumulate, the data drifts away from the<br \/>\ndistribution on which the routing model was trained. Search<br \/>\naccuracy degrades, latency increases, and the standard<br \/>\nremedy\u2014retraining the model on the entire dataset\u2014becomes<br \/>\ncomputationally prohibitive past tens of millions of<br \/>\nvectors. Learned indexes thus remain restricted to static<br \/>\nsettings. To this end, we present a general framework that<br \/>\ndynamizes any learned index exposing a minimal static<br \/>\ninterface, by adapting the Bentley-Saxe decomposition to<br \/>\nANN search. Incoming vectors are absorbed into a small<br \/>\nin-memory buffer and migrated through compaction into a<br \/>\nsequence of static learned indexes (levels), each trained<br \/>\nonly on its own subset of the data. We develop multi-level<br \/>\nsearch strategies, one of which uses probability-normalized<br \/>\nscoring to resolve cross-level bucket incomparability,<br \/>\ncompaction mechanisms, rebuild policies for deletions, and<br \/>\nretraining strategies for managing distribution shift. We<br \/>\nalso introduce three diagnostic metrics that decompose<br \/>\nrecall loss into partitioning and routing quality<br \/>\ncomponents. We instantiate the framework as the Dynamic<br \/>\nLearned Index (DLI) using the Learned Metric Index as the<br \/>\ninternal static learned index, and evaluate it on several<br \/>\nlarge-scale datasets of up to 100M vectors. We study DLI&#8217;s<br \/>\nperformance under continuous insert\u2013delete cycles,<br \/>\ndistribution shift, and out-of-distribution queries,<br \/>\ncomparing it against HNSW, IVFFlat, and a periodically<br \/>\nretrained LMI. Based on the evaluation, DLI attains the<br \/>\nsmallest memory footprint\u2014over an order of magnitude<br \/>\nsmaller than HNSW\u2014while delivering balanced throughput<br \/>\nacross insert, delete, and search. This positions DLI as a<br \/>\nstrong candidate for unpredictable dynamic workloads, where<br \/>\ncurrent indexes each optimize one axis at the expense of<br \/>\nothers.<\/p>\n","protected":false},"featured_media":26728,"template":"","meta":{"_acf_changed":false,"_links_to":"","_links_to_target":""},"university":[462,461],"thesis-year":[466],"class_list":["post-26982","thesis","type-thesis","status-publish","has-post-thumbnail","hentry","thesis-year-466"],"acf":{"autor":"Emma Sommerov\u00e1","portret":"","vedouci":"RNDr. David Proch\u00e1zka"},"_links":{"self":[{"href":"https:\/\/www.itspy.cz\/en\/wp-json\/wp\/v2\/thesis\/26982","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.itspy.cz\/en\/wp-json\/wp\/v2\/thesis"}],"about":[{"href":"https:\/\/www.itspy.cz\/en\/wp-json\/wp\/v2\/types\/thesis"}],"version-history":[{"count":1,"href":"https:\/\/www.itspy.cz\/en\/wp-json\/wp\/v2\/thesis\/26982\/revisions"}],"predecessor-version":[{"id":27037,"href":"https:\/\/www.itspy.cz\/en\/wp-json\/wp\/v2\/thesis\/26982\/revisions\/27037"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.itspy.cz\/en\/wp-json\/wp\/v2\/media\/26728"}],"wp:attachment":[{"href":"https:\/\/www.itspy.cz\/en\/wp-json\/wp\/v2\/media?parent=26982"}],"wp:term":[{"taxonomy":"university","embeddable":true,"href":"https:\/\/www.itspy.cz\/en\/wp-json\/wp\/v2\/university?post=26982"},{"taxonomy":"thesis-year","embeddable":true,"href":"https:\/\/www.itspy.cz\/en\/wp-json\/wp\/v2\/thesis-year?post=26982"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}