構造的アルゴリズム
B+Tree
B-Tree の派生型である B+Tree は、個々のキーの検索効率を下げる代わりに、ある範囲のデータをまとめて取得するケースに適した構造を持つ。B-Tree が中間ノードにもデータエントリを保持していたのに対して、B+Tree では末端の葉にのみエントリを保持し、葉は相互にリンクしたリストの構造を持っている。…
R-Tree
R-Tree は深さ平衡木 (depth-balanced tree)。葉ノード
有向非巡回グラフ
DAG (directed acyclic graph; 有向非巡回グラフ) は有向グラフの中でも閉路をもたない (つまり一度通過した頂点にふたたび戻ることはない) 構造を持つグラフ。ソフトウェアの分野ではジョブ管理システムやビルドシステム、ネットワーク問題で扱う。…
HyperLogLog
HyperLogLog は多重集合 (multiset) における異なりの数問題 (distinct-count problem) を概算するための確率的アルゴリズム。つまり同じ値が複数存在するデータセットから値の種類の数を概算する。…
Bloom Filter
Bloom Filter は、ある要素が集合内に含まれているかを効率的にテストするための確率的データ構造。false positive (偽陽性; 含まれていないのに true となること) を許容するが false negative (偽陰性; 含まれているのに false となること) は発生しない特徴を持つ。…
論文翻訳: The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree
空間インデックス (spatial index) のためのアルゴリズム Priority R-Tree (2004) に関する論文。
論文翻訳: HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm
大量のデータから要素数を推定するアルゴリズム HyperLogLog に関する 2007 年の論文。
論文翻訳: BzTree: A High-Performance Latch-free Range Index for Non-Volatile Memory
NVM (不揮発性メモリ) 向けデータ構造 BzTree に関する 2018 年の論文。Microsoft US #10599485 特許。
Multi-Versioned Hash Tree
現実的なストレージに対して効率的な追記特性を持つ、構造の加算的な変化の完全な履歴を保持するリスト構造について説明します。この構造はデータの追加が可能なハッシュツリー (Merkle ツリー) であり、一般的なハッシュツリーと同様に極めて小さいデータを用いてデータの破損や改ざんを検証することができます。…
Data Encoding
可変長整数エンコーディング
いくつかの可変長整数エンコーディング実装について。このページの話題は任意精度整数演算ではなくデータ圧縮の目的で整数値をエンコーディングする方法である。
基数変換
Base64 はバイナリを 64 種類の文字を使用した文字列に変換する。これは、基数 256 の数列を基数 64 の数列に変換し、それぞれの桁を文字にマッピングすることと等価である。Base58 のような 64 以外の符号化についても、対象とする基数が異なるだけで同じ処理となることが分かるだろう。…
擬似乱数生成
疑似乱数生成
乱数 (random number) はランダムに選択された数のこと。特定の出現パターンを持たず、選択される値が予測できないという性質を持っており、ゲームや科学技術シミュレーション、暗号セキュリティの分野で重要な役割を持っている。…
論文翻訳: Xorshift RNGs
ビット演算のみを使用した非常に高速でコンパクトな Xorshift 擬似乱数生成アルゴリズムに関する 2003 年の論文。著者はキャリー付き乗算の論文にも携わっている。Abstract にあるようにこの論文自体はアイディアの説明であり、良い乱数・悪い乱数で何点かの間違いが指摘されている。…
ランダムサンプリング
ランダムサンプリング
ランダムサンプリング (RS; random sampling) または無作為抽出、乱択とは、ある集合から無作為に要素を選択すること。社会科学分野での統計のために利用されることも多いが、このページではソフトウェアアーキテクチャに焦点を当てている。…
非復元ランダムサンプリングにおける公平性
Inverse (逆数) の重み分布に対して ×1,000 を実行してみれば明らかなように、それぞれの要素の選択頻度の分布 (Actual Win Rate) は重みの分布とはかけ離れた挙動となる。…
論文翻訳: Weighted Random Sampling (2005; Efraimidis, Spirakis)
重み付きランダムサンプリング (乱択) のアルゴリズムに関する 2005 年の論文。重み付き非復元ランダムサンプリング (weighted random sampling without replacement) に基づいて、開始時点でサイズが未知の母集団から 1 パスでサイズ \(m\) の部分集合を生成することができる。…
論文翻訳: Fast Generation of Discrete Random Variables
Walker のエイリアス法を改良して正方ヒストグラムを使う方法で高速に重み付きランダムサンプリングを行うアルゴリズムに関する 2004 年の論文。