3 ms·

I'm pretty uninformed on the subject, but I am interested to hear why an adjacency matrix is chosen over an adjacency list when it is sparse. My basic data stru

I'm pretty uninformed on the subject, but I am interested to hear why an adjacency matrix is chosen over an adjacency list when it is sparse. My basic data structures and algorithms class would lead me to believe that an adjacency list would be better. Is this due to the nature of how the database is constructed?

Groxx 8y ago
If I had to guess: redis is in general extremely predictable on both performance and memory use. A matrix is way more consistent in this.
atombender 8y ago
I found this [1] comment useful, from a thread last month. It has some background and links to the state of the art of GraphBLAS, which applies linear algebra to graphs. This [2] page has a good summary: > ... “But if we can view graphs as linear algebra problems—which have been central to science and engineering applications in high performance computing for decades—then we can immediately apply everything that we’ve learned from parallel supercomputing over the last 35 years to graphs.” [1] https://news.ycombinator.com/item?id=18099520 https://news.ycombinator.com/item?id=18099520 [2] https://crd.lbl.gov/news-and-publications/news/2017/graphblas-building-blocks-for-high-performance-graph-analytics/ https://crd.lbl.gov/news-and-publications/news/2017/graphbla...
arthurcolle 8y ago
The underlying representation is a sparse adjacency matrix. The graph that it is representing is not necessarily sparse.
- swilly022 8y ago
  True, although most "organic" graphs are sparse.
kristoff_it 8y ago
The main feature of the module is querying speed, which is achieved via matrix operations. You can't do the same with lists.
swilly022 8y ago
Another reason has to do with memory access and cache invalidation, when working with sparse matrices the entire graph structure is laid out in a contiguous block of memory which is ideal for CPU caching, unlike adjacency list where you have lots for small allocations scattered all over the memory space, this makes a huge difference when traversing the graph.
billylindeman 8y ago
Sparse matricies are represented as a sort of 2d linked list

Groxx 8y ago

If I had to guess: redis is in general extremely predictable on both performance and memory use. A matrix is way more consistent in this.

atombender 8y ago

I found this [1] comment useful, from a thread last month. It has some background and links to the state of the art of GraphBLAS, which applies linear algebra to graphs. This [2] page has a good summary: > ... “But if we can view graphs as linear algebra problems—which have been central to science and engineering applications in high performance computing for decades—then we can immediately apply everything that we’ve learned from parallel supercomputing over the last 35 years to graphs.” [1] https://news.ycombinator.com/item?id=18099520 https://news.ycombinator.com/item?id=18099520 [2] https://crd.lbl.gov/news-and-publications/news/2017/graphblas-building-blocks-for-high-performance-graph-analytics/ https://crd.lbl.gov/news-and-publications/news/2017/graphbla...

arthurcolle 8y ago

The underlying representation is a sparse adjacency matrix. The graph that it is representing is not necessarily sparse.

swilly022 8y ago
True, although most "organic" graphs are sparse.

kristoff_it 8y ago

The main feature of the module is querying speed, which is achieved via matrix operations. You can't do the same with lists.

swilly022 8y ago

Another reason has to do with memory access and cache invalidation, when working with sparse matrices the entire graph structure is laid out in a contiguous block of memory which is ideal for CPU caching, unlike adjacency list where you have lots for small allocations scattered all over the memory space, this makes a huge difference when traversing the graph.

billylindeman 8y ago

Sparse matricies are represented as a sort of 2d linked list