sis 22(1): e8

Research Article

Finding Multidimensional Constraint Reachable Paths for Attributed Graphs

Download112 downloads
  • @ARTICLE{10.4108/eetsis.v9i4.2581,
        author={Bhargavi  B. and K. Swarupa Rani and Arunjyoti Neog},
        title={Finding Multidimensional Constraint Reachable Paths for Attributed Graphs},
        journal={EAI Endorsed Transactions on Scalable Information Systems},
        keywords={hashing, attributed graph, matrix factorization, constraint reachability},
  • Bhargavi B.
    K. Swarupa Rani
    Arunjyoti Neog
    Year: 2022
    Finding Multidimensional Constraint Reachable Paths for Attributed Graphs
    DOI: 10.4108/eetsis.v9i4.2581
Bhargavi B.1, K. Swarupa Rani1,*, Arunjyoti Neog2
  • 1: University of Hyderabad
  • 2: Cognizant Technology Solutions, India
*Contact email:


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.