mhtirogla
Home
Systems
API
Pricing
About
Log in
← Back
Home
›
Systems
›
Databases and storage engines
geo-db
geospatial database and index
PostGIS, H3
System
Techniques · 5
Primitives · 22
geo-db
Polygon clipping
geometry · medium: Polygon intersection/union/difference (Weiler-Atherton, Martinez) for spatial predicates
Query optimizer
storage · medium: Cost-based plan search: join ordering (DP/greedy), rewrites, access path selection
Cardinality estimation
storage · medium: Row-count estimates from histograms, MCVs, sketches and sampling for the optimizer
Join order dynamic programming
storage · medium: DPccp and DPhyp enumeration of join orders with cost models; greedy fallback for many joins
Subquery decorrelation
storage · medium: Unnest correlated subqueries into joins via dependent join and magic sets
Point in polygon
geometry · low: Ray-casting/winding tests and indexed polygon lookup for reverse geocoding
Geodesic distance (haversine, Vince…
geometry · low: Shortest-path distance between two lat/lon points on the Earth: haversine on a sphere (about 0.5% error), Vincenty or Karney on the WGS84 ellipsoid (sub-millimetre).
›
Geospatial cell index (geohash, S2,…
geometry · low: Map a lat/lon to a 64-bit cell id on a hierarchical grid, so "near" becomes an integer range scan in any ordinary sorted index.
›
k-d tree
geometry · low: A binary tree that splits k-dimensional points by one coordinate per level, giving fast nearest-neighbour and box queries on static low-dimensional data.
›
Line simplification
geometry · low: Douglas-Peucker and Visvalingam polyline simplification
Map projections
geometry · low: Web Mercator, UTM and equal-area projections, datums and coordinate transforms
R-tree
geometry · low: A balanced tree of nested bounding boxes that indexes rectangles and points, answering window and nearest-neighbour queries by pruning whole subtrees.
›
Space filling curves
geometry · low: Z-order/Morton (geohash) and Hilbert curves mapping multi-dimensional points to sortable keys
B+ tree
storage · low: Balanced high-fanout search tree with all values in linked leaves; the default on-disk index for point lookups and range scans.
›
d-ary heap
data-structures · low: Array heap with d children per node (d = 4 typical): half the binary heap's depth, siblings in one cache line, faster priority queues.
›
Exact geometric predicates
geometry · low: Robust orient and incircle tests with adaptive-precision floats (Shewchuk) or exact arithmetic
Partition pruning
storage · low: Skip whole partitions using partition transforms and predicate analysis
Predicate pushdown
storage · low: Move filters and projections into scans and remote sources
Relational algebra
storage · low: Relational operators and equivalence rules: selection pushdown, join reordering, projections
HyperLogLog
data-structures · low: Counts distinct elements in kilobytes with about 1 % error by tracking the longest run of leading zero bits in hashed values per bucket.
›
Quantile sketches
data-structures · low: Mergeable quantile sketches: t-digest, DDSketch, HDR histograms
+ 6 more primitives
System
Techniques · 5
Primitives · 22
geo-db
Polygon clipping
geometry · medium: Polygon intersection/union/difference (Weiler-Atherton, Martinez) for spatial predicates
Query optimizer
storage · medium: Cost-based plan search: join ordering (DP/greedy), rewrites, access path selection
Cardinality estimation
storage · medium: Row-count estimates from histograms, MCVs, sketches and sampling for the optimizer
Join order dynamic programming
storage · medium: DPccp and DPhyp enumeration of join orders with cost models; greedy fallback for many joins
Subquery decorrelation
storage · medium: Unnest correlated subqueries into joins via dependent join and magic sets
Point in polygon
geometry · low: Ray-casting/winding tests and indexed polygon lookup for reverse geocoding
Geodesic distance (haversine, Vince…
geometry · low: Shortest-path distance between two lat/lon points on the Earth: haversine on a sphere (about 0.5% error), Vincenty or Karney on the WGS84 ellipsoid (sub-millimetre).
›
Geospatial cell index (geohash, S2,…
geometry · low: Map a lat/lon to a 64-bit cell id on a hierarchical grid, so "near" becomes an integer range scan in any ordinary sorted index.
›
k-d tree
geometry · low: A binary tree that splits k-dimensional points by one coordinate per level, giving fast nearest-neighbour and box queries on static low-dimensional data.
›
Line simplification
geometry · low: Douglas-Peucker and Visvalingam polyline simplification
Map projections
geometry · low: Web Mercator, UTM and equal-area projections, datums and coordinate transforms
R-tree
geometry · low: A balanced tree of nested bounding boxes that indexes rectangles and points, answering window and nearest-neighbour queries by pruning whole subtrees.
›
Space filling curves
geometry · low: Z-order/Morton (geohash) and Hilbert curves mapping multi-dimensional points to sortable keys
B+ tree
storage · low: Balanced high-fanout search tree with all values in linked leaves; the default on-disk index for point lookups and range scans.
›
d-ary heap
data-structures · low: Array heap with d children per node (d = 4 typical): half the binary heap's depth, siblings in one cache line, faster priority queues.
›
Exact geometric predicates
geometry · low: Robust orient and incircle tests with adaptive-precision floats (Shewchuk) or exact arithmetic
Partition pruning
storage · low: Skip whole partitions using partition transforms and predicate analysis
Predicate pushdown
storage · low: Move filters and projections into scans and remote sources
Relational algebra
storage · low: Relational operators and equivalence rules: selection pushdown, join reordering, projections
HyperLogLog
data-structures · low: Counts distinct elements in kilobytes with about 1 % error by tracking the longest run of leading zero bits in hashed values per bucket.
›
Quantile sketches
data-structures · low: Mergeable quantile sketches: t-digest, DDSketch, HDR histograms
Reservoir sampling
data-structures · low: Uniform k-sample from a stream of unknown length (Algorithm R/L)
Hash join
storage · low: Build a hash table on the smaller input's join key and probe it with every row of the larger one; the linear-time workhorse for equi-joins.
›
Fast hash functions
data-structures · low: Non-cryptographic hashes built from 64×64→128-bit multiplies and xor-shifts; pick by key size, trust level and whether the hash is persisted.
›
Quadtree octree
geometry · low: Adaptive spatial subdivision trees for queries and level of detail; loose and linear variants
LU and Cholesky factorization
numerics · low: Factor A = PLU (any square matrix, partial pivoting) or A = LLᵀ (SPD) once in O(n³), then solve each right-hand side in O(n²).
›
Newton root finding
numerics · low: Linearize at the guess and jump to the tangent root; quadratic convergence near a simple root, made robust by brackets (1D) or line search.
›
Copy for AI
Similar systems
Share the most building blocks with this one.
geocoder
25 %
wildfire-spread
23 %
fitness-tracking
19 %
gis-platform
16 %
map-tiles
16 %