Memory-Efficient Sequential Pattern Mining with Hybrid Tries
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913447576338432 |
|---|---|
| author | Hosseininasab, Amin van Hoeve, Willem-Jan Cire, Andre A. |
| author_facet | Hosseininasab, Amin van Hoeve, Willem-Jan Cire, Andre A. |
| contents | This paper develops a memory-efficient approach for Sequential Pattern Mining (SPM), a fundamental topic in knowledge discovery that faces a well-known memory bottleneck for large data sets. Our methodology involves a novel hybrid trie data structure that exploits recurring patterns to compactly store the data set in memory; and a corresponding mining algorithm designed to effectively extract patterns from this compact representation. Numerical results on small to medium-sized real-life test instances show an average improvement of 85% in memory consumption and 49% in computation time compared to the state of the art. For large data sets, our algorithm stands out as the only capable SPM approach within 256GB of system memory, potentially saving 1.7TB in memory consumption. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2202_06834 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Memory-Efficient Sequential Pattern Mining with Hybrid Tries Hosseininasab, Amin van Hoeve, Willem-Jan Cire, Andre A. Databases Artificial Intelligence Data Structures and Algorithms Machine Learning This paper develops a memory-efficient approach for Sequential Pattern Mining (SPM), a fundamental topic in knowledge discovery that faces a well-known memory bottleneck for large data sets. Our methodology involves a novel hybrid trie data structure that exploits recurring patterns to compactly store the data set in memory; and a corresponding mining algorithm designed to effectively extract patterns from this compact representation. Numerical results on small to medium-sized real-life test instances show an average improvement of 85% in memory consumption and 49% in computation time compared to the state of the art. For large data sets, our algorithm stands out as the only capable SPM approach within 256GB of system memory, potentially saving 1.7TB in memory consumption. |
| title | Memory-Efficient Sequential Pattern Mining with Hybrid Tries |
| topic | Databases Artificial Intelligence Data Structures and Algorithms Machine Learning |
| url | https://arxiv.org/abs/2202.06834 |