3 ms·

If anyone is interested in graph processing at scale, the largest Web Data Commons Hyperlink Graph[1] (created from Common Crawl[2] data) is 3.5 billion web pag

• shoo 11y ago
  That post from Frank McSherry is excellent. His earlier post [1] is also worth reading. I was curious to read more about the Hilbert ordering of edges, and the delta-encoding. There is a related article from Yzelman & Bisseling titled "A cache-oblivious sparse matrix–vector multiplication scheme based on the Hilbert curve"[2] which discusses Hilbert ordering combined with a delta-encoded version of the usual CSR encoding for sparse matrices [3]. > A Hilbert curve thus can be projected on any [2^m * 2^m] matrix, which in turn can embed the sparse matrix A, thus imposing a 1D ordering on its nonzeroes. The largest sparse matrix considered for the experimental results from this article was "wikipedia-20070206" with 45,030,389 nonzeros (aka weighted edges). Ignoring the weights, this is about 1/3000th of the size of the 128 billion edge graph that McSherry mentions in his post. Yzelman & Bisseling also measure the additional preprocessing time required to convert their sparse matrices using the Hilbert-ordered delta-encoded CSR scheme -- this is roughly 30x the time for a single matrix-vector product evaluation [4]. Clearly this approach is only going to pay off if one plans to do a bunch of analysis using the single matrix / graph, without changing the matrix / graph. McSherry mentions a similar issue but points out that he could preprocess the graph using his approach faster than he could download the data, so the preprocessing speed wasn't really an issue. [1] http://www.frankmcsherry.org/graph/scalability/cost/2015/01/15/COST.html http://www.frankmcsherry.org/graph/scalability/cost/2015/01/... [2] https://lirias.kuleuven.be/bitstream/123456789/400709/1/yzelman11c-pp.pdf https://lirias.kuleuven.be/bitstream/123456789/400709/1/yzel... [3] sparse matrices are a fairly obvious representation of directed graphs with edge weights, I searched for an article about sparse matrices as I am more familiar with linear algebra than graph processing. [4] edit: perhaps an crude intuitive way to think about "30x matvec products" in the context of graph algorithms would be "about one pagerank", as each pagerank iteration is doing a matvec product and a bit of other stuff, and McSherry talks about 10 or 20 iterations per pagerank evaluation.
  • Smerity 11y ago
    Agreed re: the quality of Frank McSherry's posts - they're all great fun and push the technical envelope! I'm glad you brought up Hilbert ordering. It's fascinating but I rarely see it. I usually see Z-order curves in their place - simpler and more intuitive but also less effective. Does anyone know of large scale databases with Hilbert ordering out of the box? For anyone who hasn't seen them before, or why they help in ordering, I highly recommend "Portrait of the Hilbert curve"[1] and "Spatial indexing with Quadtrees and Hilbert Curves"[2]. The tldr is that they enable efficient multi-dimensional indexing. Given a request like "X < 40 and Y > 80", most databases need to run "X < 40" and then filter over the results for "Y > 80" - Hilbert curves allow you to find the query's intersection and only then perform minor filtering. As far as large scale use of Hilbert ordering, Google use it internally for much of their geographical work. They even open sourced a Java library specialised in multi-dimensional indexing based on Hilbert curves called Uzaygezen[3]. [1]: http://corte.si/%2Fposts/code/hilbert/portrait/index.html http://corte.si/%2Fposts/code/hilbert/portrait/index.html [2]: http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-... [3]: http://google-opensource.blogspot.com/2008/08/uzaygezen-multi-dimensional-indexing.html http://google-opensource.blogspot.com/2008/08/uzaygezen-mult...
    • jandrewrogers 11y ago
      The primary advantage of Hilbert curves relative to Morton (Z) curves is that they are marginally more efficient at linearizing multidimensional point indexes e.g. storing on spinning disk. However, the reason that Hilbert curves are relatively rare in real systems these days is that (1) the optimality of Hilbert curves is largely based on the assumption of indexing on sequential storage media, and (2) for the many other applications of structures describable by space-filling curves, a Hilbert description is often inferior in practice. For example, it is a suboptimal curve to use if you are implementing spatial analysis operators in a distributed system. If you were designing a spatial indexing system from scratch today for modern applications, you would use neither Hilbert nor Morton/Z curves but they are adequate shortcuts for sufficiently narrow applications. Substantially more optimal curves also have a much more complex description.