MoVie: A scalable algorithm for answering graph pattern query using incremental views

摘要

In recent years, modeling data in graph structure became evident and effective for processing huge operational data in some of the prominent application areas like social analytics, health care analytics, scientific analytics etc. The key sources of massively scaled data are petascale simulations, experimental devices, the internet and scientific applications. Therefore, graphs are pervasive in such large scale analytics, facing new challenges of data: size, heterogeneity, uncertainty and quality. Moreover, there is a demand to adapt graph querying techniques for analyzing these large data graphs. Graph pattern matching is one of them. Traditional, pattern matching approaches are based on inherent isomorphism and simulation in graphs and for real life applications many of them either fail to capture the structure/semantic similarity or constant modifications with small updates in real life application based data graphs. In response to these challenges, we propose `Match on Views, MoVie', a scalable algorithm that revises traditional notions to characterize graph pattern match on views `Incremental Views'. It is experimentally observed that, `MoVie' improves query answering via pattern matching significantly over static and dynamic data graph, as compared to some of the traditional approaches such as isomorphism, simulation, view based.