Several of our customers needed to correlate and aggregate large volumes of location-tagged data. While many higher level databases provide rich capabilities for spatial data (such as SQL Server or MongoDB), most large scale cloud based table storages (e.g. Microsoft Azure Table Storage) don\u2019t provide native support for spatial queries. In this case study, we discuss how we implemented spatial capabilities by mapping entities to unique grid numbers. While our implementation uses Table Storage, this approach is platform independent and can be reused with other storage technologies.<\/p>\n
In one of our projects, we needed to overlay additional geo-tagged data on top of an interactive map. For instance, we visualized building constructions and overlaid that with demographic information and heat maps to show the movement of people during a specific period. When using a storage system that supports spatial data, this would be a simple query – just filtering results that are visible within the current zooming window. However if the storage technology doesn\u2019t support spatial data, the query is not so simple. Considering that our data is stored in Azure Table Storage<\/a> or ingested through a real-time analytics pipeline (using EventHub<\/a> and Stream Analytics<\/a>), we had to implement our own approach to query spatial data.<\/p>\n One of the key challenges of spatial data is that each geo-tagged entity is described by at least two properties (latitude and longitude). Therefore to retrieve all entities which are contained within a rectangular boundary requires at least the filtering of two properties (latitude and longitude), followed by an inner join:<\/p>\n This is straightforward if the storage technology indexes all properties (columns); however it is more challenging if the columns used for storing spatial data are not indexed. For instance, using Azure Table Storage, only the partition key and the row key are indexed. (That\u2019s why every query should contain at least one of these keys \u2013 if not, it will result into a full table scan). Furthermore, row keys must be unique across a partition and therefore only one discrete spatial entity can be stored for a given location. Also, both partition and row keys are of datatype string, therefore the use of numeric filters for latitude and longitude aren\u2019t directly supported.<\/p>\n To address these constraints, we decided not to work with latitude and longitude independently, but to create a combined property that refers to a geographical boundary; in our case, a grid. Each set of latitude and longitude values belongs to a discrete grid, and each grid is identified by a unique grid number. We simply use this grid number as the partition key. This allows us to efficiently look up all entities that belong to a certain rectangular boundary by simply filtering the partition key for the required grid identification numbers. Because Table Storage filters are restricted to 15 discrete comparisons, we decided to create a new table for each required grid size. For instance, we store the building construction entities in two tables; one with a grid size of 50 meters, and one with a grid size of 1000 meters.<\/p>\n To map latitude and longitude to a discrete grid, we used J\u00fcrgen Pfeifer\u2019s Geodesy library which is available on GitHub ( https:\/\/github.com\/juergenpf\/Geodesy) as well as a NuGet package.<\/p>\n[(Entity.Lon \u2265 Query.SouthEast.Lon) AND (Entity.Lon \u2264 Query.NorthWest.Lon)]\r\nINNER JOIN\r\n[(Entity.Lat \u2265 Query.SouthEast.Lat) AND (Entity.Lat \u2264 Query.NorthWest.Lat)]\r\n<\/code><\/pre>\n<\/div>\nImplementation<\/h2>\n