論文メモ Isolation Forest
Isolation Forestは、完全二分木による異常検知の手法で、iForestともよばれる。時間計算量が線形で、ハイパーパラメタがわずか2つで、メモリ効率がよい。 時間、空間計算量が少なく高次元のデータに向く。
Posts
論文メモ TAO: Facebook's Distributed Data Store for the Social Graph
TAOは、Facebookで開発されたソーシャルグラフのためのマルチリージョンの分散システムで、秒間10億件の読み込みと数百万件の書き込みの性能を発揮する。 Facebookは、もともとソーシャルグラフを、MySQLに保存し、memcacheでキャッシュし、PHPで問いあわせるシステムで構成していた。 TAOは、そのシステムの現状を引きつぎ、MySQLをストレージに採用している。
論文メモ The Daily Life of Software Engineers during the COVID-19 Pandemic
COVID19でソフトウェア開発者が在宅稼動(WFH)をはじめたことによる稼動時間の使い方、良好性(Well-being), 生産性の変化を調査した。 ロックダウンを実施した国々のエンジニア500名の中から、2020年4月20日から26日の一波について192名、2020年5月4日から10日の二波について184名を選び、サンプルを集めた。 結果、会社での勤務とWFHの間で、稼動時間の使い方はほぼ変わっていないかった。 また、一波において休憩と生産性の間に負の相関がみられたが、それ以外では良好性、生産性、社会性、心理の4つと特定の業務内容の間に相関関係はみられなかった。 結果、組織やエンジニアにとってWFHそれ自体が課題になるわけではないと結論づけている。
論文メモ Dapper, a Large-Scale Distributed Systems Tracing Infrastructure
論文メモ Convolutional 2D Knowledge Graph Embeddings
論文メモ Multiversion Concurrency Control - Theory and Algorithms
データベースのトランザクション制御Multiversion Concurrency Control(MVCC, 多版型同時実行制御) 下のトランザクションが逐次実行と等価な結果になる条件を定義した。 また、その定義を既存のMVCCのアルゴリズム3つにあてはめ、アルゴリズムの正しさを確かめた。
論文メモ Paxos Made Simple
The Part-Time Parliamentで提唱された分散含意アルゴリズムPaxosをLamport自身が平易に解説した。 エージェントの処理速度やメッセージが配信されるまでの長さに仮定はない。 メッセージは複製、喪失してもよい。 他方で、ビザンチン将軍問題は扱わず、メッセージが壊れることは考えない。
論文メモ Impossibility of Distributed Consensus with One Faulty Process
プロセスが1つでもクラッシュしうる場合には常に含意を保証できる完全な非同期アルゴリズムは存在しないことを示した。 この定理はFLP帰結とよばれる。 FLPは、著者Fischer, Lynch, Patersonの頭文字に由来する。 ここでの完全は、プロセスの処理速度やメッセージの配信遅延に仮定をおかず、同期クロックがないためにタイムアウトを使えず、ほかのプロセスが別のプロセスの障害を検知できないことを意味する。 いいかえると、含意アルゴリズムを実装するには上のいずれかを仮定しなければないことを示した。
論文メモ Availability in Globally Distributed Storage Systems
Googleの分散ストレージで生じた障害の統計をとり、ストレージの可用性の予測モデルを提唱した。 ディスク、ノード、ラックなどハードウェアの粒度を変えて、粒度ごとの平均故障間隔を計測し、故障原因を分類した。 2分のウィンドウで生じた障害をグループにまとめると、ほとんどの障害が同時多発的な障害の一部であった。 20以上のノードを巻き込む大きな障害では、別々のラックにあるノードに障害が起きるよりも、特定のラックのノードに障害が起きることが多かった。
論文メモ What You Always Wanted to Know About Datalog
論理型のデータベースのクエリ言語Datalogの構文、意味論、最適化が解説されている。 最適化の節はサーベイ論文の形式で、最適化を分類し、各種類の先行研究に案内がある。