シグナチャマシンハード

シグナチャを階層化すると速く検索できるといっている。 階層化は各シグナチャのORをとったものを親とすることに より行なう。実験結果しか書いていない。

Partial-Match retrieval(2次キーによる検索ともいうら しい)というのはファイルのレコードに属性の組が付加さ れていることを仮定した検索方法である。レコード毎に各 属性をコード化して並べたもの(デスクリプタ)を記憶して おき、検索の際は質問を同様にコード化したものがそれに 含まれればマッチしたと判断する。レコードデスクリプタ は膨大な数になってしまうので、いくつかのレコードをま とめてORをとってブロックデスクリプタを作る。それをま とめてまた上位のデスクリプタを作る...というのをくり かえす。

デスクリプタというのはシグナチャのようなものであり、 Signature Treeというのと全く同じものである。

シグナチャのコーディング方法の比較解説。Variable Bit-block Compressonという方法でシグナチャのビットベ クトルを圧縮するのがよいとしている。(比較になってい るのはWord Signature(語のシグナチャを並べたもの)、 Superimposed Coding(語のシグナチャのORをとったもの)、 Run Length、Bit-block Compression(シグナチャをブロッ クに分割して0の連続を圧縮するもの) 、VBC(BCの変型)で ある。) シグナチャのサイズを大きくすればFalse Dropを 小さくすることができるから、圧縮効率をあげることがで きれば同じサイズのシグナチャでFalse Dropを小さくする ことができるというわけである。

要するに0の多い画像の圧縮と同じことだと思うが...01列 の効率的圧縮法としてVBCが最適であるとも思えない。(シ グナチャデータの特性によるだろう。) ちょっと信用でき ない。

シグナチャを検索するのに時間がかかるので分割統治で検 索する。シグナチャの一部分をキーとして別に持っておき、 検索シグナチャはまずキーと照合してから本体と照合する。 キーの選び方として何種類か比較している。

情報の追加のときシグナチャだけでなくキー(ファイル?) も変更しなければならないような気がするが?

シグナチャの高速検索各方式の比較。

Pfaltz_indexedsignatureとやりたいことは似てい る。ハッシュを並べてデスクリプタ(シグナチャ)を作るか わりにsuperimposed codeを使う。(本質に違いはないと思 うが。) シグナチャの木を作るかわりに Roberts_bitsliceの方法(ビットスライス)を使う。 それでも大きくなると困るのでシグナチャを階層化する。 デスクリプタを使うとJ. SmithとただのSmithから同じデ スクリプタが計算されるようにすることによりあいまい検 索っぽいことができるとか、1940-1949,1950-1959という のを各ビットにわりつけることにより1940-1959も簡単に 検索できるとかいった利点もあるという。