GLX v1 specification

Generated from spec/v1/spec.md in the geolith/glx repository at commit 561a984.

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119.

Please refer to the change log for a documentation of changes to this specification.

Small sample files and the values they hold are in fixtures/.

1 Abstract

GLX is geolith's single-file format for map data that is queried, not rendered. A file holds one or more parts, each an independent byte range for one service:

• the search part: a geocoding index for full-text search over place names and addresses, autocomplete, reverse geocoding and lookup by id (Chapters 3 to 8);
• the routing part: a road graph cut into tiles, for routing (Chapter 10).

Each part is answered from the file while a reader holds only a small part of it in memory and reads the rest with HTTP range requests. A reader for one part never reads the bytes of another.

The recommended file extension is .glx. The recommended MIME type is application/vnd.glx.

2 Overview

A GLX file starts with a fixed 256-byte file header that lists its parts (2.6). The rest of this overview and Chapters 3 to 8 describe the search part; Chapter 10 describes the routing part.

The search part consists of a fixed 256-byte search header (Chapter 3) followed by thirteen sections (Chapters 4 and 5). Each section is a contiguous byte range; the search header's section table gives the offset and length of each, counted from the start of the part.

Seven sections are the boot sections: a reader loads them once, right after the header, and keeps them in memory. The other six hold the bulk of the data, cut into independently compressed blocks that a reader fetches one range at a time, as a query needs them.

           <------------------ boot span ------------------>+--------+------+-------+-------+------+------+-------+------+------+------+------+-------+-----+--------+| Search | term | spat. | doc   | chun-| id   | shape | rec. | dict-| post-| docu-| spat- | ids | shapes || header | idx  | dir   | index | ks   | dir  | dir   | dict | ion- | ings | ments| ial   |     |        ||        |      |       |       |      |      |       |      | ary  |      |      |       |     |        |+--------+------+-------+-------+------+------+-------+------+------+------+------+-------+-----+--------+P      P+256                                      (P: where the search part starts in the file)           <------------- in memory ------------------>  <--------- fetched block by block --------->

A file stores each place once, as a record in a document block. Places are numbered 0 to N - 1 in the order the writer added them; this number is the document number (or document) and is how every other section refers to a place.

2.1 Byte order and integer encodings

All fixed-width integers and floats are little-endian. u8, u16, u32, u64 are unsigned; i32, i64 are two's-complement signed; f32 is an IEEE 754 binary32.

varint: an unsigned integer in LEB128: seven bits per byte, least significant group first, the high bit of each byte set when more bytes follow. 0 is 0x00, 127 is 0x7F, 128 is 0x80 0x01, 300 is 0xAC 0x02. A varint in this format holds at most 64 bits (10 bytes). A reader MUST refuse a varint that is cut short by the end of its buffer or that runs past 64 bits.

zigzag varint: a signed integer v mapped to an unsigned one, (v << 1) ^ (v >> 63) (arithmetic shift), then written as a varint, so small magnitudes take one byte: 0 → 0, -1 → 1, 1 → 2, -2 → 3. Decoding is (u >> 1) ^ -(u & 1).

gap list: a list of ascending unsigned integers written as the first value, then each value minus the one before, each a varint.

delta list: a list of signed integers written as each value minus the one before (the first minus 0), each a zigzag varint.

2.2 Text

All text is UTF-8. A string stored with an explicit length is a varint byte count followed by that many bytes; it is not terminated. Term order (Chapter 5.6) is the order of the strings' UTF-8 bytes compared lexicographically as unsigned bytes, which is the order of their Unicode code points.

2.3 Coordinates

A coordinate is stored as a fixed-point i32 of millionths of a degree (1e-6 degree, about 11 cm): round(clamp(degrees, -L, L) * 1_000_000), rounding half away from zero, where L is 180 for a longitude and 90 for a latitude. Decoding is value / 1_000_000.

A box is four fixed-point i32 in the order west (minimum longitude), south (minimum latitude), east (maximum longitude), north (maximum latitude): 16 bytes.

2.4 Layers and countries

A place's layer is one of the strings venue, address, street, locality, county, region, country, or another string. Where a section stores a layer as a code, it is a u8:

A country code is an ISO 3166-1 alpha-2 code. Where a section stores it as a code, it is a u16 whose little-endian bytes are the code's two ASCII bytes as written in the record (so IN is 0x49 0x4E, the u16 value 0x4E49). Any string that is not exactly two bytes long is code 0.

2.5 Compression

Every block a reader fetches from a block section is exactly one zstd frame, decompressed on its own. A reader MUST NOT assume a frame states its content size, but writers SHOULD write it (the reference writer does).

Document blocks are compressed with the record dictionary (Chapter 5.12) when that section is not empty, and without a dictionary when it is empty. Every other block is compressed without a dictionary.

The compression level is the writer's choice. The reference writer uses zstd level 3 for posting, spatial and id blocks and level 19 for dictionary, document and shape blocks.

2.6 File header and parts

Every GLX file starts with this 256-byte file header:

• Magic number: always GLX0 in ASCII (0x47 0x4C 0x58 0x30). The 0 is part of the magic, not a version number.
• Version: always 1.
• Part count: the number of part entries in use, 1 to 7.
• Reserved and padding: writers MUST write zero; readers MUST ignore them. Unused part entries are all zero.

Each part entry is 32 bytes:

• Kind: four ASCII bytes naming the part: SRCH for the search part (Chapter 3), ROUT for the routing part (Chapter 10). A file holds at most one part of each kind.
• Offset and length: the part's byte range in the file. Parts do not overlap each other or the file header.
• Checksum: the XXH3-64 hash (seed 0) of the part's bytes. A reader that serves queries over HTTP does not read whole parts and so does not check it; a tool that copies a part from one file to another MUST check it, and a reader MAY.

Every offset inside a part is counted from the start of that part, so a part's bytes are the same in any file that holds it: a writer adds a part to a file, or merges the parts of several files into one, by copying each part's bytes unchanged and writing a new file header.

The first part starts at offset 256, right after the file header. A file that holds a search part lists it first, so that its search header is in the first 512 bytes. Further parts follow with no gaps, in part-table order; a reader MUST locate them through the part table only.

A reader MUST refuse a file whose magic is not GLX0, whose version is not 1, whose part count is 0 or above 7, that lists a kind twice, or whose parts overlap each other or the file header. A reader for one kind of part MUST refuse a file that holds no part of that kind, and MUST ignore parts of other kinds, including kinds this specification does not name. The reference reader refuses a file without the part it needs with a message naming the kinds the file does hold.

3 Search header

The search header is 256 bytes long and is always at the start of the search part. Every offset in it, and in the sections it locates, is counted from the start of the search part.

3.1 Overview

Offset     00   01   02   03   04   05   06   07   08   09   0A   0B   0C   0D   0E   0F         +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+000000   |       Kind        |     Reserved      |               Documents               |         +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+000010   |  Avg field length |  Importance wt.   |     Features      |     Reserved      |         +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+000020   |          Section 0 offset             |          Section 0 length             |         +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+  ...                                   sections 1 to 11         +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+0000E0   |          Section 12 offset            |          Section 12 length            |         +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+0000F0   |                                    Padding                                    |         +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+

3.2 Fields

Kind

Always SRCH in ASCII (0x53 0x52 0x43 0x48), the kind of the part's entry in the file header (2.6). A reader MUST refuse a search part whose kind field is not SRCH.

Reserved

Four bytes at offset 4. Writers MUST write zero. Readers MUST ignore them.

Documents

A u64: the number of places in the file, N. Document numbers are 0 to N - 1 and are stored as u32, so N MUST NOT exceed 2^32 - 1. A reader MUST refuse a header whose N exceeds 2^32 - 1.

Average Field Length

An f32: the average field length (Chapter 6.5) over all documents, computed as the sum of every document's field length divided by N in 64-bit floating point, then rounded to f32; 1.0 when N is 0. A reader uses it for BM25 length normalisation.

Importance Weight

An f32: the weight of a place's importance in its rank, chosen by the writer. It is used by readers when ranking (Chapter 8) and by the writer to choose head lists (Chapter 5.6.4). The reference writer is given it by its caller; the fixtures use 10.0.

Features

A u32 bit field. Each bit says how part of the file is encoded. Chapter 3.3 lists the bits and the rules for readers and writers.

Reserved

Four bytes at offset 28. Writers MUST write zero. Readers MUST ignore them.

Section Table

Thirteen entries, one per section in section-number order. Entry n is at offset 32 + 16 n: the section's offset from the start of the search part (u64), then its length in bytes (u64). A section of length 0 is empty; its offset is still where it would start. Every section lies inside the search part; a reader MUST refuse a search header whose section table points past the part's length.

Padding

Sixteen bytes after the section table. Writers MUST write zero. Readers MUST ignore them.

3.3 Feature bits

Bits 0 to 14 are required: every version 1 file has all of them set, and each one names an encoding that this specification describes as the only one. Bits 15 and 16 are optional: each selects between two encodings of one section, both described here. Bits 17 to 31 are reserved: they name nothing in this specification.

The required bits together are 0x7FFF. A file written by the reference writer with both optional bits set has features 0x1FFFF.

A writer MUST set every required bit. A writer MUST set an optional bit exactly when the section it governs is in the encoding the bit selects. A writer MUST NOT set a reserved bit.

A reader MUST refuse a search part whose features lack any required bit, or whose features set any bit the reader does not know (for a reader of this specification, any reserved bit): such a part was written to another layout and its records would not decode, or its words would be folded differently, so reading it would give empty or wrong answers rather than an error. The reference reader refuses it with the message "not a .glx file, or one built by an older or newer glx writer: rebuild it with the current geolith". A reader MUST support both encodings of each optional bit.

A bit added by a later revision is therefore refused by every reader that predates it, whether the revision calls it required or optional; files that leave it clear stay readable by those readers.

4 File layout

The search header is at offset 0 of the search part. Sections follow it with no gaps, in this order, which is not section-number order:

The boot span runs from the term index's offset to the end of the record dictionary. A writer MUST place the seven boot sections in it, back to back in the order above, starting at part offset 256, so that one range request after the header fetches all of them. The six block sections SHOULD follow in the order above; a reader MUST locate them through the section table only, never by position. The part SHOULD end at the end of its last section.

5 Sections

5.1 Term index

The index of the dictionary's blocks, one entry per dictionary block in term order.

Entries are in ascending term order, and so are the blocks they point to. The block that may hold a term t is the last block whose first term is less than or equal to t; when there is none, t is in no block.

5.2 Spatial directory

The top level of the two-level spatial directory: one node per group of 64 consecutive spatial blocks (Chapter 5.8), in block order.

24 bytes per node. Node k covers blocks 64 k to 64 k + count - 1; every node but the last has count = 64. The sum of count over all nodes is the number of spatial blocks, B.

5.3 Document index

The offset of every document block in the documents section, relative to the start of that section, followed by the section's length: D + 1 offsets for D = ceil(N / 256) blocks. Block i runs from offset i to offset i + 1. Offsets MUST be non-decreasing; the first is 0.

5.3.1 Wide form

Used when feature bit 16 is clear: D + 1 offsets, each a u64.

5.3.2 Compact form

Used when feature bit 16 is set.

D / 64 is integer division. The section's length MUST be exactly 8 + 8 (D / 64 + 1) + 2 D + 8 E. The length of block i is its u16 when that is below 0xFFFF, else the length its escape gives. A block of 2^32 bytes or more cannot be written in this form.

Offset i is anchor i / 64 plus the lengths of blocks 64 (i / 64) to i - 1. A reader MUST refuse the section when its length does not match its counts, the anchors decrease, the escapes are not in ascending block order, or the escape table does not hold exactly one entry for each 0xFFFF length.

5.4 Chunks

One 5-byte entry per chunk of 1024 consecutive documents (the last chunk may be shorter): ceil(N / 1024) entries.

A reader MAY use chunks to bound the rank of any document from a given number on.

5.5 Id directory

The top level of the two-level id directory: one node per group of 64 consecutive id blocks (Chapter 5.9), in block order.

16 bytes per node; as in Chapter 5.2, node k covers blocks 64 k on, and the counts sum to the number of id blocks, I.

5.6 Dictionary and postings

The dictionary section is a sequence of dictionary blocks, each a zstd frame, located through the term index (5.1).

5.6.1 Terms

A term is either a word, a folded index token (Chapter 6), or a prefix key: the character U+0001 followed by the first 2 to 6 characters (Unicode scalar values) of a word. Prefix keys sort before every word that starts with a letter or a digit.

Each term appears in the dictionary exactly once, in ascending term order across all blocks.

A decompressed dictionary block is:

The reference writer closes a block once its entries pass 32 KiB (256 KiB when feature bit 15 is clear); readers MUST NOT depend on block sizes.

5.6.2 Term entry

Kinds above 2 are reserved: writers MUST NOT write them, and a reader MUST refuse an entry that has one, since nothing says what follows it.

A stored term frequency is a u8: the low seven bits are the number of times the word occurs in the place, which is always 1 (feature bit 1); the high bit (0x80) is the name flag, set when the word is one of the place's name words (Chapter 6.4). For prefix keys max tf is 1.

Prefix keys hold no term frequencies. Whether an entry is a word or a prefix key is told by its first character, not by its kind.

5.6.3 Posting blocks

A posting block lists documents holding a term, ascending, with what a reader needs to rank and filter them without reading their records.

A word's posting block:

A prefix key's posting block is the same without the term frequencies and the lengths: count, documents, importances, layers, countries.

The quantized importance of a place of importance x is the smallest q in 0..=255 with q / 255 ≥ min(max(x, 0), 1) (computed in binary32): ceil(x × 255) raised until it is not below x, so q / 255 is an upper bound on the importance.

A term's list is inline (kind 0) when its whole posting block is in the term entry. Otherwise it is external (kind 1): the list is cut into posting blocks of at most 512 postings, each compressed into its own zstd frame, stored one after another in the postings section. The reference writer stores a list inline when it holds at most 16,384 documents and its posting block is at most 16,384 bytes; readers MUST accept either kind for any list.

An external list in the term entry:

A skip entry:

The frame of block b is at postings offset + list offset + skip offset. Blocks of one list are in ascending document order and do not overlap.

5.6.4 Head lists

A head is a short list of a term's best documents, so that a one-word query can be answered without walking the term's postings. Each entry is 12 bytes:

Inline entries have an empty head. The reference writer gives an external word the up to 32 documents of highest score + weight × importance (weight from the header), best first, earliest document first on ties, where the score is the BM25 of the word alone (Chapter 8), plus the name weight 3.0 when the name flag is set. For an external prefix key the score is 0 and the order is by importance. The choice and order of head documents is implementation-defined; a reader MAY use a head only as a set of documents that hold the term together with their stored scores.

5.6.5 Prefix layout

Prefix keys are written for every word of a place as written (Chapter 6.4; not the name initials), for each length from 2 to 6 characters the word reaches. A place appears at most once in each prefix key's list.

When feature bit 15 is set, every prefix key of 2 to 6 characters has an inline or external list.

When feature bit 15 is clear, prefix keys of 4 to 6 characters have lists as above, while prefix keys of 2 or 3 characters are kind 2 (head only): doc freq is the number of documents holding the prefix, max tf is 1, and the head holds the up to 32 most important of them, most important first, earliest first on ties, with score 0. A reader of such a file answers a 2- or 3-character prefix from its head alone.

5.7 Documents

The documents section is a sequence of document blocks, each one zstd frame (compressed with the record dictionary when there is one, 2.5), located through the document index (5.3). Block i holds documents 256 i to 256 i + 255 (fewer in the last block), in order; document d is entry d mod 256 of block d / 256.

A decompressed document block is stored column by column:

A plain string column is n varint lengths followed by the n entries' bytes, one after another. A table column is the number of distinct entries m (varint), their m varint lengths, their bytes one after another, then n varint indices into the distinct entries, one per record. The reference writer lists distinct entries in order of first appearance. A reader MUST refuse an index of m or more.

Every entry of every column except 9, 10 and 15 is UTF-8 text, empty when the place has no such field. The block ends with column 15.

5.7.1 Name text

name_text is every name of the place (its name, translations and other names), space-separated. Column 10's entry is a tag byte, then:

• tag 0 (derived): bytes r; name_text is the name (column 0) followed by r;
• tag 1 (literal): name_text is the remaining bytes.

Tag 0 is only possible when name_text starts with the name; the reference writer then always uses it.

5.7.2 Search text

search_text is the text the place is indexed by (Chapter 6). Column 9's entry is a tag byte, then:

• tag 1 (literal): search_text is the remaining bytes;
• tag 0 (derived): a varint k, which MUST end the entry. The name text MUST be derived; let r be its bytes after the tag. Then search_text is the concatenation of
  1. the name (column 0),
  2. r without its last k bytes,
  3. when A is not empty, a space and A,
  4. the last k bytes of r,
  5. when S is not empty, the character U+001F and S,
  
  where A is the non-empty ones of street, locality, county, region and country, in that order, joined by single spaces, and S is the non-empty ones of neighbourhood and borough, joined by a single space. k MUST NOT exceed the length of r, and the split MUST fall on a character boundary.

A writer MAY use tag 0 whenever some k rebuilds search_text exactly; the reference writer uses the smallest such k.

U+001F in search_text is the language mark: the words after it are indexed but not counted in the field length (6.5).

5.7.3 Languages

Column 14 holds the place's names by language: entries of a language code (an OpenStreetMap name:<code> code), the character U+001F, and the name, joined by U+001E. Empty when there are none.

5.7.4 Box

Column 15 is empty, or four zigzag varints: the outline's west, south, east and north in fixed-point, each minus the record's own longitude, latitude, longitude and latitude respectively. A reader MUST refuse an entry that has bytes after the fourth varint.

5.8 Spatial

Every place, in Hilbert order, cut into spatial blocks of at most 512 places: the answer to reverse geocoding and to box restrictions. Spatial blocks are numbered 0 to B - 1 in order.

5.8.1 Order

The reference writer orders places by the Hilbert index (5.8.4) of their quantized position (Chapter 6.6), then by document number, and fills every block but the last with 512 places. Readers MUST NOT depend on the order or the block size: a block's box, below, is all a reader relies on.

5.8.2 Section layout

B is the sum of the spatial directory's node counts (5.2). An entry:

A block's box MUST hold every place in the block; a node's box MUST hold the boxes of its blocks. The entries of node k are entries first to first + count - 1, at section offset + 28 first.

5.8.3 Spatial block

A decompressed spatial block of n places:

A reader MUST refuse a block whose counts run past its end, or whose deltas leave the u32 range of a document or the i32 range of a coordinate. The coordinates are the record's (5.7) exactly.

5.8.4 Hilbert index

The Hilbert index of a cell (x, y) of the 65,536 × 65,536 grid, both u16, is the u32 d computed as:

d = 0for s in 32768, 16384, ..., 1:    rx = 1 if x & s else 0    ry = 1 if y & s else 0    d += s * s * ((3 * rx) ^ ry)    if ry == 0:        if rx == 1:            x = 65535 - x            y = 65535 - y        swap(x, y)

5.9 Ids

Every (id, document) pair, sorted by id as a signed i64 and then by document, cut into id blocks of at most 1024 pairs: lookup of a place by the id of its record. Ids need not be unique: every place with the id is found. Id blocks are numbered 0 to I - 1.

5.9.1 Section layout

An entry:

The entries of id-directory node k (5.5) are entries first to first + count - 1.

5.9.2 Finding an id

Because ids repeat, the pairs of one id may span blocks. The blocks that may hold id v are: the last block whose lowest id is below v, and every block whose lowest id equals v. The same rule over the nodes' lowest ids gives the nodes whose entries to read.

5.9.3 Id block

A decompressed id block of n pairs:

The block MUST end after the documents. The full ids are not in the block: a reader takes every pair whose fingerprint is that of the asked id, reads the documents' records, and keeps those whose record id (5.7) is the asked id.

5.10 Shape directory

One 16-byte entry per shape block, in block order:

Entries are in ascending first-document order. The shape of document d, if it has one, is in the last block whose first document is at most d. A file whose places have no shapes has an empty shape directory and an empty shapes section.

5.11 Shapes

A sequence of shape blocks, each one zstd frame. A shape is a place's outline as polygons; only some places have one. The reference writer closes a block once its shapes pass 128 KiB.

A decompressed shape block:

Documents in a block are strictly ascending. The block MUST end with the last shape.

A shape:

The shape MUST end after its last point. A reader MUST refuse a shape with a coordinate beyond ±180 degrees.

5.12 Record dictionary

A zstd dictionary, as defined by RFC 8878 §5, with which every document block is compressed; or empty, in which case document blocks are plain zstd frames. The reference writer trains the dictionary (at most 110 KiB) on a sample of the file's own raw document blocks when there are at least 8 blocks, and leaves the section empty otherwise. Feature bit 9 is set in both cases.

6 Text processing

What a place is found by: how a writer turns search_text and name_text into terms. Everything in this chapter is normative for writers, because readers look terms up by their exact bytes; the query-side rules of Chapter 6.7 are what a reader needs to find them.

The Unicode algorithms named here are those of the Unicode version of the reference implementation (the Rust crates unicode-segmentation 1.13 and unicode-normalization 0.1.25). A writer on another Unicode version MAY fold or segment rare characters differently.

6.1 Folding

fold(w):

1. Lowercase every character (full Unicode lowercase mapping).
2. Decompose to NFD.
3. Walk the characters with a flag diacritics, initially true. A combining mark (General Category Mn, Mc or Me) is dropped when diacritics is true and kept otherwise. Any other character is kept and sets diacritics to whether its code point is in U+0000–U+08FF, U+1D00–U+1FFF, U+2C60–U+2C7F, U+A640–U+A69F, U+A720–U+A7FF or U+FB00–U+FDFF (Latin, Greek, Cyrillic, Armenian, Hebrew, Arabic and their extensions).

So Café folds to cafe, while an Indic vowel sign, which tells words apart (दिल्ली, दुल्लु), is kept. The result is not recomposed.

6.2 Index tokens

index_tokens(text) walks the words of text by Unicode word boundaries (UAX #29, words that hold at least one letter or digit), keeping a pending Chinese and Japanese run (a list of units) and a pending initials string:

1. A word all of whose characters are CJK (below) joins the run: when the word does not start where the previous CJK word ended, the run is first flushed (6.3). Each character becomes a unit of its own, except U+3099 and U+309A, which join the unit before them. Go to the next word.
2. Otherwise flush the run.
3. If the word is one ASCII letter (an initial), append fold(word) to the initials string and continue at step 6.
4. Else, if the word contains . and every part between dots is an initial: flush the initials (below); emit fold of each part, then the folded parts joined; go to the next word.
5. Else flush the initials.
6. If the word contains an apostrophe (' or U+2019): emit fold of each part between apostrophes that has 2 characters or more (when not empty), then fold of the word with its apostrophes removed. Else emit fold(word).

At the end, flush the run, then the initials. Flushing the initials emits the initials string when it has 2 characters or more, and empties it. Empty tokens are dropped.

M G Road gives m, g, mg, road; D.Y. Patil gives d, y, dy, patil; Swensen's gives swensen, swensens; Rue de l'Église gives rue, de, eglise, leglise.

6.3 Chinese and Japanese pairs

A character is CJK when its code point is U+3005, U+3007, U+3021–U+3029, U+3040–U+30FF, U+31F0–U+31FF, U+3400–U+4DBF, U+4E00–U+9FFF, U+F900–U+FAFF or U+20000–U+3FFFF.

Flushing a run of u units emits nothing when u = 0, fold of the unit when u = 1, and otherwise fold of each pair of adjacent units (the u - 1 pairs, in order). The run is then empty. 東京タワー gives 東京, 京タ, タワ, ワー.

6.4 A place's terms

For a place with search text s, name text t, name m and layer l:

• Its words are index_tokens(s) with repeats removed, the first of each kept.
• Its name initials: when l is neither address nor street, split m at every character that is not alphanumeric, drop empty pieces and the pieces of, and, the, for (compared lowercased); when 3 to 6 pieces remain and each starts with an ASCII letter, the initials are those letters lowercased, joined (State Bank of India gives sbi). When the initials are not already one of its words, they are added as a word after the others.
• A word's name flag (5.6.2) is set when it is one of index_tokens(t) or the name initials.

The place is in the posting list of each of its words, with stored term frequency 1 plus the name flag, and in the list of each prefix key (5.6.1) of 2 to 6 characters of each of its words other than the name initials.

6.5 Field length

The field length of a place is the number of distinct written words in its search text before the first language mark U+001F:

1. Take the text before the first U+001F.
2. Remove each apostrophe (', U+2019) that has a word character just before and just after it.
3. Split at every character that is not a word character (a letter, a digit, or a combining mark of General Category Mn, Mc or Me).
4. Fold each piece; count the distinct non-empty results.

So a run of ideographs counts as one word, and names after the language mark do not lengthen the field. The field-norm id is the index of the largest entry not above the field length in tantivy's 256-entry field-norm table (tantivy/src/fieldnorm/code.rs), whose entries are 0 to 40 exactly and then grow geometrically. The posting length byte is the field length capped at 255.

6.6 Quantized position

The reference writer orders spatial blocks (5.8.1) by the Hilbert index of the cell (x, y) with x = round((clamp(lon, -180, 180) + 180) / 360 × 65534) and y = round((clamp(lat, -90, 90) + 90) / 180 × 65534), each 0 for a NaN coordinate.

6.7 Query side

A reader SHOULD turn query text into terms the same way the writer did:

1. Remove each possessive 's (an apostrophe after a word character, then s or S, then the end or a non-word character).
2. Remove each apostrophe between two word characters.
3. Split at non-word characters (6.5); keep at most 12 pieces.
4. A piece with any CJK character gives index_tokens(piece); any other gives fold(piece).

The word terms are looked up as they are; a prefix of the last query word (autocomplete) is looked up as the prefix key of its first 2 to 6 characters.

7 Reading over HTTP

A reader that holds the file in object storage reads it with HTTP range requests (Range: bytes=a-b), and MAY merge requests for nearby ranges. The order below is what this format is laid out for.

7.1 Opening

1. Fetch bytes 0 to 511: the file header and, since a file with a search part lists it first (2.6), the search header. Check the file header (2.6), find the SRCH entry, then check the search header's kind, feature bits and document count (3.2, 3.3).
2. Fetch the boot span (Chapter 4): from the term index's offset to the end of the record dictionary, both counted from the start of the search part. Keep the seven boot sections in memory.

A reader MAY instead fetch a fixed first range (for example the first 64 KiB) and fetch the rest of the boot span only when the header shows it is longer. The boot span is small for small files, and tens of megabytes for a planet.

7.2 Search and autocomplete

1. Dictionary: for each query term, find its dictionary block in the term index and fetch the blocks (one wave, in parallel).
2. Postings: for external terms, fetch the posting blocks the query needs, located by the skips, in as many waves as the reader's strategy takes.
3. Records: fetch the document blocks of the candidates, located by the document index, to read their records.

7.3 Reverse geocoding and boxes

1. Choose the spatial-directory nodes whose box meets the search area and fetch their second-level entries.
2. Fetch the spatial blocks whose box meets the area.
3. Fetch the document blocks of the places kept.

7.4 Lookup by id

1. Choose the id-directory nodes that may hold the ids (5.9.2) and fetch their second-level entries.
2. Fetch the id blocks that may hold the ids.
3. Fetch the document blocks of the matching fingerprints, and, for shapes, the shape blocks (5.10), in the same wave.

8 Ranking (informative)

Ranking is implementation-defined. This chapter describes the reference reader so that the fields above make sense; nothing here constrains a conforming reader.

The reference reader ranks a place by BM25 + name bonus + phrase bonus + importance weight × importance. BM25 is tantivy's (k1 = 1.2, b = 0.75, length normalised by the field-norm id against the header's average field length, idf = ln(1 + (N - df + 0.5) / (df + 0.5))); terms in a tenth of the documents or more score zero. The name bonus is 3.0 times the share of query words found with the name flag; the phrase bonus is 2.0 times the share of neighbouring query-word pairs found next to each other, in order, in the name. Every query word is required first; if that finds too few places, about three quarters of them. Posting lengths, importances and the chunks bound a candidate's rank so that most candidates are ruled out without their records; records give the exact rank.

9 Conformance

A conforming writer:

• writes the file header of 2.6, with each part's checksum;
• writes the search header of Chapter 3 with every required feature bit, and an optional bit exactly when the governed section uses that encoding;
• lays the sections out as Chapter 4 orders;
• writes each section in the layout of Chapter 5, and every term by the rules of Chapter 6.

A conforming reader:

• refuses files as 2.6 and Chapter 3 require, and supports both encodings of each optional bit;
• locates its part through the part table, every section through the section table, and every block through its directory;
• decodes every block of Chapter 5, refusing a block that is cut short or inconsistent where this specification says so, rather than reading it as empty;
• does not depend on the reference writer's block sizes, orders or head choices where this specification marks them as the writer's choice.

The files in fixtures/ are written by the reference writer. fixtures/fixtures.json lists, for each, its header, its section table, the number of dictionary and document blocks, the first records of its first document block, and queries with the ids the reference reader answers them with. fixtures/describe.ts (node spec/v1/fixtures/describe.ts) produces that file from the bytes with a decoder written from this document alone.

9.1 Notes

• The magic ends in 0 while the version is 1: the magic names the format, the version field names the specification (2.6).
• Feature bits 8 (SHAPES) and 9 (RECORD_DICTIONARY) mean the sections exist, not that they are non-empty: a file without shapes, or too small to train a dictionary, still sets them.

10 Routing part

The routing part holds a road graph cut into graph tiles: each tile holds the nodes, directed edges, edge shapes and names, access rules and turn restrictions of one cell of a grid. Each tile is stored as fixed-size blocks, each its own zstd frame, so a router reads only the parts of a tile a route touches and keeps the tile index in memory. A part may also hold a customizable contraction hierarchy per costing profile (10.5).

10.1 Graph tiles

A graph tile is a byte string in the graph tile format of Valhalla 3.9.1 (commit 2085e78a517a0680a39d3b89efb7eff1f5cf9201): a 272-byte tile header, then its records and sections in that format's order. This specification does not repeat that layout; the geolith-routing crate is the reference codec and is tested to reproduce reference tiles byte for byte. The tile header holds the offset of every section, and nodes, directed edges, transitions, access restrictions and signs are fixed-size records, so a reader that has the first block of a tile can compute the byte range of any record.

Tiles sit on three grids, the levels: level 0 of 4° cells, level 1 of 1° cells and level 2 of 0.25° cells, each covering longitudes −180 to 180 and latitudes −90 to 90, with cells numbered row by row from the south-west. A tile's key is the u32 level | cell << 3, the low 25 bits of the format's graph id; the key orders tiles by level, then cell.

10.2 Layout

The routing header is at offset 0 of the routing part. It is 64 bytes, or 80 when the part sets feature bit 0:

• Kind: always ROUT in ASCII. A reader MUST refuse a routing part whose kind field is not ROUT.
• Block size: the bytes of tile data per block, B. It MUST be a power of two from 4096 (4 KiB) to 16777216 (16 MiB); a reader MUST refuse any other value. The reference writer uses 65536 (10.4).
• Features: bit 0 (CCH) means the part holds a customizable contraction hierarchy (10.5) and the header ends with the CCH directory's (offset, length). No other bit is defined; writers MUST write 0 for them and readers MUST refuse a part that sets any. A reader that only routes over tiles MAY ignore the CCH sections, but it MUST still read the 80-byte header to find the boot span.
• Tile count: the number of tiles, T.
• Section table: three (offset, length) pairs, each counted from the start of the routing part, for the sections below in this order. Every section MUST lie inside the part.

The boot sections follow the routing header back to back: the tile index, the tile dictionary and, with feature bit 0, the CCH directory, so that one range request fetches the header and the boot span; the tiles follow them, then the CCH sections. A reader MUST refuse a part whose CCH directory does not directly follow the tile dictionary. A reader that does not yet know the features fetches the first 80 bytes.

Tile index: T entries of 16 bytes, in ascending key order with no key twice:

• Tile length: the graph tile's length in bytes, L. The tile has N = ceil(L / B) blocks.
• First frame length: the length of block 0's frame; 0 if and only if L is 0.
• Stored length: the length of the tile's stored bytes (below); 0 when L is 0, and otherwise at least 4 N plus the first frame length.

A reader MUST refuse an index whose length is not 16 T, whose keys do not ascend, or whose entry breaks a rule above. Tiles are stored in index order with no gaps, so a tile's offset in the tiles section is the sum of the stored lengths before it; a reader computes these sums once, when it opens the part, and MUST refuse an index whose stored lengths do not add up to the tiles section's length.

Tile dictionary: a zstd dictionary that every block frame is compressed with; empty when the tiles use none.

Tiles: for each tile, its block directory, then its N block frames in block order with no gaps.

• Block directory: N u32 values, the length of each block's frame. Every length is at least 1. A reader MUST refuse a directory whose lengths, plus 4 N, do not add up to the stored length, or whose first length differs from the index's first frame length.
• Block b holds tile bytes b B up to min((b + 1) B, L): every block but the last holds exactly B bytes. Its frame is one zstd frame (2.5), with the tile dictionary when it is not empty, and MUST decompress to exactly those bytes; a reader MUST refuse a frame that decompresses to any other length.

The directory and the first frame are adjacent, so one range request fetches both: the head of a tile, at the tile's offset with length 4 N plus the first frame length. Block 0 holds the 272-byte tile header because B is at least 4096.

10.3 Reading

1. Fetch the file header (2.6) and find the ROUT entry.
2. Fetch the routing header and the boot span; check the kind, the block size, the features and the tile index, and keep the index and the dictionary in memory.
3. For each tile a route search needs, find its key in the index (binary search) and fetch its head. A missing key means the cell has no roads. Block 0 gives the tile header and so the offset of every section.
4. To read tile bytes s up to s + n, fetch and decompress the blocks floor(s / B) to floor((s + n − 1) / B) the reader does not hold; their frames lie at the tile's offset plus 4 N plus the sum of the directory lengths before them. A reader MAY drop blocks it no longer needs and fetch them again later, and MAY coalesce the frames of adjacent blocks into one range request.

A reader MUST treat every graph tile as untrusted input: a record that points outside the tile, or past the end of a section, is refused, never read in part.

10.4 Block size (informative)

A Cloudflare Worker has 128 MB per isolate. Valhalla maps whole tiles into memory, which needs the page cache of a server; a Worker has no file to map, so a router that decompresses whole tiles holds them whole on its heap. Berlin's largest tiles are 47 MB and 53 MB; with one frame per tile, a route over Berlin held a median of 121 MB of tile bytes (157 MB at most) plus up to 50 MB of frames, and 87 of 100 test routes ran out of memory. The search part solves the same problem with blocks behind a directory (5.4), and PMTiles with a directory of independently compressed tiles fetched by range; this chapter applies the same pattern inside a tile.

Measured over the 100 auto routes of the router's reference test (Berlin, seed 42), counting every byte the router reads: snapping touches a few hundred kilobytes of a tile (edge bins, nearby nodes and edges, under 1% of edge info), but the search touches up to 81% of the nodes and directed edges of the largest tile, and trip building reads at most 30 KB of edge info and 1.5 KB of names. Splitting a tile into a graph frame (every section before edge info) and paged edge info therefore does not bound memory: the graph sections of the tiles a route touches reach 130 MB. Paging the whole tile does:

At 64 KiB the part is as small as with one frame per tile, a route holds at most 48.7 MiB of decompressed blocks (under 64 MiB, with room for the frames in flight), and the blocks of a tile are adjacent, so a reader coalesces them into few requests. Readers that need a tighter bound drop blocks (10.3, step 4).

10.5 Customizable contraction hierarchy

With feature bit 0, a routing part also holds, for each of one or more costing profiles (auto, pedestrian, bicycle), a customizable contraction hierarchy (CCH; Dibbelt, Strasser and Wagner, ACM JEA 21, 2016) of that profile's metric over the part's graph, so a router answers a route by reading the records of the endpoints' ancestors instead of searching the tiles. Every profile is independent: its own vertices, order and sections.

Vertices and weights. A profile's vertices are the directed edges it may use, one per internal-turn state a search label on the edge can carry, plus a copy of each edge on the via chain of a complex turn restriction; an arc is a turn the profile's forward search may take, weighted by the transition cost plus the entered edge's cost. A vertex's rank is its position in a nested-dissection order; ranks number the vertices 0 to V − 1. Weights are the costs in units of the profile's weight scale milli cost units, rounded up, at least 1; the hierarchy is exact on these weights. The cost of a route is recomputed from the graph tiles; the weights only choose it.

CCH directory (a boot section):

• Tile count MUST equal the routing header's.
• Tile edge positions: for each tile in index order, the edge position of its directed edge 0, then the total number of directed edges E; ascending. Edge i of the tile at index position k has edge position positions[k] + i.
• Profile entry: the name (16 bytes ASCII, padded with zero bytes, at least one byte), u32 vertex count V, u32 weight scale, u32 block counts of its three sections (vertex map, records, road lists), u32 reserved 0, then each section's (u64 offset, u64 length) from the start of the part.
• Block tables: for each profile in order and each of its three sections, one (u32 first item, u32 frame length) per block. The items are edge positions for the vertex map and ranks otherwise. The first items MUST start at 0 and ascend, each below the section's item count (E, or V); block b holds items from its first item to the next block's (or the item count). Frames are stored in block order with no gaps and MUST add up to the section's length. A reader refuses a directory whose lengths do not add up or that has bytes left over.

Each block is one zstd frame without a dictionary that decompresses to at most 16 MiB; the reference writer ends a block after the item that brings it to 64 KiB. A block's items are encoded back to back as LEB128 varints; zig-zag maps a signed delta d to (d << 1) ^ (d >> 63).

Vertex map, one entry per edge position: the number of ranks k (0 when the profile cannot use the edge); then the first rank (the edge's own vertex, no internal turn, not a copy) and k − 1 zig-zag deltas of the others; then, when k > 0, the ancestor runs: the union of the elimination-tree ancestors of those ranks, each rank included, as a run count and per run the gap from the previous run's end (from 0 for the first; at least 1 after it) and the run length minus one.

Records, one per rank r: the kept up directions (the reduced query graph after perfect customization: the arcs to higher ranks a shortest path may take, travelled r → h), then the kept down directions (travelled h → r). Each list is a count, then per arc the head's delta from the previous head (from r for the first; at least 1) and the weight.

Road lists, per rank r: the counts of its kept up and down directions, then for each of them in record order the directed edges entered along it, start excluded, in travel order: a count, then the first raw graph id and zig-zag deltas of the rest.

Reading a route. Snap the endpoints to edges (10.3); read their vertex-map entries; read the records of every rank in the sources' ancestor runs and in the targets' (one parallel wave), search upwards from both sides and take the best common ancestor; read the road lists of the path's arcs (a second wave); read the tiles for those edges (a third wave). A reader MUST treat every CCH block as untrusted: a head that does not ascend, a rank outside V, a run that overflows or a list cut short is refused.