Graph streaming algorithms - CS 591 K1: Data Stream Processing and Analytics Spring 2020

• 语言: 英语
• 格式: .pdf
• 来源: vasia.github.io

摘要

The document discusses graph streaming algorithms, focusing on their application in data stream processing and analytics. It covers various graph stream models, including edge events and vertex events, and their challenges in real-world unbounded streams. The document also introduces the vertex-centric model, where vertices communicate through messages, and addresses computations in streaming dataflow engines. Additionally, it explores graph analytics, such as handling continuously generated graphs, iterative computation, and one-pass graph synopses.

AI总结

《Graph streaming algorithms - CS 591 K1: Data Stream Processing and Analytics Spring 2020》课程 materials 提供了关于图流算法的概述、模型和相关挑战的详细介绍。以下是文档的核心内容和关键信息的总结：

---

### 课程信息
- **课程名称**: Data Stream Processing and Analytics (数据流处理与分析)
- **授课老师**: Vasiliki (Vasia) Kalavri
- **开课时间**: Spring 2020
- **主题**: 图流（Graph Streaming）

### 图流的基本概念
- **图流模型**: 图流将交互或事件表示为更新底层图结构的流。图流可以分为：
- **边事件（Edge Events）**: 表示边的插入或删除，例如购买记录、评分、点赞等。
- **顶点事件（Vertex Events）**: 表示顶点的添加，例如新产品、用户注册等。
- **动态变化的图**: 图的状态随时间变化，边的事件流可以是插入-only或完全动态（允许插入和删除）。
- **持续更新**: 每个时间戳 `t`，图的状态由 `G(t) = (V(t), E(t))` 表示，新增边或删除边会更新顶点集和边集。

---

### 图流处理的挑战
1. **实时计算**: 如何在边或顶点事件流中实时计算图的性质（如连通分量、距离、主题）？
2. **单次遍历**: Whether we can compute graph analytics in one pass without storing the entire graph.
3. **迭代计算**: 如何在流数据引擎中进行迭代计算？例如，如何处理水印（watermarks）以同步迭代步骤？
4. **图摘要**: 是否可以通过图摘要或总结来高效计算图分析结果？

---

### 分布式图流处理
1. **顶点中心模型**: 从单个顶点的视角进行计算，顶点通过消息传递与其他顶点通信，计算在同步迭代步骤中进行。
2. **基于 Flink 的数据并行流处理**: 如何在分布式流处理框架（如 Apache Flink）中实现图流处理。
3. **图分区**: 如何在大规模分布式图中进行高效的流分区。

---

### 图流算法的实际应用
- **社会网络分析**: 例如，朋友关系、粉丝数。
- **Web 网络**: 页面之间的链接关系。
- **交通网络**: 例如，城市之间的交通路线。
- **事务网络**: 截止、电影演员与电影的关联关系。

---

### 关键问题与解决方案
1. **连通分量**: 如何在实时流中计算图的连通分量？
2. **三角形计数**: 如何在图流中高效计数本地和全局三角形？
3. **动态图的存储与处理**: 如何在固定内存大小下处理动态图的三角形计数问题？

---

### 参考文献
1. McGregor, Andrew. "Graph stream algorithms: a survey." ACM SIGMOD Record 43.1 (2014).
2. Stanton, Isabelle, and Gabriel Kliot. "Streaming graph partitioning for large distributed graphs." ACM SIGKDD, 2012.
3. Stefani, Lorenzo De, et al. "Triest: Counting local and global triangles in fully dynamic streams with fixed memory size." TKDD 2017.

---

### 总结
图流处理是大数据时代的重要研究方向，涉及如何在动态变化的图结构中高效计算图的性质。课程材料涵盖了图流的基本模型、分布式处理方法以及实际应用场景，并提出了相关的挑战和解决方案。通过图摘要、迭代计算和分布式流处理等技术，可以实现高效的图流分析。