Exact and approximate maximum inner product search with LEMP


Teflioudi, Christina ; Gemulla, Rainer


[img]
Vorschau
PDF
teflioudi16lemp-draft.pdf - Veröffentlichte Version

Download (605kB)

DOI: https://doi.org/10.1145/2996452
URL: https://madoc.bib.uni-mannheim.de/42428
Weitere URL: http://dws.informatik.uni-mannheim.de/fileadmin/le...
URN: urn:nbn:de:bsz:180-madoc-424288
Dokumenttyp: Zeitschriftenartikel
Erscheinungsjahr: 2017
Titel einer Zeitschrift oder einer Reihe: ACM Transactions on Database Systems : TODS
Band/Volume: 42
Heft/Issue: 1
Seitenbereich: Article 5
Ort der Veröffentlichung: New York, NY
Verlag: ACM Press
ISSN: 0362-5915 , 1557-4644
Verwandte URLs:
Sprache der Veröffentlichung: Englisch
Einrichtung: Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Practical Computer Science I: Data Analytics (Gemulla 2014-)
Fachgebiet: 004 Informatik
Fachklassifikation: CCS: Data Management Systems , Data structures , Data access methods,
Abstract: We study exact and approximate methods for maximum inner product search, a fundamental problem in a number of data mining and information retrieval tasks. We propose the LEMP framework, which supports both exact and approximate search with quality guarantees. At its heart, LEMP transforms a maximum inner product search problem over a large database of vectors into a number of smaller cosine similarity search problems. This transformation allows LEMP to prune large parts of the search space immediately and to select suitable search algorithms for each of the remaining problems individually. LEMP is able to leverage existing methods for cosine similarity search, but we also provide a number of novel search algorithms tailored to our setting. We conducted an extensive experimental study that provides insight into the performance of many state-of-the-art techniques—including LEMP—on multiple real-world datasets. We found that LEMP often was significantly faster or more accurate than alternative methods.




Dieser Eintrag ist Teil der Universitätsbibliographie.

Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt.




Metadaten-Export


Zitation


+ Suche Autoren in

+ Download-Statistik

Downloads im letzten Jahr

Detaillierte Angaben



Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail


Actions (login required)

Eintrag anzeigen Eintrag anzeigen