Exact and approximate maximum inner product search with LEMP

Teflioudi, Christina ; Gemulla, Rainer

teflioudi16lemp-draft.pdf - Published

Download (605kB)

DOI: https://doi.org/10.1145/2996452
URL: https://madoc.bib.uni-mannheim.de/42428
Additional URL: http://dws.informatik.uni-mannheim.de/fileadmin/le...
URN: urn:nbn:de:bsz:180-madoc-424288
Document Type: Article
Year of publication: 2017
The title of a journal, publication series: ACM Transactions on Database Systems : TODS
Volume: 42
Issue number: 1
Page range: Article 5
Place of publication: New York, NY
Publishing house: ACM Press
ISSN: 0362-5915 , 1557-4644
Related URLs:
Publication language: English
Institution: School of Business Informatics and Mathematics > Practical Computer Science I: Data Analytics (Gemulla 2014-)
Subject: 004 Computer science, internet
Classification: 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.

Metadata export


+ Search Authors in

+ Download Statistics

Downloads per month over past year

View more statistics

You have found an error? Please let us know about your desired correction here: E-Mail

Actions (login required)

Show item Show item