Write a Blog >>

Many big data processing applications rely on a \emph{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.

Mon 24 Feb

Displayed time zone: Tijuana, Baja California change

10:55 - 12:35
Machine Learning/Big Data (Mediterranean Ballroom)Main Conference
Chair(s): Shuaiwen Leon Song University of Sydney
10:55
25m
Talk
Optimizing Batched Winograd Convolution on GPUs
Main Conference
Da Yan Hong Kong University of Science and Technology, Wei Wang Hong Kong University of Science and Technology, Xiaowen Chu Hong Kong Baptist University
11:20
25m
Talk
Taming Unbalanced Training Workloads in Deep Learning with Partial Collective Operations
Main Conference
Shigang Li Department of Computer Science, ETH Zurich, Tal Ben-Nun Department of Computer Science, ETH Zurich, Salvatore Di Girolamo Department of Computer Science, ETH Zurich, Dan Alistarh IST Austria, Torsten Hoefler Department of Computer Science, ETH Zurich
11:45
25m
Talk
Scalable Top-K Retrieval with Sparta
Main Conference
Gali Sheffi Technion - Israel, Dmitry Basin Yahoo Research, Edward Bortnikov Yahoo Research, David Carmel Amazon, Idit Keidar Technion - Israel institute of technology
12:10
25m
Talk
waveSZ: A Hardware-Algorithm Co-Design of Efficient Lossy Compression for Scientific Data
Main Conference
Jiannan Tian University of Alabama, Sheng Di Argonne National Laboratory, Chengming Zhang University of Alabama, Xin Liang , Sian Jin University of Alabama, Dazhao Cheng University of North Carolina at Charlotte, Dingwen Tao University of Alabama, Franck Cappello Argonne National Laboratory