Exact and Approximate Maximum Inner Product Search with LEMP
Exact and Approximate Maximum Inner Product Search with LEMP
复制标题
DOI：
10.1145/2996452
复制
发表时间：
2016-12
期刊：
影响因子：
--
通讯作者：
Christina Teflioudi;Rainer Gemulla
中科院分区：
文献类型：
--
作者：
Christina Teflioudi;Rainer Gemulla
我们研究了最大内积搜索的精确和近似方法，这是许多数据挖掘和信息检索任务中的基本问题。我们提出了LEMP框架，该框架支持精确和近似搜索，并提供质量保证。LEMP的核心是将大型向量数据库上的最大内积搜索问题转换为许多较小的余弦相似度搜索问题。这种转换允许LEMP立即删减搜索空间的大部分，并为每个剩余问题单独选择合适的搜索算法。LEMP能够利用现有的余弦相似度搜索方法，但我们也提供了许多针对我们的设置量身定制的新颖搜索算法。我们进行了一项广泛的实验研究，深入了解了许多最先进的技术（包括lemp）在多个真实数据集上的性能。我们发现LEMP通常比其他方法更快或更准确。
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.