Indeksy wyuczone na danych; najnowsze wyniki

Speaker(s)

Jakub Pawlewicz

Affiliation

MIMUW

Date

Feb. 29, 2024, 12:15 p.m.

Room

room 4060

Seminar

Seminarium "DeSeR: Dane, strumienie, rozpraszanie"

---

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.

---