Inspired by the simplicity of implementing a proximity search using MongoDB, I found myself keen to try out another technology.

It just so happened that I was presented with a fun little problem the other day. Given a latitude and longitude, how do I quickly determine what the time is? Continuing the recent trend, I wanted to solve this problem with Node.JS.

Unsurprisingly, there's a lot of information out there about timezones. Whenever I've worked with timezones in the past, I've always gotten a little bit lost so this time, I decided to actually read a bit and find out what was supposed to happen. In essence, if you're doing this sort of task. you do not want to have to figure out the actual time yourself. Nope. It's quite similar to one of my top web dev rules:

Never host your own video.

(Really, never deal with video yourself. Pay someone else to host it, transcode it and serve it up. It'll will always work out cheaper.)

What you want to do when working with timezones is tie into someone else's database. There are just too many rules around international boundaries, summer time, leap years, leap seconds, countries that have jumped over the international date line (more than once!), islands whose timezone is 30 minutes off the adjacent ones...

To solve this problem, it needs to be split into two: the first part is to determine which timezone the coordinate is in, the second is the harder problem of figuring out what time it is in that timezone. Fortunately, there are other people who are already doing this. Buried near the back of the bottom drawer in very operating system is some version of the tz database. You can spend hours reading up about it, its controversies and history on Wikipedia if you like. More relevantly, however, is what it can do for us in this case. Given an IANA timezone name – "America/New_York", "Asia/Tokyo" – you can retrieve the current time from the system's tz database. I don't know how it works. I don't need to know. It works.

Node

Even better for reaching a solution to this problem, there's a node module that will abstract the problem of loading and querying the database. If you use the zoneinfo module, you can create a new timezone-aware Date object, pass the timezone name to it and it will do the hard work. awsm. The module wasn't perfect, however. It loaded the system database synchronously using fs.readFileSync which is I/O blocking and therefore a Bad Thing. Boo.

10 minutes later and Max had wrangled it into using the asynchronous, non-blocking fs.ReadFile. Hooray!

Now all I needed to do was figure out how to do the first half of the problem: map a coordinate to a timezone name.

Nearest-Neighbour vs Point-in-Polygon

There are probably more ways to solve this problem but these were the two routes that jumped to mind. The tricky thing is that the latitude and longitude provided could be arbitrarily accurate. A simple lookup table just wouldn't work. Of course, the core of the problem was that we needed to figure out the answer fast.

Nearest Neighbour

1. Create a data file containing a spread of points across the globe, determine (using any slow solution) the timezone at that point.
2. Load the data into an easily searchable in-memory data-structure (such as a k-d tree)
3. Given a coordinate, find the nearest existing data point and return its value.

Point in Polygon

1. Create a data file specifying the geometry of all timezones.
2. Given a coordinate, loop over each polygon and determine whether this coordinate is positioned inside or outside the polygon.
3. Return the first containing polygon

This second algorithm could be improved by using a coarse binary search to quickly reduce the number of possible polygons that contain this point before step 2.

Despite some kind of qualification in mathematic-y computer-y stuff, algorithm analysis isn't my strong point. To be fair, I spent the first three years of my degree trying to get a record deal and the fourth trying to be a stand-up comedian so we may have covered complexity analysis at some point and I just didn't notice. What I do know, however, is that k-d trees are fast for searching. Super fast. They can be a bit slower to create initially but the point to bear in mind is that you only load it once while you search for data lots. On the other hand, while it's a quick task to load the geometry of a small number of polygons into memory, determining which polygon a given point is in can be slow, particularly if the polygons are complex.

Given this vague intuition, I settled on the first option.

If I wanted to create a spread of coordinates and their known timezones from scratch, it might have been an annoyingly slow process but, the Internet being what it is, someone already did the hard work. This gist contains the latitude and longitude for every city in the world and what IANA timezone it is in. Score! A quick regex later and it looks like this:

module.exports = [
  {"latitude": 42.50729, "longitude": 1.53414, "timezone": "Europe/Andorra"},
  {"latitude": 42.50779, "longitude": 1.52109, "timezone": "Europe/Andorra"},
  {"latitude": 25.56473, "longitude": 55.55517, "timezone": "Asia/Dubai"},
  {"latitude": 25.78953, "longitude": 55.9432, "timezone": "Asia/Dubai"},
  {"latitude": 25.33132, "longitude": 56.34199, "timezone": "Asia/Dubai"},
  etc…

(See the original on GitHub)

All that's left is to load that into a k-d tree and we've got a fully-searchable, fast nearest neighbour lookup.

Source

The source for this node module is, of course, available on GitHub and the module itself is available for install via npm using:

npm install coordinate-tz

When combined with the zoneinfo module (or, even better, this async fork of the module), you can get a fast, accurate current time lookup for any latitude and longitude.

Not a bad little challenge for a Monday evening.

This is the detailed post to go with yesterday's quick discussion about proximity search. All the code is available on GitHub.

This assumes a bit of NodeJS knowledge, a working copy of homebrew or something similar.

Install

• MongoDB - brew install mongodb
• NodeJS
• NPM (included in NodeJS installer these days)

These are included in the package.json but it can't hurt to mention them here:

• npm install twitter (node twitter streaming API library)
• npm install mongodb (native mongodb driver for node)
• npm install express (for convenience with API later)

Start mongod in the background. We don't quite need it yet but it needs done at some point, may as well do it now.

Create a Twitter App

Fill out the form Then press the button to get the single-user access token and key. I love that Twitter does this now, rather than having to create a full authentication flow for single-user applications.

ingest.js

(open the ingest.js file and read along with this bit)

Using the basic native MongoDB driver, everything must be done in the database.open callback. This might lead to a bit of Nested Callback Fury but if it bothers you or becomes a bit too furious for your particular implementation, there are a couple of alternative Node-MongoDB modules that abstract this out a bit.

// Open the proximity database
db.open(function() {
    // Open the post collection
    db.collection('posts', function(err, collection) {
        // Start listening to the global stream
        twit.stream('statuses/sample', function(stream) {
            // For each post
            stream.on('data', function(data) {
                if ( !! data.geo) {
                    collection.insert(data);
                }
            });
        });
    });
});

Index the data

The hard work has all been done for us: Geospatial Indexing in MongoDB. That's a good thing.

Ensure the system has a Geospatial index on the tweets.

db.posts.ensureIndex({"geo.coordinates" : "2d"})

Standard Geospatial search query:

db.posts.find({"geo.coordinates": {$near: [50, 13]}}).pretty()
(find the closest points to (50,13) and return them sorted by distance)

By this point, we've got a database full of geo-searchable posts and a way to do a proximity search on them. To be fair, it's more down to mongodb than anything we've done.

Next, we extend the search on those posts to allow filtering by query

---

db.posts.find({"geo.coordinates": {$near: [50, 13]}, text: /.*searchterm.*/}).pretty()

API

Super simple API, we only have two main query types:

• /proximity?latitude=55&longitude=13
• /proximity?latitude=55&longitude=13&q=searchterm

Each of these can take an optional 'callback' parameter to enable jsonp. We're using express so the callback parameter and content type for returning JSON are both handled automatically.

api.js

(open the api.js file and read along with this bit)

This next chunk of code contains everything so don't panic.

db.open(function() {
  db.collection('posts', function(err, collection) {
    app.get('/proximity', function(req, res) {
      var latitude, longitude, q;
      latitude = parseFloat(req.query["latitude"]);
      longitude = parseFloat(req.query["longitude"]);
      q = req.query["q"];

      if (/^(-?d+(.d+)?)$/.test(latitude) && /^(-?d+(.d+)?)$/.test(longitude)) {
        if (typeof q === 'undefined') {
          collection.find({
            "geo.coordinates": {
              $near: [latitude, longitude]
            }
          }, function(err, cursor) {
            cursor.toArray(function(err, items) {
              writeResponse(items, res);
            });
          });
        } else {
          var regexQuery = new RegExp(".*" + q + ".*");
          collection.find({
            "geo.coordinates": {
              $near: [latitude, longitude]
            },
            'text': regexQuery
          }, function(err, cursor) {
            cursor.toArray(function(err, items) {
              writeResponse(items, res);
            });
          });
        }
      } else {
        res.send('malformed lat/lng');
      }

    });
  });
});

If you've already implemented the ingest.js bit, the majority of this api.js will be fairly obvious. The biggest change is that instead of loading the data stream then acting upon each individual post that comes in, we're acting on URL requests.

app.get('/proximity', function(req, res) {

For every request on this path, we try and parse the query string to pull out a latitude, longitude and optional query parameter.

if (/^(-?d+(.d+)?)$/.test(latitude) && /^(-?d+(.d+)?)$/.test(longitude)) {

If we do have valid coordinates, pass through to Mongo to do that actual search:

collection.find({
  "geo.coordinates": {
    $near: [latitude, longitude]
  }
}, function(err, cursor) {
  cursor.toArray(function(err, items) {
    writeResponse(items, res);
  });
});

To add a text search into this, we just need to add one more parameter to the collection.find call:

var regexQuery = new RegExp(".*" + q + ".*");
collection.find({
  "geo.coordinates": {
    $near: [latitude, longitude]
  },
  'text': regexQuery
}

This makes it so simple, making it it kind of feels like cheating. Somebody else did all the hard work first.

App.net Proximity

This works quite well on the App.net Global Timeline but it'll really become useful once the streaming API is switched on.

Of course, the code is all there. If you want to have a go yourself, feel free.

Now that geolocated posts are beginning to show up around app.net, I found myself wondering about proximity search. Twitter provides one themselves for geotagged tweets. What a proximity search does, essentially, is provide results from a data set ordered by increasing distance from a given location. This can be further enhanced by combining it with a text search either before or after the distance sorting. This would give you a way to search for a certain query within a certain area.

Here, for example, is a proximity search centred on Berlin including any tweet in 1000 miles containing the word 'toast'.

When I first started thinking about the tech required for a proximity search, I remembered Lukas Nowacki back in our old Whitespace days implementing the Haversine formula in MySQL (Alexander Rubin has a good overview of how to do this). As much as I love my trigonometry and logarithms, I must admit, I was looking around for a simpler solution. Actually, I was looking around for a copy-paste solution, to be honest. I may even have spent some time going down that route if Max hadn't pointed me in the direction of MongoDB.

I'd been putting off digging into NoSQL databases for a while because, well, I had no real reason to. Recently, I've either been focused on front-end dev or hacking away at Java and never really had any good reason to investigate any of these new-fangled technologies get off my lawn you kids.

MongoDB

After 10 minutes of messing around with Mongo, I pretty much just found myself saying “No... way. There's no way that's actually working” I'm sure those of you experience with document-oriented databases are rolling your eyes right now but for those few of us left with an entirely relational concept of databases, let me just explain it like this: you know those things you want to do with a database that are just a hassle of multiple joins and confusing references? Document databases do some of those things really really well.

The biggest selling point for me, however was the native geospatial indexing. That pretty much made the majority of my proximity search complete. All I needed to do was wrap it in a nice interface and call it a day...

I'll follow up tomorrow with a more detailed 'How-to' guide.

I'm almost managing to keep to my intended schedule of one map-based web experiment per week. Unfortunately, I've mostly been working on internal Nokia Maps projects over the weekends recently so I've not had much to post here.

I can share my latest toy, though: CoverMap.me

Using just the public APIs over a couple of hours last Sunday afternoon, I made this to allow you to set a Nokia Map as your Facebook Timeline cover. The whole process is really straightforward so I thought I'd go over the main parts.

The exact aim of CoverMap.me is to allow the user to position a map exactly, choose from any of the available map styles and set the image as their cover image.

Make a Facebook App

Go to developers.facebook.com/apps/ and click 'Create New App', fill in the basic details – name of the app, URL it will be hosted on, etc – and you're done.

Facebook login

I've used the Facebook JS SDK extensively over the summer for various projects but I wanted to try out the PHP one for this. Super, super simple. Really. Include the library (available here), set your appId and secret and request the $login_url.

$facebook->getLoginUrl(array('redirect_uri' => "http://example.com/index.php"));

That will give you a link which will take care of logging the user in and giving you basic access permissions and details about them.

Nokia Maps JS API

When I'm hacking together something quick and simple with the Nokia Maps API, I usually use the properly awsm jQuery plugin jOVI written by the equally awsm Max. This makes 90% of the things you would want to do with a map extremely easy and if you're doing stuff advanced enough to want the extra 10%, you're probably not the type who'd want to use a jQuery plugin, anyway. Either way, you need to register on the Nokia developer site to get your Nokia app_id and secret.

To create a map using jOVI, simply include the plugin in your page then run .jOVI on the object you want to contain the map along with starting parameters:

$(window).on('load', function() {
  $('#mapContainer').jOVI({
    center: [38.895111, -77.036667], // Washington D.C.
    zoom: 12,           // zoom level
    behavior: true,     // map interaction
    zoomBar: true,      // zoom bar
    scaleBar: false,    // scale bar at the bottom
    overview: false,    // minimap (bottom-right)
    typeSelector: false,// normal, satellite, terrain
    positioning: true   // geolocation
  }, "APP_ID", "APP_SECRET");
});

This gives us a complete embedded map.

As I mentioned above, part of the idea for CoverMap.me was to allow the to choose from any of the available map styles. This was an interesting oddity because the public JS API gives you the choice of 'Normal', 'Satellite', 'Satellite Plain' (a.k.a. no text), 'Smart' (a.k.a. grey), 'Smart Public Transport', 'Terrain' and 'Traffic' while the RESTful Maps API (the API that provides static, non-interactive map images) supports all of these plus options to choose each of them with big or small text plus a 'Night Time' mode. Because of this, I decided to go for a two-step approach where users were shown the JS-powered map to let them choose their location then they went through to the RESTful static map to allow them to choose from the larger array of static tiles.

RESTful Maps

The RESTful Maps API is relatively new but does provide a nice, quick map solution when you don't need any interactivity. Just set an img src with the query parameters you need and get back an image.

(this should be all on one line)
http://m.nok.it/
    ?app_id=APP_ID
    &token=APP_TOKEN
    &nord       // Don't redirect to maps.nokia.com
    &w=640      // Width
    &h=480      // Height
    &nodot      // Don't put a green dot in the centre
    &c=38.895111, -77.036667 // Where to centre
    &z=12       // Zoom level
    &t=0        // Tile Style

That URL produces this image:

Upload to Facebook

Given the above, we've now got an image showing a map positioned exactly where the user wants it in the tile style the user likes. We just need to make the Facebook API call to set it as Timeline Cover Image and we're done.

You'd think.

Facebook doesn't provide an API endpoint to update a user's profile image or timeline cover. It's probably a privacy thing or a security thing or something. Either way, it doesn't exist. Never fear! There's a solution!

With the default permissions given by a Facebook login/OAUTH token exchange/etc... (that thing we did earlier), we are allowed to upload a photo to an album.

The easiest way to do this is to download the map tile using cURL then repost it to Facebook. The clever way to do it would be to pipe the incoming input stream directly back out to Facebook without writing to the local file system but it would be slightly more hassle to set that up and wouldn't really make much of a difference to how it works.

// Download from RESTful Maps
$tileUrl = "http://m.nok.it/?app_id=APP_ID&token=APP_TOKEN&nord&w=640&h=480&nodot&c=38.895111,%20-77.036667&z=12&t=0";
$ch = curl_init( $tileUrl );
$fp = fopen( $filename, 'wb' );
curl_setopt( $ch, CURLOPT_FILE, $fp );
curl_setopt( $ch, CURLOPT_HEADER, 0 );
curl_exec( $ch ); 
curl_close( $ch );
fclose( $fp );

//Upload to Facebook
$full_image_path = realpath($filename);
$args = array('message' => 'Uploaded by CoverMap.me');
$args['image'] = '@' . $full_image_path;
$data = $facebook->api("/{$album_id}/photos", 'post', $args);

The closest thing we can do then is to construct a Facebook link which suggests the user should set the uploaded image as their Timeline Cover:

// $data['id'] is the image's Facebook ID 
$fb_image_link = "http://www.facebook.com/" . $username . "?preview_cover=" . $data['id'];

Done

There we go. Minimal development required to create a web app with very little demand on the user that gives them a Nokia Map on their Facebook profile. Not too bad for a Sunday afternoon.

Go try it out and let me know what you think.