nach oben

Datenbank-Spektrum

Erschienen in:

01.04.2011 | Fachbeitrag

Projektseminar „Similarity Search Algorithms“

verfasst von: Dustin Lange, Tobias Vogel, Uwe Draisbach, Felix Naumann

Erschienen in: Datenbank-Spektrum | Ausgabe 1/2011

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Zusammenfassung

Mithilfe von Verfahren aus dem Bereich Ähnlichkeitssuche können zu einer Anfrage an einen Datenbestand nicht nur exakte, sondern auch ähnliche Objekte gefunden werden, z. B. Bilder mit ähnlichen Motiven wie auf dem Anfragebild. Mit aktuellen Forschungsansätzen aus diesem Bereich befasste sich das Seminar „Similarity Search Algorithms“, welches wir in diesem Bericht vorstellen.

Das Ziel des Seminars war ein breiter Vergleich bekannter Indexierungsalgorithmen mit Datensätzen aus verschiedenen Bereichen. Die Studenten befassten sich mit je zwei Ähnlichkeitsmaßen für Datensätze aus fünf verschiedenen Domänen und mit je einem von sechs verschiedenen Indexstrukturen zur Ähnlichkeitssuche in metrischen Räumen. In diesem Bericht evaluieren wir die Kombination der Ähnlichkeitsmaße mit den Indexstrukturen bzgl. Indexaufbau und knn-Anfragen. Außerdem beschreiben wir die Durchführung des Seminars und werfen einen Blick auf lessons learned.

Vorheriger Artikel An Efficient Blocking Technique for Reference Matching using MapReduce

Nächster Artikel Kurz erklärt: Datenfusion

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Datenbank-Spektrum

Datenbank-Spektrum ist das offizielle Organ der Fachgruppe Datenbanken und Information Retrieval der Gesellschaft für Informatik (GI) e.V. Die Zeitschrift widmet sich den Themen Datenbanken, Datenbankanwendungen und Information Retrieval.

Jetzt informieren

MAGIX AG. freedb.org. http://www.freedb.org, January 2011.

C. Sadowski and G. Levin. SimHash: Hash-based similarity detection. http://simhash.googlecode.com/svn/trunk/paper/SimHashWithBib.pdf, December 2007.

http://www.hpi-web.de/naumann/sites/SimSearch2010/.

Bingham E, Mannila H (2001) Random projection in dimensionality reduction: applications to image and text data. In: KDD ’01: Proceedings of the seventh ACM SIGKDD international conference on knowledge discovery and data mining. ACM, New York, S 245–250 CrossRef

Bizer C, Lehmann J, Kobilarov G, Auer S, Becker C, Cyganiak R, Hellmann S (2009) DBpedia—a crystallization point for the Web of data. J Web Semant 7:154–165

Bozkaya T, Ozsoyoglu M (1997) Distance-based indexing for high-dimensional metric spaces. In: Proceedings of the 1997 ACM SIGMOD international conference on management of data, SIGMOD ’97. ACM, New York, S 357–368 CrossRef

Brin S (1995) Near neighbor search in large metric spaces. VLDB J 7(4):574–584

Ciaccia P, Patella M, Zezula P (1997) M-tree: an efficient access method for similarity search in metric spaces. In: Proceedings of the 23rd international conference on very large data bases, VLDB ’97. Morgan Kaufmann, San Francisco, S 426–435

Cohen WW, Ravikumar P, Fienberg SE (2003) A comparison of string distance metrics for name-matching tasks. In: Proceedings of IJCAI-03 workshop on information integration, S 73–78

Curran T, Keller G, Ladd A (1998) SAP R/3 business blueprint: understanding the business process reference model. Prentice-Hall, Upper Saddle River

Dohnal V, Gennaro C, Savino P, Zezula P (2003) D-index: distance searching index for metric data sets. Multimed Tools Appl 21(1):9–33 CrossRef

Gotoh O (1982) An improved algorithm for matching biological sequences. J Mol Biol 162(3):705–708 CrossRef

10.

Jaccard P (1901) Étude comparative de la distribution florale dans une portion des alpes et des jura. Bull Soc Vaud Sci Nat 37:547–579

11.

Jacobs CE, Finkelstein A, Salesin D (1995) Fast multiresolution image querying. In: SIGGRAPH, S 277–286

12.

Keller G, Teufel T (1998) SAP R/3 process oriented implementation, 1. Aufl. Addison-Wesley/Longman, Boston

13.

Levenshtein VI (1966) Binary codes capable of correcting deletions, insertions and reversals. Sov Phys Dokl 10:707–710 MathSciNet

14.

Liu T, Rosenberg C, Rowley H (2007) Clustering billions of images with large scale nearest neighbor search. In: Proceedings of the eighth IEEE workshop on applications of computer vision. IEEE Comput Soc, Los Alamitos

15.

Martin D, Fowlkes C, Tal D, Malik J (2001) A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In: Proc 8th int’l conf computer vision, July 2001, Bd 2, S 416–423

16.

Micó ML, Oncina J, Vidal E (1994) A new version of the nearest-neighbour approximating and eliminating search algorithm (aesa) with linear preprocessing time and memory requirements. Pattern Recognit Lett 15(1):9–17 CrossRef

17.

Monge A, Elkan C (1996) The field matching problem: algorithms and applications. In: Proceedings of the second international conference on knowledge discovery and data mining, S 267–270

18.

Munkres J (1957) Algorithms for the assignment and transportation problems. J Soc Ind Appl Math 5(1):32–38 CrossRefMATHMathSciNet

19.

Olson C (1998) A probabilistic formulation for Hausdorff matching. In: Proceedings of the IEEE conference on computer vision and pattern recognition, S 150–156

20.

Pearson K (1896) Mathematical contributions to the theory of evolution. III. Regression, heredity, and panmixia. In: Phil Trans R Soc Lond, Bd 187, S 253–318

21.

Philips L (2000) The double metaphone search algorithm. C/C++ Users J 18:38–43

22.

Phillips W Jr, Bahn AK, Miyasaki M (1962) Person-matching by electronic methods. Commun ACM 5:404–407 CrossRef

23.

Postel H-J (1969) Die Kölner Phonetik – Ein Verfahren zur Identifizierung von Personennamen auf der Grundlage der Gestaltanalyse. IBM-Nachr 19:925–931

24.

Samet H (2006) Foundations of multidimensional and metric data structures. Morgan Kaufmann, San Mateo MATH

25.

Winkler WE (2003) Methods for evaluating and creating data quality. Inf Syst (Oxf) 29:531–550 CrossRef

26.

Yianilos PN (1993) Data structures and algorithms for nearest neighbor search in general metric spaces. In: SODA: ACM-SIAM symposium on discrete algorithms (A conference on theoretical and experimental analysis of discrete algorithms)

27.

Zezula P, Amato G, Dohnal V, Batko M (2006) Similarity search—the metric space approach. Springer, Berlin MATH

Titel: Projektseminar „Similarity Search Algorithms“
verfasst von: Dustin Lange
Tobias Vogel
Uwe Draisbach
Felix Naumann
Publikationsdatum: 01.04.2011
Verlag: Springer-Verlag
Erschienen in: Datenbank-Spektrum / Ausgabe 1/2011
Print ISSN: 1618-2162
Elektronische ISSN: 1610-1995
DOI: https://doi.org/10.1007/s13222-011-0046-6

Springer Professional

Zusammenfassung

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Datenbank-Spektrum

Weitere Artikel der Ausgabe 1/2011

News

RDF-Stores und RDF-Query-Engines

Kurz erklärt: Datenfusion

Bericht zur Herbstschule Information Retrieval 2010

AnduIN: Anwendungsentwicklung für drahtlose Sensornetzwerke

An Efficient Blocking Technique for Reference Matching using MapReduce

Premium Partner