Redis
3 HN recommenders · recommended in 4 months, 2018–2023
46:06 · 3.5K views · May 24, 2018
Redis Labs and Tim Davis present RedisGraph, which uses GraphBLAS to treat graph queries in Cypher as sparse linear algebra for lower latency.
Recommended in graph database threads as a mind-blowing case for expressing graph analysis as linear algebra.
5 comments from Hacker News
> If you want to be my hero, find a way to fix this problem: [LINK] Let me (try to) be your hero, Marzi. (Insert favorite reference to famous cheezy pop music song, if you like.) Couldn't you use GraphBLAS algorithms, like they do in RedisGraph (which supports Cypher, btw) to fix that problem with "death star" queries? Those algorithms are based on linear algebra and matrix operations on sparse matrices (which are like compressed bitmaps on speed, re: [LINK] ). The insight is that the adjacency list of a property-graph is actually a matrix, and then you can use linear algebra on it. But it may require the DB is built bottom up with matrices in mind from the start (instead of linked lists like Neo4j does). Maybe your double array approach in RageDB could be made to fit.. I think you'll find this presentation on GraphBLAS positively mind-blowing, especially from this moment: this video Such math-based algorithms seem perfect to optimally answer unbounded (death) star queries like “How are you connected to your neighbors and what are they?” That way, for such queries one doesn't have to traverse the graph database as a discovery process through what each node "knows about", but could view and operate on the database from a God-like perspective, similar to table operations in relational databases. Further reading: [LINK]
Thanks for this link, very interesting talk from the graphblas author: this video I've never seen any advantage to graphdbs over relational models until I saw this talk. Raising graph analysis to the level of linear algebra is brilliant.
On a related note, this upcoming paper on succinct graph representations will be presented at PACT next month ( [LINK] ) -- it's more data model than database, but I think you'll find it interesting... Log(Graph): A Near-Optimal High-Performance Graph Representation [pdf] [LINK] 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] this video 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 wit
This paper on succinct graph data structures will be presented at PACT ( [LINK] ) 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 [LINK] --//-- 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] this video 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 s
Hi Emil - I don't understand this comment. Last year, the MIT team showed the GraphBLAS/D4M model can achieve 100M inserts per second on a cluster [1], and it's improved since then. The GraphBLAS [2] standard has been in the works for more than 10 years. It's the culmination of the initial D4M matrix model design by Jeremy Kepner [3] and his team at MIT Lincoln Laboratory Supercomputing Center, which models graphs in the language of linear algebra. And for the last ~5 years or so the GraphBLAS software model has been designed in collaboration with hardware teams at Intel, NVIDIA, IBM, and the labs to make chips and architectures optimized for these new matrix models and capable of scaling out to exascale [4]. From a query perspective the GraphBLAS model is even better now that GPU and TPU accelerators are populating the data centers since it means you can now run local graph queries and global graph analytics algorithms on the same system and both return results in less than a second. * Google Cloud GPUs [LINK] * Google Cloud TPUs [LINK] For an overview of GraphBLAS in the context Heterogeneous High-Performance Computing (HHPC) systems running on NVIDIA GPUs and Intel Xeon Phis, see the 2015 talk Scott McMillan [5] gave at the CMU Software Engineering Institute [6]. GraphBLAS is in RedisGraph now [7] -- it uses the official GraphBLAS C implementation written by Tim Davis [8], who as you know implements the underlying sparse matrix algos used in everything from MATLAB to Googl