Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units

Naiyong Ao, Fan Zhang, Di Wu, Douglas S. Stones, Gang Wang, Xiaoguang Liu, Jing Liu, Sheng Lin

TL;DR

This paper tackles the performance bottleneck of lists intersection and index compression in large-scale web search engines, which are crucial for fast query processing. The authors propose novel GPU-accelerated algorithms, Linear Regression (LR) and Hash Segmentation (HS) for lists intersection, and Linear Regression Compression (LRC) for index compression, demonstrating significant speedups and improved efficiency.

What Problem Does This Paper Address?

Modern web search engines handle massive amounts of data and an ever-increasing volume of user queries. Two operations that significantly impact query processing speed are lists intersection (finding documents that contain all query terms) and index decompression (retrieving compressed index data). Traditional algorithms for these tasks, often designed for CPUs, struggle to scale efficiently on modern hardware, especially when leveraging the parallel processing power of Graphics Processing Units (GPUs). The paper aims to bridge this gap by developing and evaluating GPU-optimized algorithms that can handle the demands of large-scale search engines.

Methods

The core of this paper lies in its novel algorithmic approaches designed for GPU execution:

  • Lists Intersection:
    • Linear Regression (LR): This technique exploits the observed linear trend in inverted lists (sequences of document IDs for a given term). By fitting a linear regression model to an inverted list, the algorithm can predict the approximate location of a target document ID, thereby contracting the search range for binary search. This reduces the number of global memory accesses, a key performance bottleneck on GPUs.
  • Hash Segmentation (HS): This method partitions an inverted list into smaller "buckets" based on a hash function. When searching for a document ID, the algorithm first identifies the relevant bucket and then performs a binary search within that smaller segment. This also aims to reduce the search space.
  • Combined Approaches: The paper also explores combining LR and HS, as well as segmenting lists before applying LR (LRCSeg) or applying LR to segments (SegLRC), to further refine search ranges.
  • Index Compression:
    • Linear Regression Compression (LRC): This approach leverages the linearity of inverted lists to compress them. Instead of storing raw document IDs or d-gaps, LRC stores the difference between the actual document ID and its predicted value from a linear regression model. This "vertical deviation" is then compressed using an efficient parallel compression scheme (ParaPFor). LRC is designed to allow for faster decompression of individual elements, crucial for GPU-based intersection.
  • ParaPFor: This is an improvement over the standard PFor compression algorithm, specifically designed for parallel decompression on GPUs. It addresses the sequential bottleneck in handling exceptions by storing exception indices, enabling concurrent recovery.

Datasets

The authors evaluated their algorithms on several real-world and synthetic datasets:

  • TREC GOV and GOV2: These are standard web document collections used in information retrieval research.
  • GOVPR: This dataset is derived from GOV, with document IDs reordered based on PageRank, simulating a scenario where documents are ordered by importance.
  • GOVR and GOV2R: These datasets are generated by randomly shuffling the document IDs of GOV and GOV2, respectively. This is important because the paper hypothesizes that randomized docIDs can lead to better performance with their proposed linear regression-based methods.
  • Baidu Dataset (BD): A large dataset from Baidu, a major Chinese search engine.
  • BDR: A dataset derived from BD by randomly shuffling document IDs.

Key Insights and Ideas

  • Inverted Lists Exhibit Linearity: A crucial observation is that inverted lists, even those reordered for compression, tend to exhibit a significant linear characteristic. This linearity is the foundation for the proposed Linear Regression (LR) and Linear Regression Compression (LRC) techniques.
  • Randomized DocIDs Can Be Beneficial: Contrary to some compression strategies that rely on locality, the paper finds that randomized docIDs can actually improve the performance of LR-based algorithms. This is because randomization can lead to more predictable linear behavior and reduce branch divergency on GPUs.
  • GPU Architecture Demands Different Optimizations: The paper highlights that algorithms suitable for CPUs (like interpolation search) may not perform well on GPUs due to SIMT architecture, memory access patterns, and the cost of global memory operations. This justifies the development of GPU-specific parallel algorithms.
  • Decompression Speed is Critical for Intersection: For query processing, the speed at which compressed lists can be decompressed is paramount, especially when performing intersections. LRC is designed to enable faster, more parallel decompression of individual elements.

Key Results

  • Significant Throughput Improvements: The proposed LR and HS algorithms for uncompressed lists intersection achieved substantial throughput gains. For instance, HS16 boosted throughput by up to 60% compared to a baseline binary search.
  • Efficient Compressed Lists Intersection: When applied to compressed lists, algorithms like SegLRC and HS256_LRC demonstrated considerable speedups over baseline methods. SegLRC, for example, achieved a throughput of over 160,000 queries/s on the GOV dataset.
  • Competitive Compression Ratios: While prioritizing decompression speed, the LRC-based compression methods achieved reasonable compression ratios, comparable to or only slightly worse than established methods like PFor.
  • Speedup Scalability: The paper shows that the proposed algorithms scale well with the number of GPU Streaming Multiprocessors (SMs), indicating their suitability for future GPU architectures.

Limitations and Future Work

  • Branch Divergency: The paper notes that branch divergency can impact performance, especially on randomized datasets. While LR helps mitigate this, it remains a factor.
  • CPU-GPU Transfers: The authors acknowledge that CPU-GPU transfers and CPU computation still constitute a significant portion of the total execution time. Overlapping these operations with GPU computation is identified as a future avenue for improvement.
  • Dataset Specificity: While experiments were conducted on various datasets, the performance of LR-based methods is noted to be particularly sensitive to the linearity of the inverted lists, suggesting that their effectiveness might vary across different types of web corpora.
  • Further Optimization of LRC: While LRC shows promise, further research into optimizing its segmentation strategies (LRCSeg, SegLRC) and combining it with other techniques like Hash Segmentation (HS-LRC) is explored.

Summary updated

BibTeX
@article{ao2011efficient,
  author = {Naiyong Ao and Fan Zhang and Di Wu and Douglas S. Stones and Gang Wang and Xiaoguang Liu and Jing Liu and Sheng Lin},
  title = {{Efficient Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units}},
  journal = {Proc. VLDB Endow.},
  year = {2011},
  doi = {10.14778/2002974.2002975},
}
Figure