Det är vanligt att hitta grafer med miljontals noder och miljarder kanter i t.ex. sociala nätverk. Frågor på sådana grafer är ofta oöverkomligt dyra. Dessa motiverar oss att föreslå frågebevarande grafkompression, att komprimera grafer i förhållande till en klass Q frågor av användarnas val. Vi beräknar en liten G r från en graf G så att (a) för alla frågor Q  med Q, Q(G) = Q (Gr), där Q kan beräknas effektivt från Q; och (b) alla algoritmer för att beräkna Q(G) kan användas direkt för att utvärdera Q på Gr som är. Det vill säga, även om vi inte kan minska komplexiteten i att utvärdera graffrågor, vi minskar datagrafer samtidigt som svaren på alla frågor i Q. För att verifiera effektiviteten av detta tillvägagångssätt, (1) utvecklar vi komprimeringsstrategier för två klasser av frågor: nåbarhet och graf mönster frågor via (begränsad) simulering. Vi visar att grafer effektivt kan komprimeras genom en nåbarhet ekvivalens förhållande respektive graf bisimulation, samtidigt som frågesvaren bevaras. (2) Vi tillhandahåller tekniker för att upprätthålla komprimerad graf G r som svar på förändringar ΔG till den ursprungliga grafen G. Vi visar att de inkrementella underhållsproblem är obundna för de två klasserna av frågor, d.v.s., deras kostnader är inte en funktion av storleken på ΔG och förändringar i G r. Icke desto mindre utvecklar vi inkrementella algoritmer som endast beror på ΔG och G r, oberoende av G, d.v.s. behöver vi inte dekompressera G r för att sprida förändringarna. (3) Med hjälp av verkliga data verifierar vi experimentellt att våra kompressionstekniker kan reducera grafer i genomsnitt med 95% för räckvidd och 57% för grafmönstermatchning, och att våra inkrementella underhållsalgoritmer är effektiva.
Fläkt et al. REF föreslår frågebevarande grafkompression som behåller likvärdiga frågeresultat på två särskilda frågeklasser.
Query preserving graph compression
{'venue': 'SIGMOD Conference', 'journal': None, 'mag_field_of_study': ['Computer Science']}