trajectory-rollup

trajectory-rollup turns ordered position observations into deterministic cell and directed-edge summaries. Session boundaries, idle gaps, spatial jumps, exact distinct membership, late data, and window closure are explicit parts of the contract.

The package has no runtime dependencies and supports both import and require.

Install

npm install trajectory-rollup

Why it exists

Batch mobility jobs often hide important policy in SQL: which timestamp owns a transition, whether an equality is inside an idle threshold, how negative coordinates map to cells, and whether daily distinct counts can be added. This package makes those choices testable and versioned.

Core example

import { rollupTrajectory } from "trajectory-rollup";

const result = rollupTrajectory(
  [
    {
      kind: "position",
      actorKey: "actor-a",
      eventTimeMs: 1_000,
      orderKey: "001",
      space: "alpha",
      x: -1,
      z: 5,
    },
    {
      kind: "position",
      actorKey: "actor-a",
      eventTimeMs: 2_000,
      orderKey: "002",
      space: "alpha",
      x: 12,
      z: 5,
    },
  ],
  {
    window: { startMs: 0, endMs: 10_000 },
    regionSize: 10,
    idleGapMs: 5_000,
    maxJumpDistance: 1_000,
    actorToken: (actorKey) => `opaque:${actorKey}`,
  }
);

The first point belongs to cell (-1, 0): cell coordinates use mathematical floor, including for negative positions. An edge belongs to the window containing its origin observation. A destination may therefore fall just beyond the window end when it is within the configured idle look-ahead.

Ordering and boundaries

Records are grouped by actorKey and sorted by (eventTimeMs, orderKey). Reusing the same tuple is an error because silently choosing a predecessor would make the result input-order dependent. session-start and session-end records break continuity. A gap equal to idleGapMs remains continuous; a larger gap begins a new segment.

Changing space or exceeding maxJumpDistance produces a teleport-like edge rather than a normal trip. Space-changing edges retain both space (the origin) and toSpace (the destination), so coordinates from different spaces cannot collapse into one key. sumDistance adds Euclidean distance only within one coordinate space; it is zero for a space-changing edge rather than inventing a metric between unrelated frames. Same-cell observations contribute cell samples but do not create an edge.

Exact distinct counts

Every cell and edge contains an ordered set of opaque membership tokens. mergeTrajectoryRollups unions those tokens and recomputes the count; it never adds per-part distinct counts. The actorToken callback should return a stable, non-reversible token suitable for the caller's privacy model. This package does not provide anonymity or k-anonymity.

Parts with different profile IDs cannot be merged. The profile captures algorithm version, region size, idle threshold, jump threshold, time source, and attribution policy.

With no target window, every part must describe the same interval; this is useful for merging shards. To combine daily parts into a monthly result, pass the monthly window. The unique part intervals must cover it exactly without gaps or partial overlaps. Identical intervals may repeat for shards, and exact memberships are unioned across every part. The caller must supply every record-disjoint shard exactly once; exact interval coverage cannot detect a missing or repeated shard, and repeated scalar inputs would be added twice.

Window closure and late data

planClosableWindows marks a window closable only after the source watermark reaches:

window end + idle gap + allowed lateness + ingestion flush delay

Late observations or ranges can mark every affected origin window dirty, including the preceding idle-look-ahead interval. Recompute dirty windows from source records; do not incrementally subtract an unknown prior predecessor.

PostgreSQL

The trajectory-rollup/postgres entrypoint accepts a complete rollup (including diagnostics) and a structural query client, with no dependency on a particular PostgreSQL driver. Its revision executor uses one client for BEGIN through COMMIT, takes a transaction-scoped lock, stages a new revision, replaces one window/profile revision, writes exact memberships, and rolls back on error. When recomputing a dirty window, pass the marker's observed dirtyGeneration. The transaction deletes that marker only when the generation still matches, so a concurrent late-data update remains queued. Marker writers must increment generation on every conflict; omitting dirtyGeneration leaves the marker untouched. Generated schema and table identifiers are rejected when they exceed PostgreSQL's standard 63-byte identifier limit, avoiding silent server-side truncation and collisions.

See design, service adapter, and prior art for the boundaries of the package.

Performance

The reproducible benchmark compares the unordered batch API, which validates and sorts a retained input, with the sorted one-pass API, which consumes an iterable without retaining all source records:

npm run benchmark

It reports distribution and per-record timing across a scaling matrix. Exact membership tokens remain part of every result, so source streaming reduces input retention but does not make result cardinality approximate or free. See performance notes for the measurement contract.

Limitations

• Input coordinates are planar. Supply a projection before calling the package.
• Opaque membership tokens can still be personal data depending on how they are made and retained.
• A watermark is a caller assertion about source completeness, not a guarantee created here.
• PostgreSQL execution is atomic within one database transaction; it is not atomic with external queues, object stores, or caches.

Development

npm install
npm run check

Related projects

• event-watermark-store — deterministic event-time watermarks for the same closure question.
• gap-tolerant-router — deterministic routing over planar line networks.
• sparse-proximity-graph — deterministic graph structure over the same kind of 2D observations.

Licensed under the ISC License.