RFC 3: Tiled and multiscale points#

RFC 3 · draft · data model; storage format · created 2026-09-17

Authors: Luca Marconato (@LucaMarconato)
Input from Nicolas Fernandez (@cornhundred), Arne Defauw, Jonas Windhager, Ilan Gold, Ignatius Jenie, Mark Keller, Christian La France, Tim Treis, Marco Varrone, Sonja Stockhaus, Brian Long, Clarence Mah

Abstract#

Specification for spatially indexing points, enabling optional multiscale subsampled levels, spatially chunked storage: a regular 2-D or 3-D grid of tiles, with the points stored in tile-major order and, optionally, in feature-major order. Each point carries a random value \(p\), which defines the levels. This enables viewers and other processing applications to load only the points in view, or only those of the genes shown; zoomed out, they load a density-preserving sample, with as many points as the resources they have available allow (memory, bandwidth, rendering time). Shapes are in RFC 4.

Overview of the spatial index. Top: 44 points of genes A and B and of a rare gene C (3 points, one kept at level 1, none at level 2) on a rectangular support, shown at three levels; level 0 on a grid of 8 × 4 rectangular tiles holds all the points (p < 1), level 1 on 4 × 2 tiles holds those with p < 0.3, level 2 on 2 × 1 tiles holds those with p < 0.1. Each point has a random value p in [0, 1), shown on a ruler split into bands 2, 1 and 0 at 0.1 and 0.3. Bottom: the tile-major table holds every point once, as bands (coarsest first), tiles inside each band and rows sorted by p; tile_offsets point at the first row of each tile, and the row groups follow the tiles, with small tiles of a band sharing one row group. Two queries are shown. View 1 (dashed red), one tile of level 1 with all genes: it reads level 1, so the tile-major table reads two compact ranges, the rows of band 2 in the tile of level 2 that contains it and the rows of that tile in band 1 (5 rows). The feature-major table holds the same points sorted by gene, then band, then tile, then p: the 3 points of the rare gene C are one short range at its end. Inside each gene and band the rows are again grouped by tile, shown by separators in both tables. Its tile_offsets point at the start of each tile inside each gene's band, and its row groups follow one gene in one band, with small ones sharing a row group. For view 1 the feature-major table reads the same 5 rows, but as one range per gene and band, found through its tile_offsets. View 2 (dashed green), another region with only the rare gene C selected, drawn on all three levels: it fits, so all its bands are read, at every level. The tile-major table reads all the rows of the tiles of view 2 in every band (6 rows in 4 ranges) and discards the other genes, drawn faded, to keep 1 row of gene C; the feature-major table reads only that row.

Overview of the spatial index; each part is described in the text.#

Description#

The key words MUST, MUST NOT, SHOULD, SHOULD NOT and MAY are to be interpreted as described in RFC 2119. Key words have this meaning only in capitals (RFC 8174).

Motivation#

Without an index, a reader can already skip the Parquet row groups whose minimum and maximum coordinates fall outside a box, and data written in spatially grouped row groups (as by the 10x Xenium and Atera software) then answer box queries quickly on a local disk: in a test with 1.2 billion transcripts, a 200 µm box kept 15% of the row groups and scanned 176 million rows to return 0.5 million points, in 0.2 s on a 14-core laptop with the data in memory. This does not hold remotely, where the same query reads gigabytes instead of the few megabytes of the tiles in view; it cannot sample, so a zoomed-out view reads every row group; and it cannot select features, unless the data happen to be sorted by feature. These are the cases the index is for.

Scope#

  • In scope: points, 2-D and 3-D; spatial indexing via chunking and sorting; tile-major order and feature-major order; sampled levels; a per-point random value \(p\).

  • Out of scope: shapes (RFC 4), the matrix of a table annotating the shapes and its sparse storage (CSR/CSC, RFC 4), aggregation to cells or bins (square/hexagonal), spatial orders inside tiles (Morton, Hilbert), ordering of the tiles other than C order (e.g. Morton).

Data model#

The data model does not depend on how the points are stored, in Parquet or in Zarr (Storage format).

Overview#

This section is an overview: it lists all the terms of the spatial index and how they relate. Each is defined in the sections that follow, starting from the tiles, then \(p\), which defines levels and bands on top of them; Summary lists them again in a table, with which are required. The terms are in three layers: the data, the data model and the storage format.

Data. The points with their columns (coordinates, feature, any other) are always there, as today. The data model and the storage format of the spatial index are optional: an element may have no spatial index at all. If it has one, some of its parts MUST be present, others SHOULD or MAY be.

Data model. It says which tile and which level each point belongs to:

  • grid parameters: the axes; per axis, the origin \(o_a\) and the tile size \(s_a\) of level 0; the grid of every coarser level, which refines the next one (recommended recipe: the merge rule) (Grid and tiles);

  • sampling parameters: a random value \(p\) per point, and the fraction \(P^{(l)}\) of each level, a fixed rate, by default the ratio of the tile volumes of level 0 and level \(l\) (\(1/2^d\) per level when all \(d\) axes are merged); level \(l\) holds the points with \(p < P^{(l)}\) (Priority, Levels and bands, Sampling);

  • derived from these, the number of points per tile at each level, which guides the choice of the tile size and the rates together (Choosing the tile size and the rates);

  • the feature column (e.g. the gene), which sorts the feature-major order (Tile-major order and feature-major order).

Storage format. It says how the points are written (Storage format), in Parquet or in Zarr:

  • the metadata declares which parts are present: the orders (tile-major and feature-major), the levels, and the grid and sampling of each level; in Parquet, a sidecar JSON file lists the part files of each table;

  • each order is one table, with the levels as bands of rows, with offsets that address rows: tile_offsets in the tile-major table (the tile index) and in each feature-major table (the feature index), and the column __spatialdata_p__, which stores \(p\); the row groups (Parquet) or chunks (Zarr) are a choice of the writer.

Grid and tiles#

A grid is defined for a specific points element (the SpatialData term for a 2D/3D points cloud), in the coordinates of its points. The metadata MUST specify the axes of the grid, and the grid MUST have all the spatial axes of the element; it MAY have a single tile along an axis, for instance along \(z\) for a thin section of tissue.

Each element has its own grid, chosen for its own data: two elements, for instance the transcripts and the cells of a dataset, do not have to share a grid (see RFC 4 for the shapes, which recommends nested grids when a client loads both tile by tile).

An axis \(a\) is one of the spatial axes \(x\), \(y\) and \(z\) (not the channel axis \(c\)). The grid has, per axis \(a\), an arbitrary origin \(o_a\), which MUST be given (for instance the corner with the minimum coordinates of the bounding box of all the points), one tile size \(s_a\), which MUST be given (square tiles are a special case), and an arbitrary number of tiles \(n_a\): the number of intervals into which the grid divides axis \(a\), not the total number of tiles of the grid, which is \(N = \prod_a n_a\). All the tiles are identical. The tiles MUST cover all the points. Each tile is to be interpreted as a semi-open hyper-interval, with the interval closed for the lowest value, and open for the highest. For example, in 2 dimensions, the tile

\[[\, x_{\min},\ x_{\max} \,) \times [\, y_{\min},\ y_{\max} \,)\]

contains the points \((x, y)\) that satisfy \(x_{\min} \le x < x_{\max}\) and \(y_{\min} \le y < y_{\max}\).

The grid of every level present, \(0, \dots, L\), MUST be given in the metadata (see Metadata); since level 0 is always present, so is its grid. The grids of the coarser levels are the writer’s choice, with one constraint: the grid of each level \(l\) MUST refine the grid of level \(l + 1\), that is every tile of level \(l\) MUST lie inside a single tile of level \(l + 1\), so that no tile of a finer level overlaps several tiles of a coarser level. The grids SHOULD get coarser with the level, but a level MAY keep the grid of the level below, since a grid refines itself: at the limit, a single tile for the whole dataset at every level, or the same grid at all the levels, which avoids the many small, almost empty tiles of the coarse levels of a rare feature.

A recommended recipe, the merge rule, builds the grid of each coarser level from the grid of the previous level: it is merged by a factor of 2 along one or more axes, keeping the tiles as isotropic as possible. It satisfies the constraint, since the origin stays the same and each tile size is either kept or doubled, and the initial grid then determines the granularity of the spatial index at every level. Below are two merging steps that keep the tiles as isotropic as possible: in the first, by merging along one axis; in the second, by merging along two axes.

Two tiles of size 2 × 2 × 1, stacked along z, become one tile of size 2 × 2 × 2.

Merging along one axis (z). Tile sizes along (x, y, z).#

Four tiles of size 1 × 1 × 2, side by side along x and y, become one tile of size 2 × 2 × 2.

Merging along two axes (x and y). Tile sizes along (x, y, z).#

The rule in formulas

Let \(s_a^{(l)}\) and \(n_a^{(l)}\) be the tile size \(s_a\) and the number of tiles \(n_a\) along axis \(a\) at level \(l\). At level \(l\):

  • \(A^{(l)}\) are the axes that still have more than one tile at level \(l - 1\);

  • \(m^{(l)}\) is the smallest tile size among them;

  • \(M^{(l)}\) are the axes that will be merged at level \(l\): those of \(A^{(l)}\) whose tile size is less than twice \(m^{(l)}\).

\[\begin{split}\begin{aligned} A^{(l)} &= \{\, a : n_a^{(l-1)} > 1 \,\} \\ m^{(l)} &= \min_{a \in A^{(l)}} s_a^{(l-1)} \\ M^{(l)} &= \{\, a \in A^{(l)} : s_a^{(l-1)} < 2\, m^{(l)} \,\} \\ s_a^{(l)} &= \begin{cases} 2\, s_a^{(l-1)} & a \in M^{(l)} \\ s_a^{(l-1)} & \text{otherwise} \end{cases} \qquad n_a^{(l)} = \begin{cases} \lceil n_a^{(l-1)} / 2 \rceil & a \in M^{(l)} \\ n_a^{(l-1)} & \text{otherwise} \end{cases} \end{aligned}\end{split}\]

Applied to the end, the merge rule stops at the first level with \(n_a = 1\) along every axis (a single tile). A writer may also stop earlier, so the lowest-resolution level may still contain multiple tiles.

Example: an anisotropic extent, 10 × 100 × 1000 along (z, y, x), origin 0.

Anisotropic tiles: initial tile size 1 × 10 × 100

Starting from “# tiles along axis” 10 × 10 × 10, the thin axes are merged first; z then stops at a single tile, and x is merged last:

level  tile size (z, y, x)  # tiles along axis (z, y, x)  merged
0         1 ×  10 ×  100    10 × 10 × 10                  -
1         2 ×  10 ×  100     5 × 10 × 10                  z
2         4 ×  10 ×  100     3 × 10 × 10                  z
3         8 ×  10 ×  100     2 × 10 × 10                  z
4        16 ×  20 ×  100     1 ×  5 × 10                  z, y
5        16 ×  40 ×  100     1 ×  3 × 10                  y
6        16 ×  80 ×  100     1 ×  2 × 10                  y
7        16 × 160 ×  200     1 ×  1 ×  5                  y, x
8        16 × 160 ×  400     1 ×  1 ×  3                  x
9        16 × 160 ×  800     1 ×  1 ×  2                  x
10       16 × 160 × 1600     1 ×  1 ×  1                  x

Tiles ordering#

At each level, the tiles are indexed by their coordinates along the axes and ordered by a single tile id, in C order (row-major): the last axis declared in the metadata varies fastest.

A grid of 3 × 4 tiles with axes (y, x); each tile shows its coordinates (t_y, t_x) and its id, 0 to 11, increasing along x first and then along y.

Tile ids on a 2-D grid with axes (y, x) and 3 × 4 tiles: \(k = 4\, t_y + t_x\).#

The tile id in formulas

At a given level, with the origin \(o_a\), the tile size \(s_a\) and the number of tiles along axis \(a\), \(n_a\), as in Grid and tiles, the tile containing a position \(p\) has, along each axis \(a\), the coordinate

\[t_a(p) = \left\lfloor \frac{p_a - o_a}{s_a} \right\rfloor, \qquad 0 \le t_a < n_a .\]

With the axes \(a_1, \dots, a_d\) in the order declared in the metadata, its id is

\[k(p) = \sum_{j=1}^{d} t_{a_j}(p) \prod_{i = j + 1}^{d} n_{a_i},\]

i.e. each coordinate is multiplied by the number of tiles along all the axes that come after it. For the usual axis orders:

\[\begin{split}\begin{aligned} \text{2-D, axes } (y, x):\quad & k = t_y\, n_x + t_x \\ \text{3-D, axes } (z, y, x):\quad & k = (t_z\, n_y + t_y)\, n_x + t_x \end{aligned}\end{split}\]

With \(N = \prod_a n_a\) tiles, \(0 \le k < N\).

One could instead order the tiles by Morton code (Z-order), which keeps tiles that are close in space close in the order. This is not done in this version and is left for future versions.

Priority#

Every point \(i\) MUST have a uniformly sampled random value \(p_i \in [0, 1)\), termed priority, adapted from the continuous level of detail of van Oosterom et al., 2022 and Schütz et al., 2019. It is drawn once when the points are written and MUST be stored with them, as a column (see Columns). Any uniform random generator may be used, and \(p\) may be derived from a hash of the point. The priority is fixed: it defines which points are in which level, and the order of the rows inside a tile, in both orders of the points. When an element that already has \(p\) is indexed again (another tile size, the other format, a new feature-major table), writers MUST keep its \(p\), so that the levels hold the same points.

\(p\) MUST be of the form \(k / 2^{b}\), with \(k\) an integer in \([0, 2^{b})\) and \(b\) the precision declared in the metadata (p_bits, see Columns): it is stored as \(k\), and comparisons with the fractions \(P^{(l)}\) are then exact. Writers SHOULD draw \(k\) directly as a random integer. Drawing a real number and rounding it is a common mistake: for instance, a value \(u = 0.99999999\) drawn in \([0, 1)\) in double precision becomes exactly 1 when rounded to single precision (float32 has 24 bits of precision, so every \(u \ge 1 - 2^{-25}\) rounds to 1), and \(p = 1\) belongs to no level, since level 0 holds the points with \(p < P^{(0)} = 1\). In the same way, rounding can move a value across a fraction \(P^{(l)}\), so that the band of a point computed before and after rounding disagree.

Levels and bands#

Every point belongs to exactly one band \(l \in \{0, \dots, L\}\), \(L \ge 0\), given by its \(p\) and by fractions \(1 = P^{(0)} > P^{(1)} > \dots > P^{(L)}\) (see Sampling):

\[\text{band } L = \{\, i : p_i < P^{(L)} \,\}, \qquad \text{band } l = \{\, i : P^{(l+1)} \le p_i < P^{(l)} \,\} \quad (l < L)\]

With \(L = 0\) there is a single band, with all the points; bands \(1, \dots, L\) MAY be present. The comparisons are strict: a point with \(p = P^{(l)}\) exactly is not in level \(l\). The tiles of band \(l\) are those of the grid of level \(l\). Level \(l\) is the union of the bands \(L, L - 1, \dots, l\), the points with \(p < P^{(l)}\); level 0 holds all the points.

The axis of p from 0 to 1, cut at P(2) and P(1) into three disjoint bands, 2, 1 and 0. Below, level 2 covers band 2; level 1 covers bands 2 and 1; level 0 covers all three bands.

A level is the union of its band and all coarser bands.#

This is the priority-band (continuous level of detail) organization of van Oosterom et al., 2022, with discrete bands on a grid.

Tile-major order and feature-major order#

An order is a table with all the points and all their columns, sorted in a given way. The points are written in exactly one tile-major order and in zero, one or more feature-major orders, one per feature column chosen by the writer and named in the metadata:

  • tile-major order, which MUST be written: sorted by band (coarsest first, see Levels and bands), then by tile id on the grid of the band, then by \(p\);

  • feature-major order, optional, for a given feature column named in the metadata: sorted by feature, then by band, then by tile id, then by \(p\). The feature is a categorical column chosen when writing: for spatial transcriptomics, usually the gene id. A writer MAY choose several feature columns, for instance the gene id and the cell type, each with its own feature-major table; it SHOULD choose at most one, the column used most often to select points, for the best performance at the lowest storage cost.

Both orders hold exactly the same points at every level; only the order of the rows differs, so a client gets the same result from either, at a different cost. Since each order is sorted by band, coarsest first (see Levels and bands):

  • each point is stored once per order: the levels need no extra storage (up to 1.33× in 2-D if each level were a table of its own);

  • going to a finer level reads only the next band; the points already loaded stay valid;

  • with the rows of each tile sorted by \(p\), a client can stop reading at any budget \(b\), not only at the \(P^{(l)}\) of the levels (see Reading with a budget).

The two orders answer two different questions with a contiguous range of rows:

  • Tile-major order: which points are in this region? The points of a tile are one row range, whatever their gene. A client showing the region reads the tiles in view.

  • Feature-major order: where are the points of this gene? The points of a gene are one row range; inside it, the points of each band are one range, and inside a band the points of each tile. A client showing a few genes reads only their points.

A client looking for the points of a feature uses the feature-major table of that column if there is one. Otherwise it falls back to the tile-major table, as for any other column: it reads every point of the tiles in view and discards the other features, so the cost grows with all the points in view, not with the points of the feature; zoomed out, this can be most of the data. The price of the feature-major table is a second table of the points. Per-tile statistics (e.g. which features a tile contains, or how many points of each) could let a client skip tiles without the feature it shows and improve performance; they are out of scope for this RFC.

Eight points of genes A and B in two tiles, each with its p. Level 1 is a single tile with the points p < 0.25 (A5, B2, A3), which form band 1; the other five form band 0. Tile-major table: band 1 (A5, B2, A3), then band 0 by tile (tile 0: A1, B8; tile 1: A7, B6, B4). Feature-major table: gene A (band 1: A5, A3; band 0: A1, A7), then gene B (band 1: B2; band 0: B8, B6, B4); a second row of brackets shows the tiles inside each band of each gene (band 1: tile 0 of level 1; band 0: tiles 0 and 1).

The two orders, as bands. Each table holds every point once, in the band of the coarsest level that holds it: band 1 is level 1 (\(p < 0.25\)), and both bands together are level 0.#

Sampling#

Sampling chooses the fractions \(P^{(l)}\) of the levels (see Levels and bands). The fractions are fixed rates: they do not depend on how many points the tiles hold, and the same \(P^{(l)}\) applies to all the points, whatever their feature, and to both orders. Level \(l\) keeps the points with \(p < P^{(l)}\).

By default, the fraction of a level is the ratio of the tile volumes (areas in 2-D) of level 0 and of that level:

\[P^{(l)} = \frac{V^{(0)}}{V^{(l)}}, \qquad V^{(l)} = \prod_a s_a^{(l)} .\]

A tile of level \(l\) then covers \(V^{(l)} / V^{(0)}\) tiles of level 0 and keeps that fraction of their points, so it holds on average as many points as a tile of level 0 in the same region, whatever axes were merged. With the merge rule, each level divides the fraction by 2 per merged axis: \(1 / 2^d\) per level when all \(d\) axes are merged (1/4 in 2-D, 1/8 in 3-D), more when only some are. A writer MAY choose any other rates, as long as they strictly decrease with \(l\). When a level keeps the grid of the level below, the tile volume does not change and the default would keep the same fraction; the writer then chooses the rates, e.g. \(1/2^d\) per level. Dense regions stay denser than sparse ones: the sample is density-preserving.

Because \(p\) is uniform, keeping the points with \(p < P^{(l)}\) keeps each point with probability \(P^{(l)}\), independently of the others.

The \(P^{(l)}\) of every level present, including \(P^{(0)} = 1\), MUST be given in the metadata (see Metadata); a reader uses the values of the metadata, whatever rates the writer chose.

Sampling in formulas

A tile of level \(l\) with volume \(V^{(l)}\) (area in 2-D) in a region of density \(\rho\) holds on average

\[n^{(l)} = \rho\, V^{(l)}\, P^{(l)}\]

points. With the default rates \(P^{(l)} = V^{(0)} / V^{(l)}\) the two factors cancel, and \(n^{(l)} = \rho\, V^{(0)} = n^{(0)}\) at every level. With the merge rule and all \(d\) axes merged at every level, \(V^{(l)} = 2^{d\,l}\, V^{(0)}\) and \(P^{(l)} = 2^{-d\,l}\). For example, in 2-D with tiles of 10 × 10 at level 0 and of 40 × 40 at level 2, a tile of level 2 covers 16 tiles of level 0 and keeps 1 point in 16.

A client MAY support only level 0 and ignore the sampled levels, and show zoomed-out views with other strategies, such as aggregation (see RFC 4).

Choosing the tile size and the rates#

The levels and the tiles let a client read only a part of the data: the tiles in view, at a level coarse enough for the view. This works well only if the tile size and the rates suit the data and each other. There is no parameter for this in the format: the number of points per tile at each level, \(n^{(l)}\), follows from the density of the points, the tile size and the rates (see Sampling), and guides the choice of the two.

A good target is the number of points a client can comfortably load and display at once from one tile, for now about 10,000, while this RFC is a draft; it will be adjusted from user feedback. The reasoning: with the coordinates and a feature code, about 16 bytes per point, a tile is about 160 kB before compression, a comfortable size for one request, and a view of 4 × 4 tiles shows about 160,000 points, which a browser renders easily. The target is not stored in the metadata and is not a cap: level 0 holds all the points, and a tile may hold any number of them.

The tile size of level 0 SHOULD be chosen for the typical tile, not for the densest one: the median number of points per non-empty tile of level 0 SHOULD be about the target, between 5,000 and 20,000, which usually gives \(10^4\) to \(10^5\) tiles at level 0. If the typical region has \(\rho\) points per unit of area (2-D) or volume (3-D), the tile size along each of the \(d\) axes is about

\[s \approx \left( \frac{n^{(0)}}{\rho} \right)^{1/d}.\]

This estimate assumes that the tiles are isotropic. In practice, a writer can pick a tile size, compute the median number of points of the non-empty tiles, and adjust. Real data are uneven: sizing the tiles for the densest tile makes the typical tile far too small. In two 10x Atera datasets (740 million and 1.2 billion transcripts), tiles sized so that the densest tile holds 10,000 points were 7–9 µm wide, with a median of 200–350 points per tile and 0.8 to 1.9 million tiles; tiles of 27–35 µm give a median of 6,000–9,000 points and 50,000–120,000 tiles. The densest tiles then hold about 100,000 points, which is not a problem: the rows of a tile are sorted by \(p\), so a client reads only as many of them as its budget allows (see Reading with a budget), and the storage splits large tiles into several row groups or chunks (see Points as a tall table).

With the default rates, \(n^{(l)} = n^{(0)}\): the tiles then hold about the same number of points at every level (see Sampling). What is stored per tile is a band, a part of its level: band \(l\) holds a fraction \(1 - P^{(l+1)} / P^{(l)}\) of the level-\(l\) points of the tile (3/4 in 2-D with all axes merged).

The cost of a view stays about the same as the client zooms in and out, plus one cost of the bands: to show a small region at full detail, a client also needs the points of the coarser bands in that region. These are stored in the larger tiles of the coarser levels, so the client reads those larger tiles and discards the points outside the view.

Four panels with the same target of 40 points per tile. (a) 4 × 4 tiles on uniform points, densest tile 37 points. (b) 2 × 2 tiles, densest tile 127 points, all tiles above the target. (c) 16 × 16 tiles, densest tile 6 points. (d) 4 × 4 tiles with a hotspot, one tile of 220 points, the others at most 16.

The tile size of level 0 for a target of 40 points per tile, on 400 points.#

The figure shows the edge cases:

  • (a) Tiles that fit: the typical tile holds about the target number of points.

  • (b) Tiles too large: the tiles of level 0 hold far more points than the target. Level 0 is not sampled, but a client zoomed in does not have to load a whole tile: its rows are sorted by \(p\), so the first rows are a fair sample of it (see Reading with a budget), and the storage can split it into several row groups or chunks (see Points as a tall table). The cost is coarser spatial selection: a client still reads tiles that are only partly in view. A finer grid is better.

  • (c) Tiles too small: many tiles with few points each, so a view needs many small requests and the index is large. With the default rates, each level keeps about as many points per tile as the level below, so the tiles of the coarser levels hold few points too, and a view needs many small requests at every level.

  • (d) Hotspot: a region much denser than the rest puts many points in a few tiles. A tile size chosen for the hotspot is too small elsewhere, as in (c); one chosen for the rest is too large in the hotspot, as in (b), and handled as in (b): this is why the tile size is chosen for the typical tile. A future extension could address this with an adaptive grid, if the community identifies it as a need.

The grid and the rates are the same for all the features, so a rare feature has few points per tile, and at the coarser levels few or none: in the feature-major table most of its tiles are empty. This is not a problem: an empty tile holds no rows and costs nothing in the feature index, which stores only the non-empty tiles of each feature (see Feature index), and the rows of a feature are contiguous, sorted by band, so a client showing a rare feature reads all its levels, down to level 0, as one contiguous range.

Reading with a budget#

Sometimes a client does not have the resources to read all the points of the tiles in view, even at the right level: for instance with tiles that are too large, as in case (b). Here \(p\) comes into play. With a budget \(b \in (0, 1]\), the client reads only the points with \(p < b\): since \(p\) is uniform, a representative sample of a fraction \(b\) of the points, and since the rows of each tile are sorted by \(p\), the first rows of each tile. The budget is not limited to the fractions \(P^{(l)}\) of the levels: the client reads the coarsest level with \(P^{(l)} \ge b\), the bands coarser than \(l\) in full and band \(l\) up to \(p < b\).

Storage format#

The data model above can be implemented both in Parquet and in Zarr, and this RFC describes both. SpatialData already stores points in Parquet, so the Parquet format is to be interpreted as the default, and the Zarr format as experimental. Whether the Zarr format replaces it or the two coexist will be determined from user feedback and real usage; Zarr would also be more flexible for 3-D shapes (meshes, see RFC 4) and closer to zarr-vectors (see Related work).

The two formats have the same layout and the same metadata; they differ only in how a table of points is stored (Parquet files or a Zarr dataframe), and Parquet adds one file of its own, the Parquet sidecar (see Metadata). The offsets are Zarr arrays in both formats.

The format is self-contained: compatible with the way OME-NGFF stores coordinate systems, but usable on its own, even outside an OME-Zarr store, because its metadata is defined as a Zarr convention. Compatible means that this storage of points could in the future be proposed as an OME-NGFF extension, with the extensibility mechanism of NGFF RFC-8, and later, through an NGFF RFC, as part of the OME-NGFF specification. This is not a goal for now: for the time being this specification remains part of SpatialData, and is neither an official OME-NGFF extension nor OME-NGFF compliant.

The spatial index is optional (see Overview). Without it, an element is stored as today (see Compatibility). With it, the metadata declares which parts are present (see Metadata).

Points as a tall table#

In both formats, each table of points is a tall table: one row per point, one column per attribute. The tile index and the feature index address rows (see Tile index, Feature index), so how the rows are grouped into row groups (Parquet) or chunks (Zarr) does not change the index: a row group or a chunk may hold several small tiles, and a large tile may span several. A reader maps a range of rows to the row groups or chunks that overlap it: in Zarr, with chunk length \(c\), the rows \([\,a, b\,)\) are in the chunks \(\lfloor a / c \rfloor, \dots, \lfloor (b - 1) / c \rfloor\); in Parquet, through the part files of the table (see Metadata) and the row counts in their footers. A range of rows MAY span several row groups, chunks, part files or shards, and readers MUST support it.

The row groups and chunks are a choice of the writer, guided by two costs. Each row group or chunk is one unit of reading: a tile smaller than it costs the read of its neighbours, so they should not be much larger than the tiles in view. Each row group also adds an entry, per column, to the footer of its Parquet file, which a reader parses before it reads any row of that file: tiny row groups make the footers large (with one row group of about 10,000 rows per tile, 740 million points give 67,000 row groups and footers of about 2.6 MB per part file). Recommendations:

  • Parquet writers SHOULD use row groups of about 100,000 to 1,000,000 rows (a few MB compressed), each holding several consecutive tiles, and SHOULD split a larger tile into several row groups. A row group SHOULD start at the start of a tile. In the feature-major table, the same with the rows of one feature in one band.

  • Parquet writers SHOULD start a new part file only at the start of a tile of a band (tile-major table) or of a feature in a band (feature-major table), so that the rows of a tile are in a single file.

  • Zarr writers SHOULD choose a chunk length of the same order as the rows of a typical tile, and SHOULD store the chunks in shards (Zarr sharding codec), e.g. of a few million rows: with chunks of one tile and no shards, a table has one object per chunk and per column (about 74,000 per column for 740 million points). Writers MUST NOT write the same shard concurrently from several processes or threads without coordination: a partial write of a shard rewrites the whole shard.

Another option in Zarr is rectilinear chunk grids, an experimental Zarr feature that allows chunks of different sizes along an array: each tile would then be one chunk of its own size.

A spatial index without a spatial subdivision is a special case of this format, not a separate one: a grid with a single tile covering all the points, the same at every level (see Grid and tiles). Each band is then one range of rows sorted by \(p\), so any first rows of a band are a uniform sample of it, which a reader can load progressively.

File layout#

The two formats have the same layout; only the tables differ (Parquet files or a Zarr dataframe, see Columns):

points/<name>/
├── zarr.json                      # attrs incl. spatial_index
├── spatial_index.parquet.json     # Parquet only: the Parquet sidecar
├── spatial/                       # tile-major order, all bands
│   ├── points.parquet/            # Parquet: part files, listed in the sidecar
│   │   ├── part.000000000000.parquet
│   │   └── …
│   ├── points/                    # Zarr instead: df: convention
│   │   ├── columns                # ["x", "y", "z", "gene", "__spatialdata_p__", …]
│   │   ├── column_0               # x
│   │   ├── …
│   │   └── column_3/              # gene, enum: convention (codes, enum_values)
│   └── tile_offsets/              # the tile index of each band: 0, 1, … (Zarr arrays)
└── feature/                       # optional: one feature-major table per entry of feature_keys
    └── gene/
        ├── points.parquet/        # Parquet; or points/ (Zarr)
        └── tile_offsets/          # the feature index of each band: 0, 1, … (Zarr groups)

In Zarr, the offsets sit next to the dataframe, not inside it: the df: convention requires all the members of the group to be columns of the same length. The offsets SHOULD be chunked so that a lookup reads one small chunk, e.g. 65,536 entries.

Metadata#

The metadata is a Zarr convention, spatial_index, in the zarr.json of the Zarr group of the points element, next to the existing attributes of the element, the same in both formats. It is registered in zarr_conventions with its name and the URL of this specification; the uuid and a JSON schema are optional and will be added when the convention is released. levels lists the levels present, level 0 first, each with its grid and its fraction:

{
  "zarr_conventions": [
    {
      "name": "spatial_index",
      "spec_url": "https://spatialdata-spec.scverse.org/rfcs/0003-tiled-points.html",
      "description": "Tiled and multiscale points"
    }
  ],
  "spatial_index": {
    "version": "0.1.0-draft",
    "axes": ["x", "y", "z"],
    "feature_keys": ["gene"],
    "p_bits": 16,
    "levels": [
      {
        "origin": [0.0, 0.0, 0.0],
        "tile_size": [35.0, 35.0, 40.0],
        "grid_shape": [280, 170, 1],
        "P": 1.0
      },
      {
        "origin": [0.0, 0.0, 0.0],
        "tile_size": [70.0, 70.0, 40.0],
        "grid_shape": [140, 85, 1],
        "P": 0.25
      }
    ],
    "parquet": "spatial_index.parquet.json"
  }
}

version is the version of this specification that the element follows; it MUST be given, so that readers can tell future versions (e.g. with tiles in Morton order) apart. While this RFC is a draft, the version carries the suffix -draft. Following the versioning of Zarr conventions, a released version will also be referenced by a spec_url (and schema_url) pinned to that version, e.g. a tagged URL. axes MUST list all the spatial axes of the element (see Grid and tiles). levels[l] gives the grid of level \(l\): origin, tile_size and grid_shape (the number of tiles \(n_a\) along each axis, here a single tile along z). P is the fraction \(P^{(l)}\) of the level (here 1/4, the default in 2-D tiles), the same for both orders: level \(l\) holds the points whose value of \(p\) is below P. The P of level 0 MUST be 1: level 0 holds all the points. p_bits is the precision of \(p\) (see Columns). feature_keys lists the feature columns, each with its own feature-major table (see File layout); it is empty if there is none. The tile-major table is always present.

parquet is present only in the Parquet format: the path, relative to the element, of the Parquet sidecar, a JSON file that holds what exists only because the Parquet tables are split into several files:

{
  "tables": {
    "spatial": {
      "files": ["spatial/points.parquet/part.000000000000.parquet",
                "spatial/points.parquet/part.000020000564.parquet", "…"],
      "first_row": [0, 20000564, "…", 740442119]
    },
    "feature/gene": {
      "files": ["feature/gene/points.parquet/part.000000000000.parquet", "…"],
      "first_row": [0, "…", 740442119],
      "categories": ["ACTA2", "CD3E", "…"]
    }
  }
}
  • files MUST list the part files of each table, in order, relative to the element: the rows of the table are the rows of these files, one file after the other. Readers MUST NOT rely on the order in which a directory lists the files, and writers SHOULD zero-pad the numbers in the file names (as above), so that tools that list and sort the directory read the files in the same order.

  • first_row[i] is the first row of files[i] in the table, and the last entry is the number of rows of the table (len(first_row) == len(files) + 1). A reader finds the file that holds a row from it, and opens only the footers of the files it reads.

  • categories (feature-major tables): the global category list of the feature column, in the order of the codes of the feature index (see Feature index). In Zarr the global list is the enum_values of the feature column, so it needs no sidecar.

The sidecar is kept out of zarr.json for two reasons: it grows with the number of part files (about 45 bytes per file, plus the categories), while spatial_index stays small, and keeping it apart makes clear which parts of the format are specific to Parquet. With part files of millions of rows, it is a few kilobytes for most datasets.

Columns#

  • x, y, z: float32, absolute, in the element’s coordinate system. (Spacing of float32 at 10 cm in µm units is about 8 nm, well below localization error.)

  • Feature: integer codes with the category list stored once. In Zarr, the column follows the enum: convention: the arrays codes and enum_values, the categories; the number of features is the length of enum_values. In Parquet, a dictionary-encoded column. Parquet stores the dictionary of a column once per row group, so the dictionary of a row group SHOULD hold only the categories present in that row group, in any order: with tens of thousands of features, a full dictionary in every row group dominates the size of the table (9.3 GB of 23 GB in a test with 27,000 genes and one row group per tile). The codes inside a row group are then local to it; the codes of the feature index refer to the global list of the Parquet sidecar. Writers SHOULD keep the pandas metadata in the schema of the Parquet files, so that readers such as dask read the column as a categorical (the per-row-group dictionaries are unified when reading).

  • \(p\): in the column __spatialdata_p__, a name reserved by SpatialData, the same in every element, stored as an unsigned integer \(k\), with \(p = k / 2^{b}\) and \(b\) = p_bits of the metadata: uint16 for \(b = 16\) (recommended), uint32 for \(b = 24\) or \(32\) (see Priority). The levels need \(P^{(L)} \ge 2^{4 - b}\), so that the coarsest level still holds a fraction close to \(P^{(L)}\): with \(b = 16\) and the default rates in 2-D, at most 6 levels besides level 0; more levels need \(b = 24\). Ties between equal values are harmless: levels compare \(p\) with \(P^{(l)}\), and ties may be in any order inside a tile.

  • Any other columns, unchanged. An identifier column of the points (e.g. transcript_id) is not needed by the index, and writers MAY drop it: points are usually not annotated by a table, and their only relationship, being within a cell, is either computed when needed (a spatial join) or stored as a column of the points. Sorting by tile also removes most of the compression of a sequential identifier (3.8 GB in the test above).

In Zarr, each table of points is a dataframe following the df: convention: one 1-D array, or a group read as one, such as an enum: column, per column, all of the same length.

Order of the columns#

Within a row group, Parquet stores the values column by column: a row group holds the values of the first column, then those of the second, and so on, in the order of the schema. The coordinate columns SHOULD come first and next to each other, in the order of axes, followed by the feature column(s) and __spatialdata_p__, then by the other columns. A client reading the coordinates and the feature of a tile then reads one contiguous byte range instead of one per column. This is also the column order of the Celldega profile (PR #423), where it makes column projection and filtering in the browser more efficient with parquet-wasm.

In Zarr, each column is an array of its own, all with the same chunk length, so the same chunks of each array hold the same rows: a client reads a tile with one request per column and per chunk that overlaps the tile, whatever the order of the columns. The coordinate and feature columns SHOULD still come first, in the same order as in Parquet.

A tall table of three columns x, y, z (blue, red, green) and three tiles of 4, 2 and 3 rows. In Parquet, row group 0 holds tile 0 and row group 1 holds tiles 1 and 2; each row group holds all its x values, then all y, then all z, in one byte range. In Zarr each column is an array of its own, column_0 to column_2, cut into chunks of 4 rows independently of the tiles: chunk 0 is tile 0, chunk 1 holds tile 1 and the start of tile 2, chunk 2 the end of tile 2.

The tiles are row ranges. In Parquet the row groups follow the tiles; in Zarr the chunks have a fixed length and may cut a tile.#

Tile index#

To find the points of a tile, a reader uses the tile index of a band of the tile-major table. Since the rows of a band are sorted by tile id, the points of each tile are consecutive rows. The index of band \(l\), which MUST be written, records where each tile starts: an integer array tile_offsets/<l> (\(O\)) with one entry per tile plus one, for the \(N\) tiles of the grid of level \(l\), in rows of the table. The points of tile \(k\) in the band are the rows

\[[\, O_k,\ O_{k+1} \,), \qquad O_0 = \text{first row of the band}, \quad O_N = \text{end of the band},\]

so tile \(k\) holds \(n_k = O_{k+1} - O_k\) points. An empty tile has \(O_k = O_{k+1}\): it repeats the offset of the next tile, so that the formula holds for every \(k\) and the end of a tile is always the start of the next. The rows of the band are \([\, O_0, O_N \,)\): the range of each band follows from its tile index. A reader reads these rows from the row groups or chunks that overlap them (see Points as a tall table). A client with a budget \(b\) reads the first rows of the tile, until it reaches a row with \(p \ge b\).

The offsets are global row numbers of the table, in both formats. Their integer type MAY be the smallest that holds the number of rows of the table: int32 below \(2^{31}\) rows, int64 otherwise; readers take it from the metadata of the Zarr array. The same holds for the arrays of the feature index.

Feature index#

Each feature-major table MUST have its own feature index, per band. Inside a band the rows of the table are grouped by feature, then by tile, so the points of feature \(g\) in tile \(k\) are one range of rows. Most features are absent from most tiles, and the index stores only the non-empty tiles of each feature, as a CSR (compressed sparse row) structure over the features: a Zarr group tile_offsets/<l> with three arrays,

tile_offsets/<l>/feature_ptr: [n_features + 1]          # entries of feature g: feature_ptr[g] … feature_ptr[g+1] - 1
tile_offsets/<l>/tile_ids:    [nnz]                     # the non-empty tiles of each feature, increasing
tile_offsets/<l>/row_offsets: [nnz + n_features]        # their first row, + the end of the feature in the band

For feature \(g\), with \(a\) = feature_ptr[g] and \(e\) = feature_ptr[g+1], the non-empty tiles are tile_ids[a:e], and the \(j\)-th of them holds the rows [row_offsets[a + g + j], row_offsets[a + g + j + 1]); the last entry of the feature, row_offsets[e + g], is the end of its rows in the band. This extra end entry plays the role of the repeated offsets of the tile index: the end of a tile is the start of the next one, and the end of the last one is given explicitly, so that every non-empty tile is one range found in one array. A feature without points in band \(l\) has no entries in tile_ids and a single entry in row_offsets: the row where its range would start. With it, the rows of feature \(g\) in band \(l\) are always [row_offsets[a + g], row_offsets[e + g]), and, since the table is sorted by feature then band (coarsest first), the rows of feature \(g\) at level \(l\) (bands \(L, \dots, l\)) are one range, from the start of \(g\) in band \(L\) to the end of \(g\) in band \(l\).

Top, a feature-major table of one band with 11 rows: gene A in tiles 0, 2 and 5 (rows 0 to 5), gene B in tile 3 (rows 6 to 9), gene C in tile 1 (row 10). Left, the dense layout, a 3 by 7 matrix with an offset for every gene and every tile; the cells of empty tiles repeat the next offset and are greyed out; for the breast dataset this would be 27,104 by 759,595 entries for band 0. Right, the sparse layout used here: feature_ptr [0, 3, 4, 5], tile_ids [0, 2, 5, 3, 1] and row_offsets [0, 2, 3, 6, 6, 10, 10, 11]. Bottom, the rows of gene A in tile 5 found both ways: rows 3 to 6.

The feature index of one band. Left, for explanation only, a dense matrix with an offset for every feature and every tile, the end of each tile being the start of the next. It is not part of the format: it does not scale to whole-transcriptome panels (27,104 genes on a grid of 760,000 tiles would be \(2 \cdot 10^{10}\) entries, about 165 GB, for one band). Right, the format: only the non-empty tiles of each feature.#

The codes \(g\) are the positions of the features in the global category list: the enum_values of the feature column in Zarr, the categories of the Parquet sidecar in Parquet. In the example of the orders figure (see Tile-major order and feature-major order), with bands 1 and 0 and the 2 tiles of level 0, band 1 has feature_ptr [0, 1, 2], tile_ids [0, 0] and row_offsets [0, 2, 4, 5] (gene A: tile 0, rows 0 to 2; gene B: tile 0, rows 4 to 5), and band 0 has feature_ptr [0, 2, 4], tile_ids [0, 1, 0, 1] and row_offsets [2, 3, 4, 5, 6, 8] (gene A: rows 2 to 3 in tile 0 and 3 to 4 in tile 1; gene B: 5 to 6 and 6 to 8). Level 1 of gene A is rows \([\,0, 2\,)\) and level 0 rows \([\,0, 4\,)\).

The index has about one entry per non-empty pair of feature and tile: in a test with 740 million points, 27,104 genes and 760,000 tiles, 0.5 GB for all the bands.

TODO(Luca): Ilan suggests writing both orders by default, configurable; the proposal said “recommended but optional”. Pending his answer on the Google Doc comment (transcripts or cell matrix?).

Reading#

A client chooses a budget from the number of points in view, counted from the offsets without reading any point, then reads the bands from the coarsest one, from the feature-major table if it shows only some features and the table exists, otherwise from the tile-major table:

n = count_in_view(view, selection)                  # from the offsets, see below
b = min(1, max_points / n)                          # the budget, see "Reading with a budget"
l = coarsest level with P(l) >= b
if selection.features and selection.feature_key in feature_keys:
    for band in range(L, l - 1, -1):                # feature index of that table
        for g in selection.features:
            for k in non_empty_tiles(g, band) ∩ tiles_intersecting(view, level=band):
                yield prefix(rows_of(g, k, band), p < b)
else:                                               # tile-major table
    for band in range(L, l - 1, -1):
        for k in tiles_intersecting(view, level=band):
            yield prefix(range(tile_offsets[band][k], tile_offsets[band][k + 1]), p < b)
# then: drop the points outside the view (tiles cross its edges), and, from the
# tile-major table, the points of the features not shown

prefix(rows, p < b): the rows of a tile are sorted by \(p\), so the points with \(p < b\) are its first rows; a reader finds where they end from the __spatialdata_p__ column of the tile (e.g. by a binary search). count_in_view sums \(O_{k+1} - O_k\) over the tiles in view, each weighted by the part of the tile that lies in the view: the tiles of the coarse bands are larger than the view, and counting them whole overestimates the points in view by orders of magnitude when zoomed in.

Compatibility#

  • Without spatial_index an element is stored as today, and reads as today.

  • An element with spatial_index is a new version of the points format (see the versions of SpatialData): it is not readable by older readers, and the tables are under spatial/ and feature/, the same layout in Parquet and in Zarr. A reader that does not use the index can still read the points from the tile-major table: every point once, sorted by band and tile, with the extra column __spatialdata_p__.

Summary#

The terms of this RFC in three layers. The data is always there. The data model and the storage format of the spatial index are optional; the requirements below apply only to an element that has a spatial index.

Layer

Term

Requirement

Section

Data

the points, one row each, with their coordinates, feature and other columns

always present, as today

Columns

Data model

axes: all the spatial axes of the element

MUST

Grid and tiles

origin \(o_a\) and tile size \(s_a\) of level 0, per axis (a single tile along an axis allowed)

MUST

Grid and tiles

bands \(0, \dots, L\) (\(L \ge 0\)): band 0 always, bands \(1, \dots, L\); level \(l\) = bands \(L, \dots, l\)

MAY

Levels and bands

grid of every level present, \(0, \dots, L\)

MUST

Grid and tiles

grid of each level refines the grid of the next coarser level (recommended recipe: the merge rule)

MUST

Grid and tiles

grids get coarser with the level (a level may keep the grid of the level below)

SHOULD

Grid and tiles

tile order: C order of the tile ids

MUST

Tiles ordering

random value \(p = k / 2^b\) per point, kept when the element is indexed again

MUST

Priority

fraction \(P^{(l)}\) of every level present (\(P^{(0)} = 1\)), a fixed rate (default: ratio of the tile volumes of level 0 and level \(l\); any strictly decreasing rates allowed)

MUST

Sampling

tile size for the typical tile (median of level 0 about 5,000 to 20,000 points)

SHOULD

Choosing the tile size and the rates

feature column(s)

MAY; at most one SHOULD

Tile-major order and feature-major order

Storage format

metadata: spatial_index convention in zarr.json, with its version, axes, p_bits and levels

MUST

Metadata

Parquet (default) or Zarr (experimental), same layout

MUST, one of them

File layout

Parquet sidecar: part files in order, their first rows, global categories

MUST, in Parquet

Metadata

column __spatialdata_p__, unsigned integer codes

MUST

Columns

tile-major table, levels as bands

MUST

Levels and bands

tile index: tile_offsets of every band (int32 or int64)

MUST

Tile index

row groups of 100,000 to 1,000,000 rows, starting at tiles; part files starting at tiles (Parquet); chunks of about a tile, in shards (Zarr)

SHOULD

Points as a tall table

per-row-group dictionaries with only the categories present (Parquet)

SHOULD

Columns

feature-major table, one per feature column

MUST, for each feature column

Tile-major order and feature-major order

feature index: sparse (CSR) tile_offsets per band

MUST, with a feature-major table

Feature index

offsets chunked for small reads (e.g. 65,536 entries)

SHOULD

File layout

coordinate and feature columns first

SHOULD

Order of the columns

identifier column of the points

MAY be dropped

Columns

Implementation#

An experimental implementation of this draft (both formats, reading and writing, a napari-spatialdata reader that loads the points in view) was tested on two 10x Atera datasets of 0.7 and 1.2 billion transcripts; the numbers quoted in this RFC come from it.

TODO: spatialdata (read/write), spatialdata-io (Celldega PR #423), tissue-map-tools (sampling), a viewer (Celldega, Vitessce, TissUUmaps, merfisheyes, spatiato).

Discussion#

References#

  • RFC 4: Tiled and multiscale shapes

  • P. van Oosterom, S. van Oosterom, H. Liu, R. Thompson, M. Meijers, E. Verbree, “Organizing and visualizing point clouds with continuous levels of detail”, ISPRS Journal of Photogrammetry and Remote Sensing 194 (2022) 119–131, doi:10.1016/j.isprsjprs.2022.10.004 (PDF, open access, CC BY 4.0). The cLoD value of a point is drawn from a continuous distribution through a uniform random number, \(l = F^{-1}(U)\); it is a monotone function of \(U\), so thresholds on the cLoD value are thresholds on a uniform priority, as here. The paper declares no patent and no competing interests.

  • M. Schütz, K. Krösl, M. Wimmer, “Real-Time Continuous Level of Detail Rendering of Point Clouds”, IEEE VR 2019 (page): a fixed uniform random value per point, to avoid flicker.