Using Graphics Processors for High Performance IR Query Processing

Using Graphics Processors for High Performance IR Query Processing is a paper exploring the use of CUDA GPU as co-processor for serving search queries. The idea is quite intriguiging since GPUs may potentially offer amazing performances at very low cost.

The authors propose a parallel sum prefix based Rice encoding and a PForDelta encoding.
Rice coding encodes an integer (the gap between two consecutive docIDs) by choosing a number of bits b such that 2^b is close to the average of all the gaps, and then representing each integer
as q · 2^b + r for some r < 2b. Then the integer is encoded in a unary part, consisting of q 1s followed by a 0, and a binary part of b bits representing r. PForDelta first selects a value b such that most gaps are less than 2^b, and then uses an array of b-bit values to store all gaps less then 2^b while all other gaps are stored in a special format as exceptions.

The paper describes gap encoding, decoding, and merge operations. In addition, it discusses how to process ranked query, skip lists, dijunctive and conjiuntive queries.

Performances are good, a single server with a GPU and a CPU we can sustain a query arrival rate beyond 300 q/s, versus less than 100 for CPU only. The index size was ~25M documents.

Quite an interesting paper, indeed.