Exact and approximate maximum inner product search with LEMP


Teflioudi, Christina ; Gemulla, Rainer


[img]
Preview
PDF
teflioudi16lemp-draft.pdf - Published

Download (605kB)

DOI: https://doi.org/10.1145/2996452
URL: https://ub-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: http://dl.acm.org/citation.cfm?id=2996452
Publication language: English
Institution: School of Business Informatics and Mathematics > Praktische Informatik I (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.




+ Citation Example and Export

Teflioudi, Christina ; Gemulla, Rainer ORCID: 0000-0003-2762-0050 (2017) Exact and approximate maximum inner product search with LEMP. Open Access ACM Transactions on Database Systems : TODS New York, NY 42 1 Article 5 [Article]
[img]
Preview


+ Search Authors in

BASE: Teflioudi, Christina ; Gemulla, Rainer

Google Scholar: Teflioudi, Christina ; Gemulla, Rainer

ORCID: Teflioudi, Christina ; Gemulla, Rainer ORCID: 0000-0003-2762-0050

+ 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