GPU-Based Graph Matching for Accelerating Similarity Assessment in Process-Oriented Case-Based Reasoning. Hoffmann, M., Malburg, L., Bach, N., & Bergmann, R. In Keane, M. T. & Wiratunga, N., editors, Case-Based Reasoning Research and Development - 30th International Conference, ICCBR 2022, Nancy, France, September 12-15, 2022, Proceedings, volume 13405, of Lecture Notes in Computer Science, pages 240–255, 2022. Springer. ![GPU-Based Graph Matching for Accelerating Similarity Assessment in Process-Oriented Case-Based Reasoning [pdf]](https://bibbase.org/img/filetypes/pdf.svg "pdf")
Paper doi abstract bibtex 11 downloads In Process-Oriented Case-Based Reasoning (POCBR), determining the similarity between cases represented as semantic graphs often requires some kind of inexact graph matching, which generally is an NP-hard problem. Heuristic search algorithms such as A* search have been successfully applied for this task, but the computational performance is still a limiting factor for large case bases. As related work shows a great potential for accelerating A* search by using GPUs, we propose a novel approach called AMonG for efficiently computing graph similarities with an A* graph matching process involving GPU computing. The three-phased matching process distributes the search process over multiple search instances running in parallel on the GPU. We develop and examine different strategies within these phases that allow to customize the matching process adjusted to the problem situation to be solved. The experimental evaluation compares the proposed GPU-based approach with a pure CPU-based one. The results clearly demonstrate that the GPU-based approach significantly outperforms the CPU-based approach in a retrieval scenario, leading to an average speedup factor of 16.
@inproceedings{hoffmann_gpu_astar_2022,
title = {{GPU-Based Graph Matching for Accelerating Similarity Assessment in Process-Oriented Case-Based Reasoning}},
author = {Maximilian Hoffmann and Lukas Malburg and Nico Bach and Ralph Bergmann},
year = 2022,
booktitle = {Case-Based Reasoning Research and Development - 30th International Conference, {ICCBR} 2022, Nancy, France, September 12-15, 2022, Proceedings},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = 13405,
pages = {240--255},
doi = {10.1007/978-3-031-14923-8\_16},
url = {http://www.wi2.uni-trier.de/shared/publications/2022_ICCBR__A_Star_GPU.pdf},
editor = {Mark T. Keane and Nirmalie Wiratunga},
abstract = {In Process-Oriented Case-Based Reasoning (POCBR), determining the similarity between cases represented as semantic graphs often requires some kind of inexact graph matching, which generally is an NP-hard problem. Heuristic search algorithms such as A* search have been successfully applied for this task, but the computational performance is still a limiting factor for large case bases. As related work shows a great potential for accelerating A* search by using GPUs, we propose a novel approach called AMonG for efficiently computing graph similarities with an A* graph matching process involving GPU computing. The three-phased matching process distributes the search process over multiple search instances running in parallel on the GPU. We develop and examine different strategies within these phases that allow to customize the matching process adjusted to the problem situation to be solved. The experimental evaluation compares the proposed GPU-based approach with a pure CPU-based one. The results clearly demonstrate that the GPU-based approach significantly outperforms the CPU-based approach in a retrieval scenario, leading to an average speedup factor of 16.}
}
Downloads: 11
{"_id":"rJCWquopCKp8HEm8c","bibbaseid":"hoffmann-malburg-bach-bergmann-gpubasedgraphmatchingforacceleratingsimilarityassessmentinprocessorientedcasebasedreasoning-2022","author_short":["Hoffmann, M.","Malburg, L.","Bach, N.","Bergmann, R."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","title":"GPU-Based Graph Matching for Accelerating Similarity Assessment in Process-Oriented Case-Based Reasoning","author":[{"firstnames":["Maximilian"],"propositions":[],"lastnames":["Hoffmann"],"suffixes":[]},{"firstnames":["Lukas"],"propositions":[],"lastnames":["Malburg"],"suffixes":[]},{"firstnames":["Nico"],"propositions":[],"lastnames":["Bach"],"suffixes":[]},{"firstnames":["Ralph"],"propositions":[],"lastnames":["Bergmann"],"suffixes":[]}],"year":"2022","booktitle":"Case-Based Reasoning Research and Development - 30th International Conference, ICCBR 2022, Nancy, France, September 12-15, 2022, Proceedings","publisher":"Springer","series":"Lecture Notes in Computer Science","volume":"13405","pages":"240–255","doi":"10.1007/978-3-031-14923-8_16","url":"http://www.wi2.uni-trier.de/shared/publications/2022_ICCBR__A_Star_GPU.pdf","editor":[{"firstnames":["Mark","T."],"propositions":[],"lastnames":["Keane"],"suffixes":[]},{"firstnames":["Nirmalie"],"propositions":[],"lastnames":["Wiratunga"],"suffixes":[]}],"abstract":"In Process-Oriented Case-Based Reasoning (POCBR), determining the similarity between cases represented as semantic graphs often requires some kind of inexact graph matching, which generally is an NP-hard problem. Heuristic search algorithms such as A* search have been successfully applied for this task, but the computational performance is still a limiting factor for large case bases. As related work shows a great potential for accelerating A* search by using GPUs, we propose a novel approach called AMonG for efficiently computing graph similarities with an A* graph matching process involving GPU computing. The three-phased matching process distributes the search process over multiple search instances running in parallel on the GPU. We develop and examine different strategies within these phases that allow to customize the matching process adjusted to the problem situation to be solved. The experimental evaluation compares the proposed GPU-based approach with a pure CPU-based one. The results clearly demonstrate that the GPU-based approach significantly outperforms the CPU-based approach in a retrieval scenario, leading to an average speedup factor of 16.","bibtex":"@inproceedings{hoffmann_gpu_astar_2022,\n\ttitle = {{GPU-Based Graph Matching for Accelerating Similarity Assessment in Process-Oriented Case-Based Reasoning}},\n\tauthor = {Maximilian Hoffmann and Lukas Malburg and Nico Bach and Ralph Bergmann},\n\tyear = 2022,\n\tbooktitle = {Case-Based Reasoning Research and Development - 30th International Conference, {ICCBR} 2022, Nancy, France, September 12-15, 2022, Proceedings},\n\tpublisher = {Springer},\n\tseries = {Lecture Notes in Computer Science},\n\tvolume = 13405,\n\tpages = {240--255},\n\tdoi = {10.1007/978-3-031-14923-8\\_16},\n\turl = {http://www.wi2.uni-trier.de/shared/publications/2022_ICCBR__A_Star_GPU.pdf},\n\teditor = {Mark T. Keane and Nirmalie Wiratunga},\n\tabstract = {In Process-Oriented Case-Based Reasoning (POCBR), determining the similarity between cases represented as semantic graphs often requires some kind of inexact graph matching, which generally is an NP-hard problem. Heuristic search algorithms such as A* search have been successfully applied for this task, but the computational performance is still a limiting factor for large case bases. As related work shows a great potential for accelerating A* search by using GPUs, we propose a novel approach called AMonG for efficiently computing graph similarities with an A* graph matching process involving GPU computing. The three-phased matching process distributes the search process over multiple search instances running in parallel on the GPU. We develop and examine different strategies within these phases that allow to customize the matching process adjusted to the problem situation to be solved. The experimental evaluation compares the proposed GPU-based approach with a pure CPU-based one. The results clearly demonstrate that the GPU-based approach significantly outperforms the CPU-based approach in a retrieval scenario, leading to an average speedup factor of 16.}\n}\n","author_short":["Hoffmann, M.","Malburg, L.","Bach, N.","Bergmann, R."],"editor_short":["Keane, M. T.","Wiratunga, N."],"key":"hoffmann_gpu_astar_2022","id":"hoffmann_gpu_astar_2022","bibbaseid":"hoffmann-malburg-bach-bergmann-gpubasedgraphmatchingforacceleratingsimilarityassessmentinprocessorientedcasebasedreasoning-2022","role":"author","urls":{"Paper":"http://www.wi2.uni-trier.de/shared/publications/2022_ICCBR__A_Star_GPU.pdf"},"metadata":{"authorlinks":{}},"downloads":11},"bibtype":"inproceedings","biburl":"https://web.wi2.uni-trier.de/publications/WI2Publikationen.bib","dataSources":["vtdjwAo6eNiqRLfnG","CnwPa99ZchEF4SZgh","j2fC6S9dR4Pu3hmnz","nZxfXH3fRFhwWejKL","MSp3DzP4ToPojqkFy","J3orK6zvpR7d8vDmC"],"keywords":[],"search_terms":["gpu","based","graph","matching","accelerating","similarity","assessment","process","oriented","case","based","reasoning","hoffmann","malburg","bach","bergmann"],"title":"GPU-Based Graph Matching for Accelerating Similarity Assessment in Process-Oriented Case-Based Reasoning","year":2022,"downloads":11}