使用 Redis 降低 Cypher 中的延迟图查询 - Roi Lipman, Redis Labs 和 Tim Davis, 德州农工大学

Lower Latency Graph Queries in Cypher with Redis GraphRoi Lipman, Redis LabsTim Davis, Texas A&M U

频道:Redis · 时长:46:05 · 发布:2018-05-24 · 播放:3466

在 YouTube 观看

简介

Redis Labs 和 Tim Davis 介绍 RedisGraph,它使用 GraphBLAS 将 Cypher 中的图查询视为稀疏线性代数以降低延迟。

HN 为什么推荐

在图数据库相关帖子中推荐,作为将图分析表达为线性代数的令人惊叹的案例。

我认为你会发现这个关于 GraphBLAS 的演讲令人惊叹 — HN, 2023

数据库与存储 · 算法与数据结构

中文字幕节选

好的,大家好,我叫Roi Lipman 我在Redis Labs工作,过去 近两年来一直在开发RedisGraph,这次演讲 是关于矩阵或CSR矩阵以及线性代数,以及我们如何 在图数据库中使用这些概念。所以为了确保在座的各位 都理解一致,我们先给出图的正式定义。图 基本上就是一组节点,每个节点可以代表 某个实体,以及一组连接这些节点的边,每条边可以代表 某种关系。以Facebook为例,节点代表用户, 边代表这些用户之间的好友关系。 一旦有了图,你有几种选择来 在内存或磁盘上存储这个图。有非 传统或非正式的方法,比如使用表,如SQL表,或 JSON文档来存储图。显然 这些结构并非为存储图而设计,但你可以用它们来保存你的 图。还有那些经典结构,如邻接表和邻接 矩阵。本次演讲将聚焦于邻接矩阵。 邻接矩阵背后的思想是,你有一个矩阵,其行和 列基本上代表你的节点。行I可以代表ID为I的节点, 列J代表节点J。如果节点i 连接到节点j,那么第I行第J列的元素值为1, 否则为0。某个元素IJ 会告诉你节点I没有连接到节点J。 所以如果我们尝试创建这样一个邻接矩阵,并尽量保持其大小 最小,我们会为每个元素使用1位,是的,我们会为 每个元素使用1位。因此要执行矩阵 操作,如加法或乘法,我们可以使用位运算,这 非常棒,因为位运算非常快。 唯一的问题是,对于一个有100万 节点的图,这将需要一个有100万行和100万 列的矩阵,总计125GB的空间, 这基本上扼杀了使用矩阵表示图的想法。 幸运的是,真实的图是稀疏的。所谓稀疏,我指的是 非零元素的数量相对于矩阵中 总元素数量来说相对较小。 以Facebook为例,Facebook大约有20亿用户,每个用户 平均有338个好友。所以如果我们看 Facebook的好友矩阵,我们只有20亿乘以338 个非零元素,而总元素数为20亿的平方,所以矩阵 利用率非常低。因此我们希望使用所谓的 稀疏矩阵来表示这种类型的图。稀疏矩阵背后的思想 是我们只跟踪非零值。例如,如果我们 查询矩阵中第I行第J列的位置,即IJ元素,我们发现 这个位置没有被跟踪,我们可以立即得出该 元素的值为0。GraphBLAS是一个软件库, 允许你在稀疏矩阵上执行矩阵操作。现在我想 欢迎Tim Davis教授上台,为大家讲解GraphBLAS。好的,谢 谢Roi,感谢邀请我来和大家讨论这个。这是 GraphBLAS。我在主题演讲中做了一个很简短的介绍。这是一个 社区主导的努力,有来自学术界、 政府实验室的人参与。我与MIT林肯实验室、MIT、IBM、Intel密切合作, 他们也参与其中。它是什么?它是一个社区驱动的努力, 旨在利用一个关键观察,这个观察其实很久以前就被提出了: 图算法和线性代数之间的紧密联系。如果你 只是进行矩阵计算,你说好吧,我不做加法,我不 做乘法,我要把那个替换掉,换成另一个运算符,比如

HN 上的讨论

> 如果你想成为我的英雄,找到解决这个问题的方法:[LINK] 让我(尝试)成为你的英雄,Marzi。(如果你愿意,可以插入对著名俗气流行歌曲的引用。)你不能使用GraphBLAS算法,就像他们在RedisGraph(顺便说一句,它支持Cypher)中所做的那样,来解决“死亡之星”查询的问题吗?这些算法基于线性代数和稀疏矩阵上的矩阵运算(它们就像加速的压缩位图,参见:[LINK])。其洞察力在于,属性图的邻接表实际上是一个矩阵,然后你可以在其上使用线性代数。但这可能需要数据库从一开始就以矩阵为设计基础(而不是像Neo4j那样使用链表)。也许你在RageDB中的双数组方法可以适应... 我想你会发现这个关于GraphBLAS的演讲绝对令人脑洞大开,特别是从这一刻开始:[VIDEO] 这种基于数学的算法似乎非常适合最优地回答无界(死亡)星形查询,如“你如何与你的邻居连接,他们是什么?”这样,… — redbar0n, 2023-01
感谢这个链接,来自GraphBLAS作者的非常有趣的演讲:[VIDEO] 在看到这个演讲之前,我从未看到图数据库相对于关系模型的任何优势。将图分析提升到线性代数的水平是 brilliant 的。 — michelpp, 2018-12
相关地,这篇即将发表的关于简洁图表示的论文将在下个月的PACT上展示([LINK])——它更多是数据模型而非数据库,但我想你会觉得有趣... Log(Graph): 一种近乎最优的高性能图表示 [pdf] [LINK] 对于更数据库特定的内容,请查看新的RedisGraph模块[1],它由GraphBLAS[2]实现,由尊敬的Tim Davis[3]亲自开发,如你所知,他实现了从MATLAB到Google Maps等一切中使用的底层稀疏矩阵算法... RedisGraph在线性代数语言中与GraphBLAS,由RedisLabs和Tim Davis共同展示 [VIDEO] [VIDEO] GraphBLAS并非Redis特有,但Redis数据结构和新的模块化设计使其成为首个流行数据库实现的理想候选。这很重要,因为GraphBLAS历经10多年打造,是MIT林肯实验室超级计算中心的Jere… — espeed, 2018-09
这篇关于简洁图数据结构的论文将在下个月的PACT([LINK])上展示。为了将其置于关系数据库编程的更广泛背景中,并说明为什么它对一般软件开发者现在很重要,以下是我昨天发布的一个帖子[0]中的一些想法,关于过去10多年在图数据库领域一直在酝酿的思想融合,以及硬件和其他方面已经对齐的力量,以带来即将到来的架构范式转变... [0] 现代列式数据库系统的设计与实现 [LINK] --//-- 这篇即将发表的论文[...]更多是数据模型而非数据库,但我想你会觉得有趣。对于更数据库特定的内容,请查看新的RedisGraph模块[1],它由GraphBLAS[2]实现,由尊敬的Tim Davis[3]亲自开发,如你所知,他实现了从MATLAB到Google Maps等一切中使用的底层稀疏矩阵算法... RedisGraph在线性代数语言中与GraphBLAS,由RedisLabs和Tim Davi… — espeed, 2018-09
嗨Emil - 我不理解这个评论。去年,MIT团队展示了GraphBLAS/D4M模型可以在集群上实现每秒1亿次插入[1],并且此后有所改进。GraphBLAS[2]标准已经酝酿了10多年。它是MIT林肯实验室超级计算中心的Jeremy Kepner[3]及其团队最初D4M矩阵模型设计的结晶,该模型用线性代数语言对图进行建模。在过去约5年里,GraphBLAS软件模型与Intel、NVIDIA、IBM和实验室的硬件团队合作设计,以制造针对这些新矩阵模型优化并能扩展到百亿亿次计算的芯片和架构[4]。从查询角度来看,GraphBLAS模型现在更好,因为GPU和TPU加速器正在填充数据中心,这意味着你现在可以在同一系统上运行本地图查询和全局图分析算法,并且两者都能在不到一秒内返回结果。* Google Cloud GPUs [LINK] * Google Cloud TPUs [LINK] 关… — espeed, 2018-11

相关视频