Roberto Bosio
Subgraph isomorphism acceleration on FPGAs using High-Level Synthesis.
Rel. Luciano Lavagno, Mihai Teodor Lazarescu. Politecnico di Torino, Corso di laurea magistrale in Ingegneria Informatica (Computer Engineering), 2022
|
Preview |
PDF (Tesi_di_laurea)
- Tesi
Licenza: Creative Commons Attribution Non-commercial No Derivatives. Download (1MB) | Preview |
Abstract
Subgraph isomorphism (or subgraph matching) is a well-known NP-hard problem that consists of searching all the distinct embeddings of a query graph in a large data graph. It has a wide range of applications, almost in all the domains in which graph patterns reveal valuable information, especially in social network analysis, chemical compound search, and computer-aided design. Due to the relevance of the problem, starting from 1970, several algorithms have been proposed, most of which adopt a backtracking approach by recursively mapping query vertices to data vertices. However, due to the intrinsic properties of graph computations, such as irregular communication patterns and little spatial and temporal locality, these algorithms cannot be easily accelerated in hardware.
An alternative approach to address the problem consists of seeing the query graph as a multiway join between relations, which are the edges, and where the vertices are the attributes
Relatori
Anno Accademico
Tipo di pubblicazione
Numero di pagine
Corso di laurea
Classe di laurea
URI
![]() |
Modifica (riservato agli operatori) |
