論文メモ HyperDex: A Distribute, searchable Key-Value Store

May 7, 2021

HyperDexはキー以外の要素で値を検索できるキーバリューストアで、このキー以外の要素による検索速度がCassandraやMongoDBと比べて12-13倍速い。 キーバリューストアは、RDBMSとくらべて、処理速度は速く、検索条件の機能に乏しい。 HyperDexは、要素数と同数の次元からなるユークリッド空間を構成し、要素のハッシュ値で決まる座標に値をおくことで、キー以外でも高速に検索することを可能にする。 もとのドメインの順序関係を保持するハッシュ関数を使うため、範囲検索もあつかえる。

一方、単純に要素数と次元数を対応させると、指数関数的にユークリッド空間が大きくなってしまう。 たとえば、キーを除いた\(D\)個の要素からなる値をAND条件で検索させるなら、\(2^D\)の領域が必要になる。

そのため、Hyperdexは、ユークリッド空間を一部の要素からなる超直方体に分割して管理する。 具体的には、要素の部分集合からなるsubspaceをつくり、必要な領域数を減らす。 以下の図は、\(D\)次元の空間を\(S\)個の超直方体に分割する様子をあらわす。 \(D=9\)かつ3要素で1つのsubspaceをつくる場合、subspaceは3つになる。 また、3要素を条件として検索する場合、検索対象のsubspaceは、全ての要素が同じsubspaceにあれば1つであり、異なるsubspaceであれば3つになる。 検索条件における要素の共起頻度をもとにsubspaceを決めることで、検索対象のsubspaceの数を減らすことができる。 partitions

論文をこちらからダウンロードできます。 図は論文から引用されています。