Posts

ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging (1992)

ARIES(Algorithm for Recovery and Isolation Exploiting Semantics)は、ログ先行書き込み(write-ahead-logging, WAL)によるSAVEPOINTまでの部分的なトランザクションのロールバック、レコード単位のロック、回復のためのアルゴリズムである。ログの対象と粒度はページの更新であり、レコードには単調増加するLSN(Log Sequence number)をわりあてる。レコードは直前の更新のレコードへのポインタであるPrevLSNも含み、あるレコードから以前の更新のレコードへ遡行できる。

ロールバックやリスタート時の更新は、通常時の更新とは別に、保証ログレコード(compensation log record, CLR)に記録される。 ARIESのCLSに記録された更新はUNDOされない。一方、IMS, AS/400, DB2のCLSは、あるトランザクションが何度もロールバックされると、対応するCLSの更新をUNDOすることがある。

#RDBMS

February 26, 2023

Scatter/Gather: A Cluster-based Approach to Browsing Large Document Collections(1992)

Scatter/Gatherは、ユーザーにクエリを入力するかわりに、システムが提示する文書のクラスタをユーザーに選ばせる情報検索の手法である。ユーザーが目的の情報にだどりつける適当なクエリをいつも作れるとはかぎらない。ユーザーが詳しくない分野の情報を調べるときは、クエリにつかえる用語を知らないかもしれない。また、ある分野の情報を広く浅く収集したいときは、クエリの単語によって検索対象を狭く限定したくないかもしれない。

#クラスタリング

February 19, 2023

AtCoder Regular Contest 028 B 特別賞

Pythonであればheap, C++であればsetを2つ使えばよい。新しい要素を追加する度に、一方に上位kの要素、他方にk+1以降の要素があるように、2つのset, heap間で要素を交換する。類似の問題をLeetCodeのHard modeで見かけたことがある。

February 19, 2023

Zookeeper: Wait-free coordination for Internet-scale systems (2010)

ZooKeeperは、リーダ選出と構成管理の機能を提供するためのインメモリーデータベースである。データーベースは、ファイルシステムのような階層構造のwait-freeな抽象データ型であり、各ノードにはデフォルトで最大1MBの少量のデータを保存できる。たとえば、ノードに設定を保存して共有することも、設定ファイルが編集中でないことを示すフラグ代わりのファイルを置くこともできる。

February 12, 2023

AtCoder Regular Contest 007 C - 節約生活

文字数を\(n\)とすると複数のテレビを組合せたときの視聴パターンの重ね方は\(2^n\)個ある。最大文字数は整数型のビット数より数分の1しかないので、ビット操作ですべての重ね方を試行することを考える。各重ね方について、パターンを十分に連結した値の論理和に最大文字数以上連続する1があれば、その試行は要件を満たす。

February 11, 2023

ARC 005C 器物損壊！高橋君

ダイクストラ法を使えば、スタート地点から各区画への最短距離を求められる。塀に移動にかかる時間を十分に大きい値、かりに\(HM+1\)として、ダイクストラ法適用すると、ゴール地点が\(3(HM+1)\)以下未満であり、そのときに限り、塀を壊す回数が2回以下でゴール地点に到達できる。

February 7, 2023

From RankNet to LambdaRank to LambdaMART: An Overview (2010)

LambdaMARTは、勾配ブースティング決定木(MART)の訓練に、RankNetとLambdaRankを応用したランキング学習である。 RankNetとLambdaRankを以前抄訳で解説した(RankNet, LambdaRank)。 RankNetは、名前にNetがついているが、RankNetの論文で提案されたものは、ネットワークアーキテクチャではなくランキング学習のための損失関数である。入力されたベクトルをモデルが実数に写像することができれば、ニューラルネットワークでなくてもよい。 RankNetの学習は、モデルの出力する実数をスコアとみなし、あるクエリに該当する2つの事例のうち、より該当する事例に高いスコアを与えられるようにモデルを訓練する。各訓練データはランキングの異なる2つの特徴とランキングの高い方を示すラベルであり、2つのスコアの差をシグモイドに与えたときの出力を、一方のサンプルが他方よりもランキングが高い確率とみなす。そして、交差エントロピーが最小になるようにモデルを訓練する。 LambdaRankは、損失の計算を省き、スコアと損失の勾配で重みを更新することで、RankNetの学習を高速化する。 LambdaMARTは、RankNetに勾配ブースティング決定木を使い、残差の計算にLambdaRankを応用したランキング学習のモデルである。

#ランキング学習

February 3, 2023

Principles of Transaction-Oriented Database Recovery(1983)

クラッシュしたRDMSのディスクとバッファの状態をクラッシュ前の状態にもどす手法を体系化する。体系は、Propagation, Buffer handling, EOT Processing, Checkpointingの4要素に着目して技術を分類する。

#RDBMS

January 29, 2023

抄訳 Learning to Rank with Nonsmooth Cost Functions (2006)

情報検索の指標は、モデルの返す文書の順序を評価する。指標の関数自体を損失関数にできれば、重みの更新を指標に最適化できる。ところが、文書の順序を評価する指標は、重みによる微分が未定義や0になりえるので、損失関数には使えない。 LambdaRankは損失関数に直接は使えない関数を学習に応用するアルゴリズムである。 RankNetをLambdaRankで学習することで、学習時間を短縮し、NDCGを向上できた。

January 23, 2023

Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web (2002)

分散システムは一貫性、可用性、分断耐性を同時に満たすことができない。この予想は、2000年のPODCでBrewerが発表したCAP定理として知られている。しかし、Brewerの講演では厳密な定義や証明はない。そこで、それを補うために、ある2つの計算モデルでCAPが成立することを証明する。計算モデルは、asynchronous network modelとpartially synchhronous modelである。 asynchronouse network modelでは、モデルのノードは、クロックをもたず、受信したメッセージとノード内の計算のみで出力を決定する。 partially synchronous modelでは、各ノードは、一定間隔で単調増加するクロックをもち、処理をタイムアウトしたり、スケジューリングしたりできる。ただし、ノード間でクロックが同期されているとは限らない。

January 17, 2023