Using graphics processors for high performance IR query processing

ABSTRACT

Web search engines are facing formidable performance challenges due to data sizes and query loads. The major engines have to process tens of thousands of queries per second over tens of billions of documents. To deal with this heavy workload, such engines employ massively parallel systems consisting of thousands of machines. The significant cost of operating these systems has motivated a lot of recent research into more efficient query processing mechanisms. We investigate a new way to build such high performance IR systems using graphical processing units (GPUs). GPUs were originally designed to accelerate computer graphics applications through massive on-chip parallelism. Recently a number of researchers have studied how to use GPUs for other problem domains such as databases and scientific computing. Our contribution here is to design a basic system architecture for GPU-based high-performance IR, to develop suitable algorithms for subtasks such as inverted list compression, list intersection, and top-$k$ scoring, and to show how to achieve highly efficient query processing on GPU-based systems. Our experimental results for a prototype GPU-based system on $25.2$ million web pages indicate that significant gains in query processing performance can be obtained.

REFERENCES

• 1: Nvidia CUDA programming guide, June 2007. http://www.nvidia.com/object/cuda develop.html.
• 2: Ricardo Baeza-Yates , Aristides Gionis , Flavio Junqueira , Vanessa Murdock , Vassilis Plachouras , Fabrizio Silvestri, The impact of caching on search engines, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277775]
• 3: G. Blelloch. Prefix sums and their applications. In J. H. Reif, editor, Synthesis of Parallel Algorithms, pages 35--60, 1993.
• 4: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 5: Andrei Z. Broder , David Carmel , Michael Herscovici , Aya Soffer , Jason Zien, Efficient query evaluation using a two-level retrieval process, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956944]
• 6: Alexandros Ntoulas , Junghoo Cho, Pruning policies for two-tiered inverted index with correctness guarantee, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277776]
• 7: Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
• 8: Naga Govindaraju , Jim Gray , Ritesh Kumar , Dinesh Manocha, GPUTeraSort: high performance graphics co-processor sorting for large database management, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142511]
• 9: Naga K. Govindaraju , Brandon Lloyd , Wei Wang , Ming Lin , Dinesh Manocha, Fast computation of database operations using graphics processors, ACM SIGGRAPH 2005 Courses, July 31-August 04, 2005, Los Angeles, California [doi>10.1145/1198555.1198787]
• 10: M. Harris. Parallel prefix sum (scan) with CUDA, April 2007. http://developer.download.nvidia.com/compute/cuda/sdk/website/projects/scan/doc/scan.pdf.
• 11: Bingsheng He , Wenbin Fang , Qiong Luo , Naga K. Govindaraju , Tuyong Wang, Mars: a MapReduce framework on graphics processors, Proceedings of the 17th international conference on Parallel architectures and compilation techniques, October 25-29, 2008, Toronto, Ontario, Canada [doi>10.1145/1454115.1454152]
• 12: Bingsheng He , Ke Yang , Rui Fang , Mian Lu , Naga Govindaraju , Qiong Luo , Pedro Sander, Relational joins on graphics processors, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376670]
• 13: S. Heman. Super-scalar database compression between RAM and CPU-cache. MS Thesis, Centrum voor Wiskunde en Informatica, Amsterdam, Netherlands, July 2005.
• 14: S. Heman, M. Zukowski, A. de Vries, and P. Boncz. MonetDBX100 at the 2006 TREC Terabyte Track. In Proc. of the 15th Text REtrieval Conference (TREC), 2006.
• 15: Marcin Kaszkiel , Justin Zobel , Ron Sacks-Davis, Efficient passage ranking for document databases, ACM Transactions on Information Systems (TOIS), v.17 n.4, p.406-439, Oct. 1999 [doi>10.1145/326440.326445]
• 16: E. Lawler, J. Lenstra, A. Kan, and D. Shmoys. Sequencing and scheduling: algorithms and complexity. Elsevier, 1993.
• 17: D. Lichterman. Course project for ECE498, Univ. of Illinois at Urbana-Champaign. http://courses.ece.uiuc.edu/ece498/al1/Archive/Spring2007/HallOfFame.html.
• 18: Alistair Moffat , Justin Zobel, Self-indexing inverted files for fast text retrieval, ACM Transactions on Information Systems (TOIS), v.14 n.4, p.349-379, Oct. 1996 [doi>10.1145/237496.237497]
• 19: J. Owens, D. Luebke, N. Govindaraju, M. Harris, J. Kruger, A. Lefohn, and T. Purcell. A survey of general-purpose computation on graphics hardware. In Eurographics, 2005.
• 20: R. D. Blumofe , C. E. Leiserson, Scheduling multithreaded computations by work stealing, Proceedings of the 35th Annual Symposium on Foundations of Computer Science, p.356-368, November 20-22, 1994 [doi>10.1109/SFCS.1994.365680]
• 21: Knut Magne Risvik , Yngve Aasheim , Mathias Lidal, Multi-Tier Architecture for Web Search Engines, Proceedings of the First Conference on Latin American Web Congress, p.132, November 10-12, 2003
• 22: S. Robertson, S. Walker, S. Jones, M. Hancock-Beaulieu, and M. Gatford. Okapi at trec-3. In Proc. of the 3rd Text Retrieval Conference (TREC), Nov 1994.
• 23: Jiangong Zhang , Xiaohui Long , Torsten Suel, Performance of compressed inverted list caching in search engines, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367550]
• 24: Justin Zobel , Alistair Moffat, Inverted files for text search engines, ACM Computing Surveys (CSUR), v.38 n.2, p.6-es, 2006 [doi>10.1145/1132956.1132959]
• 25: Marcin Zukowski , Sandor Heman , Niels Nes , Peter Boncz, Super-Scalar RAM-CPU Cache Compression, Proceedings of the 22nd International Conference on Data Engineering, p.59, April 03-07, 2006 [doi>10.1109/ICDE.2006.150]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Performance

Keywords:
GPU, index compression, ir query processing, search engines