\( \def\vector#1{\boldsymbol{#1}} \)

Algorithms

Takami Torao
  • このエントリーをはてなブックマークに追加

アルゴリズムやデータ構造、設計パターンに関するあれこれ。

構造的アルゴリズム

ハッシュテーブル

ハッシュテーブル (hashtable) はさまざまなデータ型のキーをハッシュ化 (hashing) して効率的に管理し検索するためのデータ構造である。一般にキー \(x\) と関連する任意の値 \(y\) (サテライトデータ) を保持して \(y\) を効率的に検索するために用いられる。…

2024年8月9日(Fri) #Hashtable #Hashing

R-Tree

R-Tree は深さ平衡木 (depth-balanced tree)。葉ノード

2018年4月7日(Sat) #RTree

有向非巡回グラフ

DAG (directed acyclic graph; 有向非巡回グラフ) は有向グラフの中でも閉路をもたない (つまり一度通過した頂点にふたたび戻ることはない) 構造を持つグラフ。ソフトウェアの分野ではジョブ管理システムやビルドシステム、ネットワーク問題で扱う。…

2020年7月21日(Tue) #DAG

Banded Hash Tree

現実的なストレージに対して追記効率が良く、累積的な構造変化の完全な履歴を保持するリスト構造 Banded Hash Tree (BHT) について説明します。この構造はデータの追加が可能なハッシュツリー (Merkle ツリー) であり、一般的なハッシュツリーと同様に小さなデータ片を用いてデータの破損や改ざんを検証することができます。…

2021年7月12日(Mon) #BHT #HashTree #MerkleTree 作業中

キャッシュ

キャッシュ (cache) はプログラムやシステムのデータアクセスの高速化を目的としたメカニズムおよびその保存領域。アクセス頻度の高いデータや、次にアクセスされることが予測されるデータ、または生成や取得に時間がかかるデータを一時的に高速に読み取りが可能なキャッシュに保存することでアプリケーションの処理時間を短縮することを狙う。…

2023年2月22日(Wed) #LRU #MRU

論文翻訳: The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree

空間インデックス (spatial index) のためのアルゴリズム Priority R-Tree (2004) に関する論文。

2018年4月5日(Thu) 2004年の論文 #RTree 作業中

論文翻訳: Cuckoo hashing

衝突時に他の位置へ要素を「追い出す」ことで高速な検索、挿入、削除が可能なハッシュテーブルの一種である Cuckoo Hashing に関する 2014 年の論文。

2024年4月26日(Fri) 2004年の論文 #CuckooHashing #Hashtable

論文翻訳: Hopscotch Hashing

既知のハッシュテーブルアルゴリズムより逐次/並行の両面でパフォーマンスに優れている Hopscotch ハッシュ法に関する 2008 年の論文 (ドラフト)。

2024年8月28日(Wed) 2008年の論文 #HopscotchHashing #Hashtable

論文翻訳: The Log-Structured Merge-Tree (LSM-Tree)

メモリ内のデータを定期的にストレージ上の大規模構造にマージすることで高い書き込みスループットと効率的なクエリー処理を実現するデータ構造である LSM-Tree に関する 1996 年の論文。

2024年6月19日(Wed) 1996年の論文 #LSMTree

木構造

木構造 (tree structure) はデータを階層的に表現するためのデータ構造である。ノード (頂点) とエッジ (辺) で構成されるグラフ構造の一種だが、閉路を持たない DAG である。…

2024年11月13日(Wed) #BTree

B-Tree

B-Tree または B 木は自己平衡型の多分木データ構造である。各ノードがソート済みの複数のキーと子ノードへの参照を持つことで、二分木より高さの低いツリー構造を形成することができる。このため検索や挿入、削除操作の効率が良く、特にディスクや SSD のようなストレージドライブに対する I/O を最適化するように設計できることから、大量のデータを効率的に管理するようなデータベースやファイルシステムなどで広く使用されている。…

2024年12月5日(Thu) #BTree

B+Tree

B-Tree の派生型である B+Tree は、個々のキーの検索効率を下げる代わりに、ある範囲のデータをまとめて取得するケースに適した構造を持つ。B-Tree が中間ノードにもデータエントリを保持していたのに対して、B+Tree では末端の葉にのみエントリを保持し、葉は相互にリンクしたリストの構造を持っている。…

2018年4月15日(Sun) #BTree

論文翻訳: Lower Bounds for External Memory Dictionaries

検索操作においては従来の B-Tree の定数オーダーの性能を維持しながら、更新操作のスループットを大幅に改善する Bε-Tree についての 2003 年の論文。

2024年11月6日(Wed) 2003年の論文 #BTree #BεTree

論文翻訳: An Introduction to Bε-trees and Write-Optimization

B-Tree と似た構造を持ち、更新と挿入で高い性能を持つ Bε-Tree に関する 2015 年の記事。

2024年11月9日(Sat) 2015年の記事 #BTree #BεTree

確率的データ構造

Bloom Filter

Bloom Filter (ブルームフィルタ) は大規模データセットに対する近似メンバーシップクエリー (approximately membership query)、つまり特定の要素が含まれているかを効率的にテストするための確率的データ構造。…

2020年11月28日(Sat) #AMQ #BloomFilter #確率的データ構造

Quotient フィルター

Quotient フィルター (3) または商フィルターは大規模データセットに対する近似メンバーシップクエリー (AMQ; approximately membership query) を行うための確率的データ構造である。…

2024年8月13日(Tue) #AMQ #QuotientFilter #確率的データ構造

Count-Min スケッチ

Count-Min スケッチ (count-min sketch) (1) は大規模データセットにおいて頻度や重み付け合計を効率的に推定するための確率的データ構造である。膨大な数の要素を複数のハッシュ関数を用いて異なるカウンターにマッピングし、その最小値を参照することで頻度を推定する。…

2024年8月23日(Fri) #CMS #確率的データ構造

HyperLogLog

HyperLogLog は多重集合 (multiset) における異なりの数問題 (distinct-count problem) を概算するための確率的アルゴリズム。つまり同じ値が複数存在するデータセットから値の種類の数を概算する。…

2024年8月30日(Fri) #HyperLogLog #Redis #大規模データ構造 #確率的データ構造 #ストリーミングアルゴリズム

論文翻訳: Don't Thrash: How to Cache your Hash on Flash

Quotient フィルターをカスケード上に配置してフラッシュデバイスへ対応した、近似メンバーシップクエリーのための確率的データ構造である Cascade フィルターに関する 2012 年の論文。…

2024年8月14日(Wed) 2012年の論文 #QuotientFilter #CascadeFilter #確率的データ構造

論文翻訳: Cuckoo Filter: Practically Better Than Bloom

要素が集合に含まれているかを効率的に判断するための確率的データ構造である Bloom フィルターの変種で、削除操作において Bloom フィルターより高い性能を示す Cuckoo フィルターに関する 2014 年の論文。…

2024年4月22日(Mon) 2014年の論文 #CuckooFilter #BloomFilter #確率的データ構造

論文翻訳: HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm

大規模データセットから要素のカーディナリティを推定するアルゴリズムである HyperLogLog に関する 2007 年の論文。HyperLogLog におけるカーディナリティとは distinct つまり「異なりの数」であり、集合論の文脈において「濃度」を意味するカーディナリティとは異なる点に注意。…

2024年8月27日(Tue) 2007年の論文 #HyperLogLog #BigData #確率的データ構造

シーケンシャルアルゴリズム

情報検索

データ分析

並行プログラミング

符号理論

データエンコーディング

擬似乱数生成

疑似乱数生成

乱数 (random number) はランダムに選択された数のこと。特定の出現パターンを持たず、選択される値が予測できないという性質を持っており、ゲームや科学技術シミュレーション、暗号セキュリティの分野で重要な役割を持っている。…

2020年2月2日(Sun) #PRNG #MersenneTwister #xorshift

論文翻訳: Xorshift RNGs

ビット演算のみを使用した非常に高速でコンパクトな Xorshift 擬似乱数生成アルゴリズムに関する 2003 年の論文。著者はキャリー付き乗算の論文にも携わっている。Abstract にあるようにこの論文自体はアイディアの説明であり、良い乱数・悪い乱数で何点かの間違いが指摘されている。…

2020年2月2日(Sun) 2003年の論文 #Xorshift #PRNG

乱数検定: RMT 検定

RMT 検定 (random matrix theory test) (1) はデータ列の乱数性を検定するためのアルゴリズム。与えられたデータ列で相互相関行列を作成し、その固有値分布が RMT に基づく理論曲線と一致すれば検定に合格する。…

2023年2月8日(Wed) #RMTTest #RMT検定

乱数検定: NIST SP 800-22

NIST SP 800-22 (1) (または単に NIST 検定) は NIST が 2001 年に刊行した論文による (疑似) 乱数生成器のランダム性を検定するための検定スイートである。…

2023年2月19日(Sun) 2001年の論文 #NIST検定 #Randomness

論文翻訳: 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 からダウンロードできる。…

2023年2月8日(Wed) 2001年の論文 #NIST #NIST80022

ランダムサンプリング

ランダムサンプリング

ランダムサンプリング (RS; random sampling) は統計学やデータ分析において大規模な集合 (母集団) から無作為にデータを抽出する手法である。母集団の各要素が等しい確率で選ばれるサンプリングでは、得られたサンプルは母集団全体の特性を統計的に正しく反映していることが期待される。…

2020年5月29日(Fri) #RandomSampling #WRS #ReservoirSampling

非復元ランダムサンプリングにおける公平性

Inverse (逆数) の重み分布に対して ×1,000 を実行してみれば明らかなように、それぞれの要素の選択頻度の分布 (Actual Win Rate) は重みの分布とはかけ離れた挙動となる。…

2020年7月12日(Sun) #RandomSampling #WRS #fairness

論文翻訳: Weighted Random Sampling (2005; Efraimidis, Spirakis)

重み付きランダムサンプリング (乱択) のアルゴリズムに関する 2005 年の論文。重み付き非復元ランダムサンプリング (weighted random sampling without replacement) に基づいて、開始時点でサイズが未知の母集団から 1 パスでサイズ \(m\) の部分集合を生成することができる。…

2020年5月22日(Fri) 2005年の論文 #WeightedRandomSampling #ReservoirSampling

論文翻訳: Fast Generation of Discrete Random Variables

Walker のエイリアス法を改良して正方ヒストグラムを使う方法で高速に重み付きランダムサンプリングを行うアルゴリズムに関する 2004 年の論文。

2020年5月31日(Sun) 2004年の論文 #WeightedRandomSampling #SquareHistogram

論文翻訳: Min-Wise Independent Permutations (Extended abstract)

min-wise 独立置換族 (min-wise independent permutations family) に関する 1998 年の論文。Brahms サンプリングの関連で調べたもの。…

2023年1月31日(Tue) #最小値独立置換族

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.

2024年9月9日(Mon) 1951年の論文

論文翻訳: Sampling From a Moving Window Over Streaming Data

データストリームから得られる最近の \(n\) 個のデータからランダムサンプリングを行うために移動ウィンドウを使用した手法を解説する 2002 年の論文。1 つの「現在選択されているサンプル」と複数の「選択されているサンプルまたはその後継者がウィンドウを外れたときにサンプルとして選択される後継者」をチェーン状に保持することで、サイズ \(n\) の移動ウィンドウの中で常に 1 つの要素をサンプリングする。…

2024年9月17日(Tue) 2002年の論文

グラフィックス

組み合わせ問題

設計パターン