Abstract
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the VLDB Endowment |
| Editors | H V Jagadish, Jose Blakeley, Joseph M Hellerstein, Nick Koudas, Wolfgang Lehner, Sunita Sarawagi, Uwe Rohm |
| Place of Publication | USA |
| Publisher | Association for Computing Machinery (ACM) |
| Pages | 470 - 481 |
| Number of pages | 12 |
| Volume | 4 |
| Publication status | Published - 2011 |
| Event | International Conference on Very Large Databases 2011 - The Westin, Seattle, United States of America Duration: 29 Aug 2011 → 3 Sep 2011 Conference number: 37th |
Conference
| Conference | International Conference on Very Large Databases 2011 |
|---|---|
| Abbreviated title | VLDB 2011 |
| Country | United States of America |
| City | Seattle |
| Period | 29/08/11 → 3/09/11 |
Cite this
}
Efficient parallel lists intersection and index compression algorithms using graphics processing units. / Ao, Naiyong; Zhang, Fan; Wu, Di; Stones, Douglas; Wang, Gang; Liu, Xiaoguang; Liu, Jing; Lin, Sheng.
Proceedings of the VLDB Endowment. ed. / H V Jagadish; Jose Blakeley; Joseph M Hellerstein; Nick Koudas; Wolfgang Lehner; Sunita Sarawagi; Uwe Rohm. Vol. 4 USA : Association for Computing Machinery (ACM), 2011. p. 470 - 481.Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review
TY - GEN
T1 - Efficient parallel lists intersection and index compression algorithms using graphics processing units
AU - Ao, Naiyong
AU - Zhang, Fan
AU - Wu, Di
AU - Stones, Douglas
AU - Wang, Gang
AU - Liu, Xiaoguang
AU - Liu, Jing
AU - Lin, Sheng
PY - 2011
Y1 - 2011
N2 - 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. 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 and that a succiently 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 signifcant improvements in the query processing throughput on several datasets.
AB - 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. 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 and that a succiently 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 signifcant improvements in the query processing throughput on several datasets.
UR - http://www.vldb.org/pvldb/vol4/p470-ao.pdf
M3 - Conference Paper
VL - 4
SP - 470
EP - 481
BT - Proceedings of the VLDB Endowment
A2 - Jagadish, H V
A2 - Blakeley, Jose
A2 - Hellerstein, Joseph M
A2 - Koudas, Nick
A2 - Lehner, Wolfgang
A2 - Sarawagi, Sunita
A2 - Rohm, Uwe
PB - Association for Computing Machinery (ACM)
CY - USA
ER -