Algorithm & Architecture

B+Tree

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

2018年4月15日(Sun)

R-Tree

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

2018年4月7日(Sat)

The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree

我々はウィンドウクエリーを常に \(O((\frac{N}{B})^{1-\frac{1}{d}} + \frac{T}{B})\) の I/O で応答する最初の R-Tree 変種である Priority R-Tree、または PR-Tree を提示する。…

2018年4月5日(Thu)

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

この Extended Abstract は、非常に大きなデータアンサンブルの一意な要素の数 (基数) を推定することに貢献する、ほぼ最適な確率的アルゴリズムである HYPERLOGLOG を詳述し分析する。…

2018年10月30日(Tue) 2007年の論文

可変長整数エンコーディング

いくつかの可変長整数エンコーディング実装について。このページの話題は任意精度整数演算ではなくデータ圧縮の目的で整数値をエンコーディングする方法である。

2018年3月26日(Mon)

基数変換

Base64 はバイナリを 64 種類の文字を使用した文字列に変換する。これは、基数 256 の数列を基数 64 の数列に変換し、それぞれの桁を文字にマッピングすることと等価である。Base58 のような 64 以外の符号化についても、対象とする基数が異なるだけで同じ処理となることが分かるだろう。…

2019年2月2日(Sat) 作業中

Resource Pooing 実装

リソースプーリング (resource pooling) は有限のリソースをプールしアプリケーション内の複数の処理で共有 (resource sharing) する仕組み。一般的に、生成や消滅のコストの高いリソースを初期化を終えた状態で共有、再利用することによるパフォーマンス向上の効果を目的としている。…

2018年11月27日(Tue)