Indeksy wyuczone na danych; najnowsze wyniki

Prelegent(ci)

Jakub Pawlewicz

Afiliacja

MIMUW

Termin

29 lutego 2024 12:15

Pokój

p. 4060

Seminarium

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.

---