Algorithm & Architecture

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

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

構造的アルゴリズム

B+Tree

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

2018年4月15日(Sun) #BTree

R-Tree

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

2018年4月7日(Sat) #RTree

有向非巡回グラフ

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

2020年7月21日(Tue) #DAG

HyperLogLog

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

2020年11月28日(Sat) #HyperLogLog #Redis #BigData

Bloom Filter

Bloom Filter は、ある要素が集合内に含まれているかを効率的にテストするための確率的データ構造。false positive (偽陽性; 含まれていないのに true となること) を許容するが false negative (偽陰性; 含まれているのに false となること) は発生しない特徴を持つ。…

2020年11月28日(Sat) #BloomFilter

論文翻訳: 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 作業中

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

大量のデータから要素数を推定するアルゴリズム HyperLogLog に関する 2007 年の論文。

2018年10月30日(Tue) 2007年の論文 #HyperLogLog #BigData 作業中

論文翻訳: BzTree: A High-Performance Latch-free Range Index for Non-Volatile Memory

NVM (不揮発性メモリ) 向けデータ構造 BzTree に関する 2018 年の論文。Microsoft US #10599485 特許。

2021年4月11日(Sun) 2018年の論文 #BzTree #B+Tree #NVM #PMwCAS #CAS

Multi-Versioned Hash Tree

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

2021年6月8日(Tue) #LSHTree 作業中

Data Encoding

擬似乱数生成

ランダムサンプリング

ランダムサンプリング

ランダムサンプリング (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

設計パターン

F