Name
Abstract | ||
|---|---|---|
Inverted index serves as a fundamental data structure for efficient search across various applications such as full-text search engine, document analytics and other information retrieval systems. The storage requirement and query load for these structures have been growing at a rapid rate. Thus, an ideal indexing system should maintain a small index size with a low query processing time. Previous works have mainly focused on using CPUs and GPUs to exploit query parallelism while utilizing state-of-the-art compression schemes to fit the index in memory. However, scaling parallelism to maximally utilize memory bandwidth on these architectures is still challenging. In this work, we present IIU, a novel inverted index processing unit, to optimize the query performance while maintaining a low memory overhead for index storage. To this end, we co-design the indexing scheme and hardware accelerator so that the accelerator can process highly compressed inverted index at a high throughput. In addition, IIU provides flexible interconnects between modules to take advantage of both intra- and inter-query parallelism. Our evaluation using a cycle-level simulator demonstrates that IIU provides an average of 13.8\times× query latency reduction and 5.4\times× throughput improvement across different query types, while reducing the average energy consumption by 18.6\times×, compared to Apache Lucene, a production-grade full-text search framework.
|
Year | DOI | Venue |
|---|---|---|
2020 | 10.1145/3373376.3378521 | ASPLOS '20: Architectural Support for Programming Languages and Operating Systems
Lausanne
Switzerland
March, 2020 |
Keywords | DocType | ISBN |
full-text search,inverted index,domain-specific architecture,accelerator,hardware/software co-design | Conference | 978-1-4503-7102-5 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
7 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jun Heo | 1 | 8 | 2.53 |
| Jaeyeon Won | 2 | 2 | 0.71 |
| Yejin Lee | 3 | 10 | 2.33 |
| Shivam Bharuka | 4 | 0 | 0.34 |
| Jaeyoung Jang | 5 | 7 | 2.18 |
| Tae Jun Ham | 6 | 23 | 4.58 |
| Jae W. Lee | 7 | 22 | 6.26 |