Linear-Space Data Structures for Range Minority Query in Arrays

Timothy M. Chan, Stephane Durocher, Matthew Skala, Bryan T. Wilkinson

Research output: Contribution to journalArticlepeer-review

Abstract

We consider range queries that search for low-frequency elements (least frequent elements and α-minorities) in arrays. An α-minority of a query range has multiplicity no greater than an α fraction of the elements in the range. Our data structure for the least frequent element range query problem requires O(n) space, O(n3/2) preprocessing time, and O(n) query time. A reduction from boolean matrix multiplication to this problem shows the hardness of simultaneous improvements in both preprocessing time and query time. Our data structure for the α-minority range query problem requires O(n) space, supports queries in O(1/α) time, and allows α to be specified at query time.

Original languageEnglish (US)
Pages (from-to)901-913
Number of pages13
JournalAlgorithmica
Volume72
Issue number4
DOIs
StatePublished - Aug 19 2015
Externally publishedYes

Keywords

  • Data structures
  • Least frequent element
  • Minority
  • Range queries

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Linear-Space Data Structures for Range Minority Query in Arrays'. Together they form a unique fingerprint.

Cite this