Zenn
MIERUNEのZennブログPublicationへの投稿
💠

MapLibre Tiles (MLT) 仕様 - 日本語訳（非公式）

ciscorn
2025/02/27に公開
2
map
MapLibre
mvt
tech

これは MapLibre Tiles (MLT) 仕様の「非公式の」日本語訳です。英語の原版は maplibre/maplibre-tile-spec にあります。2025-02-27 時点の翻訳です。ライセンス: CC0 1.0 Universal

MapLibre Tiles (MLT)

MLT 形式は主に MVT 形式 から着想を得ているが、次のような領域を改善するためにゼロから再設計されている：

  • 圧縮率の改善 — 列指向レイアウトと（カスタムの）軽量エンコーディングを採用し、大きなタイルでは最大 6 倍の圧縮率を実現
  • デコード速度の向上 — 高速な軽量エンコーディングを採用し、SIMD/ベクトル化命令と組み合わせて使用可能
  • リニアリファレンスや M 値のサポート — Overture Maps (GeoParquet) のような今後登場する次世代のソース形式を効率的にサポートするため
  • 3D 座標 (i.e. 標高) のサポート
  • 複雑型のサポート — 例：ネストされたプロパティ、リスト、マップ
  • 処理パフォーマンスの改善 — 部分的に（WebGLでのポリゴンのように）または完全に（WebGPU のコンピュートシェーダーで使用する場合）、追加の処理なしに GPU バッファへ直接ロードできるインメモリ形式に基づく

良好な圧縮率と、高速なデコードや処理を両立するため、MLT 形式はインメモリ形式とストレージ形式に分かれている。ストレージ形式は、コスト効率の良いデータ保管や低レイテンシーなネットワーク転送に使用される。一方、インメモリ形式は、Apache Arrow のようなインメモリの分析用形式や、glTFのような 3D グラフィックス形式から着想を得て、地図の可視化用途に最適化されている。MLT 仕様の重要な設計目標の一つは、ストレージ形式からインメモリ形式への高速なトランスコーディングを実現することである。

1. ストレージ形式 (Storage Format)

1.1 基本 (Basics)

MLT (MapLibre Tile) は、特定の地理的領域（タイル）についての情報を持つ。各タイルは FeatureTable のコレクションであり、これは MVT 仕様 における Layer に相当する。

各 FeatureTable には、テーマごとにグループ化されたベクターデータ (Features) が含まれる。一つの FeatureTable 内にある Feature は、共通の属性カラム（プロパティ）セットを共有し、通常は同じジオメトリ型を共有する（ただし必須ではない）。

地図上でのタイルの視覚的な見た目は、通常 MapLibre Style Specification によって制御され、FeatureTables の Features がどのように描画されるかを指定する。

各 Feature は、ジオメトリカラム（必須）と、オプションの ID カラム、オプションのプロパティカラムを持つ。ジオメトリカラムの型は、OGC の Simple Feature Access Model (SFA) から GeometryCollection 型のサポートを抜いたものに基づいている。

ジオメトリは 1 つのジオメトリ型に制限されないが、効率の観点から統一することが推奨される。MVT と同様に、ジオメトリ座標はベクタータイルのグリッド座標系で整数値としてエンコードされる。

注: 本ドキュメントでは 「カラム（column）」「フィールド（field）」「プロパティ（property）」 は同じ意味で用いられる。

1.2 ファイルレイアウト (File Layout)

MLT 仕様における FeatureTable は、表形式の列指向レイアウトに基づいている。各カラムの値を効率的にエンコードするために複数の異なる軽量な圧縮方式を採用している。FeatureTable は、オプションの id カラム、必須の geometry カラム、およびオプションの property カラム群で構成される。タイルヘッダーが存在しないため、FeatureTables はそのまま連結することができる。

論理カラムは、ORC ファイル形式に着想を得た複数の物理 stream (サブカラム) に分割され、それらは隣接して格納される。ストリームとは、既知の長さを持つ同じ型の値のシーケンスであり、連続したメモリのチャンク内に格納される。また、ストリームにはサイズやエンコーディングタイプなどの追加のメタデータが含まれる。例えば、nullable な文字列プロパティカラムは、present stream（値の有無）、length stream（各文字列の文字数）、data stream（実際の UTF-8 エンコードされた文字列値）の 3 つのストリームに分割されうる。

MLT は、ストリームを次の種類に区別する：

  • present:
    疎なカラムを効率的にエンコードするために使用され、ビットフラグに基づいて値の存在を示す。このストリームは、カラムが FieldMetadata 内で nullable として宣言されていない場合、省略可能である。
  • data:
    カラムの実際のデータを格納し、ブール値、整数、浮動小数点数、文字列などの Feature のプロパティを保持する。また、辞書エンコードされた文字列値 や、ジオメトリカラムの座標値もこのタイプのストリームに格納される。オプションの presence ストリームを別にすれば、ブール値、整数、浮動小数点数などの固定サイズデータ型に対して使用される唯一のストリームである。
  • length:
    文字列やリストなどの可変長データ型の要素数を指定する。
  • offset:
    辞書エンコーディングが使用される場合に（例：文字列や頂点）、データストリーム内のオフセットを格納する。

この物理ストリームは、データをどのように解釈するかに関する追加のセマンティクスを加える論理ストリームにさらに分けられる。

1.2.1 メタデータ (Metadata)

タイルセットメタデータ (Tileset Metadata)

タイルセットごとのメタデータは、別途の Protocol Buffers ファイルに格納される。タイルセットメタデータファイルには、タイルセット全体の情報や FeatureTable の名前と構造が定義されており、MVT において併用される TileJSON 仕様に相当する。タイルセットごとに情報を一度だけ指定することで、冗長な（共有の）メタデータをタイルごとに定義することを避けられる。特に小さなタイルでは、冗長なメタデータが全体のサイズに対して無視できない割合を占める可能性がある。タイルセットメタデータのスキーマは こちら にある。

Open Question: MVT が TileJSON なしで利用できるように、タイルにメタデータを埋め込めるようにもして、単体でも利用できる自己完結型のタイルのオプションも提供すべきか？

タイルメタデータ (Tile Metadata)

タイルセット全体に適用されるメタデータに加えて、各タイルはタイルの構造に関する 3 種類の追加セクションを持つ。

  • FeatureTableMetadata: FeatureTable に関する情報を含む。例えば、タイルセットメタデータと接続するための ID や、Feature の数など。すべての FeatureTable の前に FeatureTableMetadata セクションが置かれる。
  • FieldMetadata: フィールドが何個のストリームに分けられているかや、インメモリ形式へ効率的にデコードするためのベクター型などの情報を含む。すべてのフィールド（カラム）セクションの前に FieldMetadata セクションが置かれる。
  • StreamMetadata: ストリームで使われるエンコーディング方式や値の数などの情報を含む。すべてのストリームセクションの前に StreamMetadata セクションが置かれる。

すべてのフィールド対して FieldMetadata セクションが存在する必要があり、あるタイルには含まれないフィールドについてもそうであるため、フィールドを識別するための ID は不要である。あるタイルにあるフィールドが存在しないことは、ストリームの数がゼロであることで識別できる。メタデータセクション内のすべての整数は、u32 の場合は Varint エンコーディング、u8 の場合はビットパックされる。

1.2.2 型システム (Type system)

MLT の型システムは物理型と論理型に分けられる。物理型はストレージ形式におけるデータのレイアウトを定め、論理型は物理型への追加のセマンティクスを与える。この分離により、データのエンコードとデコードが簡素化される。これは、エンコーダーやデコーダーを実装する複雑さを減らすとともに、エンコーディングの再利用も可能にする。

1.2.2.1 物理型 (Physical Types)

物理型は、ストレージ形式におけるデータのレイアウトを定義する。スカラー型と複合型のいずれも、固定サイズバイナリと可変サイズバイナリに分けられる。可変サイズバイナリには、各要素のサイズを指定する追加の長さストリーム (length stream) が含まれる。一方、固定サイズバイナリは、すべてのデータが同じビット (boolean) またはバイト幅を持つため、追加の長さストリームは不要である。

スカラー型 (Scalar Types)

個々のスカラー型は、data ストリームに適用できる特定のエンコーディング方式を持つ。

データ型 論理型 説明 レイアウト
Boolean 固定長
Int8, UInt8, Int32, UInt32, Int64 , UInt64 Date (int32), Timestamp (int64) 固定長
Float, Double 固定長
String JSON UTF-8 でエンコードされた文字の列 可変長

複雑型 (Complex Types)

複雑型はスカラー型から構成される。

データ型 論理型 説明 Layout
List Binary (List<UInt8>) 可変長
Map RangeMap (Map<vec2d, T>) additional key stream -> length, key, data streams 可変長
Struct
Vec2<T>, Vec3<T> Geometry, GeometryZ 固定長
1.2.2.2 論理型 (Logical Types)

物理型のうえに追加のセマンティクスを加える。これには、エンコーディングが再利用でき、エンコーダーとデコーダーが簡素化できるという利点がある。

論理型 物理型 説明
Date Int32 Unix エポックからの経過日数
Timestamp Int64 Unix エポックからの経過時間 (ms)
RangeMap RangeMap (Map<vec2<Double>, T>) リニアリファレンスの格納向け
Binary List<UInt8>
JSON String
Geometry vec2<Int32>
GeometryZ vec3<Int32>
Nested Fields Encoding

構造体やリストのようなネストされたプロパティには、広く使われる Dremel エンコーディングではなく、present/length ペアエンコーディングを採用している。これは、実装がシンプルで、インメモリ形式へのデコードが高速であるためである。タイルセットメタデータに定義された各 nullable フィールド（タイルセットのメタデータで定義されたもの）には、追加の present ストリーム が存在する。また、リストなどのコレクション型のフィールド には、フィールドの長さを指定する追加の length ストリーム がある。ORC と同様に、ネストされたフィールドは前順走査 (pre-order traversal) に基づいてフラット化される。さらに、ネストされたフィールドでは、共有辞書エンコーディングを使用し、共通の辞書を複数のフィールド間で共有することができる。例えば、OSM データセットの name:* カラムのローカライズされた値に適用すれば、異なるフィールド間で同じ値を共有できる。共有辞書エンコーディングがネストされたフィールドに使用される場合、共有辞書を利用するすべてのフィールドはファイル上で連続してグループ化され、そこに辞書が前置される必要がある。

RangeMap

RangeMaps は、リニアリファレンス情報を効率的にエンコードする方法の一つで、例えば Overture Maps で使用されている。RangeMap は、範囲の値とデータの値を 2 つの独立したストリーム に分けて格納する。範囲の最小値と最大値は、ダブル値をインターリーブした形式で、別の範囲ストリームに格納される。

1.2.3 エンコーディング方式 (Encoding Schemes)

MLT は、データ型の省スペースな格納と高速デコードのために、さまざまな軽量な圧縮方式を使用する。カラムのサイズをさらに削減するために、エンコーディングは一定のレベルまで再帰的にカスケード（ハイブリッドエンコーディング）することが可能である。例えば、辞書エンコーディングの結果として得られた整数カラムは、さらに整数エンコーディング方式のいずれかを適用してさらに圧縮できる。特定のデータ型のための以下のエンコーディングプールは、OpenMapTiles スキーマや Bing Maps ベースのタイルセットといったテストデータセットでの圧縮率とデコード速度の効率に関する分析結果に基づいて選定された。

データ型 論理レベル技法 物理レベル技法 説明
Boolean Boolean RLE
Integer Plain, RLE, Delta, Delta-RLE SIMD-FastPFOR, Varint
Float Plain, RLE, Dictionary, ALP
String Plain, Dictionary, FSST Dictionary
Geometry Plain, Dictionary, Morton-Dictionary

SIMD-FastPFOR は、一般により小さいデータストリームを生成し、デコード速度も高速であるため、Varint エンコーディングよりも優先すべきである。Varint エンコーディングは主に互換性のためにエンコーディングプールに追加されており、SIMD-FastPFOR と比べて実装がシンプルであるという利点がある。また、Varint エンコーディングは GZip のような重量級の圧縮方式と組み合わせることで、より効率的になる場合がある。

エンコーディングプールから特定のデータ型に対する最適な圧縮方式を選択する際に、すべての利用可能な方式を試してカラムサイズを比較する総当たりアプローチはコストが高すぎる。推奨のアプローチは、BTRBlocks 論文で説明されている選択戦略を用いることによって、選択時間を改善することである。

  • 第一段階: データメトリクスを計算し、早い段階で適さないエンコーディングを除外する。例えば、平均ランレングスが 2 未満の場合、RLE エンコーディングは候補から除外される。
  • 第二段階: サンプリングベースのアルゴリズムを使用し、最適な圧縮方式を選択する。データ全体の 1% のランダムサンプルを取得し、第一段階で選ばれたエンコーディング方式を適用。最も小さな出力を生成する方式を本番データに適用する。

1.2.4 FeatureTable のレイアウト (FeatureTable Layout)

ID カラム (ID Column)

id カラムは、MVT との互換性を高めるため、およびサイズの理由で int データ型を狭めるために properties とは別にモデル化されている。データ型を Uint32 に絞り込むことで、FastPfor128 が使用できる。

データ型 エンコーディング型
Uint32, Uint64 see availabe integer encodings

Open Question: id カラムは、本当に MVT との互換性を高め、サイズを削減するために、整数型へ絞り込むために別途にエンコードすべきなのか？ それとも特別な意味を持たせずに扱うべきなのか？

ジオメトリカラム (Geometry Column)

主なアイデアは、ジオメトリに対して structure of arrays（データ指向設計）レイアウトを採用することである。VertexBuffer に x, y およびオプションの z 座標をインターリーブして格納することで、CPU で効率的に処理できるだけでなく、GPU バッファへ直接コピーすることもできる。レンダリングにおいて z 座標が不要な場合は、m-座標として別途格納することもできる（詳細は vertex-scoped properties を参照）。

Feature のジオメトリ情報は 異なるストリームに分離されており、GeoArrow の仕様から一部の着想を得ている。ジオメトリの記述に別途のストリームを使うことで、圧縮の最適化や高速処理が可能になる。また、事前テッセレート済みのポリゴンメッシュをファイルに直接格納することで、時間のかかる三角形分割（トライアンギュレーション）のステップを回避できる。ジオメトリカラムは、次のようなストリームで構成されうる：

ストリーム名 データ型 エンコーディング 必須
GeometryType Byte 利用可能な整数エンコーディングを参照 ✓
NumGeometries UInt32 利用可能な整数エンコーディングを参照 ✗
NumParts UInt32 利用可能な整数エンコーディングを参照 ✗
NumRings UInt32 利用可能な整数エンコーディングを参照 ✗
NumTriangles UInt32 利用可能な整数エンコーディングを参照 ✗
IndexBuffer UInt32 利用可能な整数エンコーディングを参照 ✗
VertexOffsets UInt32 利用可能な整数エンコーディングを参照 ✗
VertexBuffer Int32 or Vertex[] Plain, Dictionary or Morton Dictionary ✓

ジオメトリの種類に応じて、ジオメトリカラムは GeometryType ストリームに加えて、次のようなストリームを持つことができる：

  • Point: VertexBuffer
  • LineString: NumParts, VertexBuffer
  • Polygon: NumParts (Polygon), NumRings (LinearRing), VertexBuffer
  • MultiPoint: NumGeometries, VertexBuffer
  • MultiLineString: NumGeometries, NumParts (LineString), VertexBuffer
  • MultiPolygon: NumGeometries, NumParts (Polygon), NumRings (LinearRing), VertexBuffer

さらに、ジオメトリカラムは、辞書エンコーディングまたは Morton 辞書エンコーディングが適用される場合、追加の VertexOffsets ストリームを持つことができる。また、ジオメトリ（主にポリゴン）がテッセレーション／三角形分割された形式で格納され、GPU バッファへ直接コピーされる場合、追加の NumTriangles および IndexBuffer を提供する必要がある。

プロパティカラム (Property Columns)

Feature のプロパティは、feature-scoped プロパティと vertex-scoped プロパティに分けられる。feature-scoped プロパティの値は、特定の Feature に関連しており、プロパティカラムには Feature ごとに 1 つの値が格納される。一方、vertex-scoped プロパティの値は各頂点に関連しており、VertexBuffer 内の各頂点ごとに 1 つの値がプロパティカラムに格納される。これにより、GIS アプリケーションで M 座標として知られるものをモデル化できる。

vertex-scoped プロパティはグループ化され、FeatureTable 内で feature-scoped プロパティの前に配置される必要がある。プロパティカラムのスコープは、ColumnScope 列挙型に基づいてタイルセットのメタデータドキュメントで指定される。

プロパティカラムは、データ型 で示される型のいずれかを持つことができる。

1.3 レイアウトの例 (Example Layouts)

以下に、ストレージ内での FeatureTable のレイアウト例を示す。データの種類を区別するために、次の色を使用している：

  • 青いボックス: 論理的な性質のみを持ち、永続化されないカラム。フィールドは、タイルセットメタデータに基づいてストリームから再構築できる。
  • 白いボックス: データの構造を記述するメタデータ。メタデータは、FeatureTable、フィールドメタデータ (FM)、ストリームメタデータ (SM) に分けられている。
  • 黄色いボックス: 実際のデータが含まれるストリーム

1.3.1 Placeレイヤー

以下の JSONスキーマでモデル化された構造を持つPlaceレイヤーを考える:

{
  "title": "Place Feature",
  "type": "object",
  "properties": {
    "id": { "type": "integer" },
    "geometry": { "type": "MultiPolygon" },
    "properties": {
      "type": "object",
      "properties": {
        "speed": { "type": "number" },
        "rank": { "type": "integer" },
        "name": {
          "type": "object",
          "properties": {
            "en": { "type": "string" },
            "de": { "type": "string" }
          },
          "required": ["en"]
        }
      }
    }
  },
  "required": ["geometry"]
}

このスキーマに基づき、geometry および name カラムに辞書が使用される場合、MLT タイル内でのプレイスレイヤのレイアウトは以下のようになる。

1.3.2 フラットプロパティを持つ LineString ジオメトリ

id フィールド、LineString ジオメトリフィールド、さらにフラットな feature-scoped プロパティ（class および subclass）を持つ FeatureTable のエンコーディング例。

1.3.3 フラットプロパティを持つ MultiPolygon

id フィールド、MultiPolygon ジオメトリフィールド、そしてフラットなフィーチャースコープのプロパティフィールドを持つ FeatureTable のエンコーディング例。頂点の辞書エンコーディングが使用されるため、VertexOffsets ストリームが含まれている：

1.3.4 Vertex-scoped プロパティと feature-scoped プロパティ

vertex-scoped プロパティと feature-scoped プロパティのエンコーディング例。すべての vertex-scoped プロパティはグループ化され、ファイル内では feature-scoped プロパティの前に配置する必要がある。この例では、id カラムが nullable でないため present stream は省略できる。

Sorting

Feature のソートに適したカラムを選択することは、FeatureTable のサイズに大きな影響を与える可能性がある。列指向レイアウトを最大限に活かすには適切なソートが不可欠である。しかし、すべてのレイヤーに対して、あらゆるカラムの並び替え順を試すのはコストがかかりすぎる。以下に示すシンプルなルールセットは、テストにおいて良好な結果を示した。

TBD

2. インメモリ形式 (In-Memory Format)

Notes: インメモリ形式の詳細については後述する。以下はその概要である。

Mapbox Vector Tiles を処理するライブラリが使用するレコード指向のメモリモデル (array of structures アプローチ) は、例えば小さなオブジェクトの大量生成 (オブジェクトごとのメモリ割り当て) がブラウザのガベージコレクタに追加の負荷をかけるなど、かなりのオーバーヘッドがある。MLT のインメモリ形式では、カラム指向のメモリレイアウト (データ指向設計) を採用することで、この問題を解決し、キャッシュ利用の最適化や SIMD 命令を活用した高速なデータ処理を実現できる。MLT のインメモリ形式は、Apache Arrow、Velox、DuckDB のインメモリ分析形式のアイデアを取り入れ、さらに可視化ユースケース向けに拡張されている。将来の拡張性を確保するため、GPU のコンピュートシェーダー内で並列処理が可能な設計であることが重要である。MLT のインメモリ形式の主な設計目標は以下の通り：

  • プラットフォーム非依存の表現を定義し、高いマテリアライゼーションコスト（特に文字列）を回避する
  • メモリレイアウトをキャッシュ局所性や SIMD 命令に向けて最適化し、高い CPU スループットを実現する
  • すべてのデータに対するランダムアクセス（主に定数時間）を可能にし、GPU (コンピュートシェーダー) でも並列処理可能にする
  • デコードなしに直接処理できる圧縮データ構造を提供する
  • タイルのジオメトリを GPU バッファへ直接ロード可能な形式で格納し、追加の処理を最小限または不要にする

データはベクターと呼ばれる連続メモリバッファに格納され、追加のメタデータと、null 値を表現するためのオプションの nullability ビットマップを持つことができる。ストレージ形式には VectorType フィールドが含まれており、特定のフィールドに対してどのベクタータイプをデコーダーが使用すべきかを指定する。可変長データ型（文字列やリストなど）へのランダムアクセスを可能にするため、オフセット値を格納する補助バッファを利用する。

MLT のインメモリ形式は、以下のベクターをサポートする：

Note: 最新の研究成果 が、デルタエンコードされた値に対してもランダムアクセスを可能にできるか判断するため、さらなる評価が必要である。

圧縮ベクターが使用可能な場合は、ストレージからインメモリ形式への変換が基本的にゼロコピーで行えるという追加の利点がある。

Intel のパフォーマンスガイド に基づいた Apache Arrow のアプローチに従い、デコーダーは（可能であれば）64 バイトの倍数のアライメントでメモリを確保することを推奨する。

技術用語 (Technical Terminology)

以下に、曖昧さを解消するための小さな用語集を示す

  • Column or Field:
  • Stream:
  • Feature:
  • FeatureTable:

MLT エンコーディング定義 (MLT encoding definitions)

プレーン (Plain)

データに圧縮技術を適用しない。データ型に応じてデータは次の形式で格納される：

  • ブール値 (Boolean):
  • 整数 (Integer): リトルエンディアンバイトオーダー
  • ロング (Long): リトルエンディアンバイトオーダー
  • 浮動小数点 (Float): リトルエンディアンバイトオーダーのIEEE754浮動小数点数
  • 倍精度浮動小数点 (Double): リトルエンディアンバイトオーダーのIEEE754浮動小数点数
  • 文字列 (String): 長さおよびデータストリーム

Boolean-RLE

このエンコーディングは、ブール値の列を圧縮するために使用される。ビット順序として、最下位ビットからの番号付け（ビットエンディアン）が使われる。実装の詳細については、ORC仕様を参照。

Byte-RLE

このエンコーディングは、ジオメトリカラムの GeometryType ストリームのようなバイトストリームを圧縮するために使用される。実装の詳細については、ORC仕様を参照。

辞書エンコーディング (Dictionary Encoding)

辞書エンコーディングは、繰り返し現れる値をコンパクトに表現するために使用され、String および Geometry 列に適用できる。重複のない実際の値が dictionary ストリームに格納されつつ、辞書へのインデックスのために別の data ストリームが使用される。

文字列辞書エンコーディング (String Dictionary Encoding)

辞書ストリームには、重複のないUTF-8エンコードされた文字列値が含まれる。データストリームには、UInt32 形式でエンコードされた辞書へのインデックスが含まれる。辞書エンコーディングされた null 許容の文字列カラムは、以下のストリームの順序で構成される: Present, Length, Dictionary, Data.

すべてのストリームは、軽量エンコーディングを再帰的に適用することでさらに圧縮できる：

  • Present ストリーム: ブールRLE
  • Length および Data ストリーム: 整数エンコーディングを参照
  • Dictionary: FSST 辞書エンコーディングを参照
FSST 辞書エンコーディング (FSST Dictionary Encoding)

辞書エンコーディングは、サイズを縮小するために、完全に繰り返される文字列を必要とする。しかし、地理空間データの属性には共通の接頭辞を持ちつつも完全には一致しない文字列（例えばローカライズされた国名など）が含まれることが多い。FSSTは、効率的なスキャンとランダム検索のサポートを維持しつつ、頻出する部分文字列を置換する。MLTでは、UTF-8エンコードされた辞書の値をさらに圧縮するために使用される。FSSTで辞書エンコーディングされた null 許容の文字列カラムは、以下のストリームの順序で構成される: Present, SymbolLength, SymbolTable, String Length, Dictionary (Compressed Corpus) 。実装の詳細については、こちらの論文を参照。

利用可能な実装:

共有辞書エンコーディング (Shared Dictionary Encoding)

共有辞書エンコーディングは、カラム間で共通の辞書を共有するために使用できる。また、入れ子になったフィールドでも共有辞書エンコーディングを使用して、フィールド間で共通の辞書を共有できる。例えば、OSMデータセットの name:* 列におけるローカライズされた値は、フィールド間で同一となる場合がある。入れ子フィールドに共有辞書エンコーディングを使用する場合、共有辞書を使用するすべてのフィールドはファイル内で連続して配置され、そこに辞書が前置される必要がある。

共有辞書でエンコーディングされた null 許容の文字列カラムは、以下のストリームの順序で構成される: Present, Length, Dictionary, Present1, Data1, Present2, Data2

共有FSST辞書でエンコーディングされた null 許容の文字列カラムは、以下のストリームの順序で構成される:
SymbolLength, SymbolTable, String Length, Dictionary (Compressed Corpus), Present1, Data1, Present2, Data2

頂点辞書エンコーディング (Vertex Dictionary Encoding)

VertexBuffer ストリーム内の頂点の座標へのインデックスを格納するために、追加の VertexOffsets ストリームを使用する。頂点バッファ内の頂点はヒルベルト曲線に沿ってソートされ、null 抑制技術と組み合わせたデルタエンコーディングが適用される。

モートン頂点辞書エンコーディング (Morton Vertex Dictionary Encoding)

VertexBuffer の座標は、Mortonコードを使用して1次元の整数に変換される。その後、Mortonコードに従ってデータがソートされ、整数圧縮技術を適用することでさらに圧縮される。

整数エンコーディング

一般に、MLTのほとんどのデータは整数の配列の形で格納される。整数の配列を効率的かつ高速に圧縮するアルゴリズムの利用は非常に重要である。

論理レベル技法 (Logical Level Technique)

整数は、軽量圧縮技術であるデルタおよびRLE、およびその2つを組み合わせたDelta-RLEに基づいてエンコードされる。

デルタ (Delta)

シーケンスの連続する要素間の差分（例: x2 - x1, x3 - x2, ...）を計算する。デルタ値を格納するために必要なビット数を削減するため、常に物理レベルの技法と組み合わせて使用される。

RLE

基本的な説明については https://en.wikipedia.org/wiki/Run-length_encoding を参照。すべての連続する値（ラン）と個々の値は、別々のバッファに格納される。値が符号付き整数の場合、値のバッファにZigZagエンコーディングが適用される。その後、両方のバッファは null 抑制技術を使用してさらに圧縮される。

デルタとRLEの組み合わせ（Delta-RLE）

デルタ圧縮を適用した後にRLEエンコーディングを適用する。この手法は、IDのような昇順シーケンスに対して効果的である。

物理レベル技法（Null抑制）(Physical Level Technique (Null Suppression))

ZigZagエンコーディング

符号付き整数のエンコーディングには、以下の null 抑制技術の両方にZigZagエンコーディングが用いられる。ZigZagエンコーディングは、符号のエンコードに最下位ビットを使用する。

Varintエンコーディング

最小限のバイト数で整数を圧縮しようとする、バイト境界に合わせた null 抑制技術。実装の詳細については Protobuf を参照。

SIMD-FastPFOR

ビット境界に合わせた null 抑制技術であり、全体のビット幅を小さく保つために外れ値（outliers）を別のセクションに格納するパッチアプローチを用いて、最小限のビット数で整数を圧縮する。

https://arxiv.org/pdf/1209.2137.pdf および https://ayende.com/blog/199524-C/integer-compression-the-fastpfor-code を参照。

利用可能な実装：

浮動小数点エンコーディング

適応型ロスレス浮動小数点圧縮 (ALP)

詳細な説明は https://dl.acm.org/doi/pdf/10.1145/3626717 を参照。ALPは、MLT内の浮動小数点値を圧縮するために使用されるロスレス浮動小数点圧縮技術である。

利用可能な実装：

2
MIERUNEのZennブログ
MIERUNEのZennブログPublication

MIERUNE（みえるね）は、GIS（地理情報システム）を専門とする会社です。❤️ #FOSS4G !

Discussion

ログインするとコメントできます