Nun erklärten Algorithmen für die Indizierung und Suche in metrischen Räumen

StackOverflow https://stackoverflow.com/questions/206270

Frage

Ich brauche eine Art von metrischer Raum Suche in Postgres (*) (PL oder PL / Python) zu implementieren. Also, ich bin für gute Quellen suchen (oder Papiere) mit einem sehr klaren und gestochen scharfe Erklärung der Maschinerie hinter diesen Ideen, in einer solchen Weise, dass ich es selbst umsetzen kann.

Ich würde Klarheit über Effizienz bevorzugen.

(*) Die Notwendigkeit, das ist besser beschrieben hier .

War es hilfreich?

Lösung

Speziell für geografische Daten, suchen Sie unter PostGIS zuerst, um zu sehen, wenn Sie etwas implementieren müssen. Wenn Sie das tun, mit den Papieren in der Wikipedia-Eintrag auf GiST .

auf Ihrem Link Blick scheint es, Ihr metrischer Raum Strings mit irgendeiner Art von Editierdistanz als Metrik ist. Ein schöner, aber ältlich Überblick über einige Lösungen von Navarro, Baeza -Yates, Sutinen und Tarhio, IEEE Data Engineering Bulletin 2001 ; die dazugehörigen Papiere auf Citeseer könnte auch nützlich sein. Ort Sensitive Hashing ist eine neuere Technik, die nützlich sein könnten, aber viele der Papiere sind schwer auf math.

Andere Tipps

BK-Trees für die Indizierung nützlich sind, und suchen alles, was die Dreiecksungleichung gehorcht , metrische Räume enthalten. Das bekannteste Beispiel ist die Suche nach Zeichenketten innerhalb eines gegebenen Editierdistanz eines Ziels. Ich schrieb einen Artikel über diese hier .

Leider gibt es keine dafür in Postgres Unterstützung gebaut. Man könnte es selbst implementieren mit GIST , aber offensichtlich, dass‘ ll eine Menge Arbeit sein. Ich kann nicht von irgendeiner Weise zu denken, es zu implementieren, ohne Ihre eigene Indizes kurz zu schreiben, um den Baum in einer Tabelle gespeichert, die offensichtlich nicht sehr effizient sein werden.

Sie können versuchen, http://sisap.org wo viele moderne metrische Indizes gelistet sind, einschließlich BK-Bäume. Sie können Code in C finden verschiedene Alternativen zu versuchen.

Einige Techniken, die Raum-Suche einbeziehen, dass Sie Hill-Climbing, Neural Network Training, Genetic Algorithm und Particle Swarm könnte helfen.

Sie müssen auch eine Abstandsmetrik über die metrischen Raum definieren. Haben Sie dies getan? (& Aus Neugier, was ist es, wenn Sie dies getan haben)

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top