Range Quantile Queries: Another Virtue of Wavelet Trees

We show how to use a balanced wavelet tree as a data structure that stores a list of numbers and supports efficient range quantile queries . A range quantile query takes a rank and the endpoints of a sublist and returns the number with that rank in that sublist. For example, if the rank is half the sublist's length, then the query returns the sublist's median. We also show how these queries can be used to support space-efficient coloured range reporting and document listing .

• Publication year

  2009

• Venue

  SPIRE

• Publication date

  2009-03-26

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/978-3-642-03784-9_1arXiv 0903.4726
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Towards Optimal Range Medians

  2009cited by this paper
• Range mode and range median queries in constant time and sub-quadratic space

  2009cited by this paper
• Space Efficient Multi-dimensional Range Reporting

  2008cited by this paper
• Range Medians

  2008cited by this paper
• Improved Bounds for Range Mode and Range Median Queries

  2008cited by this paper
• Space-Efficient Algorithms for Document Retrieval

  2007cited by this paper
• Compressed representations of sequences and full-text indexes

  2007cited by this paper
• Rank and select revisited and extended

  2007influential reference
• Compressed full-text indexes

  2007cited by this paper
• Compressed Representations of Sequences and Full-Text Indexes

  2006cited by this paper
• Approximate Range Mode and Range Median Queries

  2005cited by this paper
• High-order entropy-compressed text indexes

  2003influential reference
• Range Mode and Range Median Queries on Lists and Trees

  2003cited by this paper
• Efficient algorithms for document retrieval problems

  2002cited by this paper
• Succinct indexable dictionaries with applications to encoding k-ary trees and multisets

  2002cited by this paper
• Compact pat trees

  1998cited by this paper
• Space-efficient static trees and graphs

  1989cited by this paper
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching

  1988cited by this paper
• Time Bounds for Selection

  1973cited by this paper
• journal homepage: www.elsevier.com/locate/ic The myriad virtues of Wavelet Trees �

  year unknowncited by this paper

• Algorithms for Galois Words: Detection, Factorization, and Rotation

  2024cites this paper
• Memory–Efficient FM-Index Construction for Reference Genomes

  2022cites this paper
• A comprehensive analysis of wavelet tree based indexing schemes in GIR systems

  2021cites this paper
• String Processing and Information Retrieval: 27th International Symposium, SPIRE 2020, Orlando, FL, USA, October 13–15, 2020, Proceedings

  2020cites this paper
• Efficient tree-structured categorical retrieval

  2020cites this paper
• FM-Index Reveals the Reverse Suffix Array

  2020cites this paper
• Tailoring r-index for metagenomics

  2020cites this paper
• Path Query Data Structures in Practice

  2020cites this paper
• Tailoring r-index for Document Listing Towards Metagenomics Applications

  2020cites this paper
• On Approximate Range Mode and Range Selection

  2019cites this paper
• A Guide to Designing Top-k Indexes

  2019cites this paper
• Efficient Semantic Ranking for Top-K Document Retrieval Based on SG-Reversed Index

  2018cites this paper
• Non Hybrid Long Read Consensus Using Local De Bruijn Graph Assembly

  2017cites this paper
• Range selection and predecessor queries in data aware space and time

  2017cites this paper
• Range Queries Using Huffman Wavelet Trees

  2017influential citation
• Quality Assessment of High-throughput DNA Sequencing Data via Range analysis

  2017cites this paper
• Asymptotically Optimal Encodings of Range Data Structures for Selection and Top-k Queries

  2017cites this paper
• Wavelet Trees for Competitive Programming

  2016cites this paper
• Inverse Range Selection Queries

  2016cites this paper
• Statistical and repetition-based compressed data structures

  2015cites this paper
• TB±tree: Index structure for Information Retrieval Systems

  2015cites this paper
• Approximating Document Frequency for Self-Index based Top-k Document Retrieval

  2015cites this paper
• The wavelet matrix: An efficient wavelet tree for large alphabets

  2015cites this paper
• An Efficient Solution for the Generalized Median Problem

  2015cites this paper
• Range Selection Queries in Data Aware Space and Time

  2015influential citation
• General Document Retrieval in Compact Space

  2015cites this paper
• Engineering Rank and Select Queries on Wavelet Trees

  2015cites this paper
• A Practical Algorithm and Data Structures for Range Selection Queries

  2014cites this paper
• Efficient Compressed Wavelet Trees over Large Alphabets

  2014cites this paper
• Space-Efficient Frameworks for Top-k String Retrieval

  2014cites this paper
• Optimal Encodings for Range Top-k, Selection, and Min-Max

  2014cites this paper
• A General Technique for Top-$k$ Geometric Intersection Query Problems

  2014cites this paper
• Optimal Encodings for Range Min-Max and Top-k

  2014cites this paper
• Top-k Color Queries on Tree Paths

  2013cites this paper
• Spaces, Trees, and Colors

  2013cites this paper
• A Lempel-Ziv Compressed Structure for Document Listing

  2013cites this paper
• Space-Efficient Data Structures in the Word-RAM and Bitprobe Models

  2013cites this paper
• Array Range Queries

  2013cites this paper
• Linear-Space Data Structures for Range Frequency Queries on Arrays and Trees

  2013cites this paper
• Improved compressed indexes for full-text document retrieval

  2013influential citation
• ESTRUCTURAS DE DATOS SUCINTAS PARA RECUPERACIÓN DE DOCUMENTOS

  2013cites this paper
• Encodings for Range Selection and Top-k Queries

  2013cites this paper
• String Searching Methods for Bioinformatics ; Merkkijonohaun Menetelmät Bioinformatiikassa

  2013cites this paper
• Scalable succinct indexing for large text collections

  2013influential citation
• The Wavelet Matrix

  2012cites this paper
• Efficient in-memory top-k document retrieval

  2012cites this paper
• Space-Efficient Top-k Document Retrieval

  2012cites this paper
• Wavelet trees: A survey

  2012cites this paper
• Multi-pattern matching with bidirectional indexes

  2012cites this paper
• Linear-Space Data Structures for Range Minority Query in Arrays

  2012cites this paper
• FEMTO: Fast Search of Large Sequence Collections

  2012cites this paper
• Succinct representations of weighted trees supporting path queries

  2012cites this paper
• Adaptive Range Counting and Other Frequency-Based Range Query Problems

  2012cites this paper
• Applications of Compressed Data Structures on Sequences and Structured Data

  2012cites this paper
• Top-k document retrieval in optimal time and linear space

  2012cites this paper
• Wavelet trees for all

  2012cites this paper
• Dual-Sorted Inverted Lists in Practice

  2012cites this paper
• Forbidden Patterns

  2012cites this paper
• Dynamic Range Selection in Linear Space

  2011cites this paper
• RANGE-AGGREGATE QUERY PROBLEMS IN COMPUTATIONAL GEOMETRY

  2011cites this paper
• Path Queries in Weighted Trees

  2011cites this paper
• Linear-Space Data Structures for Range Mode Query in Arrays

  2011cites this paper
• Succinct Gapped Suffix Arrays

  2011cites this paper
• Computing the longest common prefix array based on the Burrows-Wheeler transform

  2011cites this paper
• Range selection and median: tight cell probe lower bounds and adaptive data structures

  2011cites this paper
• Practical Compressed Document Retrieval

  2011cites this paper
• Improved Compressed Indexes for Full-Text Document Retrieval

  2011influential citation
• On Wavelet Tree Construction

  2011cites this paper
• Efficient Top-k Queries for Orthogonal Ranges

  2011cites this paper
• Practical Top-K Document Retrieval in Reduced Space

  2011cites this paper
• Towards an Optimal Space-and-Query-Time Index for Top-k Document Retrieval

  2011cites this paper
• Wavelet Trees: From Theory to Practice

  2011cites this paper
• Space-Efficient Data-Analysis Queries on Grids

  2011cites this paper
• Colored range queries and document retrieval

  2010influential citation
• Top-K color queries for document retrieval

  2010cites this paper
• Dual-Sorted Inverted Lists

  2010cites this paper
• New algorithms on wavelet trees and applications to information retrieval

  2010influential citation
• Top-k Ranked Document Search in General Text Databases

  2010cites this paper
• Compressed Self-indices Supporting Conjunctive Queries on Document Collections

  2010cites this paper
• Data Structures for Range Median Queries

  2009cites this paper
• On efficient implementations of median filters in theory and in practice

  2009cites this paper
• Fully compressed suffix trees

  2008cites this paper