Octopus: Efficient Hypergraph Pattern Mining with Practical Processing-in-Memory Architecture
Open Access
- 18 May 2026
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 4 (3) , 1-27
Abstract
\noindent Hypergraph pattern mining (HPM) is a key analytical primitive for discovering higher-order relationships in complex data. Despite decades of algorithmic progress, existing systems remain far from saturating available compute resources, as the memory-bound and irregular nature of hypergraph workloads severely constrains sustained throughput. Our empirical characterization shows that even state-of-the-art (SOTA) HPM systems achieve only a small fraction of their theoretical peak performance on real workloads. In this paper, we propose Octopus, the first full-stack hardware-software co-designed system for accelerating HPM on practical processing-in-memory (PIM) hardware. Octopus targets UPMEM, an emerging commercially available PIM platform that integrates thousands of lightweight in-memory compute units within standard DRAM modules. To fully exploit UPMEM's massive parallelism and bandwidth potential while addressing its stringent architectural constraints, Octopus introduces two tightly integrated components: (i) an inter-DPU coordination framework that orchestrates compact data partitioning and balanced workload distribution across thousands of DPUs, and (ii) an intra-DPU mining engine that enables efficient hyperedge-level candidate generation and asynchronous multithreaded execution. We evaluate Octopus on a real UPMEM platform using diverse real-world hypergraph workloads. Experimental results demonstrate up to 55.37×, 19.80×, 1033.89×, and 795.08× speedups over SOTA solutions HGMatch, OHMiner, Pangolin, and PimPam, respectively.Keywords
This publication has 16 references indexed in Scilit:
- Exploring the DIMM PIM Architecture for Accelerating Time Series AnalysisIEEE Computer Architecture Letters, 2025
- Accelerating RNA-Seq Quantification on a Real Processing-in-Memory SystemIEEE Transactions on Computers, 2025
- Analysis of Data Transfer Bottlenecks in Commercial PIM Systems: A Study With UPMEM-PIMIEEE Computer Architecture Letters, 2024
- Benchmarking a New Paradigm: Experimental Analysis and Characterization of a Real Processing-in-Memory SystemIEEE Access, 2022
- Accelerating Graph Convolutional Networks Using Crossbar-based Processing-In-Memory Architectures2022
- Efficient subhypergraph matching based on hyperedge featuresIEEE Transactions on Knowledge and Data Engineering, 2022
- A hypergraph-based context-sensitive representation technique for VHR remote-sensing image change detectionInternational Journal of Remote Sensing, 2016
- Arabesque2015
- Hypergraph querying using structural indexing and layer-related-closure verificationKnowledge and Information Systems, 2015
- Hypergraph imaging: an overviewPattern Recognition, 2002