{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:15:17Z","timestamp":1779174917480,"version":"3.51.4"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2011,5]]},"abstract":"<jats:p>Major web search engines answer thousands of queries per second requesting information about billions of web pages. The data sizes and query loads are growing at an exponential rate. To manage the heavy workload, we consider techniques for utilizing a Graphics Processing Unit (GPU). We investigate new approaches to improve two important operations of search engines -- lists intersection and index compression.<\/jats:p>\n          <jats:p>For lists intersection, we develop techniques for efficient implementation of the binary search algorithm for parallel computation. We inspect some representative real-world datasets and find that a sufficiently long inverted list has an overall linear rate of increase. Based on this observation, we propose Linear Regression and Hash Segmentation techniques for contracting the search range. For index compression, the traditional d-gap based compression schemata are not well-suited for parallel computation, so we propose a Linear Regression Compression schema which has an inherent parallel structure. We further discuss how to efficiently intersect the compressed lists on a GPU. Our experimental results show significant improvements in the query processing throughput on several datasets.<\/jats:p>","DOI":"10.14778\/2002974.2002975","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"470-481","source":"Crossref","is-referenced-by-count":72,"title":["Efficient parallel lists intersection and index compression algorithms using graphics processing units"],"prefix":"10.14778","volume":"4","author":[{"given":"Naiyong","family":"Ao","sequence":"first","affiliation":[{"name":"Nankai University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fan","family":"Zhang","sequence":"additional","affiliation":[{"name":"Nankai University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Di","family":"Wu","sequence":"additional","affiliation":[{"name":"Nankai University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Douglas S.","family":"Stones","sequence":"additional","affiliation":[{"name":"Monash University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gang","family":"Wang","sequence":"additional","affiliation":[{"name":"Nankai University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaoguang","family":"Liu","sequence":"additional","affiliation":[{"name":"Nankai University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jing","family":"Liu","sequence":"additional","affiliation":[{"name":"Nankai University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sheng","family":"Lin","sequence":"additional","affiliation":[{"name":"Nankai University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:INRT.0000048490.99518.5c"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27801-6_30"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575832_2"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/11764298_13"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1572769.1572795"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/882455.875020"},{"key":"e_1_2_1_7_1","volume-title":"MIT Press","author":"Cormen T. H.","year":"1990"},{"key":"e_1_2_1_8_1","first-page":"743","volume-title":"Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Demaine E. D.","year":"2000"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/646679.702301"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526766"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/146370.146381"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/88.242438"},{"key":"e_1_2_1_13_1","unstructured":"S. H\u00e9man. Super-scalar database compression between RAM and CPU-cache. Master's thesis Centrum voor Wiskunde en Informatica Amsterdam 2005.  S. H\u00e9man. Super-scalar database compression between RAM and CPU-cache. Master's thesis Centrum voor Wiskunde en Informatica Amsterdam 2005."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1394399"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359557"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/78973.78977"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/564376.564416"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1280094.1280110"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0306-4573(02)00020-1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/967900.968024"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1571941.1572104"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687722"},{"key":"e_1_2_1_23_1","volume-title":"Morgan Kaufmann","author":"Witten I. H.","year":"1999"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2010.5470720"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526764"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132956.1132959"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.150"},{"key":"e_1_2_1_28_1","volume-title":"The TREC 2006 terabyte track. In Proc. 15th Text Retrieval Conference (TREC 2006)","author":"B\u00fcttcher S.","year":"2006"},{"key":"e_1_2_1_29_1","volume-title":"Agricultural and Medical Research. Oliver and Boyd","author":"Fisher R.","year":"1963"},{"key":"e_1_2_1_30_1","unstructured":"NVIDIA Corporation. NVIDIA CUDA Programming Guide v3. 2010.  NVIDIA Corporation. NVIDIA CUDA Programming Guide v3. 2010."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"e_1_2_1_32_1","unstructured":"E. M. Voorhees. Overview of trec 2004. In In NIST Special Publication 500-261: The Thirteenth Text Retrieval Conference Proceedings (TREC 2004) pages 1--12 2004.  E. M. Voorhees. Overview of trec 2004. In In NIST Special Publication 500-261: The Thirteenth Text Retrieval Conference Proceedings (TREC 2004) pages 1--12 2004."},{"key":"e_1_2_1_33_1","first-page":"1","volume-title":"Overview of TREC 2002. In Proc. 11th Text Retrieval Conference (TREC 2002","author":"Voorhees E. M.","year":"2003"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2002974.2002975","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:45:14Z","timestamp":1672224314000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2002974.2002975"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5]]},"references-count":33,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2011,5]]}},"alternative-id":["10.14778\/2002974.2002975"],"URL":"https:\/\/doi.org\/10.14778\/2002974.2002975","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2011,5]]}}}