Publications

Stats

View publication

Title Ranked Document Retrieval in (Almost) No Space
Authors Nieves Brisaboa, Ana Cerdeira, Gonzalo Navarro, Óscar Pedreira Fernández
Publication date 2012
Abstract Ranked document retrieval is a fundamental task in search engines. Such
queries are solved with inverted indices that require
additional 45%-80% of the compressed text space, and take tens to
hundreds of microseconds per query.
In this paper we show how ranked document retrieval queries can be
solved within tens of milliseconds using essentially no extra space
over an in-memory compressed representation of the document collection.
More precisely, we enhance wavelet trees on bytecodes (WTBCs), a
data structure that rearranges the bytes of the
compressed collection, so that they support ranked conjunctive and disjunctive
queries, using just 6%-18% of the compressed text space.
Downloaded 12 times
Pages 155-160
Conference name International Symposium on String Processing and Information Retrieval
Publisher Springer-Verlag (Berlin/Heidelberg, Germany)
PDF View PDF
Reference URL View reference page