Indeksowanie grafów

Speaker(s)

Łukasz Puławski

Date

March 15, 2013, 2:15 p.m.

Room

room 5820

Seminar

Research Seminar of the Logic Group: Approximate reasoning in data mining

---

Grafy sa stosowane jako modele zjawisk badanych w bardzo wielu
obszarach nauki. Dlatego metody efektywnego wyszukiwania roznych
wzorcow strukturalnych w grafach maja ogromne znaczenie praktyczne.
Jednym z podstawowych problemow jest przeszukiwanie baz danych grafow
pod katem wystpienia w nich wzorca rozumianego jako zadany podgraf.
Z punktu widzenia zlozonosci obliczeniowej czescia tego zgadnienia
jest problem SUBGRAPH-ISOMORPHISM - problem NP-zupelny, dlatego tez
bardzo istotne sa metody heurystyczne pozwalajace  znalezc chocby
przyblizone rozwiazanie.

W moim referacie omowie *indeksowanie grafow*  -  pewna klase metod,
ktore pozwalaja w sposob heurystyczny przyblizac zbior grafow,
zawierajaacych zadany podgraf.  Istnieje pewna analogia miedzy
indeksami w relacyjnej bazie danych a indeksami w bazie grafow. Tak
jak w relacyjnej bazie indeks pozwala ogranicyc liczbe blokow
niezbednych do przeczytania aby odpowiedziec na zadane zapytanie, tak
indeks w bazie grafow pozwala ograniczyc liczbe grafow, w ktorych
nalezy szukac wzorca. 

---