← Back
Home › Systems › Transport, logistics and mobility

transit-planner

public transit trip planner

GTFS, RAPTOR

SystemTechniques · 5Primitives · 22 transit-planner Connection scan algorithmgraphs · medium: Earliest-arrival transit routing by scanning departure-sorted connections onceContraction hierarchies (shortcut-b…graphs · medium: Rank the nodes, remove them one by one while adding shortcut edges that keep distances intact, then answer queries with two tiny searches that only climb the ranking.›Raptor transit routinggraphs · medium: Round-based public transit / schedule routing (RAPTOR) with Pareto setsTime dependent shortest pathgraphs · medium: Shortest paths where edge costs depend on departure time (FIFO property, timetable graphs)Inverted indexstorage · medium: Map each term to a sorted, compressed list of the documents containing it; the core of full-text search and other fast set queries.›Dijkstra's algorithmgraphs · low: Single-source shortest paths with non-negative edge weights by settling vertices in order of distance with a priority queue.›Radix sortsearch-sort · low: Non-comparison sort that distributes keys by 8-bit digits; several times faster than comparison sorts on large arrays of integers, floats or fixed-size keys.›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).›R-treegeometry · low: A balanced tree of nested bounding boxes that indexes rectangles and points, answering window and nearest-neighbour queries by pruning whole subtrees.›Protobuf wire formatnetworking · low: Protocol Buffers wire format: tags, varints, length-delimited fields and schema evolutionFuzzy string matchingsearch-sort · low: Edit distance, Jaro-Winkler and trigram indexes for approximate name and address matchingW-TinyLFUsystems · low: An LRU window plus segmented LRU, guarded by a 4-bit Count-Min sketch that admits a newcomer only if it beats the victim's frequency.›d-ary heapdata-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.›BFS and DFSgraphs · low: The two basic graph traversals; BFS gives hop distances and levels, DFS gives discovery/finish order for cycles, components and topological order.›Calendar date arithmeticsystems · low: Civil dates, time zones (tzdb), DST gaps, month-end anchoring and duration mathBit packing and PFORcompression · low: Store blocks of integers with exactly b bits each and patch rare outliers separately (PFOR); the fastest integer codec family, billions of values per second.›Delta encodingcompression · low: Store differences between consecutive values instead of the values, turning sorted IDs, timestamps and counters into small numbers that pack into few bits.›Varint (LEB128)compression · low: Variable-length integers in 7-bit groups with a continuation bit; small numbers take 1 byte, the wire format of Protobuf, WebAssembly and DWARF.›BM25 rankingsearch-sort · low: The standard lexical relevance score: IDF-weighted term frequency with saturation (k1) and length normalization (b); default in Lucene, Elasticsearch and SQLite FTS5.›Sorted-list intersectionsearch-sort · low: Intersect sorted id lists by merging, galloping from the short list into the long one, and skipping whole compressed blocks, shortest list first.›SIMD programminghardware-os · low: Process 4-16 lanes per instruction with AVX2, AVX-512 or NEON via Rust std::arch, with runtime dispatch and a portable fallback.›+ 6 more primitives