Posts

ハッシュコーディングで要素がハッシュエリアにあるかを高速に調べる手法で、ブルームフィルタの名で知られる。 偽陽性を認めることで、ハッシュ値の保持に必要なハッシュエリアを小さくしているため、ハッシュエリアが大きくなるデータでも利用することができる。 例えば、データベースのストレージで使われており、検索するキーがデータベースに存在するか事前に確かめることで、存在しないキーのための不要なディスクの読み取りを省くことができる。 なお、偽陰性の誤りはない。

SSDのランダムな書き込みを高速化するために、インデックスにつかうデータ構造FD-treeを提案した。 FD-treeのエントリ数が\(n\)でページサイズが\(B\)のとき、ランダムな読み込みと書き込みの計算量はともに\(\mathcal{O}(\log_B(n))\)になる。

Isolation Forestは、iForestともいい、完全二分木による異常検知の手法であり、時間計算量が線形で、ハイパーパラメタがわずか2つで、メモリ効率がよいところに特徴がある。 時間、空間計算量がすくないので高次元のデータに向いている。

TAOは、Facebookで開発されたソーシャルグラフのためのマルチリージョンの分散システムで、秒間で10億件の読み込みと数百万件の書き込みの性能を誇る。 Facebookは、もともと、ソーシャルグラフをMySQLに保存し、memcacheをキャッシュにつかい、PHPで問いあわせるシステムを構成していた。 TAOは、そのシステムの現状を引きつぎ、MySQLをストレージに採用している。

COVID19でソフトウェア開発者が在宅稼動(WFH)をはじめたことによる稼動時間の使い方、良好性(Well-being), 生産性の変化を調査した。 ロックダウンを実施した国々のエンジニア500名の中から、2020年4月20日から26日の一波について192名、2020年5月4日から10日の二波について184名を選び、サンプルを集めた。 結果、会社での勤務とWFHの間で、稼動時間の使い方はほぼ変わっていないかった。 また、一波において休憩と生産性の間に負の相関がみられたが、それ以外では良好性、生産性、社会性、心理の4つと特定の業務内容の間に相関関係はみられなかった。 結果、組織やエンジニアにとってWFHそれ自体が課題になるわけではないと結論づけている。

分散トレーシングシステムDapperをGoogle社内で開発、デプロイ、2年間の運用を経た知見をまとめている。 Dapperをもとにして、TwitterはZipkinを、UberはJaegerを開発した。 Dapper以前に開発されたMagpie X-Traceとの違いは、サンプリングされたリクエストのみをトレースし負荷を低減する機能がある点や、少数の共通ライブラリだけを測定対象にするところにある。

ナレッジグラフに欠けたリンクを予測するモデルは、一般に大きなグラフをあつかうために浅く高速なネットワークをもち、層の深いモデルと比べて表現力に欠ける。 提唱されるネットワークConvEは、畳み込み層をつかった深めのネットワークで予測性能の向上をはかる。 層が深くなると計算コストの増加や過学習が課題になるが、先行研究のDistMultやR-GCNと比べたConvEのパラメタ数は1/8や1/17であり、パラメタ効率が高い。

データベースのトランザクション制御ultiversion Concurrency Control(MVCC, 多版型同時実行制御) 下のトランザクションが逐次実行と等価な結果になる条件を定義した。 また、その定義を既存のMVCCのアルゴリズム3つに適用し、その正しさを確かめた。

The Part-Time Parliamentで提唱された分散含意アルゴリズムPaxosをLamport自身が平易に解説したもの。 エージェントの処理速度やメッセージが配信されるまでの長さに仮定はない。 メッセージは複製、喪失する可能性がある。 ただし、ビザンチン将軍問題は扱わず、メッセージが壊れることは考えない。

プロセスが1つでもクラッシュしうる場合には常に含意を保証できる完全な非同期アルゴリズムは存在しないことを示した。 この定理はFLP帰結とよばれている。 FLPは、著者Fischer, Lynch, Patersonの頭文字に由来する。 ここでの完全は、プロセスの処理速度やメッセージの配信遅延に仮定をおかず、同期クロックがないためにタイムアウトを使えず、ほかのプロセスが別のプロセスの障害を検知できないことを意味する。 いいかえると、含意アルゴリズムを実装するには上のいずれかを仮定しなければないことを示した。