espeed

McLuhan's Understanding Media is a seminal work and one of the books that most shaped my thinking. "Electric Speed is synonymous with light and with the understanding of causes..." That line inspired the name for the Internet consulting company I formed in 1999, and espeed has been my online handle ever since.

  At no period in human culture have men understood 
  the psychic mechanisms involved in invention and 
  technology. Today it is the instant speed of electric 
  information that, for the first time, permits easy 
  recognition of the patterns and the formal contours of 
  change and development. The entire world, past and 
  present, now reveals itself to us like a growing plant 
  in an enormously accelerated movie. Electric speed is 
  synonymous with light and with the understanding of
  causes.

  — Marshall McLuhan, Understanding Media: The Extensions of Man (1964)

> Everything is a device!

There Are No Things. [0] ... only actions and properties. Everything is an actor [1].

In his Turing lecture, Robin Milner wrote [2]:

  Now, the pure lambda-calculus is built with just two 
  kinds of thing: terms and variables. Can we achieve 
  the same economy for a process calculus? Carl Hewitt, 
  with his Actors model, responded to this challenge 
  long ago; he declared that a value, an operator on 
  values, and a process should all be the same kind of 
  thing: an Actor.

  This goal impressed me, because it implies the 
  homogeneity and completeness of expression ... But it 
  was long before I could see how to attain the goal in 
  terms of an algebraic calculus...

  So, in the spirit of Hewitt, our first step is to 
  demand that all things denoted by terms or accessed by 
  names--values, registers, operators, processes, 
  objects--are all of the same kind of thing; they 
  should all be processes.

And now today Hewitt's elusive true mythical Actor model may have finally been realized and embodied in a language called Pony [3].

[0] https://www.edge.org/response-detail/11514

[1] https://en.wikipedia.org/wiki/Actor_model#Fundamental_concep...

[2] https://en.wikipedia.org/wiki/Actor_model#Theory

[3] https://github.com/ponylang/ponyc

To be precise, this is about the bitlevel SDS rank and select operation.

https://en.wikipedia.org/wiki/Succinct_data_structure

Hi Todd - Has your team looked at GraphBLAS [1] yet for MapD [2] now that Tim Davis has released a 2.0 reference C implementation (included in SuiteSparse 5.3) [3]? There is a GraphBLAS 2.0 CPU implementation in RedisGraph now [4] and official GraphBLAS 2.x GPU implementations are in the works.

[1] GraphBLAS http://graphblas.org

[2] OmniSci MapD DB https://github.com/omnisci/mapd-core

[3] SuiteSparse::GraphBLAS http://faculty.cse.tamu.edu/davis/suitesparse.html

[4] Previous Discussion https://news.ycombinator.com/item?id=18099520

Previous discussion in 2015 with the main authors: https://news.ycombinator.com/item?id=10157558

See Bradley's comment wrt to licensing the fractal tree code as GPLv2 w/ a patent provision https://news.ycombinator.com/item?id=18208209

I think/thought there were Python and Julia SDSL libs...does anyone know the state of those?

Note that some of the people involved are also the original authors of TokuDB [0], including Bradley Kuszmaul [1] , Michael Bender [2], and Martin Farach-Colton [3] who were the founders of Tokutek (acquired by Percona in 2015).

Previous discussion with the authors: A Comparison of Log-Structured Merge (LSM) and Fractal Tree Indexing https://news.ycombinator.com/item?id=9248298

[0] TokuDB Fractal Tree Index https://github.com/Tokutek/ft-index TokuDB Engine https://github.com/percona/tokudb-engine

[1] Bradley Kuszmaul http://people.csail.mit.edu/bradley/startups.html

[2] Michael Bender https://www3.cs.stonybrook.edu/~bender/

[3] Martin Farach-Colton https://www.cs.rutgers.edu/~farach/

Erik Demaine [1] gave two good lectures on succinct data structures [2] in the 2012 MIT 6.851 Advanced Data Structures course, and Rajeev Raman [3] just gave a tutorial on succinct data structures [4] at SIGMOD 2018.

NB: SDSL Cheatsheet http://simongog.github.io/assets/data/sdsl-cheatsheet.pdf

[1] http://erikdemaine.org/

[2] MIT 6.851 Succinct Structures I https://www.youtube.com/watch?v=3Y2weLDiUWw II https://www.youtube.com/watch?v=ABX-Hvn8ymE

[3] https://www.cs.le.ac.uk/people/rraman/

[4] SIGMOD 2018 Tutorial: In-memory Representations of Databases via Succinct Data Structures https://www.youtube.com/watch?v=_3q7T_5JaTI

Here's the talk Bradley Kuszmaul [1] gave to MIT 6.172 in 2010...

How TokuDB Fractal Tree Indexes Work https://www.youtube.com/watch?v=9Rb85cOXTKU&t=202s

[1] https://people.csail.mit.edu/bradley/

Talk given by Rob Johnson [1] at MSR a few years back...

BetrFS: A Right-Optimized Write-Optimized File System https://www.youtube.com/watch?v=fBt5NuNsoII

[1] http://www3.cs.stonybrook.edu/~rob/

Masstree is one of the DBs Berkeley used when comparing the performance of Anna [1] (now Fluent [2]):

[1] https://rise.cs.berkeley.edu/blog/anna-kvs/

[2] https://github.com/fluent-project/fluent

It's Texas OU weekend. The State Fair is going on this month too. Everyone's been at the stadium for the game and Texas just beat OU 48 to 45 so everyone from Oklahoma, Austin, Dallas...half the state is partying in Downtown/Uptown by now. There's probably a million people down there right now. You're in the wrong place.

https://www.google.com/search?q=texas+ou+weekend

See the Semantic Hashing paper by G. Hinton...

Semantic Hashing http://www.cs.toronto.edu/~rsalakhu/papers/sdarticle.pdf

https://scholar.google.com/scholar?q=related:_jJNEcvrLfQJ:sc...

Peterson was a Harvard professor from 1993–1998 so he was there at the time this paper was being written. Now that he's at Toronto, I'm curious to know how much interaction he has with Geoffrey Hinton. He's made references to research related to the AI embodiment problem, and one of his business partners is Daniel Higgins who was at MIT.

You mean this paper by E. A. Kravitz at Harvard Medical School Department of Neurobiology that was published in the Journal of Comparative Physiology in 1999?

Serotonin and aggression: insights gained from a lobster model system and speculations on the role of amine neurons in a complex behavior [pdf]

https://caspar.bgsu.edu/~huberlab/private/KingSolPub.pdf

Like the Tesla Valve...

https://en.wikipedia.org/wiki/Tesla_valve

Yes, graphs have been around for ages. They're as old as trees! ;-)

And you're right, first-year intro courses present graphs as matrices, it's usually the first graph representation you learn.

However, historically that's not how graphs have been represented in commercial or open-source databases due to the computational complexity and impracticality of supporting different architectures. Many PhD research papers over the years have been about the task of creating one-off implementations for the new hardware of the day.

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 (https://insights.sei.cmu.edu/author/scott-mcmillan/) gave at the CMU Software Engineering Institute:

Graph Algorithms on Future Architectures [video] https://www.youtube.com/watch?v=-sIdS4cz7-4

The figure cited by Scott McMillan in the CMU video is that each new hardware architecture implementation requires about 10,000 lines of code for BFS, and that's just one algorithm. The GraphBLAS standard makes this problem go away.

Furthermore, general on-demand access to GPU and TPU accelerators in cloud data centers just now became a thing. GraphBLAS will make it possible for non PhDs to run graph algos on clusters of accelerators in the cloud at supercomputer speeds.

https://cloud.google.com/gpu/

https://cloud.google.com/tpu/

Having the power of a Graph 500 (https://graph500.org) supercomputer at your fingertips and the ability to tap into that power on demand...well that's new! :-) And kinda crazy cool too, don't ya think?

P.S. A few years back, Jeremy Kepner did a mini-course on D4M (the precursor to GraphBLAS). The videos and material are on MIT OCW...

MIT D4M: Mathematics of Big Data and Machine Learning [video] https://www.youtube.com/watch?v=iCAZLl6nq4c&list=PLUl4u3cNGP...

Discussion: https://news.ycombinator.com/item?id=18105931

The first lecture is from this summer, the others are from an MIT mini-course few years back when D4M was still incubating.

During that time D4M was developed into a standard, which is now GraphBLAS, see my comment from yesterday...

Log(Graph): A Near-Optimal High-Performance Graph Representation (2018)

https://news.ycombinator.com/item?id=18099520

For an overview of GraphBLAS in the context of Heterogeneous High-Performance Computing (HHPC) systems such as NVIDIA GPUs or Intel Xeon Phis, see the 2015 talk Scott McMillan (https://insights.sei.cmu.edu/author/scott-mcmillan/) gave at the CMU Software Engineering Institute:

Graph Algorithms on Future Architectures [video] https://www.youtube.com/watch?v=-sIdS4cz7-4

Re: nvgraph, NVIDIA is one of Tim Davis's research sponsors and uses his code, as is (and does) Google. Among other things, he also wrote the open-source NVIDIA CULA sparse matrix library. See the list of libraries at the bottom of this page (scroll down) http://faculty.cse.tamu.edu/davis/research.html

Re: cuStinger, it's no longer...it's now Hornet, which uses CUB by NVIDIA Research https://github.com/hornet-gt/hornet

Re: gunrock, they have plans on adding GraphBLAS as part of their backend: https://github.com/gunrock/gunrock/issues?utf8=%E2%9C%93&q=i...

Re: GraphBLAS, see my comment from yesterday...

Log(Graph): A Near-Optimal High-Performance Graph Representation (2018)

https://news.ycombinator.com/item?id=18099520

For an overview of GraphBLAS in the context of Heterogeneous High-Performance Computing (HHPC) systems such as NVIDIA GPUs or Intel Xeon Phis, see the 2015 talk Scott McMillan (https://insights.sei.cmu.edu/author/scott-mcmillan/) gave at the CMU Software Engineering Institute:

Graph Algorithms on Future Architectures [video] https://www.youtube.com/watch?v=-sIdS4cz7-4

And a few years back, Jeremy Kepner did a mini-course on D4M (the precursor to GraphBLAS). The videos and material are on MIT OCW...

MIT D4M: Mathematics of Big Data and Machine Learning [video] https://www.youtube.com/watch?v=iCAZLl6nq4c&list=PLUl4u3cNGP...

Discussion: https://news.ycombinator.com/item?id=18105931

> I have no idea what it is supposed to accomplish, let alone what the advantage is

Did you read/view any of the references?

I tend to cite everything so that you have direct access to the source material for reference in case the context isn't clear.

This is not a "mess of buzzwords." It's how we move beyond the limits of Moore's Law. A lot of smart people have been working on various aspects of this for a long time. It's a big deal because it's a big change in how we model data, write algorithms, and think about computation in general, from the design of low-level hardware all the way up the stack to application design. It will behoove you to understand the change that's coming because it's what's next, and it's already here.

Re: your question on "Why did someone write an entire paper about counting triangles?"

Prof Tim Davis wrote the paper. He is one of the world's leading experts on sparse matrix implementations, and after the GraphBLAS Steering Committee finalized the 1.0 spec, they asked him to create the reference C implementation. Triangle counting is a common graph algorithm so it provides a familiar reference point when illustrating and comparing the characteristics of an implementation. Dr. Davis presented the paper this week at the HPEC 2018 conference (http://www.ieee-hpec.org), and in the paper's abstract he articulates precisely why:

Graph algorithms via SuiteSparse:GraphBLAS: triangle counting and K-truss

Abstract — SuiteSparse:GraphBLAS is a full implementation of the GraphBLAS standard, which defines a set of sparse matrix operations on an extended algebra of semirings using an almost unlimited variety of operators and types. When applied to sparse adjacency matrices, these algebraic operations are equivalent to computations on graphs. GraphBLAS provides a powerful and expressive framework for creating graph algorithms based on the elegant mathematics of sparse matrix operations on a semiring. To illustrate GraphBLAS, two graph algorithms are constructed in GraphBLAS and compared with efficient implementations without GraphBLAS: triangle counting and constructing the ktruss of a graph.

http://faculty.cse.tamu.edu/davis/GraphBLAS/HPEC18/Davis_HPE...

Watch the RedisGraph video for a general overview of how it works, but the big picture in the gist of it all is that data used in machine learning, AI, and relational databases is now being modeled in the same way -- as vectors/matrices/tensors -- to take advantage of modern CPU/GPU/TPU hardware accelerators that are being optimized for vector/matrix/tensor multiply-add operations. This means we can now run local and global algorithms in the same way, using the same code and the same data model, and we can return queries in real time -- executed in parallel, both locally or distributed -- it doesn't matter how the data is partitioned, the computation model is the same. Not only is this fast and compact, it unifies and simplifies things.

See https://solid.mit.edu

Starting offensive linemen are among the highest paid players in the NFL and have the longest careers on average, some spanning more than 15 years.

Dallas is paying its O-Line $41,174,860 this year, $4,574,984 per player on average (including all 9 starters and backups), which is 22.25% of the salary cap.

NFL Offensive Line Spending by Team https://www.spotrac.com/nfl/positional/offensive-line/

And the Giants just made Nate Solder the highest-paid offensive lineman in NFL, "a contract worth $62 million — an average of $15.5 million per year — with a $34.9 million guaranteed."

https://www.bostonglobe.com/sports/patriots/2018/03/14/nate-...

Evidently Oliver Selfridge [1] said a puzzle based on deriving the radius like this once tripped Feynman up...

"Puzzles from last week" http://web.media.mit.edu/~walter/MAS-A12/week11.html

[1] https://en.wikipedia.org/wiki/Oliver_Selfridge

This paper on succinct graph data structures will be presented at PACT (http://www.pactconf.org) 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 https://news.ycombinator.com/item?id=18076547

   --//--

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]

https://www.youtube.com/watch?v=xnez6tloNSQ

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 with the background understanding and a working mental model for the underpinning architectural paradigm shift [7].

[1] RedisGraph https://oss.redislabs.com/redisgraph/

[2] GraphBLAS http://graphblas.org

[3] Tim Davis http://faculty.cse.tamu.edu/davis/

[4] Jeremy Kepner http://www.mit.edu/~kepner/

[5] GraphBLAS: Building Blocks For High Performance Graph Analytics https://crd.lbl.gov/news-and-publications/news/2017/graphbla...

[6] Graph algorithms via SuiteSparse:GraphBLAS: triangle counting and K-truss [pdf] http://faculty.cse.tamu.edu/davis/GraphBLAS/HPEC18/Davis_HPE...

[7] David Patterson Says It’s Time for New Computer Architectures and Languages https://news.ycombinator.com/item?id=18009581

There's was a talk at StrangeLoop a few years back about a language syntax being designed based on user feedback from its ongoing usability studies. I'm on my phone now, but I'll try to find and post the link later when I'm at my computer if someone else doesn't find it first.

Here is the list of pinned domains [1] in Chrome:

Chrome Pinsets https://cs.chromium.org/chromium/src/net/http/transport_secu...

[1] https://www.chromium.org/sts

https://en.wikipedia.org/wiki/HTTP_Public_Key_Pinning

On a related note, this upcoming paper on succinct graph representations will be presented at PACT next month (http://www.pactconf.org) -- 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]

https://people.csail.mit.edu/jshun/papers/loggraph.pdf

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]

https://www.youtube.com/watch?v=xnez6tloNSQ

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 with the background understanding and a working mental model for the underpinning architectural paradigm shift [7].

[1] RedisGraph https://oss.redislabs.com/redisgraph/

[2] GraphBLAS http://graphblas.org

[3] Tim Davis http://faculty.cse.tamu.edu/davis/

[4] Jeremy Kepner http://www.mit.edu/~kepner/

[5] GraphBLAS: Building Blocks For High Performance Graph Analytics https://crd.lbl.gov/news-and-publications/news/2017/graphbla...

[6] Graph algorithms via SuiteSparse:GraphBLAS: triangle counting and K-truss [pdf] http://faculty.cse.tamu.edu/davis/GraphBLAS/HPEC18/Davis_HPE...

[7] David Patterson Says It’s Time for New Computer Architectures and Languages https://news.ycombinator.com/item?id=18009581

Yeah, that's a good paper -- Vadim's nested-interval tree method is quite clever. For more related references, see...

Using rational numbers to key nested sets https://news.ycombinator.com/item?id=13517490

Let's take a poll ... Who's submarines [0] are these?

Who's PR firm is behind this and the originally posted TC piece [1]? What's their angle? And Why?

[0] http://www.paulgraham.com/submarine.html

[1] https://techcrunch.com/2018/09/26/whatsapp-founder-brian-act... https://news.ycombinator.com/item?id=18076008