Trading Memory versus Workload Overhead in Graph Pattern Matching on Multiprocessor Systems
Research output: Contribution to book/Conference proceedings/Anthology/Report › Conference contribution › Contributed › peer-review
Contributors
Abstract
Graph pattern matching (GPM) is a core primitive in graph analysis with many applications. Efficient processing of GPM on modern NUMA systems poses several challenges, such as an intelligent storage of the graph itself or keeping track of vertex locality information. During query processing, intermediate results need to be communicated, but target partitions are not always directly identifiable, which requires all workers to scan for requested vertices. To optimize this performance bottleneck, we introduce a Bloom filter based workload reduction approach and discuss the benefits and drawbacks of different implementations. Furthermore, we show the trade-offs between invested memory and performance gain, compared to fully redundant storage.
Details
Original language | English |
---|---|
Title of host publication | DATA 2019 - Proceedings of the 8th International Conference on Data Science, Technology and Applications |
Editors | Slimane Hammoudi, Christoph Quix, Jorge Bernardino |
Publisher | SCITEPRESS - Science and Technology Publications |
Pages | 400-407 |
Number of pages | 8 |
ISBN (electronic) | 9789897583773 |
Publication status | Published - 2019 |
Peer-reviewed | Yes |
Conference
Title | 8th International Conference on Data Science, Technology and Applications, DATA 2019 |
---|---|
Duration | 26 - 28 July 2019 |
City | Prague |
Country | Czech Republic |
External IDs
dblp | conf/data/KrauseEHL19 |
---|---|
ORCID | /0000-0001-8107-2775/work/142253492 |
Keywords
ASJC Scopus subject areas
Keywords
- Bloom Filter, Graph Processing, In-memory, Multiprocessor System, NUMA