Accelerating subgraph isomorphism search using graphlets

By transitioning from static heuristics to dynamic adaptability, this approach achieves runtime improvements of up to 1.54 times across diverse datasets. The second contribution introduces OrbitSI, a heuristic algorithm. OrbitSI accelerates the SI search process by exploiting the local topological properties of both the data and pattern graphs during preprocessing.

By enforcing stricter preprocessing constraints based on local structures, OrbitSI drastically reduces the viable search space and eliminates redundant computations. Evaluations demonstrate that OrbitSI outperforms state-of-the-art baselines, delivering speedups ranging from 2.69 to 11.49 times on various datasets. The final contribution addresses the need for rapid topological profiling by introducing the NI-ORCA algorithm.

Profiling the local structures around vertices is a prerequisite for many graph analytics algorithms, including OrbitSI. NI-ORCA studies parallelisation techniques to efficiently distribute computational workloads across multiple processing units. This yields massive improvements in scalability and execution time, achieving speedups of up to 60 times.<br><br>Together, these three contributions form a framework that improves the efficiency, scalability, and adaptability of Subgraph Isomorphism search in modern graph analytics.