構造的アルゴリズム
ハッシュテーブル
ハッシュテーブル (hashtable) はさまざまなデータ型のキーをハッシュ化 (hashing) して効率的に管理し検索するためのデータ構造である。一般にキー \(x\) と関連する任意の値 \(y\) (サテライトデータ) を保持して \(y\) を効率的に検索するために用いられる。…
R-Tree
R-Tree は深さ平衡木 (depth-balanced tree)。葉ノード
有向非巡回グラフ
DAG (directed acyclic graph; 有向非巡回グラフ) は有向グラフの中でも閉路をもたない (つまり一度通過した頂点にふたたび戻ることはない) 構造を持つグラフ。ソフトウェアの分野ではジョブ管理システムやビルドシステム、ネットワーク問題で扱う。…
Slate: Stratified Hash Tree
現実の階層記憶構造に対して追記とアクセス効率が良く、累積的な構造変化の履歴をすべて保持するハッシュツリー構造である Slate, Stratified Hash Tree を提案します。このデータ構造の設計における核心的要件は以下の 3 点です:
キャッシュ
キャッシュ (cache) はプログラムやシステムのデータアクセスの高速化を目的としたメカニズムであり、そのデータを一時的に保存する高速な記憶領域である。本質的には局所参照性 (locality of reference)、すなはち「直近でアクセスのあったデータは近い将来に再度アクセスされる可能性が高い」という原理に基づいて機能する。…
論文翻訳: The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree
空間インデックス (spatial index) のためのアルゴリズム Priority R-Tree (2004) に関する論文。
論文翻訳: Cuckoo hashing
衝突時に他の位置へ要素を「追い出す」ことで高速な検索、挿入、削除が可能なハッシュテーブルの一種である Cuckoo Hashing に関する 2014 年の論文。
論文翻訳: Hopscotch Hashing
既知のハッシュテーブルアルゴリズムより逐次/並行の両面でパフォーマンスに優れている Hopscotch ハッシュ法に関する 2008 年の論文 (ドラフト)。
木構造
木構造 (tree structure) はデータを階層的に表現するためのデータ構造である。ノード (頂点) とエッジ (辺) で構成されるグラフ構造の一種だが、閉路を持たない DAG である。…
B-Tree
B-Tree または B 木は自己平衡型の多分木データ構造である。各ノードがソート済みの複数のキーと子ノードへの参照を持つことで、二分木より高さの低いツリー構造を形成することができる。このため検索や挿入、削除操作の効率が良く、特にディスクや SSD のようなストレージドライブに対する I/O を最適化するように設計できることから、大量のデータを効率的に管理するようなデータベースやファイルシステムなどで広く使用されている。…
B+Tree
B-Tree の派生型である B+Tree は、個々のキーの検索効率を下げる代わりに、ある範囲のデータをまとめて取得するケース (レンジクエリー) に適した構造を持つ。B-Tree が中間ノードにもデータエントリを保持していたのに対して、B+Tree では末端の葉にのみエントリを保持し、葉は相互にリンクしたリストの構造を持っている。…
Log-Structured Merge Tree (LSMT)
LSM ツリー (log-structured merge tree) またはログ構造マージツリーはデータベースのようなストレージエンジンにおいて検索性能を維持しながら高い書き込み性能を達成することを主な目的として使用されるデータ構造の一種である。…
論文翻訳: Lower Bounds for External Memory Dictionaries
検索操作においては従来の B-Tree の定数オーダーの性能を維持しながら、更新操作のスループットを大幅に改善する Bε-Tree についての 2003 年の論文。
論文翻訳: An Introduction to Bε-trees and Write-Optimization
B-Tree と似た構造を持ち、更新と挿入で高い性能を持つ Bε-Tree に関する 2015 年の記事。
論文翻訳: The Log-Structured Merge-Tree (LSM-Tree)
メモリ内のデータを定期的にストレージ上の大規模構造にマージすることで高い書き込みスループットと効率的なクエリー処理を実現するデータ構造である LSM-Tree に関する 1996 年の論文。
論文翻訳: PRESERVING ORDER IN A FOREST IN LESS THAN LOGARITHMIC TIME
1975 年の論文。
確率的データ構造
Bloom Filter
Bloom Filter (ブルームフィルタ) は大規模データセットに対する近似メンバーシップクエリー (approximately membership query)、つまり特定の要素が含まれているかを効率的にテストするための確率的データ構造。…
Quotient フィルター
Quotient フィルター (3) または商フィルターは大規模データセットに対する近似メンバーシップクエリー (AMQ; approximately membership query) を行うための確率的データ構造である。…
Count-Min スケッチ
Count-Min スケッチ (count-min sketch) (1) は大規模データセットにおいて頻度や重み付け合計を効率的に推定するための確率的データ構造である。膨大な数の要素を複数のハッシュ関数を用いて異なるカウンターにマッピングし、その最小値を参照することで頻度を推定する。…
HyperLogLog
HyperLogLog は多重集合 (multiset) における異なりの数問題 (distinct-count problem) を概算するための確率的アルゴリズム。つまり同じ値が複数存在するデータセットから値の種類の数を概算する。…
論文翻訳: Don't Thrash: How to Cache your Hash on Flash
Quotient フィルターをカスケード上に配置してフラッシュデバイスへ対応した、近似メンバーシップクエリーのための確率的データ構造である Cascade フィルターに関する 2012 年の論文。…
論文翻訳: Cuckoo Filter: Practically Better Than Bloom
要素が集合に含まれているかを効率的に判断するための確率的データ構造である Bloom フィルターの変種で、削除操作において Bloom フィルターより高い性能を示す Cuckoo フィルターに関する 2014 年の論文。…
論文翻訳: HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm
大規模データセットから要素のカーディナリティを推定するアルゴリズムである HyperLogLog に関する 2007 年の論文。HyperLogLog におけるカーディナリティとは distinct つまり「異なりの数」であり、集合論の文脈において「濃度」を意味するカーディナリティとは異なる点に注意。…
シーケンシャルアルゴリズム
情報検索
文字列マッチング
文字列マッチングは、テキストデータに含まれる特定の部分文字列 (パターン) を効率的に検索する技術である。大きな文書や巨大なデータベースで特定の単語やフレーズを見つけ出すために使用される。
全文検索
全文検索 (full-text search) はテキストデータベースや文書集合として存在する構造化されていないテキストから特定の単語やフレーズを検索し、その出現位置や関連する文書を取得するための検索技術である。…
データ分析
分位数
分位数 (quantile) またはクォンタイルはデータや確率の分布を一定の割合で区切るための値を指す。例えばデータを昇順に並べたとき、その累積割合が特定の値 (20%, 50%, 75% など) となる点を示すことで、データのばらつきや中心傾向、偏りなどを把握しやすくするための指標として使用される。…
論文翻訳: Computing Extremely Accurate Quantiles Using \(t\)-Digests
大規模データセットから \(k\) 番目に小さい要素の近似値を効率的に見つけるためのアルゴリズム \(t\)-digest についての 2019 年の論文。
並行プログラミング
並行プログラミング
並行プログラミングとは、そのような環境で効率的な処理を実装するために複数のタスクを同時に実行するプログラミング技法である。並行性によりプログラムは一度に多くのタスクを処理することができるが、並行プログラムを書くことはことさら簡単なことではない。…
非同期処理
符号理論
符号理論
誤り検出訂正
誤り検出訂正 (error detection and correction) はデータの伝送やデータ保存時におけるエラー (誤り) の検出と訂正を行うための手法。データは、伝送やストレージで生じる物理的なノイズや機器の不具合によって情報の欠損が生じ正確性を損なう可能性があるが、誤り検出訂正によってそれらのエラーを検出し訂正することで正確性と信頼性を向上させることができる。…
Erasure コーディング
Erasure コード (erasure code; 末梢符号) はビットの喪失に対する誤り訂正符号である。誤り検出訂正がビットエラーの検出や訂正を対象としていたのに対して、Erasure コードは喪失したデータブロックを他のデータブロックとパリティブロックから復元できることから、高い信頼性が求められる分散ストレージシステムなどで使用されている。…
編集距離
編集距離 (edit distance) は 2 つの文字列間で一方の文字列を他方の文字列と一致させるために必要な最小の操作回数である。これは 2 つの文字列が互いにどれだけ異なるかを定量化している。…
データエンコーディング
可変長整数エンコーディング
いくつかの可変長整数エンコーディング実装について。このページの話題は任意精度整数演算ではなくデータ圧縮の目的で整数値をエンコーディングする方法である。
基数変換
数の表現ですべての数値に一意の記号を割り当てようとすることは非現実的である。代わりに、古代から有限の記号の組み合わせで任意の数を表現する記数法 (numerical notation) が用いられてきた。…
Base64 エンコーディング
Base64 エンコーディングは任意の長さを持つバイナリデータを ASCII テキストに変換するための符号化アルゴリズム。
擬似乱数生成
疑似乱数生成
乱数 (random number) はランダムに選択された数のこと。特定の出現パターンを持たず、選択される値が予測できないという性質を持っており、ゲームや科学技術シミュレーション、暗号セキュリティの分野で重要な役割を持っている。…
論文翻訳: Xorshift RNGs
ビット演算のみを使用した非常に高速でコンパクトな Xorshift 擬似乱数生成アルゴリズムに関する 2003 年の論文。著者はキャリー付き乗算の論文にも携わっている。Abstract にあるようにこの論文自体はアイディアの説明であり、良い乱数・悪い乱数で何点かの間違いが指摘されている。…
乱数検定: RMT 検定
RMT 検定 (random matrix theory test) (1) はデータ列の乱数性を検定するためのアルゴリズム。与えられたデータ列で相互相関行列を作成し、その固有値分布が RMT に基づく理論曲線と一致すれば検定に合格する。…
乱数検定: NIST SP 800-22
NIST SP 800-22 (1) (または単に NIST 検定) は NIST が 2001 年に刊行した論文による (疑似) 乱数生成器のランダム性を検定するための検定スイートである。…
論文翻訳: NIST SP 800-22: A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications / 暗号アプリケーションのための乱数・擬似乱数生成器の統計的検定スイート
NIST SP 800-22 として刊行された (疑似) 乱数生成器のランダム性の検定に関する 2001 年の論文。15 の検定で構成されている。この論文に基づいた検定スイートは NIST SP 800-22: Download Documentation and Software からダウンロードできる。…
ランダムサンプリング
ランダムサンプリング
ランダムサンプリング (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 年の論文。
論文翻訳: Min-Wise Independent Permutations (Extended abstract)
min-wise 独立置換族 (min-wise independent permutations family) に関する 1998 年の論文。Brahms サンプリングの関連で調べたもの。…
TRANSCRIPT: Various Techniques Used in Connection With Random Digits
A 1951 paper by John von Neumann discussing techniques for generating random numbers, dealing with pseudo-random number generation for Monte Carlo methods and its limitations.
論文翻訳: Sampling From a Moving Window Over Streaming Data
データストリームから得られる最近の \(n\) 個のデータからランダムサンプリングを行うために移動ウィンドウを使用した手法を解説する 2002 年の論文。1 つの「現在選択されているサンプル」と複数の「選択されているサンプルまたはその後継者がウィンドウを外れたときにサンプルとして選択される後継者」をチェーン状に保持することで、サイズ \(n\) の移動ウィンドウの中で常に 1 つの要素をサンプリングする。…
