Dual-Sorted Inverted Lists in Practice
Roberto Konow and Gonzalo Navarro
We implement a recent theoretical proposal to represent inverted lists in a
way that docid-sorted and weight-sorted lists are simultaneously
represented in a single wavelet tree data structure. We compare our
implementation with classical representations, where the ordering favors
either bag-of-word queries or Boolean and weighted conjunctive queries,
and demonstrate that the new data structure is faster than the state of the
art for conjunctive queries, while it offers an attractive space/time
tradeoff when both kinds of queries are of interest.