Finding Multidimensional Constraint Reachable Paths for Attributed Graphs

EAI Endorsed Transactions on Scalable Information Systems

article

Bhargavi B.¹  K. Swarupa Rani¹  Arunjyoti Neog² 

[1] University of Hyderabad;Cognizant Technology Solutions

关键词: hashing;    attributed graph;    matrix factorization;    constraint reachability;   

DOI  :  10.4108/eetsis.v9i4.2581

学科分类：社会科学、人文和艺术（综合）

来源: Bern Open Publishing

【 摘 要 】

A graph acts as a powerful modelling tool to represent complex relationships between objects in the big data era. Given two vertices, vertex and edge constraints, the multidimensional constraint reachable ( MCR) paths problem finds the path between the given vertices that match the user-specified constraints. A significant challenge is to store the graph topology and attribute information while constructing a reachability index. We propose an optimized hashing-based heuristic search technique to address this challenge while solving the multidimensional constraint reachability queries. In the proposed technique, we optimize hashing and recommend an efficient clustering technique based on matrix factorization. We further extend the heuristic search technique to improve the accuracy. We experimentally prove that our proposed techniques are scalable and accurate on real and synthetic datasets. Our proposed extended heuristic search technique is able to achieve an average execution time of 0.17 seconds and 2.55 seconds on MCR true queries with vertex and edge constraints for Robots and Twitter datasets respectively.

【 授权许可】

CC BY