3 ms·
Show HN: Weaver, a fast and scalable store for dynamically changing graphs
- evincarofautumn 12y agoThis reminds me of the approaches used by garbage collectors on object graphs—reorganising the graph to improve locality, and ensuring consistent views despite a concurrently running mutator. I wonder if other GC algorithms would be applicable to graph stores.
- dubey 12y agoInteresting analogy! Specifically, which gc algorithms did you have in mind?
- evincarofautumn 12y agoDunno, just speculating. Generational GCs use the observation that most objects die young. A generational graph store can use the observation that most accesses are to new objects—generally true of social graphs. You can move objects that are frequently accessed together into the same region, which some moving GCs do in order to obtain better cache behaviour, or evict infrequently accessed objects to “cold nodes” which you treat as the worst-case slow path. You can prefetch objects that you intend to traverse during the evaluation of a node program. And so on.
- carterschonwald 12y agoits not an analogy, theres actually research that proves that GC can actually improve memory locality in a particular provable sense! http://www.cs.cmu.edu/~rwh/papers/iolambda/short.pdf http://www.cs.cmu.edu/~rwh/papers/iolambda/short.pdf and http://www.cs.cmu.edu/~rwh/papers/iolambda-cacm/cacm.pdf http://www.cs.cmu.edu/~rwh/papers/iolambda-cacm/cacm.pdf both treat this topic in a pretty rigorous way. (i've had some attempts at proving a similar intuition, but those papers do it right)
- uptown 12y agoFor anyone interested in graphs and mesh-networks, there's another relevant article on HN today: https://news.ycombinator.com/item?id=8762063 https://news.ycombinator.com/item?id=8762063 Hasn't popped to the front-page yet, but I found its contents interesting.