Dual-sorted inverted lists in practice
International Symposium on String Processing and Information Retrieval, 2012•Springer
We implement a recent theoretical proposal to represent inverted lists in memory, 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 …
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 …
Abstract
We implement a recent theoretical proposal to represent inverted lists in memory, 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.
Springer
