Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Efficient tree-structured categorical retrieval

Abstract : We study a document retrieval problem in the new framework where $D$ text documents are organized in a {\em category tree} with a pre-defined number $h$ of categories. This situation occurs e.g. with taxomonic trees in biology or subject classification systems for scientific literature. Given a string pattern $p$ and a category (level in the category tree), we wish to efficiently retrieve the $t$ \emph{categorical units} containing this pattern and belonging to the category. We propose several efficient solutions for this problem. One of them uses $n(\log\sigma(1+o(1))+\log D+O(h)) + O(\Delta)$ bits of space and $O(|p|+t)$ query time, where $n$ is the total length of the documents, $\sigma$ the size of the alphabet used in the documents and $\Delta$ is the total number of nodes in the category tree. Another solution uses $n(\log\sigma(1+o(1))+O(\log D))+O(\Delta)+O(D\log n)$ bits of space and $O(|p|+t\log D)$ query time. We finally propose other solutions which are more space-efficient at the expense of a slight increase in query time.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas
Contributor : Gregory Kucherov <>
Submitted on : Wednesday, December 9, 2020 - 7:03:11 PM
Last modification on : Wednesday, December 9, 2020 - 7:03:11 PM

Links full text


  • HAL Id : hal-03049384, version 1
  • ARXIV : 2006.01825



Djamal Belazzougui, Gregory Kucherov. Efficient tree-structured categorical retrieval. 2020. ⟨hal-03049384⟩



Record views