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.

@inproceedings{paperbot5435,
  title = {IIU},
  author = {Jun Heo and Jaeyeon Won and Yejin Lee and Shivam Bharuka and Jaeyoung Jang and Tae Jun Ham and Jae W. Lee},
  booktitle = {ASPLOS},
  year = {2020},
  doi = {10.1145/3373376.3378521}
}