Posts

AtCoder Beginner Contest 206 D KAIBUNsyo

Union Findを使うと通せる。すべての\(A_i\)と\(A_{N+1-i}\)が同じグループに所属するために必要なunionの回数を答えればいい。

Consistent Hashing and Random Trees: Distributed Chaching Protocols for Relieving Hot Spots on the World Wide Web

各サーバーがネットワーク全体の情報を保持できない分散キャッシュネットワークにホットスポットを作らせないためのキャッシュプロトコルを開発した。 表題のconsistent hashingは、プロトコルの基礎になるハッシュ関数で、値域の違いに関数の写像が影響されにくい。 また、クライアントは一部のキャッシュサーバーにアクセスできればよく、クライアントごとにアクセス可能なキャッシュサーバーの集合は違ってよい。

AtCoder Begineer Contest 051 D - Candidates of No Shortest Paths

ワーシャルフロイト法で全ての2頂点間の最短距離を求めた後、隣接する2頂点の辺のうち、2頂点の最短距離が辺の重みと異なる辺を数えれば通る。

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”を出している。 One Size Fits Allは以前本ページで紹介したことがある。 表題の論文では、OLTPに特化したデータベースH-Storeを実装し、TPC-Cをベンチマークとして商用データベースと比較したところ、H-Storeの方が82倍高速だった。

Burst Tries: A Fast, Efficient Data Structure for String Keys

Burst trieは、trie木の一種で、2分木よりもメモリ効率がよく、trie木と同じくらい速い。 2種類のデータ構造からなり、trie木に加えて別のデータ構造も使う。 どのデータ構造を使うかは要件次第で、論文では、連結リスト、二分探索木、スプレー木を使った場合の実験がなされた。 Burst trie内の別のデータ構造の箇所はcontainerと呼ばれる。 初期状態のBurst trieは、1つのcontainerからなり、別のデータ構造そのものに等しい。 その後、コンテナ内の要素のアクセス頻度やヒット率にもとづくヒューリスティックな基準が満たされると、containerの要素をtrie木のノードにおきかえ、ノードに下に新しいcontainerをつくる。 新しくできたcontainerにも基準を適用し、適宜おきかえる。 これにより、与えられる文字列の頻度に合わせてtrie木と別のデータ構造を使い分けることができると同時に、性能はデータの歪度に依存する。

Suffix Arrays: A New Method for On-Line String Searches

接尾辞配列 Suffix Arraysは、長さ\(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は、要素数と同数の次元からなるユークリッド空間を構成し、要素のハッシュ値で決まる座標に値をおくことで、キー以外でも高速に検索することを可能にする。 もとのドメインの順序関係を保持するハッシュ関数を使うため、範囲検索もあつかえる。