Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/97963
Title: Efficient algorithms for generalized subgraph query processing
Authors: Bhowmick, Sourav S.
Cheng, James
Lin, Wenqing
Xiao, Xiaokui
Keywords: DRNTU::Engineering::Computer science and engineering
Issue Date: 2012
Source: Lin, W., Xiao, X., Cheng, J., & Bhowmick, S. S. (2012). Efficient algorithms for generalized subgraph query processing. Proceedings of the 21st ACM international conference on Information and knowledge management.
Abstract: We study a new type of graph queries, which injectively maps its edges to paths of the graphs in a given database, where the length of each path is constrained by a given threshold specified by the weight of the corresponding matching edge. We give important applications of the new graph query and identify new challenges of processing such a query. Then, we devise the cost model of the branch-and-bound algorithm framework for processing the graph query, and propose an efficient algorithm to minimize the cost overhead. We also develop three indexing techniques to efficiently answer the queries online. Finally, we verify the efficiency of our proposed indexes with extensive experiments on large real and synthetic datasets.
URI: https://hdl.handle.net/10356/97963
http://hdl.handle.net/10220/12302
DOI: 10.1145/2396761.2396805
Rights: © 2012 ACM.
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SCSE Conference Papers

Google ScholarTM

Check

Altmetric

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.