Implicit Landmark Path Indexing for Bounded Label Constrained Reachable Paths
Bhargavi B1, K Swarupa Rani2
1Bhargavi B, School of Computer and Information Sciences, University of Hyderabad, Hyderabad, India.
2K Swarupa Rani, School of Computer and Information Sciences, University of Hyderabad, Hyderabad, India.
Manuscript received on November 11, 2019. | Revised Manuscript received on November 20 2019. | Manuscript published on 30 November, 2019. | PP: 10660-10669 | Volume-8 Issue-4, November 2019. | Retrieval Number: D4273118419/2019©BEIESP | DOI: 10.35940/ijrte.D4273.118419
Open Access | Ethics and Policies | Cite | Mendeley | Indexing and Abstracting
© The Authors. Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC-BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
Abstract: In today’s Big Data era, a graph is an essential tool that models the semi-structured or unstructured data. Graph reachability with vertex or edge constraints is one of the basic queries to extract useful information from the graph data. From the graph reachability with constraints, we obtained the information about the existence of a path between the given two vertices satisfying the vertex or edge constraints. The problem of Label Constraint Reachability (LCR) found the existence of a path between the two given vertices such that the edge-labels along the path are the subset of the given edge-label constraint. We extended the LCR queries by considering weighted directed graphs and proposed a novel technique of finding paths for LCR queries bounded by path weight. We termed these paths as bounded label constrained reachable paths (BLCRP). We extended the landmark path indexing technique [1] by incorporating the implicit paths which satisfy the user constraints but need not satisfy the minimality of edge label sets. We solved the BLCRP by using the extended landmark path indexing and BFS based query processing. We addressed the following challenges through our proposed technique of implicit landmark path indexing in the problem of BLCRP that included (1) the need to handle exponential number of edge label combinations with an additional total path weight constraint, and (2) the need to discover a technique that finds exact reachable paths between the given vertices. This problem could be applied to real network scenarios like road networks, social networks, and protein-protein interaction networks. Our experiments and statistical analysis revealed the accuracy and efficiency of the proposed approach tested on synthetic and real datasets.
Keywords: Constraint Reachability, Label Constraint, Landmark Vertex, Weighted Directed Graph.
Scope of the Article: Computer Graphics, Simulation, and Modelling.