SciDok

Eingang zum Volltext in SciDok

Lizenz

Dissertation zugänglich unter
URN: urn:nbn:de:bsz:291-scidok-64699
URL: http://scidok.sulb.uni-saarland.de/volltexte/2016/6469/


Algorithms for shared-memory matrix completion and maximum inner product search

Algorithmen für Matrixfaktorisierung unter einer gemeinsam genutzten Speicherarchitektur und für die Suche nach maximalen Skalarprodukten

Teflioudi, Christina

pdf-Format:
Dokument 1.pdf (1.178 KB)

Bookmark bei Connotea Bookmark bei del.icio.us
SWD-Schlagwörter: Matrizenzerlegung , Skalarprodukt , Algorithmus
Freie Schlagwörter (Englisch): matrix factorization , maximum inner product search
Institut: Fachrichtung 6.2 - Informatik
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
DDC-Sachgruppe: Informatik
Dokumentart: Dissertation
Hauptberichter: Gemulla, Rainer (Prof. Dr.)
Sprache: Englisch
Tag der mündlichen Prüfung: 14.04.2016
Erstellungsjahr: 2016
Publikationsdatum: 26.04.2016
Kurzfassung auf Englisch: In this thesis, we propose efficient and scalable algorithms for shared-memory matrix factorization and maximum inner product search. Matrix factorization is a popular tool in the data mining community due to its ability to quantify the interactions between different types of entities. It typically maps the (potentially noisy) original representations of the entities into a lower dimensional space, where the “true” structure of the dataset is revealed. Inner products of the new vector representations are then used to measure the interactions between different entities. The strongest of these interactions are usually of particular interest in applications and can be retrieved by solving a maximum inner product search problem. For large real-life problem instances of matrix factorization and maximum inner product search, efficient and scalable methods are necessary. We first study large-scale matrix factorization in a shared-memory setting and we propose a cache-aware, parallel method that avoids fine-grained synchronization or locking. In more detail, our approach partitions the initial large problem into small, cache-fitting sub-problems that can be solved independently using stochastic gradient descent. Due to the low cache-miss rate and the absence of any locking or synchronization, our method achieves superior performance in terms of speed (up to 60% faster) and scalability than previously proposed techniques. We then proceed with investigating the problem of maximum inner product search and design a cache-friendly framework that allows for both exact and approximate search. Our approach reduces the original maximum inner product search problem into a set of smaller cosine similarity search problems that can be solved using existing cosine similarity search techniques or our novel algorithms tailored for use within our framework. Experimental results show that our approach is multiple orders of magnitude faster than naive search, consistently faster than alternative methods for exact search, and achieves better quality-speedup tradeoff (up to 3.9x faster for similar recall levels) than state-of-the-art approximate techniques.
Kurzfassung auf Deutsch: In dieser Arbeit schlagen wir effiziente und skalierbare Algorithmen für Matrixfaktorisierung und für die Suche nach maximalen Skalarprodukten unter einer gemeinsam genutzten Speicherarchitektur vor. Matrixfaktorisierung ist ein beliebtes Werkzeug in der Data-Mining-Gemeinschaft aufgrund ihrer Fähigkeit, die Interaktionen zwischen verschiedenen Arten von Objekten zu quantifizieren. Sie bildet typischerweise die (möglicherweise verrauschte) originale Darstellung der Objekte auf einen niederdimensionalen Raum ab, wo die wahre Struktur der Daten sichtbar wird. Die Skalarprodukte zwischen den neuen Darstellungen werden dann benutzt, um die Interaktionen zwischen den verschiedenen Objekten zu messen. Die stärksten dieser Interaktionen sind in Anwendungen oft von besonderem Interesse und können durch eine Suche nach maximalen Skalarprodukten abgerufen werden. Für große, reale Probleme der Matrixfaktorisierung und der Suche nach maximalen Skalarprodukten sind effiziente und skalierbare Methoden notwendig. Zunächst betrachten wir hochskalierbare Matrixfaktorisierung unter einer gemeinsam genutzten Speicherarchitektur und schlagen eine cachebewusste, parallele Methode vor, die feingranulare Synchronisation oder Locking vermeidet. Genauer betrachtet teilt unsere Methode das ursprüngliche, große Problem in kleine, cachepassende Probleme, die unabhänging voneinander durch stochastischen Gradientenabstieg gelöst werden können. Aufgrund der niedrigen Cache Miss Rate und der Abwesenheit von Locking und Synchronisation, erreicht unsere Methode eine verbesserte Leistung in Bezug auf Laufzeit (bis zu 60% schneller) und Skalierbarkeit verglichen mit vorherigen Techniken. Anschließend erforschen wir das Problem der Suche nach maximalen Skalarprodukten und entwerfen ein cachefreundliches System, das sowohl genaue als auch approximative Suche ermöglicht. Unsere Methode reduziert das ursprüngliche Problem auf eine Reihe von kleineren Problemen der Cosinus-Ähnlichkeitssuche. Diese können durch vorhandene Techniken für Cosinus-Ähnlichkeitssuche oder neue Algorithmen, die eigens für die Benutzung innerhalb unseres Systems gebaut sind, gelöst werden. Die Versuchsergebnisse zeigen, dass unsere genauen Methoden um mehrere Größenordnungen schneller als naive Suche und konstant schneller als alternative Methoden sind, und dass unsere approximativen Techniken einen besseren Qualität-Laufzeit-Trade-Off (bis zu 3.9-Mal schneller für ähnliche Recall-Level) als der moderne Stand der Technik für approximative Suche erreichen.
Lizenz: Veröffentlichungsvertrag für Dissertationen und Habilitationen

Home | Impressum | Über SciDok | Policy | Kontakt | Datenschutzerklärung | English