Graph mönster matchning har använts i stor utsträckning i t.ex. social data analys. Ett antal matchande algoritmer har utvecklats som, med tanke på en graf mönster Q och en graf G, beräkna uppsättningen M (Q, G) av matcher av Q i G. Dessa algoritmer returnerar dock ofta ett alltför stort antal matcher, och är dyra på stora verkliga sociala grafer. Dessutom, i praktiken många sociala frågor är att hitta matchningar av en specifik mönster nod, snarare än hela M (Q, G). Detta papper studerar top-k graf mönster matchning. (1) Vi reviderar graf mönster matchning definieras i termer av simulering, genom att stödja en angiven output node uo. Eftersom G och Q, är det att hitta de noder i M (Q, G) som matchar uo, istället för den stora uppsättningen M (Q, G). (2) Vi studerar två kategorier av funktioner för att rangordna matcherna: relevansfunktioner δr() baserade på t.ex. social påverkan och avståndsfunktioner δ d () för att täcka olika element. (3) Vi utvecklar två algoritmer för att beräkna topp-k matcher av uo baserat på δr(), med den tidiga uppsägning egenskapen, dvs., de hittar topp-k matcher utan att beräkna hela M (Q, G). (4) Vi studerar också diversifierad top-k matchning, ett bi-criteria optimeringsproblem baserat på både δr() och δ d (). Vi visar att dess beslutsproblem är fullständigt. Icke desto mindre ger vi en approximationsalgoritm med prestandagarantier och en heuristisk med fastigheten för tidig uppsägning. (5) Med hjälp av verkliga och syntetiska data verifierar vi experimentellt att våra (diversifierade) toppk matchningsalgoritmer är effektiva och överträffar traditionella matchningsalgoritmer i effektivitet.
I REF presenterades en ungefärlig algoritm för top-k matchning med kapacitet för tidig uppsägning och dess tillämpning i samband med analys av sociala nätverk.
Diversified Top-k Graph Pattern Matching
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Mathematics', 'Computer Science']}