AtCoder Begineer Contest 051 D - Candidates of No Shortest Paths
ワーシャルフロイト法で全ての2頂点間の最短距離を求めた後、隣接する2頂点の辺のうち、2頂点の最短距離が辺の重みと異なる辺を数えれば通る。
Posts
AtCoder Beginner Contest 205 D - Kth Excluded
\(K_q\)ごとに二部探索で答えを直接検索しても通すことができる。
Windows Azure Storage: A Highly Available Cloud Storage Service with Strong Consistency
AzureのクラウドストレージサービスWindows Azure Storage(WAS) は、2008年の11月から本番運用されている。 保存できるデータの形式には、単なるファイル(Blob)だけでなく、テーブルのレコードとキューのメッセージがある。 ハードウェアの故障に備えたローカルでのレプリケーションだけでなく、地理的に離れたデータセンタにもレプリケーションを分散し、災害復旧にも備える。
Thrift: Scalable Cross-Language Services Implementation
ThriftはFacebookで開発されたRPCライブラリで、IDLからクライアントとサーバのコードを生成する。 Thrift自体は、大きくType, Transport, Protocol, Versioning, Processorの5つのコンポーネントからなる。
The End of an Architectural Era (It's Time for a Complete Rewrite)
発表時期は2007年で、RDBMSの源流であるSystem Rが開発された70年代からハードウェアの性能や価格が変わったことを背景に、RDMSのアーキテクチャを既存技術の延長ではなく抜本から刷新し、いわゆるNoSQLを開発する必要性を主張している。 第一著者のMichael Stonebrakerは、後の2011年に今日全てのデータベースの要件をRDMSだけでは満たすことができないと主張する論文“One Size Fits All”を出している。 表題の論文では、OLTPに特化したデータベースH-Storeを実装し、TPC-Cをベンチマークとして商用データベースと比較したところ、H-Storeの方が82倍高速だった。
Burst Tries: A Fast, Efficient Data Structure for String Keys
trie木の一種のburst trieは、2分木よりもメモリ効率がよく、trie木と同じくらい速い。 内部は2種類のデータ構造からなり、trie木のほかに別のデータ構造もつかう。 どのデータ構造を使うかは要件次第で、実験では、連結リスト、二分探索木、スプレー木をつかった。 Burst trie内の別のデータ構造はcontainerとよばれる。 初期状態のburst trieは、1つのcontainerからなり、別のデータ構造そのものに等しい。 その後、containerの要素のアクセス頻度やヒット率にもとづくヒューリスティックな基準が満たされると、containerの要素をtrie木のノードにおきかえ、ノードの下に新しいcontainerをつくる。 新しくできたcontainerにも基準を適用し、適宜containerをtrieのノードにおきかえる。 以上の手続きより、与えられる文字列の頻度に合わせてtrie木と別のデータ構造を使い分けることができる。 性能はデータ分布の歪度に依存する。
Suffix Arrays: A New Method for On-Line String Searches
接尾辞配列 Suffix Arrayは、長さ\(P\)の文字列が長さ\(W\)の文字列のどこに出現するかを時間計算量\(\mathcal{O}(P + \log N)\)で判定できるデータ構造で、接尾辞木 suffix treeよりもメモリ効率が3-5倍よい。 一方、検索の準備にかかる最悪時間計算量はsuffix treeよりも大きい。 suffix arrayの構築にかかる最悪時間計算量が\(\mathcal{O}(N\log N)\)に対して、suffix treeは\(\mathcal{O}(N)\)しかかからない。
論文メモ HyperDex: A Distribute, searchable Key-Value Store
HyperDexはキー以外の要素で値を検索できるキーバリューストアで、このキー以外の要素による検索速度がCassandraやMongoDBと比べて12-13倍速い。 キーバリューストアは、RDBMSとくらべて、処理速度は速く、検索条件の機能に乏しい。 HyperDexは、要素数と同数の次元からなるユークリッド空間を構成し、要素のハッシュ値で決まる座標に値をおくことで、キー以外でも高速に検索することを可能にする。 もとのドメインの順序関係を保持するハッシュ関数を使うため、範囲検索もあつかえる。
論文メモ Integrating the UB-Tree into a Database System Kernel
商用DBMS TransBaseのインデックスをB木からUB木に変え、 多次元アクセス（複数の列の範囲を指定するクエリ）を高速化した。 一見、商用DBMSのインデックスの拡張は複雑かつ高コストのように思える。 UB木は、B木をベースにしたインデックスで、B木のキーの生成とページ分割方法を細工し、範囲クエリを高速化できる。 範囲クエリに向きB木に似たUB木を使うことで、既存のDBMSの範囲クエリを人々の想定よりも簡単に高速化できることを例示した。 また、既存のインデックスの拡張用に提供されたインターフェースを使わず、インデックスを置き換えカーネルにUB木を密結合することで、クエリのオプティマイザを継続して利用できた。
論文メモ Designing Access Methods: The RUM Conjecture
データ構造は読み込み(Read, R), 更新(Update, U), 所要メモリ容量(Memory, M)にトリレンマを抱え、いかなるデータ構造でも、2つを最適化すると残る1つのオーバヘッドが悪化すると予想した。 Read, Update, Memoryの頭文字から、これをRUM Conjectureと名付けた。