Graph pattern matching is widely used in big data applications. However, real-world graphs are usually huge and dynamic. A small\nchange in the data graph or pattern graph could cause serious computing cost. Incremental graph matching algorithms can avoid\nrecomputing on the whole graph and reduce the computing cost when the data graph or the pattern graph is updated. The existing\nincremental algorithm PGC IncGPM can effectively reduce matching time when no more than half edges of the pattern graph are\nupdated. However, as the number of changed edges increases, the improvement of PGC IncGPM gradually decreases. To solve this\nproblem, an improved algorithm iDeltaP IncGPM is developed in this paper. For multiple insertions (resp., deletions) on pattern\ngraphs, iDeltaP IncGPM determines the nodes� matching state detection sequence and processes them together. Experimental\nresults show that iDeltaP IncGPM has higher efficiency and wider application range than PGC IncGPM.
Loading....