Top features for analytics and spatial queries use cases

[kronick]

Motivation

Without duplicating the full feature set of a heavyweight spatial database like PostGIS, what spatial features and queries could we offer with Cardboard that would capture a significant number of spatial analytics use cases? How can we efficiently serve basic queries like:

• Given a large set of points distributed widely across the globe, return the 5 nearest ones within a mile of a mobile app user's current location (i.e. Yelp) (without doing distance calculations on every point)
• Given a dataset of global postal codes, bin tens of thousands of customer point locations into each (without brute-forcing point-in-polygon comparison between all points and all polygons)
• Use a dataset of neighborhood polygons to determine which neighborhood a mobile app user is currently within
• Given a dataset of customer locations, allow a business analyst to draw an arbitrary polygon and determine how many customers lie within it (whether that polygon is the size of a city block or the size of a regional sales territory)
• @YunjieLi anything else to this list we started together?

What are the lowest-common-denominator features that would meet this challenge?

Two technical enablers

• Architecture that supports spatial indexing, so that filtering algorithms can be run only on nearby candidate features rather than the entire data set.
  • This could be an R-Tree, or perhaps something more appropriate for geospatial queries such as whatever Mongodb's 2DSphere index is built on (the issue with an R-Tree is that comparing nearby features across the poles or at 179 and -179 degrees longitude, for example, is limited if you use a tree built for flat 2D geometry)
  • More appropriate to DynamoDB might be Geohashes (see more below in References)
• Computational geometry algorithms to perform basic spatial filters, such as point-in-polygon tests, intersections, k-nearest neighbor search. Using Mongodb as the blueprint again this means:
  • A "near" filter with a min and max distance filter
  • A "within" filter that returns features contained entirely within an arbitrary query geometry
  • A "intersects" filter that returns features that intersect with an arbitrary query geometry

What we don't need right now (or maybe ever)

• A full reimplementation of Turf.js functions at the data store level. The above geometric filters would give users most of the power they need to get their data out of the store in a useful form for further processing with Turf or another analysis package.
• A full reimplementation of a generic database query language that supports parsing complex compound queries. If near, within, and intersects mapped to single API endpoints, that could be useful enough for many use cases.

References

• Geomesa, "an open-source, distributed, spatio-temporal database built on a number of distributed cloud data storage systems"

• Spatial index library for DynamoDB - very old and Java-only bindings, but the core idea looks like it calculates and stores a Geohash for each feature, which can then efficiently be sorted to find nearby features

• Details on how the above DynamoDB spatial index works

• Another implementation of Geohashes on DynamoDB

• Find Restaurants with Geospatial Queries, a tutorial on how to use Mongodb's spatial queries for a common use case

cc @mtirwin @YunjieLi @ryanbaumann @mcwhittemore

[mcwhittemore]

@kronick - thanks for putting this together.

I agree that the near, within and intersects operators are good for evaluating options.

Looking over the geohashes post, my quick take-aways are:

• geohashes work best with a max distance
• geohashes will be very easy for points, but maybe complicated for polygons and lines
• I'd like to see what the read cost of geohashes is if the geohash is fully in the RANGE, removing distance constraints. This is counter to the blog posts recommendation.

Just as a reference, the current approach the DynamoDB branch is using in this repo is based on Quadkey indexes and stores the index fully in the RANGE.

[ce-goddard]

Have you thought about using Neo4j? Here is a good article on geospatial indexing w/ neo4j-spatial (graph database).

cc @ryanbaumann @kronick