Graph mönster matchning har blivit en rutinprocess i nya tillämpningar såsom sociala nätverk. I praktiken är ett datadiagram typiskt stort och uppdateras ofta med små förändringar. Det är ofta oöverkomligt dyrt att räkna om matcher från grunden via satsalgoritmer när grafen uppdateras. Med detta kommer behovet av inkrementella algoritmer som beräknar förändringar i matcherna som svar på uppdateringar, för att minimera onödig omräkning. Detta papper undersöker inkrementella algoritmer för graf mönster matchning definieras i termer av graf simulering, begränsad simulering och subgraph isomorfism. (1) För simulering tillhandahåller vi inkrementella algoritmer för enhetsuppdateringar och vissa grafmönster. Dessa algoritmer är optimala: i linjär tid i storleken på förändringarna i input och output, som kännetecknar den kostnad som är inneboende i själva problemet. För allmänna mönster visar vi att det inkrementella matchningsproblemet är obundet, dvs. dess kostnad bestäms inte enbart av storleken på förändringarna. (2) För begränsad simulering visar vi att problemet är obundet även för enhetsuppdateringar och vägmönster. (3) För subgraph isomorfism visar vi att problemet är intractable och obunden för enhetsuppdateringar och vägmönster. (4) För flera uppdateringar utvecklar vi en inkrementell algoritm för varje simulering, begränsad simulering och subgraph isomorfism. Vi experimentellt verifiera att dessa inkrementella algoritmer avsevärt överträffar sina batch motsvarigheter som svar på små förändringar, med hjälp av verkliga data och syntetiska data.
Den studie som presenteras i REF undersöker inkrementell al gorithms för simulering, begränsad simulering och subgraph isomorfism.
Incremental graph pattern matching
{'venue': "SIGMOD '11", 'journal': None, 'mag_field_of_study': ['Computer Science']}