Streaming Temporal Graphs: Subgraph Matching
| Autor: | Dirk Grunwald, Eric L. Goodman |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
Source lines of code Matching (graph theory) Discrete Mathematics (cs.DM) Computer science 02 engineering and technology Parallel computing Node (computer science) NetFlow 0202 electrical engineering electronic engineering information engineering Code (cryptography) Throughput (business) 020203 distributed computing Computer Science - Programming Languages Hardware_MEMORYSTRUCTURES business.industry Aggregate (data warehouse) Graph Computer Science - Distributed Parallel and Cluster Computing Analytics Benchmark (computing) 020201 artificial intelligence & image processing Distributed Parallel and Cluster Computing (cs.DC) business Computer Science - Discrete Mathematics Programming Languages (cs.PL) |
| Zdroj: | IEEE BigData |
| DOI: | 10.48550/arxiv.2004.00215 |
| Popis: | We investigate solutions to subgraph matching within a temporal stream of data. We present a high-level language for describing temporal subgraphs of interest, the Streaming Analytics Language (SAL). SAL programs are translated into C++ code that is run in parallel on a cluster. We call this implementation of SAL the Streaming Analytics Machine (SAM). SAL programs are succinct, requiring about 20 times fewer lines of code than using the SAM library directly, or writing an implementation using Apache Flink. To benchmark SAM we calculate finding temporal triangles within streaming netflow data. Also, we compare SAM to an implementation written for Flink. We find that SAM is able to scale to 128 nodes or 2560 cores, while Apache Flink has max throughput with 32 nodes and degrades thereafter. Apache Flink has an advantage when triangles are rare, with max aggregate throughput for Flink at 32 nodes greater than the max achievable rate of SAM. In our experiments, when triangle occurrence was faster than five per second per node, SAM performed better. Both frameworks may miss results due to latencies in network communication. SAM consistently reported an average of 93.7% of expected results while Flink decreases from 83.7% to 52.1% as we increase to the maximum size of the cluster. Overall, SAM can obtain rates of 91.8 billion netflows per day. Comment: Big Data 2019 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|