第 4 章 評価実験
4.1 現実の音楽から 生成し た指紋 DB での評価
ま ずは現実の音楽から 生成し た指紋を 用いて ， 実装し た音楽指紋検索システムの， 特に 隣接LSH探索によ る 検索速度と 検索精度への影響を 評価する 。 こ の評価では， 音楽指紋 DBのサイ ズは300曲ま でであり ， 複数メ モリ を 用いた実験も 実施し な い。
4.1.1 開発環境と 実験環境
FPGAの開発環境を 表4.1にま と める 。 回路合成から ビッ ト スト リ ーム生成ま で通常は 数十分以上かかる ため， 高性能のサーバを 使用する こ と でビルド 時間を 短縮し た。 開発用 ツ ールおよ びラ イ ブラ リ は， 現時点で最新のも のを 使用し た。
表 4.1: FPGAの開発環境
項目 説明
CPU AMD Opteron(TM) Processor 6238 (48コ ア) メ モリ DDR3 SDRAM 271GB
スト レ ージ ST320DM000-1BC14C (SATA 3.0, 320GB) OS Scientific Linux 6.1
カ ーネ ル 2.6.32-504.30.3.el6 (64ビッ ト 版) 開発ツ ール ISE Design Suite 14.7
MIGラ イ ブラ リ Memory Interface Generator 3.92
表4.2に， 実験に用いたFPGAボード の特徴を 簡単に示す。 こ れら の機材は市販のも の を そのま ま 使用し て おり ， 未改造の状態である 。
表 4.2: FPGAボード の特徴
項目 説明
製品名 Xilinx社 Virtex-6 FPGA ML605R 評価キッ ト FPGA Virtex-6 XC6VLX240T-1FFG1156
ク ロ ッ ク 200MHz (MIGラ イ ブラ リ が出力) 搭載メ モリ DDR3 SO-DIMM， 512MB
4.1.2 隣接 LSH 探索の評価
実験パラ メ ータ
実験条件・ 実験パラ メ ータ は表4.3の通り である 。 ハッ シュ 値のビッ ト 数L0と 隣接LSH 探索のハミ ン グ半径rnについて は， Yangの手法は文献[4]のも のであり ， 提案手法は付 録A.2で求めた最適値である 。 Yangの手法のス ク リ ーニン グと 精査の閾値は文献[4]の 5.2.2節を 参考にし て ， 25%ま での歪み率を 想定し て 決定し た。
表 4.3: 隣接LSH探索の評価実験の条件
項目 Yangの手法 提案手法
試行回数 300 300
ク エリ 指紋の歪み率pber 0〜0.5 0〜0.5 スク リ ーニン グの閾値ε1 24 24
精査の閾値ε2 1024 1024 ハッ シュ のビッ ト 数L0 13 20 隣接LSH探索のハミ ン グ距離rn 0 0
な お指紋の元と な っ た音楽はYangと 同じ も のであり ， 300曲を 指紋DB化し た。 ク エ リ 指紋の歪み(ビッ ト 誤り)について も ， Yangと 同様に乱数で機械的に付与し た。
検索速度
現実の音楽データ でま ずは検索速度を 評価する 。 Yangが用いた 300曲から HiFP2.0で 指紋DBと ハッ シュ テーブルを 構築し ， メ モリ に全データ を 格納する 。 その後ク エリ 指紋 と し て ， 300曲の指紋にラ ン ダムに歪みを 付与し たも のを 検索システムに入力し ， 検索時 間を 測定する 。
表4.4， 図4.1が実験結果である 。 提案手法の方が平均検索速度において 約6.3倍高速で
表 4.4: Yangの手法と 隣接LSH探索の検索時間
歪み率 Yangの手法の 提案手法の
検索時間(ク ロ ッ ク 数) 検索時間(ク ロ ッ ク 数)
0.00 3,459 781
0.05 6,495 970
0.10 12,850 1,597
0.15 26,838 3,259
0.20 64,244 8,610
0.25 324,776 75,706
0.30 410,223 71,466
0.35 403,908 66,413
0.40 403,561 66,211
0.45 403,553 66,208
0.50 403,553 66,208
0 1 2 3 4 5
0 0.1 0.2 0.3 0.4 0.5
検索時間 (メガクロック数)
歪み率 pber
Yangの手法(理論値) 提案手法(理論値) Yangの手法(実験値) 提案手法(実験値)
図 4.1: 歪み率と 平均検索時間
検索精度
検索精度について は図4.2の通り Yangの手法も 隣接LSH探索も 同程度であっ た。 なお 不正解指紋を 返し た件数(“一致な し”ではな く 別の指紋を 誤っ て 返し た件数)は0であっ たため， 図表には正答率のみを 記載し た。
表 4.5: Yangの手法と 隣接LSH探索の検索精度
歪み率 Yangの手法の 提案手法の
正答率 正答率
0.00 1.00 1.00
0.05 1.00 1.00
0.10 1.00 1.00
0.15 1.00 1.00
0.20 0.41 0.42
0.25 0.00 0.00
0.30 0.00 0.00
0.35 0.00 0.00
0.40 0.00 0.00
0.45 0.00 0.00
0.50 0.00 0.00
0 0.2 0.4 0.6 0.8 1
0 0.1 0.2 0.3 0.4 0.5
正答率
歪み率 pber
Yangの手法(理論値) 提案手法(理論値) Yangの手法(実験値) 提案手法(実験値)
図 4.2: 歪み率と 検索精度
4.1.3 リ ソ ース使用量
実装し た指紋検索モジュ ール(Staged LSHモジュ ール)のリ ソ ース使用量は表4.6の通 り である 。 隣接LSH探索を 追加実装し て も 最大で約1.5%の増加であっ た。
表 4.6: 実装し た指紋検索モジュ ール(Staged LSHモジュ ール)のリ ソ ース使用量
項目 従来手法 提案手法
Number of Slice Registers 467 471
Number of Slice LUTs 2206 2235
Number of fully used LUT-FF pairs 329 334
Number of bounded IOB 115 115
Number of BUFG/BUFGCTRLs 1 1