kostenloser Webspace werbefrei: lima-city

MySQL: Nearest-Neighbor-Suche

lima-city → Forum → Programmiersprachen → PHP, MySQL & .htaccess

1. Autor dieses Themas

   mucho

   mucho hat kostenlosen Webspace.

   13:06, 17.11.2011

   Moin,
   
   die Situation ist folgende:
   Ich habe Vektoren (SURF-Deskriptoren, falls jemand etwas damit anfangen kann) in einer MySQL Tabelle gespeichert, die, unwichtige Spalten mal weggelassen, so aussieht:
   
   

   CREATE TABLE `surfdescs` (
     `ID` INT NOT NULL AUTO INCREMENT,
     `descriptor` BLOB,
     PRIMARY KEY (ID)
   )

   
   
   Nun suche ich für einen Anfragevektor seinem nächsten Nachbar, die dafür nötige Distanzfunktion ist als eine UDF (user defined function) eingebunden (in C geschriebene Funktion, mit Visual Studio als .dll kompiliert usw....). In diesem Fall ist es der euklidische Abstand.
   
   Mein "prepared statement" zur Abfrage sieht dann wie folgt aus (das ? steht für den Anfragevektor, die 64 ist die Dimension der Vektoren):
   
   

   SELECT ID, EDistance(`descriptor`, ?, 64) AS Distanz
   FROM `surfdescs`
   ORDER BY Distanz ASC
   LIMIT 1;

   
   
   Funktionieren tut das Ganze wunderbar, das Problem ist die Geschwindigkeit. Scheinbar brauch der MySQL Server (MySQL Community Server 5.5.16) extrem lange um für alle Zeilen (derzeit ca. 170000) den euklidischen Abstand zu berechnen, extrem langsam heißt in diesem Fall ca. 33-mal länger als es z.B. in Java dauern würde den Abstand für die gleiche Menge Vektoren auszurechnen.
   Dass die erste Anfrage lange dauert ist klar, denn zu dem Zeitpunkt hält der Server die Daten noch nicht im Speicher und muss alle Vektoren von der Festplatte laden, danach nimmt die Zeit drastisch ab (keine Festplattenaktivität mehr), ist aber eben immernoch 33-mal "zu langsam".
   
   Irgendjemand eine Idee, wo der Flaschenhals sein könnte?

2. Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!

   lima-city: Gratis werbefreier Webspace für deine eigene Homepage

Dir gefällt dieses Thema?