A method for accelerating relations search over big data scenario
Lihua Liu, Mao Wang, Kaiming Xiao, Haiwen Chen · 2022
We propose an acceleration method for relations search over big data scenario. The relations search is in essence an induced subgraph search of graph data model, which is to search all edges with all adjacent vertices falling into a given vertex set. For example, in the risk-control scenario for anti-fraud, for a swindling gang of highly similar fraud behaviors, figuring out all relations between these swindlers can be greatly beneficial to precisely attack all similar gangs. In-memory induced subgraph search requires lots of random accesses, while in big data scenario, relations data tend to be stored on disk when the memory is limited, and the corresponding random lookups over disk incorporate huge overhead. Also, even a singleton disk access could be costly since there are usually many properties data in a relation. Hence, existing methods would suffer considerable performance bottlenecks when applied over data on disk. We build graph over disk-based edge index, and propose multiple BFS (Bread First Search) level gaps based induces subgraph acceleration method, with efficient performance guarantee when the memory is limited. We avoid imbalance in performance for query evaluation with edge index based data organization, with which we further reduce redundant I/O accesses. We filter most invalid no-result edge queries based our BFS level gaps framework. We find that, for each BFS, we can confirm the no edge status between a pair of vertices if their BFS accessing level are of distance more than 1, which indicates the nonexistence of edge. Extensive experiments over real world graph datasets confirm the effectiveness of our method. We find that more than 97% invalid edge queries are filtered by our method, which greatly improve the system performance. Hence, our method with multiple BFS level gap encoding over vertices could greatly filter no-result edge queries and improve the relation search performance. Out method also reduce the redundant I/O access over disk with performance stability guarantee.