MySQLでの128次元ベクトルの距離計算高速化

質問

MySQLで128次元ベクトルの距離計算をしたいと考えています。
※　距離と書いていますが、見つけたいのは最も近くにあるデータなので厳密な距離である必要はありません。

ただし、登録されているデータ量やクエリの工夫のなさにより速度が出ない（タイムアウトするレベル）状態です。
そこで、高速化する方法についてご享受ください。

【環境】
OS：CentOS
mysql：mysql Ver 14.14 Distrib 5.1.58, for redhat-linux-gnu (x86_64) using readline 5.1
DBに登録されているデータ件数：150万件
総データサイズ：1.6GByte（1レコードあたり1k程度と思われます）
カラム数：130
　　　　　id1,id2,pt1,pt2,…,pt128
　　　　　int(11),int(11),float,float…,float
　　　　　近似値計算はfloat部分で行います
クエリ：
select id1, MIN(POWER(pt1-dat1,2) + POWER(pt2-dat2,2) + … POWER(pt128-dat128,2) ) as 'nearest' from testDB group by id1 order by nearest limit 1
※dat1は実数です

実行時はCPU使用率が100%であるため、計算量がボトルネックになっているのかなと思っています。

これをなんとか高速化する方法はないでしょうか。
SQLのチューニングや設定の見直し、はたまた次元数を減らす方法等なんでも構いません。

不明、不足な点についてはご指摘いただければ追記させて頂きます。

以上です、よろしくお願い致します。

回答No.7

ki073

No.5でありましたRubyのプログラムを載せておきます。
2つの方法計算しており、その時間を測定するようにしていますので、だいぶ長くなっています。
メモリが3GBytesで仮想メモリを使わずにぎりぎり下の計算ができます。上はもう少し少なくても大丈夫です。
こちらでの結果は、上が10秒、下が2秒程度です。メモリさえあれば下がだいぶ速いです。最近8GBytes増設して4000円弱でしたので、メモリを奮発すれば良いと思います。

narrayという行列計算ライブラリを使っていますので、rubygemsでインストールしておいてください。行列計算がかなり速くなります。
--------------

require "rubygems"
require "narray"
require "benchmark"
# 乱数でデータ作成
dat1=NArray.sfloat(128).random!(100)
pt=NArray.sfloat(128, 1500000).random!(100)
distance_sq=NArray.sfloat(pt.shape[1])

puts Benchmark::CAPTION
puts Benchmark.measure{
# メモリ節約計算
(0...pt.shape[1]).each{|i|
distance_sq[i]=((pt[true, i]-dat1)**2).sum
}
nearest_index1=distance_sq.sort_index[0]
puts "nearest_id: #{nearest_index1} distnce: #{Math.sqrt(distance_sq[nearest_index1])}"
}
puts Benchmark.measure{
# 高速計算？？
nearest_index2=((pt-dat1)**2).sum(0).sort_index[0]
puts "nearest_id: #{nearest_index2} distnce: #{Math.sqrt(((pt[true, nearest_index2]-dat1)**2).sum)}"
}