Indeksy wyuczone na danych; najnowsze wyniki

Mając dany niemalejący ciąg liczb S = {x_1, ..., x_n}, chcemy odpowiadać na pytania, gdzie wpadłby nowy klucz k: |{x \in S | x < k}|. Zakładamy, że S jest ustalone raz, a my chcemy przygotować strukturę.

Standardowym podejściem są B-drzewa, bądź interpolation-search. Ten ostatni, przy odpowiednich realnych założeniach o danych działa w czasie O(log log n).

Najnowsze podejścia polegają na analizie S próbując interpolować dystrybucję kumulacyjną. Opowiem o kilku podejściach przez uczenie maszynowe, otoczki wypukłe do indeksów kubełkowych i naszych pomysłów.

Praca wspólna z Adamem Karczmarzem i Piotrem Sankowskim.