A fast algorithm for constructing inverted files on heterogeneous platforms

Given a collection of documents residing on a disk, we develop a new strategy for processing these documents and building the inverted files extremely quickly. Our approach is tailored for a heterogeneous platform consisting of multicore CPUs and highly multithreaded GPUs. Our algorithm is based on a number of novel techniques, including a high-throughput pipelined strategy, a hybrid trie and B-tree dictionary data structure, dynamic work allocation to CPU and GPU threads, and optimized CUDA indexer implementation. We have performed extensive tests of our algorithm on a single node (two Intel Xeon X5560 Quad-core CPUs) with two NVIDIA Tesla C1060 GPUs attached to it, and were able to achieve a throughput of more than 262 MB/s on the ClueWeb09 dataset. Similar results were obtained for widely different datasets. The throughput of our algorithm is superior to the best known algorithms reported in the literature even when compared to those run on large clusters.

► A high-throughput pipelined strategy involving parallel parsers and parallel indexers.
► A hybrid trie and B-tree dictionary with fast look-up table and string caches.
► Dynamic allocation of parsed streams to CPU and GPU threads based on sampling.
► Optimized CUDA indexer with effective global and shared memory accesses.
► Performance on single node superior to MapReduce on larger clusters.