Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-26651
Titel: Algorithms for shared-memory matrix completion and maximum inner product search
Alternativtitel: Algorithmen für Matrixfaktorisierung unter einer gemeinsam genutzten Speicherarchitektur und für die Suche nach maximalen Skalarprodukten
VerfasserIn: Teflioudi, Christina
Sprache: Englisch
Erscheinungsjahr: 2016
Kontrollierte Schlagwörter: Matrizenzerlegung
Skalarprodukt
Algorithmus
Freie Schlagwörter: matrix factorization
maximum inner product search
DDC-Sachgruppe: 004 Informatik
Dokumenttyp: Dissertation
Abstract: 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.
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.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-64699
hdl:20.500.11880/26707
http://dx.doi.org/10.22028/D291-26651
Erstgutachter: Gemulla, Rainer
Tag der mündlichen Prüfung: 14-Apr-2016
Datum des Eintrags: 26-Apr-2016
Fakultät: MI - Fakultät für Mathematik und Informatik
Fachrichtung: MI - Informatik
Sammlung:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Dateien zu diesem Datensatz:
Datei Beschreibung GrößeFormat 
main.pdf1,18 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.