Source-linked AI summary
New Algorithms on Wavelet Trees and Applications to Information Retrieval
Travis Gagie, Gonzalo Navarro, Simon J. Puglisi
TL;DR
Wavelet trees have further capabilities to exploit, and this paper develops algorithms for range quantile, range next value, and range intersection. It generalizes document retrieval to temporal and hierarchical collections and applies wavelet-tree variants to inverted lists, reporting improved space or time bounds and added IR operations without extra space for basic support.
Problem
Wavelet trees are widely used, but the paper argues that their capabilities for fundamental range queries and information retrieval remain under-explored.
Source: §1 · pp. 1–2Method
The paper develops wavelet-tree algorithms for fundamental range queries and generalizes them to temporal and hierarchical document retrieval and inverted lists.
Source: §1 · pp. 2–3, §2 · p. 5Results
Range intersections match the adaptive complexity for sorted ranges, while quantile and next-value queries match or approach best known times using less space; IR operations add no space beyond basic support.
Source: §7 · p. 21Takeaways & Limitations
Document-retrieval and inverted-index operations can be supported without further increasing the space needed for their basic operations.
Source: §7 · p. 21Implementation within an IR framework and evaluation of practical performance remain future work.
Source: §7 · p. 21
Abstract
from arXiv · showhide
Wavelet trees are widely used in the representation of sequences, permutations, text collections, binary relations, discrete points, and other succinct data structures. We show, however, that this still falls short of exploiting all of the virtues of this versatile data structure. In particular we show how to use wavelet trees to solve fundamental algorithmic problems such as {\em range quantile} queries, {\em range next value} queries, and {\em range intersection} queries. We explore several applications of these queries in Information Retrieval, in particular {\em document retrieval} in hierarchical and temporal documents, and in the representation of {\em inverted lists}.
1 Introduction
The introduction presents three wavelet-tree queries—range quantile, range next value, and range intersection—and gives their costs. It then applies these capabilities to generalized document retrieval and inverted-list functionality.
1 Introduction
- Wavelet trees support range quantile and range next value in O(log σ), plus range intersection in O(α log σ α) under the paper’s adaptive analysis.The intersection bound is in terms of the problem’s alternation complexity α.Source: §1 · p. 2
- The generalized information-retrieval setting treats documents and queries as strings and retrieves matching substrings, extending beyond natural-language collections.Source: §1 · p. 2
- On a suffix-array interval for a query, document listing and intersection become distinct-value and value-intersection queries on document array D; frequency uses two rank_d queries.Source: §1 · p. 3
- The paper extends document retrieval to temporal collections, where document numbers follow version order, and hierarchical collections, where document ranges correspond to subtrees.For hierarchies, it also handles queries that mark retrievable nodes at query time.Source: §1 · p. 3
- Wavelet-tree representations of inverted lists support the basic functions of ranked and full-text retrieval within essentially the space of one, plus enhanced operations.The enhanced operations include on-the-fly stemming, document restrictions, and most list-intersection algorithms.Source: §1 · p. 3
2 Wavelet Trees
A wavelet tree represents a sequence using binary partitions of its ordered symbols and supports access, rank, and select. The section develops range counting and reporting on this structure and analyzes their costs.
2 Wavelet Trees
- A balanced wavelet tree partitions an ordered alphabet in a binary tree, with each internal node storing a bitmap that routes sequence elements to its children.The tree has at most n log σ + O(n) bits of space and can be constructed in O(n log u) time.Source: §2 · pp. 3–4
- Concatenating bitmaps by tree depth can simulate explicit nodes with one pointer per level, while the bitmap representation supports constant-time binary rank and select.The bitmap-based representation adds O(n) bits of space and can be constructed in O(n log u) time.Source: §2 · p. 4
- Storing the distinct alphabet values alongside the tree keeps total space within n log σ + O(n) bits.When σ > n, the distinct values can be represented with a compressed bitmap and retrieved using select.Source: §2 · p. 4
- Access, rank, and select follow paths through the tree, remapping positions with bitmap rank or select operations at each node.Each operation takes O(log u) time.Source: §2 · pp. 4–5
- Range count and range report act as multi-symbol rank and access operations, respectively, and are analyzed using the tree nodes covering a value interval.Range count takes O(log u) time; range report takes O(ye − ys + log u) time.Source: §2 · pp. 5–6
3 Information Retrieval Concepts
The section introduces suffix and document arrays for general-string retrieval and describes ranked and full-text inverted indexes. It frames the ordering and space tradeoff that the proposed wavelet-tree structure addresses.
3.1 Suffix and Document Arrays
- Suffix-array search finds the lexicographic interval of suffixes beginning with a query in O(|q| log n) time, while compressed self-indexes can find it in O(|q| log σ) time.The interval contains the query occurrences in the collection.Source: §3.1 · p. 7
- Listing distinct documents by scanning query occurrences can take Ω(occ) time, even when only docc distinct documents contain the query.Here occ is the number of occurrences and docc the number of matching documents.Source: §3.1 · p. 7
- Muthukrishnan's document-listing method runs in O(docc) after interval search, but uses O(n log n) bits and does not return documents in ascending order.A wavelet-tree approach is described as retaining O(docc log m) time without an RMQ structure while returning documents in increasing order.Source: §3.1 · p. 7
3.2 Inverted Indexes
- An inverted index stores a list of documents for each vocabulary word, allowing word queries to use precomputed lists.The section distinguishes ranked retrieval from full-text retrieval.Source: §3.2 · p. 8
- Ranked retrieval orders list entries by term weight and may inspect only prefixes, trading query time against retrieval quality.Weights can combine term frequency and inverse document frequency.Source: §3.2 · p. 8
- Full-text retrieval uses sorted document lists for single-word, disjunctive, and conjunctive queries, with list intersection central to conjunctive retrieval.Intersection algorithms can exploit differences in list lengths, while compression commonly encodes gaps between increasing document identifiers.Source: §3.2 · p. 8
- A wavelet-tree structure supports retrieving a term's list by decreasing weight or increasing identifier within the space of one compressed inverted index.It also supports operations for list intersection and additional capabilities such as stemming and structured document retrieval without extra space cost.Source: §3.2 · p. 9
4 New Algorithms
The section presents wavelet-tree algorithms for range quantile, range next value, and range intersection queries. It establishes logarithmic-time bounds for the first two and an adaptive intersection approach, then describes a thresholded extension.
4.1 Range Quantile
- Within n log σ + O(n) bits, range quantile queries take O(log u) time and return the selected value’s frequency.Here u is the number of distinct values in the sequence.Source: §4.1 · p. 10
4.2 Range Next Value
- Within n log σ + O(n) bits, range next value queries take O(log u) time and return the first occurrence’s position.The same wavelet tree can support the other algorithms, requiring only O(n) extra bits beyond the sequence.Source: §4.2 · p. 11
4.3 Range Intersection
- For k ranges, the intersection algorithm recursively maps each range through the wavelet tree, pruning a branch when any mapped range is empty.A reached leaf gives a common symbol and its frequency in each range.Source: §4.1 · p. 10, §4.3 · p. 12
- The intersection algorithm extends to returning symbols appearing in at least t of k ranges, and for sorted, repetition-free ranges its complexity is close to the lower bound.The thresholded variant abandons a range only after more than k − t ranges have become empty.Source: §4.3 · p. 13
- An alternative intersection procedure using repeated range next value queries takes O(α log u) time, where α measures alternations in the instance.The paper also describes a fingered-search improvement for this procedure.Source: §4.3 · pp. 12–13
5 Document Listing and Intersections
The section maps document retrieval onto operations over a document array, using the wavelet-tree range algorithms to list documents, intersect query results, and restrict retrieval to temporal, hierarchical, or tagged units.
5 Document Listing and Intersections
- After suffix-array search maps a query to a range, a document array turns document listing into reporting distinct values, while document intersection becomes range intersection.The reporting procedure can return each document’s term frequency, and the documents are delivered in increasing identifier order.Source: §5 · p. 13
- For multiple queries, document intersection maps their suffix-array ranges to document-array ranges and applies range intersection to find documents containing all queries.The method also handles documents containing at least t of k query terms, including disjunctive retrieval when t = 1.Source: §5 · p. 14
5.1 Temporal and Hierarchical Documents
- Restricting document identifiers to an interval supports temporal queries or a subtree of a document hierarchy; range counting also computes term frequency within that interval in O(log m) time.The interval is passed as a range restriction to the reporting and intersection procedures.Source: §5.1 · p. 14
5.2 Restricting to Retrievable Units
- For a specified XML tag, expand(t, i) maps an occurrence to the leaf range of its lowest ancestor with that tag, defining the corresponding retrievable unit.The expansion operation takes O(log τ) time, dominated by operations on the tag sequence.Source: §5.2 · p. 15
- Document listing restricted to tagged retrievable units builds on range next value queries, while intersection recursion avoids splitting a retrievable unit.The intersection procedure restricts document ranges as it descends and reports a unit when its leaf interval belongs to both query ranges.Source: §5.2 · pp. 15–16
6 Inverted Lists
The section concatenates inverted lists into one wavelet-tree sequence and uses it to support full-text and ranked retrieval operations. The representation combines functionality associated with document-ordered and weight-ordered lists, with reported space bounded by n log(mν) + O(n) bits.
6 Inverted Lists
- Concatenating the term lists into L and representing document identifiers with a wavelet tree yields a structure using at most n log(mν) + O(n) bits, including its list-start and term-frequency encodings.Term frequencies are stored separately in differential and run-length compressed form.Source: §6 · p. 17
- The wavelet-tree representation offers the combined functionality of inverted indexes sorted by document identifier and by term frequency, while its space does not exceed either index’s stated bound.The section contrasts the representation with differential encoding for document-ordered lists and discusses the bounds for weight-ordered lists.Source: §6 · p. 17
6.1 Full-Text Retrieval
- For full-text retrieval, direct access to Ft[k] uses a range quantile query, and repeated extraction can return a segment in order.The section also supports first-document-at-least-d searches and list intersections using range next value and range intersection queries.Source: Direct retrieval · p. 18, Intersection algorithms · p. 18
- Full-text operations extend to intersections of multiple terms and documents appearing in at least a specified number of terms; restricting document values supports temporal and hierarchical retrieval.The range restriction is applied to accesses in the lists, and the XML retrievable-unit algorithms also apply to inverted lists.Source: Intersection algorithms · p. 18, Other operations of interest · p. 19
6.2 Ranked Retrieval
- For ranked retrieval, extracting high-frequency documents in document order can support merging with a candidate set in Persin’s algorithm.The method selects the prefix of a term’s weight-ordered list whose frequencies meet the current threshold, then retrieves those documents in identifier order.Source: Direct access and Persin’s algorithm · p. 20
- Summing frequencies across stemmed terms can use a leaf-aligned encoding, but that option raises the frequency storage to n log N + O(n) bits.The current representation can retrieve stemmed-term documents in document order.Source: Direct access and Persin’s algorithm · p. 20
7 Conclusions
The paper extends wavelet trees with algorithms for range intersection, range quantile, and range next-value queries, with improved time-space trade-offs. It also applies these algorithms to information retrieval and identifies practical evaluation as future work.
7 Conclusions
- Range intersections achieve adaptive complexity matching sorted ranges, while range quantile and next-value queries match or approach best-known time complexities.Source: §7 · p. 21
- Range quantile and next-value solutions use sequence space plus O(n) extra bits, versus O(n log n) extra bits in previous solutions.Source: §7 · p. 21
- With compressed bitmaps, the algorithms retain their time complexities and represent S in nH0(S)+O(n + σ) space, including the sequence.Source: §7 · p. 21
- Applications to general-string document retrieval and inverted indexes support additional powerful operations without increasing the space needed for basic ones.Source: §7 · p. 21
- Practical evaluation remains future work; preliminary experiments on an earlier version improved general-string document retrieval, while the authors expect the revised version to widen the gap.Source: §7 · p. 21