Efficient compressed indexing for approximate top-k string retrieval.

Héctor Ricardo Ferrada Escobar, Gonzalo Navarro

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review


Given a collection of strings (called documents), the {\em top-k document retrieval} problem is that of, given a string pattern p, finding the k documents where p appears most often. This is a basic task in most information retrieval scenarios. The best current implementations require 20-30 bits per character (bpc) and k to 4k microseconds per query, or 12-24 bpc and 1-10 milliseconds per query. We introduce a Lempel-Ziv compressed data structure that occupies 5-10 bpc to answer queries in around k microseconds. The drawback is that the answer is approximate, but we show that its quality improves asymptotically with the size of the collection, being over 85% already for patterns of length 4-6 on rather small collections, and improving for larger ones.
Original languageEnglish
Title of host publicationUnknown host publication
Publication date2014
Publication statusPublished - 2014
MoE publication typeA4 Article in conference proceedings
EventSymposium on String Processing and Information Retrieval - Ouro Preto, Brazil
Duration: 1 Jan 1800 → …
Conference number: 21

Cite this