Go to page
 

Bibliographic Metadata

Title
Approaches for fast similarity search with MapReduce / Author Trong Nhan Phan
AuthorPhan, Trong Nhan
CensorKüng, Josef ; Rauber, Andreas
PublishedLinz, 2016
Descriptionxv, 171 Seiten : Illustrationen
Institutional NoteUniversität Linz, Univ., Dissertation, 2016
LanguageEnglish
Bibl. ReferenceOeBB
Document typeDissertation (PhD)
Keywords (DE)Ähnlichkeitssuche / schnelle Abfrageverarbeitung / Skalierbarkeit / Clustering / Filter / Pruning / redundanzfreie Verarbeitung / Lastverteilung / BigData / MapReduce
Keywords (EN)similarity search / fast query processing / scalability / clustering / filtering / pruning / redundancy-free capability / load balance / big data / MapReduce
Keywords (GND)Ähnlichkeitssuche / Schnelligkeit / Cluster-Analyse / Massendaten / Redundanzminderung
URNurn:nbn:at:at-ubl:1-9199 Persistent Identifier (URN)
Restriction-Information
 The work is publicly available
Files
Approaches for fast similarity search with MapReduce [4.73 mb]
Links
Reference
Classification
Abstract (English)

Similarity search is the principle operation not only in databases but also in disciplinary majors such as information retrieval, machine learning, or data mining. In addition, it has been widely-used in various applications like duplicate detection, data cleaning, or data clustering. Nevertheless, a similarity search process is expensive due to the cost of similarity computations. Moreover, similarity search becomes time-consuming when it has to access irrelevant objects and then has unnecessarily to evaluate their similarity. Furthermore, it has to deal with challenges from big data, first and foremost with the large amounts of data. Such challenges make similarity search costly but leave big motivations for us. Emerging as a paradigm for large-scale processing with the fashion of parallel and distributed computing on a cluster of commodity machines, MapReduce rapidly shows its capability as a candidate for processing massive datasets with high-fault tolerance. In our dissertation, we study the performance of similarity search with MapReduce. Moreover, we also study the problems of scalability, redundancy, and load balance when doing similarity search. Without loss of accuracy, we prefer an exact similarity search. Among various approaches, we choose the way of improving performance from similarity search schemes using MapReduce. More specifically, we propose three different kinds of approaches towards fast similarity search. They are respectively the instant approaches, the build-in approaches, and the hybrid approaches.

Firstly, we employ MapReduce to experience similarity search with particular measures, whose typical and popular representatives are Cosine and Jaccard measures. The idea behind is to utilize inverted index, which is a well-known index data structure for fast full text search. Our strategy is, however, to index those data that exist in a given query rather than indexing all original data. As a consequence, only a small portion of data is processed for similarity search. At the same time, we minimize the big amount of inessential data engaging in both the indexing and the search processes. Due to being dependent on a certain query, this approach belongs to the category of instant approaches and is considered to be suitable for one-time querying while maintaining less data throughout MapReduce jobs.

Secondly, we want to separate the indexing phase and the similarity search phase so that similarity queries are able to run multiple times from the indexing data without re-accessing the original data. This approach belongs to the build-in approaches in that the indexed data are already prepared in advance and soon ready for similarity queries. Moreover, we observe that using inverted index leads to some drawbacks that are not appropriate for similarity search using MapReduce. Consequently, we propose using document-based index instead in order to overcome these drawbacks. Furthermore, we cluster data objects into different compartments so that we reduce the search space for the task of searching.

Thirdly, we are towards the hybrid approaches that take the advantages of both the instant approaches and the build-in approaches. Our goal is to achieve fast index building as well as fast similarity search. Moreover, we are aware of organizing data when building the indices. It is, on the one hand, noticed that clustering objects too tight or too loose would not be useful for the full-scan fashion of MapReduce. On the other hand, though document-based index is exploited as a skeleton in our indexing phase, data objects should be organized in ways so that we are able to minimize unnecessary data accesses. Furthermore, we address the load imbalance and then propose a straggler mitigating method to augment better load balance and at the same time improve the runtime at reducers.

Besides, we equip our proposed methods with filtering and pruning strategies. Additionally, we propose a hybrid MapReduce-based architecture whose main aim is to deal with the "three Vs" (Volume, Velocity, Variety) of big data. Moreover, we are conscious of employing minimal MapReduce jobs. Due to the fact that a single MapReduce job is expensive, using less MapReduce jobs without re-accessing the original data results in fewer penalties. Furthermore, we intensively conduct a series of empirical experiments on real datasets. The results demonstrate that our proposed methods have better performance than the baseline method and some related work.

Abstract (German)

Similarity Search (Ähnlichkeitssuche) ist eine der zentralen Operationen, nicht nur in Datenbanken, ebenso in anderen Hauptgebieten der Datenverarbeitung wie Information Retrieval, Machine Learning oder Data Mining. Darüber hinaus wird sie in verschiedenen Anwendungen verwendet, beispielsweise Duplicate Detection, Data Cleaning oder Data Clustering. Trotz der hohen Verbreitung und Verwendung von Similarity Search, ist ihre Anwendung wegen der hohen Kosten der Ähnlichkeitsberechnungen sehr teuer. Similarity Search wird auch sehr zeitintensiv und zeitraubend, wenn es bei der Ausführung auf irrelevante Objekte zugreift und deren Ähnlichkeitswerte unnötigerweise berechnet. Mehr noch, muss Similarity Search mit den Herausforderungen von Big Data klar kommen, die größte darunter, das Verwalten großer Datenmengen. Diese Herausforderungen machen Similarity Search teuer, hinterlassen uns aber eine große Motivation. In dieser Arbeit analysieren wir die Leistung von Similarity Search in Kombination mit MapReduce. Darüber hinaus untersuchen wir die Probleme der Skalierbarkeit, Redundanz und Lastausgleich, welche bei Similarity Search immer ein Thema sind. Natürlich wird eine genaue Similarity Search ohne Verlust von Genauigkeit bevorzugt. Unter Verwendung verschiedener Ansätze streben wir eine Verbesserung der Performanz von Similarity Search Vorgängen unter Zuhilfenahme von MapReduce an. Genau genommen untersuchen bzw. verwenden wir drei unterschiedliche Ansätze für eine schnelle Similarity Search, diese sind: Instant, Build-In und Hybrid.

Zuerst wenden wir MapReduce an, um Erfahrungen mit Similarity Search mit besonderen Ähnlichkeitsmaßen zu sammeln - typische bzw. beliebte Vertreter sind Jaccard- und Cosinus (Jaccard- Koeffizient und Kosinus-Ähnlichkeit). Die Idee dahinter ist, einen Invertierten Index zu erhalten, welcher ein bekanntes Werkzeug für die Indexierung einer schnellen Volltext-Suche ist. Unsere Strategie ist es, die gegebenen Daten einer bestimmten Query zu indexieren und nicht alle vorhandenen Ausgangsdaten. Als Folge dieser Strategie wird nur ein kleiner Teil der Daten für die Similarity Search verarbeitet. Gleichzeitig wird der riesige Datenbestand von unwichtigen Daten befreit, indem sowohl in die Indizierung als auch in den Suchprozess eingegriffen wird. Da der Prozess von einer bestimmten Query abhängig ist, ist er brauchbar für einmalige Abfragen, weil weniger Daten im MapReduce verarbeitet werden müssen.

Im zweiten Schritt wollen wir die Indexierung und die Similarity Search voneinander trennen, damit Abfragen der Similarity Search mehrmals in der Queue ausgeführt werden können, ohne den originalen Datenbestand erneut verarbeiten zu müssen. Dieser Ansatz gehört zur Klasse der Build-In Ansätze, bei denen die indexierten Daten bereits gut vorbereitet sind und dann für Similarity Search Queues verwendet werden können. Wir haben herausgefunden, dass die Verwendung invertierter Indizes zu Nachteilen führen kann, welche nicht adäquat für Similarity Search unter der Verwendung von MapReduce sind. Folglich schlagen wir stattdessen dokumentbasierte Indizes vor um diese Nachteile auszugleichen. Darüber hinaus werden Datenobjekte gebündelt (clustering) womit der mögliche Suchraum eingegrenzt wird.

Im dritten Schritt beschäftigen wir uns mit den Hybrid-Ansätzen, welche die Vorteile sowohl des Instant- und des Build-In Ansätze vereinen. Unser Ziel ist das Erreichen von schnellen Indexierungen und einer schnellen Similarity Search. Weiters muss jedem bewusst sein, dass die Daten richtig organisiert gehören, wenn man die Indizes bildet. Einerseits sind zu fest oder zu lose geclusterte Objekte nicht hilfreich für die Full-Scan-Anwendung von MapReduce, andererseits sollten die Datenobjekte so organisiert werden, dass unnötige Zugriffe auf ein Minimum reduziert werden, vor allem auch deswegen, weil die dokumentbasierten Indizes das Grundgerüst unserer Indizierungsphase darstellen. Darüber hinaus widmen wir uns einer guten Arbeitsverteilung und schlagen ein Verfahren vor, den Lastenausgleich und somit die Laufzeit zu verbessern.

Außerdem statten wir unsere vorgeschlagenen Methoden mit Filtern und Kürzungsstrategien aus. Zusätzlich schlagen wir eine hybride MapReduce-basierte Architektur vor, deren Hauptaufgabe es ist, mit den "drei Vs" von BigData umzugehen (Volume/Volumen - Velocity/Geschwindigkeit - Variety/Vielfalt). Darüber hinaus sind wir uns der Verwendung von minimalistischen MapReduce Methoden bewusst. Da die Ausführung eines MapReduce Jobs teuer ist, führt die Verwendung weniger Jobs ohne wiederholte Zugriffe auf die Originaldaten zu weniger Zusatzaufwand. Schließlich haben wir intensiv eine Reihe von Experimenten an realen Datensätzen durchgeführt. Die Ergebnisse zeigen, dass unsere vorgeschlagenen Verfahren eine bessere Leistung erzielen als die Basismethode und relevante vergleichbare Arbeiten bzw. Methoden von Similarity Search.