Please use this identifier to cite or link to this item:
|Title:||Efficient algorithms for generalized subgraph query processing||Authors:||Bhowmick, Sourav S.
|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
|DOI:||http://dx.doi.org/10.1145/2396761.2396805||Rights:||© 2012 ACM.||metadata.item.grantfulltext:||none||metadata.item.fulltext:||No Fulltext|
|Appears in Collections:||SCSE Conference Papers|
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.