Scalable Top-K Retrieval with Sparta

November 3, 2019
Abstract

Many big data processing applications rely on a top-k retrieval building block, which selects (or approximates) the k highest-scoring data items based on an aggregation of features. In web search, for instance, a document's score is the sum of its scores for all query terms. Top-k retrieval is often used to sift through massive data and identify a smaller subset of it for further analysis. Because it filters out the bulk of the data, it often constitutes the main performance bottleneck. Beyond the rise in data sizes, today's data processing scenarios also increase the number of features contributing to the overall score. In web search, for example, verbose queries are becoming mainstream, while state-of-the-art algorithms fail to process long queries in real-time. We present Sparta, a practical parallel algorithm that exploits multi-core hardware for fast (approximate) top-k retrieval. Thanks to lightweight coordination and judicious context sharing among threads, Sparta scales both in the number of features and in the searched index size. In our web search case study on 50M documents, Sparta processes 12-term queries more than twice as fast as the state-of-the-art. On a tenfold bigger index, Sparta processes queries at the same speed, whereas the average latency of existing algorithms soars to be an order-of-magnitude larger than Sparta's.

Download
Publication Type
Paper
Conference / Journal Name
Principles and Practice of Parallel Programming (PPoPP) 2020

BibTeX


@inproceedings{
    author = {},
    title = {‌Scalable Top-K Retrieval with Sparta‌},
    booktitle = {Proceedings of Principles and Practice of Parallel Programming (PPoPP) 2020‌},
    year = {‌2019‌}
}