← Back
Home › Systems › Databases and storage engines

geocoder

geocoding and address search

Nominatim, Google Geocoding

SystemTechniques · 5Primitives · 27 geocoder Address parsinggeometry · medium: Split free-text addresses into components (house, street, city, postcode) with rules or a sequence modelTrigram indexsearch-sort · medium: Trigram posting lists accelerating regex and substring searchInverted 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.›Named entity recognitionmachine-learning · medium: Find the character spans of entities in text and give each a type, by labelling every token and decoding a valid label sequence.›Linear-time regular expression matc…search-sort · medium: Match a regular expression in O(pattern x text) worst case by tracking all live parse positions at once, then cache the state sets as a lazily built DFA for speed.›Unicode text tokenization for searchsearch-sort · low: Turn multilingual text into index terms: segment words (UAX 29 style, CJK bigrams), normalize, case-fold and accent-fold, identically at index and query time.›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.›Address interpolationgeometry · low: Estimate a house-number position along a street segment from known address rangesGeodesic 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).›k-d treegeometry · 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.›Point in polygongeometry · low: Ray-casting/winding tests and indexed polygon lookup for reverse geocodingR-treegeometry · 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 curvesgeometry · low: Z-order/Morton (geohash) and Hilbert curves mapping multi-dimensional points to sortable keysFinite state transducersearch-sort · low: Minimal acyclic FST mapping sorted keys to values; compact term dictionaries with prefix/fuzzy searchLevenshtein automatasearch-sort · low: Levenshtein automata / edit-distance search over dictionaries for typo toleranceTop-k selectionsearch-sort · low: Keep the k best of n items without sorting all n - bounded min-heap for streams, quickselect for arrays, threshold pruning to skip most items.›Text normalizationmachine-learning · low: Rewrite messy text into one canonical form for matchers and models, or into spoken words for speech output (and back), keeping a map to the original offsets.›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.›Bit 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.›+ 11 more primitives

Similar systems

Share the most building blocks with this one.

geo-db 25 %search-engine 22 %product-search 18 %web-search 16 %code-search 15 %