cardboard

cardboard

Demo platform for s2 on LevelDB.

Approach

This project aims to create a simple, fast geospatial index as a layer on top of LevelDB and DynamoDB. This means that the index will not be built into the database or contained in a single R-Tree - it will be baked into the indexes by which data is stored.

Support target:

• All GeoJSON geometry types should be storable
• BBOX queries should be supported

How are polygons indexed?

We generate an S2 cover of S2CellIds that covers non-point shapes with viable minimums of cells.

How do partial overlaps work?

Not sure yet.

How is data stored?

Currently as stringified GeoJSON

How are points stored

As S2CellIds that cover the point on level 30.

What are the keys like?

You need to specify a stringable primary key on the way in. The final keys look like

cell ! (s2 cell id as token) ! (primary key)

Since this indexing scheme relies on range queries, it's unlikely primary IDs will be used as hash keys in DynamoDB because you can only do a range query within a single hash key. Instead, hash keys in DynamoDB will be more like database or layer names.

What about MongoDB?

MongoDB uses S2 for its spherical indexes.

Where mongo turns cells into query parameters.

What about Amazon DynamoDB-geo?

It only supports point queries, and is written in Java.

What kinds of queries are supported?

• intersects
• contains

These query types should be roughly equivalent to the PostGIS ST_Within and ST_Intersects queries.

About DynamoDB

• Hot hash keys
• We should not use the scan operation for anything.

What Levels Should you use?

• For points, as high as possible (30?)
• For rectanges, twofishes default? - 8 to 12, mod 2

Cell IDs as strings or tokens?

• Looks like Google uses tokens in mustang (or did, mustang is retired, I think) but these are only accessible via CellId.
• We can't have them as numbers, because JavaScript does not tolerate 64-bit ints. Ints can only have 52 bits of precision in JS.
• Current approach is to use tokens

Building Loops

• GeoJSON Polygons / rings always have a duplicate vertex at the end. S2Loop doesn't like that.

Get or Scan?

DynamoDB treats Scan operations on tables with small keys very well:

You can use the Query and Scan operations in DynamoDB to retrieve multiple consecutive items from a table in a single request. With these operations, DynamoDB uses the cumulative size of the processed items to calculate provisioned throughput. For example, if a Query operation retrieves 100 items that are 1 KB each, the read capacity calculation is not (100 × 4 KB) = 100 read capacity units, as if those items were retrieved individually using GetItem or BatchGetItem. Instead, the total would be only 25 read capacity units ((100 * 1024 bytes) = 100 KB, which is then divided by 4 KB).