Trading Memory versus Workload Overhead in Graph Pattern Matching on Multiprocessor Systems

Research output: Contribution to book/Conference proceedings/Anthology/ReportConference contributionContributedpeer-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 languageEnglish
Title of host publicationDATA 2019 - Proceedings of the 8th International Conference on Data Science, Technology and Applications
EditorsSlimane Hammoudi, Christoph Quix, Jorge Bernardino
PublisherSCITEPRESS - Science and Technology Publications
Pages400-407
Number of pages8
ISBN (electronic)9789897583773
Publication statusPublished - 2019
Peer-reviewedYes

Conference

Title8th International Conference on Data Science, Technology and Applications, DATA 2019
Duration26 - 28 July 2019
CityPrague
CountryCzech Republic

External IDs

dblp conf/data/KrauseEHL19
ORCID /0000-0001-8107-2775/work/142253492

Keywords

Keywords

  • Bloom Filter, Graph Processing, In-memory, Multiprocessor System, NUMA