Have you ever thought about building an application that is location-based? Perhaps you want to display maps, or you want to show the bus stops or restaurants that are closest to the user as they roam about an unfamiliar city.
Like many types of programming and data representation problems, it turns out that efficiently storing points of interest (POIs) and then running the obvious types of queries is more complex than it might appear at first glance. A little exploration will lead you into areas such as great circle distances and spherical math. Before too long you will find yourself far afield from your original goal of answering the seemingly simple question, "what points of interest are near this point?"
Available as a Java JAR file, this new high-level library gives you the power to create geospatial data items. When stored in a DynamoDB table, items of this type include a latitude and a longitude, in addition to the attribute-value pairs maintained by the application. The library takes care of creating and maintaining the hash keys, range keys, and indexes that allow for fast and efficient execution of location-based queries.
Here's how you set up the library. This example uses a table called geo-table:
Your application will speak to the library using a data type known as a [GeoPoint]. Objects of this type store a latitude and a longitude. Once you have some GeoPoints, you write them to DynamoDB using a [putPoint] method. Let's make Seattle's Gas Works Park a Point of Interest:
Each of the items in the table must be uniquely identified by its rangeKey. In the code above, the value starting with "POI_" is a GUID which uniquely identifies the items. In practice, this value would be generated by your application's database access code.
The items can contain additional attributes. In this case, the attribute named title is set to the string "Original title". The library will encode the GeoPoint in a GeoJSON string and store the resulting value as the geoJson attribute.
Once you have created a table that contains items that are indexed by location, you can use the [queryRectangle] method to locate all of the items that fall within a pair of GeoPoints that define a rectangle as projected onto a sphere:
You can also use the [queryRadius] method to locate all of the items that are within a given radius. Here's how you find Points of Interest within 250 meters of Seattle's Space Needle:
Behind The Scenes
The library works by creating a virtual grid that overlays planet Earth. Each grid cell has an address that is derived from the location of the cell. When GeoPoints are inserted into DynamoDB, a geohash is computed and used to map the data record to the correct grid cell. The library stores each item's geohash as an item attribute. The hash preserves the proximity of nearby points and makes for efficient retrieval; it is stored as a local secondary index on the items.
When you issue a radial or rectangular query via the library, a list of candidate cells is constructed and used to form the DynamoDB query. The library post-processes the resulting items and returns those which are within the specified bounding box or radius.
To help you get started we have built a sample iOS application. Here's what it looks like:
Documentation, library and sample source code, and more are available on GitHub.
PS - We would love to get your feedback on this library! Is it a good fit for your application scenarios? What should we do to improve it in the future? Leave a comment on this blog with your feedback!