About | Contact Us | Register | Login
ProceedingsSeriesJournalsSearchEAI
sis 22(1): e8

Research Article

Finding Multidimensional Constraint Reachable Paths for Attributed Graphs

Download648 downloads
Cite
BibTeX Plain Text
  • @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},
        volume={10},
        number={1},
        publisher={EAI},
        journal_a={SIS},
        year={2022},
        month={8},
        keywords={hashing, attributed graph, matrix factorization, constraint reachability},
        doi={10.4108/eetsis.v9i4.2581}
    }
    
  • Bhargavi B.
    K. Swarupa Rani
    Arunjyoti Neog
    Year: 2022
    Finding Multidimensional Constraint Reachable Paths for Attributed Graphs
    SIS
    EAI
    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: swarupacs@uohyd.ac.in

Abstract

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.

Keywords
hashing, attributed graph, matrix factorization, constraint reachability
Received
2021-11-07
Accepted
2022-08-04
Published
2022-08-22
Publisher
EAI
http://dx.doi.org/10.4108/eetsis.v9i4.2581

Copyright © 2022 Bhargavi B. et al., licensed to EAI. This is an open access article distributed under the terms of the Creative Commons Attribution license, which permits unlimited use, distribution and reproduction in any medium so long as the original work is properly cited.

EBSCOProQuestDBLPDOAJPortico
EAI Logo

About EAI

  • Who We Are
  • Leadership
  • Research Areas
  • Partners
  • Media Center

Community

  • Membership
  • Conference
  • Recognition
  • Sponsor Us

Publish with EAI

  • Publishing
  • Journals
  • Proceedings
  • Books
  • EUDL