Geospatial and spatiotemporal indexing

SpaceKey is ShrikeDB’s geospatial index implementation for immutable observations with a position, UTC timestamp, event ID, and entity ID. Both query languages read the same index and use the same search options. The index selects candidates using Hilbert, time-major, space-major, daily, weekly, and entity orderings, then checks the original coordinates and timestamps exactly. EXPLAIN identifies the indexed operator; optional output fields expose its work.

Before you begin

Use an authenticated connection when required by your deployment. The following shell example assumes Bash and curl. Set the HTTP address first:

export SHRIKEDB_HTTP='http://127.0.0.1:8182'

The index name ais is created by the first successful append. The example uses event ID 1 and entity 1001; use a new index or unused increasing event IDs if trying it on an existing database. Add x-shrikedb-database to select a non-default database. On a local single-tenant server, omit the Authorization header below; otherwise set SHRIKEDB_ACCESS_TOKEN to your access token.

Load Observations

Append a batch using the existing authentication headers and optional x-shrikedb-database selector:

curl -X POST "$SHRIKEDB_HTTP/api/v1/spacekey/ais/observations" \
  -H 'Content-Type: application/json' \
  -H "Authorization: Bearer $SHRIKEDB_ACCESS_TOKEN" \
  -d '{
    "batch": "vessel-feed-0001",
    "domain": {"start_ms": 1672531200000, "end_ms": 1704067200000},
    "observations": [{
      "id": 1,
      "entity": 1001,
      "time_ms": 1672531201000,
      "position": {"crs": "WGS84", "x": -77.0, "y": 38.9}
    }]
  }'

An HTTP batch contains 1–10,000 observations. The response acknowledges a durable generation and returns normalization receipts, including source CRS and grid resolution. Keep these receipts with source metadata when provenance matters. An identical retry with the same batch token returns the original batch generation, including after later appends or a restart; different normalized contents with the same token are rejected. New event IDs must exceed the published maximum. Entity IDs may repeat, and timestamps may arrive out of order within the configured domain. The index preserves multiple observations at the same place and time. Choose the immutable time domain for the expected workload: a narrower domain produces finer time bins. The default spans 1970–2100; changing the domain requires a new index.

Indexes are isolated by database and authenticated subject. They are explicit event indexes: appending graph properties does not automatically populate them. To join observations to graph nodes, use that node’s UID as entity, or maintain an explicit MMSI-to-node mapping. Using MMSI as an entity ID does not create a corresponding graph node.

HTTP ingestion commits each batch as a database transaction. Applications that need graph, vector, KV, and geospatial writes to become visible together can call BeginTransaction, buffer the writes with the corresponding transaction RPCs including TransactionInsertSpaceKey, and finish with CommitTransaction. A failed or rolled-back transaction does not publish its geospatial batch.

Coordinate Reference Systems

CRS value Input Meaning

WGS84, CRS84, OGC:CRS84

x: longitude; y: latitude

Degrees on WGS84.

EPSG:4326

x: latitude; y: longitude

EPSG axis order is explicit.

EPSG:3857

x: easting; y: northing

Web Mercator meters within the world extent.

UTM:18N, UTM:56S

x: easting; y: northing

WGS84 UTM with explicit zone and hemisphere.

EPSG:32601–32660, EPSG:32701–32760

x, y

Equivalent northern/southern WGS84 UTM definitions.

GARS

grid, for example 361HN37

30-, 15-, or 5-minute cell center, with resolution in the receipt.

USNG

grid, for example 18SUJ2339407395

WGS84 UTM grid cell center, 0–5 digits per axis; UPS polar references are outside this implementation.

Numeric points and grid references are distinct input forms. GARS and USNG inputs represent cell centers, not exact sensor fixes or cell-overlap predicates. Other datums and ambiguous bare UTM inputs are rejected rather than guessed. Radius predicates use great-circle distance on a sphere of radius 6,371,008.8 meters; they are not ellipsoidal survey distances.

Cypher

Find observations near a port during a half-open UTC interval:

CALL spacekey.search('ais', {
  start_ms: 1672531200000,
  end_ms: 1672534800000,
  shape: {type:'radius_crs', position:{crs:'EPSG:4326', x:38.9, y:-77.0}, meters:5000.0}
})
YIELD event, entity, time_ms, longitude, latitude, key
RETURN event, entity, time_ms, longitude, latitude, key
ORDER BY time_ms

A box shape uses WGS84 longitude/latitude fields west, south, east, north. Bounds are inclusive; west > east crosses the antimeridian. A radius shape uses longitude, latitude, and meters; radius_crs accepts any supported coordinate input as position. Omit shape for time-only or entity-track lookups.

Add entity:1001 to restrict a vessel, or cycle:{period:'day',start_ms:72000000,end_ms:21600000} to select UTC 20:00–06:00 across dates. Weekly phases start Monday at 00:00 UTC. There is no implicit local-time or daylight-saving conversion.

For a count without materializing events:

CALL spacekey.search('ais', {entity:1001, count_only:true})
YIELD count AS observations, candidates, seeks, planning_us, execution_us, generation
RETURN observations, candidates, seeks, planning_us, execution_us, generation

count_only returns one row even for zero matches and cannot yield event fields. Ordinary results can be joined and aggregated using existing Cypher operators. Two static time-window scans can be joined by entity and ordered timestamp to test a vessel’s sequence of observed locations. Such joins return observation pairs; deriving distinct port visits or interpolated trajectories remains application logic. Options are literal maps; per-row correlated index arguments are not supported.

SPARQL

Use the proprietary internal SERVICE endpoint with a single request subject:

PREFIX sk: <urn:shrikedb:spacekey:>
SELECT ?event ?vessel ?time WHERE {
  SERVICE <urn:shrikedb:spacekey.search> {
    _:query sk:index "ais";
      sk:query '{"start_ms":1672531200000,"end_ms":1672534800000,"entity":1001}';
      sk:event ?event;
      sk:entity ?vessel;
      sk:time_ms ?time.
  }
}
ORDER BY ?time

The JSON uses the same query options as Cypher. Output predicates use the same field names. Two SERVICE blocks sharing ?vessel can join indexed observation windows; ordinary FILTERs can compare their timestamps. This is a ShrikeDB-specific local SERVICE endpoint. Remote endpoints, SERVICE SILENT, correlated inputs, unknown options, and duplicate bindings are rejected.

Check index work

Use the count example above to compare returned matches with candidates and seeks. Selective position/time windows can avoid examining much of the index; a full-domain search may still scan all observations. Measure end-to-end requests on your own query mix when sizing a deployment.

Work limits, persistence, and deployment

The default deadline is 10 seconds, candidate budget 20 million, and result budget 100,000 events. Use timeout_ms, max_candidates, and max_results to set explicit limits; hard maxima are 60 seconds, 100 million candidates, and 10 million results. A budget failure returns an error rather than an incomplete answer. max_cells (default 512) and seek_budget (default 64) bound each cover; a full-coverage segment uses a contiguous scan. Limits apply to the whole pinned query, not separately to every segment.

SpaceKey observations, multidimensional index entries, receipts, and manifests are stored as ordered records in ShrikeDB’s ACID key–value engine. Ingestion writes bounded immutable chunks through the database WAL, then publishes the completed run by replacing one checksummed catalog-head record. Readers pin each named index once per execution; a later append does not alter that reader’s generation. For a multimodal transaction, query snapshot capture and commit publication use a shared visibility gate. A Cypher or SPARQL request therefore sees the graph and geospatial state before the commit or after it, without observing the publication interval between them. Historical graph snapshot queries still reject SpaceKey scans because the SpaceKey procedure pins its named-index generation rather than a historical graph version.

HA deployments carry SpaceKey writes in the same transaction prepare/finalize payload as graph, vector, and KV writes. Peer apply is idempotent by operation and batch identity, and an acknowledged commit uses the configured transaction quorum and durable decision-recovery path. Cypher and SPARQL execute against the locally published replica generation.

Each record key includes the owner, database namespace, named index, and format incarnation. Each ingestion request accepts at most 10,000 observations. Named indexes grow through content-addressed directory pages with 256 run descriptors per page and a constant-size publication head. A validation catalog reopened 1,025 full logical runs representing 10.25 million observations and appended generation 1,026. Storage capacity, configured query budgets, and operational retention policy determine the practical size. Catalog-wide time and entity orders allow a time-window or entity lookup to scan one ordered range per cover instead of seeking once per immutable run. Existing inline catalogs are upgraded on their next append; the upgrade backfills these two global orders before publishing the paged head. Database startup recovers the index through the ordinary KV WAL. When opening an older native SpaceKey catalog, ShrikeDB validates and replays its original batches into KV storage, then archives the legacy directory after migration succeeds.

SpaceKey strings use the original 60-bit / 20-level Unicode profile. Their meaning includes the index’s immutable time domain; keys from different domains are not interchangeable.