You are not logged in | Log in

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.