Lost in Space: Binary Search Trees beyond 1D and CRDTs

This month will feature a talk from BigO regular Jeff Abrahamson and a talk Im really curious about on CRDTs from Noel Welsh.

To guarantee a place you must also register with skillsmatter directly.

See you there!

Dirk

• Lost in Space: binary search trees beyond dimension one - Jeff Abrahamson (Google)

BST's are a great general-purpose tool for locating points on the line. In higher dimensions, we have to do more work. In this talk,we'll look at a handful of algorithms that let us search for points,ranges of points, and nearest points, all in higher dimensions -- just like with BST's. We'll also touch on some surprising applications of these algorithms and even have a quick chat about the Curse of Dimensionality. The talk keeps evolving, but it's a safe bet that we'll at least discuss range trees, KD-trees, and higher dimensional Voronoi diagrams.

BioJeff Abrahamson collects advanced degrees while roaming the globe doing computer science and writing software. He currently hangs his (virtual) hat at Google London, where he is called site reliability engineer.


•  CRDTs for Fun and Eventual Profit - Noel Welsh (Myna, @noelwelsh)


CRDTs are a way of handling replicated or distributed data. What is distributed data? It just means data that is copied to many machines. As soon as we have such a distributed system we have to think about what happens when our data changes. We can decide that all machines will be aware of all changes. That is, we can maintain consistency. This is nice because it means we never deal with out-of-date data, but it requires every change to be sent to every machine before it is considered complete. If a machine (or the network) goes down we must refuse updates because we can’t ensure everyone has seen every update, and thus we can’t maintain consistency .

We can instead prefer availability, meaning we’ll just soldier on if machines go down, but this does mean we will end up with the same piece of data having different values on different machines. In other words our data will become inconsistent. CRDTs allow us to recover a particular type of consistency, called eventual consistency, without a great deal of work. With CRDTs we will be able to merge different copies of our data together without issue, and if we merge all copies together we are guaranteed to arrive at the same value everywhere.
In this talk I'll cover the basics of CRDTs and discuss some applications.

Bio: Noel is a founder of Myna and partner at Underscore. Noel has over fifteen years experience in software architecture and development, and over a decade in machine learning and data mining. Examples of the projects he's been involved with include one of the first commercial products to apply machine learning to the Internet (eventually acquired by Omniture), a BAFTA award winning website, and a custom CMS used daily by thousands of students.

Noel is an active writer, presenter, and open source contributor. Noel has a PhD in machine learning from the University of Birmingham.

Join or login to comment.

  • Christina N.

    More on CRDTs: http://hal.upmc.fr/docs/00/55/55/88/PDF/techreport.pdf
    It describes some more CRDTs designs, on top of the G-Counter.

    May 29

  • Christina N.

    Since the master theorem was mentioned, is there any interest in a presentation on it (I could do it...)? Or is it too simple for this group :)?

    3 · May 23

    • Ali S.

      +2 :)

      May 23

    • Christina N.

      Great then, I'll look into it! Dirk, I just emailed you and if anyone wants to contribute, please drop a line.

      May 23

  • Greg N.

    is there any video avaulable?

    May 22

  • Nimesh B.

    Thank you Noel and Jeff for the excellent talks.

    Further to Noel's question and the discussion on applications of the algorithms in Jeff's talk, I wanted to mention that kd-trees are used in astrophysics for the simulation of N bodies in a gravitational field. Please see the link below for a paper by Andrew Appel on this topic.

    http://repository.cmu.edu/cgi/viewcontent.cgi?article=3534&context=compsci

    Also, for newcomers to computer science like myself, the Algorithms I course on Coursera.org is fantastic, and it covers (among other things) kd-trees and some of its applications, including the above.

    1 · May 22

  • Henrik N.

    Excellent meetup, very interesting talks.

    May 22

  • Jeff A.

    The Shazam music recognition service is described in this (slightly old, brief) ACM paper. Interesting, too, is that it provides some insight on the business side.

    http://dl.acm.org/citation.cfm?id=1145312

    The technical paper is here, which describes the interesting geometric hashing they do. (TL;DR - plot fourrier transform against time, do feature extraction, for each moment in time, pick most significant point and do a clockwise scan of n most significant in the following ten seconds. The array of vectors from the chosen point to the following points is a signature for the music at that moment. Make a db. To do query, listen to ten seconds of music and construct a hash, look up in db.)

    http://www.ee.columbia.edu/~dpwe/papers/Wang03-shazam.pdf

    Patent lovers go here:
    https://www.google.com/patents/US6990453

    1 · May 22

  • Robert K.

    Two good talks on interesting data structure topics, good selection of material for the time available.

    Someone asked what is happening in the state of the art for the topics in Jeff's talk. A query for "site:research.google.com $TOPIC" often turns up interesting results. Hashing in particular turns up in a lot of interesting applications related to image processing and clustering at very large scales.

    1 · May 22

  • Peter M.

    Great meetup - learned lots from the very interesting talks.

    May 22

  • Tom F.

    Good talks, thanks.

    As mentioned: "Probabilistically Bounded Staleness" http://pbs.cs.berkeley.edu/

    1 · May 21

  • Robert

    Two really good talks

    2 · May 21

  • John Van P.

    The link "register with skillsmatter directly" seems to be broken.

    May 8

    • Dirk G.

      fixed, thanks for reporting

      May 8

Our Sponsors

People in this
Meetup are also in:

Create your own Meetup Group

Get started Learn more
Rafaël

We just grab a coffee and speak French. Some people have been coming every week for months... it creates a kind of warmth to the group.

Rafaël, started French Conversation Group

Sign up

Meetup members, Log in

By clicking "Sign up" or "Sign up using Facebook", you confirm that you accept our Terms of Service & Privacy Policy