Faster and smaller inverted indices with treaps
Proceedings of the 36th international ACM SIGIR conference on Research and development in information retrieval (SIGIR '13)
By Alejandro López-Ortíz, Charles L.A. Clarke, Gonzalo Navarro, Roberto Konow
Issue Date:July 2013
We introduce a new representation of the inverted index that performs faster ranked unions and intersections while using less space. Our index is based on the treap data structure, which allows us to intersect/merge the document identifiers while simultane...