Diagramdata har blivit allmänt förekommande och att manipulera dem på grundval av likhet är viktigt för många tillämpningar. Grafredigeringsavstånd är en av de mest accepterade åtgärderna för att fastställa likheter mellan grafer och har omfattande tillämpningar inom områdena mönsterigenkänning, datorseende etc. Tyvärr är problemet med grafredigering avståndsberäkning NP-Hard i allmänhet. I det här dokumentet introducerar vi därför tre nya metoder för att beräkna de övre och nedre gränserna för redigeringsavståndet mellan två grafer i polynomtid. Genom att tillämpa dessa metoder introduceras två algoritmer AppFull och AppSub för att utföra olika typer av grafsökning på grafdatabaser. Omfattande experimentella studier utförs på både verkliga och syntetiska dataset för att undersöka olika aspekter av metoderna för att begränsa grafredigeringsavstånd. Resultat visar att dessa metoder uppnår god skalbarhet både när det gäller antalet grafer och storleken på grafer. Effektiviteten av dessa algoritmer bekräftar också nyttan av att använda våra gränser för filtrering och sökning av grafer.
Eftersom komplexiteten i att hitta den optimala lösningen för grafredigeringsavståndet är NP-hård REF, har många ungefärliga lösningar föreslagits.
Comparing Stars: On Approximating Graph Edit Distance
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}