Partitioning Large-Scale Property Graph for Efficient Distributed Query Processing
Haohan Pang, Peng Gan, Pingpeng Yuan, Hai Jin, Qiang-Sheng Hua · 2019
Recently, many communities have published their domain knowledge in the form of graphs. A significant trend is that the relations between pairs of nodes in the graph have become so complex that these data can be treated as property graphs. Complex properties imply semantic constraints which can distinguish elements of property graph into different semantic-related aspects. If the property graph can be partitioned according to these aspects, cross-partition communication would be reduced when evaluating SPARQL queries, for the reason that a query can often be evaluated in a single aspect. Conventional graph partition methods, however, pay little attention to semantic constraints in property graphs. To solve this problem, we propose a new property graph partition method for query optimization. First, we propose the property semantic reachable path as basic partition element, with which to capture the semantic-related aspects in a property graph. Second, to combine paths into partitions, we develop a space-efficient algorithm which merges vertices rather than entire paths. Extensive experiments over representative property graph data confirm the effectiveness of our semantic awareness approach. The performance of our approach is comparable with leading competitors, in terms of load balance, data redundancy, and network overhead.