Linear-space data structures for range minority query in arrays

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider range queries in arrays that search for low-frequency elements: least frequent elements and α-minorities. 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(n 3/2) preprocessing time, and 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)
Title of host publicationAlgorithm Theory, SWAT 2012 - 13th Scandinavian Symposium and Workshops, Proceedings
Pages295-306
Number of pages12
DOIs
StatePublished - 2012
Externally publishedYes
Event13th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2012 - Helsinki, Finland
Duration: Jul 4 2012Jul 6 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7357 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other13th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2012
Country/TerritoryFinland
CityHelsinki
Period7/4/127/6/12

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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