算法与理论计算机2018people.csail.mit.edu
Log(Graph)：一种近乎最优的高性能图表示
Log(Graph): A Near-Optimal High-Performance Graph Representation (2018)
进阶 · 约 45 分钟读完前置知识：数据结构与算法、图论基础、位向量/rank-select
导读
这篇论文研究如何用接近最优空间、同时保持高性能的数据结构来表示图，提出了 Log(Graph) 表示。其核心思路之一是把偏移集合编码为带 select 结构的位向量，并可能结合顶点 ID 重排来改善效果。评论认为结果有前景，但也指出论文写作、图表和代码可用性存在问题。
HN 关注点：在简洁图数据结构上的新编码思路，以及论文宣称的代码迟迟未发布所引发的可复现性问题。
HN 评论精选
这几条评论里：质疑 2 补充 1
质疑肯定带 select 结构的位向量编码思路，同时批评顶点 ID 重排可能很慢、数学记号有误和第2页图无效。
这篇论文大部分写得不错，结果看起来有前景。一个较简单的想法是把偏移量集合表示为带 select 结构的位向量，这是我之前没想到的，我觉得是个好想法。它基于一个假设：偏移量之间的差通常小于一个偏移量用二进制表示所需的位数；我认为在很多情况下这合理。其他方法涉及重排顶点 ID（可能相当慢），让我有点难过，虽然我不确定为什么。数学记号有些地方丑且混乱，少数地方错误，但CS论文常见所以不太能抱怨。第2页的图完全离谱；能在TikZ里做疯狂图有点好笑，但它没达到解释各节内容的目的。
dan-robertson查看英文原文
Most of the paper was quite good and the results seem promising. One of the simpler ideas is to represent the set of offsets as a bitvector with a select structure which I didn’t think of and I think it’s a nice idea. It works under the assumption that the difference between offsets is typically less than the size in bits of an offset but I think this could reasonably be true in many cases. Other approaches involve permuting vertex ids (which can potentially be quite slow) which makes me a bit sad although I’m not really sure why. The mathematical notation is ugly and mangled in some places and in a few places wrong but this is sadly common with computer science papers so I can’t really complain much about it. The diagram on page 2 is completely bonkers. I sympathise a bit in that it can be amusing to create crazy graphics in TIKZ but this one doesn’t really serve its purpose (of explaining what the sections of the paper are) at all.
质疑质疑论文宣称的代码可用性，指出项目页面长期只有“即将推出”。
论文声称代码已在线可用。但该页面长时间显示“Coming soon...”。https://spcl.inf.ethz.ch/Research/Performance/LogGraph/ 请问是否预计近期发布？
erenon查看英文原文
The paper claims the code is available online. The page, however, shows: "Coming soon...", for quite some time. https://spcl.inf.ethz.ch/Research/Performance/LogGraph/ Is it expected to land in the near future?
补充把论文放到简洁图结构、GraphBLAS、RedisGraph 和图数据库架构趋势的更大背景中。
这篇关于简洁图数据结构的论文下月将在 PACT 展示。为把它放在关系数据库编程的更广背景中，并解释它为何现在对普通软件开发者重要，以下是我昨天帖子中的一些想法：过去10多年图数据库领域的思想正在汇聚，硬件等方面的力量也已对齐，将带来架构范式转变。这篇即将发表的论文更多是数据模型而非数据库，但我觉得你会感兴趣。更数据库特定的方向，可以看看新的 RedisGraph 模块，它由 Tim Davis 用 GraphBLAS 实现；GraphBLAS 不是 Redis 专属，但 Redis 的数据结构和模块化设计使其成为首个流行数据库实现的理想候选。
espeed查看英文原文
This paper on succinct graph data structures will be presented at PACT (http://www.pactconf.org) next month. To put it in the broader context of relational database programming and why it's significant now for software developers in general, here are some thoughts from a thread I posted yesterday [0] on the convergence of ideas that have been in the works for the last 10+ years on the graph database front and the forces that have aligned in hardware and other fronts to bring about the architectural paradigm shift that's to come... [0] The design and implementation of modern column-oriented database systems https://news.ycombinator.com/item?id=18076547 --//-- This upcoming paper [...] is more data model than database, but I think you'll find it interesting. For something more database specific, check out the new RedisGraph module [1] implemented with GraphBLAS [2] by the venerable Tim Davis [3] himself, who as you know implements the underlying sparse matrix algos used in everything from MATLAB to Google Maps... RedisGraph in the Language of Linear Algebra with GraphBLAS, co-presented by RedisLabs and Tim Davis [video] https://www.youtube.com/watch?v=xnez6tloNSQ GraphBLAS is not Redis-specific, but the Redis data structures and new modular design made it an ideal candidate for the first popular database implementation. This is significant because GraphBLAS is more than 10 years in the making, the culmination of the initial D4M matrix model design by Jeremy Kepner [4] and his team at MIT Lincoln Laboratory Supercomputing Center. And for the last ~5 years or so the software model has been designed in collaboration with hardware teams at Intel, NVIDIA, IBM, and the labs [5] to make chips and architectures optimized for these new matrix models and capable of exascale. It all came together this summer with the release of GraphBLAS 1.0 [6]. Now that GPU and TPU accelerators are populating the data centers and linear algebra has come en vogue, hopefully enough software engineers will be ready with the background understanding and a working mental model for the underpinning architectural paradigm shift [7]. [1] RedisGraph https://oss.redislabs.com/redisgraph/ [2] GraphBLAS http://graphblas.org [3] Tim Davis http://faculty.cse.tamu.edu/davis/ [4] Jeremy Kepner http://www.mit.edu/~kepner/ [5] GraphBLAS: Building Blocks For High Performance Graph Analytics https://crd.lbl.gov/news-and-publications/news/2017/graphblas-building-blocks-for-high-performance-graph-analytics/ [6] Graph algorithms via SuiteSparse:GraphBLAS: triangle counting and K-truss [pdf] http://faculty.cse.tamu.edu/davis/GraphBLAS/HPEC18/Davis_HPEC18.pdf [7] David Patterson Says It’s Time for New Computer Architectures and Languages https://news.ycombinator.com/item?id=18009581
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2018Hacker News 讨论帖180 分 · 12 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选通信的数学理论
A Mathematical Theory of Communication
是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。
算法与理论计算机2020 · 495 分 · 91 评进阶 · 约 120 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。
算法与理论计算机2014 · 327 分 · 57 评 · 引用 4进阶 · 约 25 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选