A Specialized B-Tree for Concurrent Datalog Evaluation


174 points | by matt_d 4 days ago


  • joshuak 4 days ago

    Another paper along these lines that I often refer too these days is:

    Concurrent Tries with Efficient Non-Blocking Snapshots http://aleksandar-prokopec.com/resources/docs/ctries-snapsho...

    But it feels likes these papers are from two different universes.

    A long time programmer (mostly for graphics), I'm new to the very large data set management applications that I'm working on these days. I find that I'm very interested in algorithms in this area, but come upon them in random ways (like these two).

    I find many algorithms are developed in wildly different contexts so the language used in papers can be confusing. In one paper a word is a term-of-art, in another purely descriptive, or understanding of the scope of applicability is completely assumed. For example I completely ignored discussions of "bloom filters" (as applied to set membership) for ages because in graphics there is a completely different kind of bloom filter in which both the meaning of "bloom" and "filter" are completely different.

    Are there any good blogs that highlight algorithms like this in an more casual style than the papers themselves (or academic proceedings) that can help give more context, and sense of how these tools fit in the landscape of algorithms?

    The "two minute papers" YouTube channel comes to mind as an example: https://www.youtube.com/channel/UCbfYPyITQ-7l4upoX8nvctg

  • lelf 3 days ago

    Also: More Scalable Ordered Set for ETS Using Adaptation http://winsh.me/papers/erlang_workshop_2014.pdf This is how Erlang Term Storage (ETS) works in newer Erlang/OTP.

    • joe_the_user 3 days ago

      Sound pretty amazing though naturally I haven't had time to look in general.

      Is this essentially based on something like a universal index, where all the elements in the system are more or less indexed upon each other?

      • 3 days ago