3

Imagine a dataset of all the restaurants in the US (similar to Yelp, etc), how would you return a set of restaurants within a certain range of a particular zip code. (Assuming you have already a function, distanceBetweenZipCodes, which figures out the distance for you.)

The brute force method would be

For each restaurant in restaurantsInUSA
  if(distanceBetweenZipCodes(restaurant.zipcode, user.zipcode) < walkingDistance)
    save restaurant

However, it seems fairly inefficient to include New York restaurants in the search if the user is in California. But, it is possible that a restaurant is located close to a state line so segmenting the data by state would be problematic. You get the same problem if trying to segment by counties, cities or any other administrative boundary.

What would be the most appropriate way to segment the data to avoid having to check each and every record for all searches?

6

You've discovered the need for spatial indexing. R-trees are probably the most common approach. The basic idea is a tree structure with rectangular bounding boxes computed over all the children of a given node. That way searching for a region or a point can traverse the tree, pruning out any parts of the tree (most of it) where the bounding box is not a match.

This is implemented in various libraries, including SQL databases PostgreSQL and SQLite (with module), and C++ library boost::geometry.

  • I'm using PostGIS (postgresql extension) in production on a million line dataset and it works well. – Clément Prévost May 26 '15 at 18:58
0

Calculate the distances between zip codes once and cache them. Keep the restaurants list sorted by the distance to the user. Enumerating the restaurants starting from the smallest distance you can detect the point when the restaurants go out of walking range - at that point you can ignore the rest and break the loop.

0

A quadtree (or octree in 3 dimensions) is also good for spatial indexing.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.