PathFinder: Algorytmy ewaluacji zapytań w bazach grafowych

Prelegent(ci)

Piotr Ulanowski

Afiliacja

MIMUW

Język referatu

polski

Termin

22 października 2024 10:15

Pokój

p. 4060

Seminarium

Seminarium "DeSeR: Dane, strumienie, rozpraszanie"

---

Zapytania ścieżkowe są kluczową funkcjonalnością współczesnych języków zapytań grafowych, takich jak Cypher, SQL/PGQ i GQL. Te języki oferują bogaty zestaw funkcji do dopasowywania ścieżek, takich jak ograniczanie do określonych trybów ścieżek (shortest, simple, trail) oraz nakładanie ograniczeń na etykiety krawędzi wzdłuż ścieżki za pomocą wyrażeń regularnych. W tym referacie omówimy krótko zastosowania baz grafowych oraz przedstawimy semantykę zapytań, jakie się w nich stosuje. Następnie przejdziemy do algorytmów zaprezentowanych w pracy: https://arxiv.org/abs/2306.02194, które służą do wykonywania takich zapytań. Zaprezentujemy także możliwe usprawnienia algorytmów z wykorzystaniem heurystyk A* oraz algorytmy do znajdywania K-shortest paths i K-groups. Pokażemy również potencjalne zastosowanie IDDFS w znajdowaniu K-shortest paths. Na zakończenie zaprezentujemy benchmarki, które zostały wykonane na tych algorytmach.

---