Damn Cool Algorithms: Spatial indexing with Quadtrees and Hilbert Curves
Posted by Nick Johnson | Filed under tech, coding, damn-cool-algorithms
Last Thursday night at Oredev, after the sessions, was "Birds of a Feather" - a sort of mini-unconference. Anyone could write up a topic on the whiteboard; interested individuals added their names, and each group got allocated a room to chat about the topic. I joined the "Spatial Indexing" group, and we spent a fascinating hour and a half talking about spatial indexing methods, reminding me of several interesting algorithms and techniques.
Spatial indexing is increasingly important as more and more data and applications are geospatially-enabled. Efficiently querying geospatial data, however, is a considerable challenge: because the data is two-dimensional (or sometimes, more), you can't use standard indexing techniques to query on position. Spatial indexes solve this through a variety of techniques. In this post, we'll cover several - quadtrees, geohashes (not to be confused with geohashing), and space-filling curves - and reveal how they're all interrelated.
Quadtrees
Quadtrees are a very straightforward spatial indexing technique. In a Quadtree, each node represents a bounding box covering some part of the space being indexed, with the root node covering the entire area. Each node is either a leaf node - in which case it contains ...
Trip reports: Stack Overflow Amsterdam, and Oredev
Posted by Nick Johnson | Filed under tech, conferences
I spent this week attending and speaking at two different conferences - the Stack Overflow Dev Day in Amsterdam, and Øredev, in Malmö, Sweden.
Stack Overflow was a lot of fun. Talks covered topics such as FogBugz, jQuery, Fog Creek Software, creators of FogBugz, QT (pronounced 'cute'), FogBugz, Python, App Engine (my own talk), Yahoo! developer tools, and, of course, FogBugz.
Particular highlights for me were Simon Willison's talk about Python, and Christian Heilmann's talk on Yahoo! developer tools. Simon works at The Guardian, a UK newspaper that is particularly keen on exposing and consuming data and APIs, and used his hour to introduce Python by demonstrating how he uses it, particularly the interactive interpreter, on a day to day basis to extract and munge statistical data and produce content for news stories, such as infographics. Although I know Python very well, his presentation style was extremely engaging, and I had to restrain myself from going up to him and asking if he was looking for apprentices in the fine art of presenting. He's also a co-author of Django, so he showed off some of Django's features in his talk as well.
Christian's talk was completely ...
Newer