Linear-Space Data Structures for Range Minority Query in Arrays

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

doi:10.1007/s00453-014-9881-9

Linear-Space Data Structures for Range Minority Query in Arrays

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

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	901-913
Number of pages	13
Journal	Algorithmica
Volume	72
Issue number	4
DOIs	https://doi.org/10.1007/s00453-014-9881-9
State	Published - Aug 19 2015
Externally published	Yes

Keywords

Data structures
Least frequent element
Minority
Range queries

ASJC Scopus subject areas

General Computer Science
Computer Science Applications
Applied Mathematics

Online availability

10.1007/s00453-014-9881-9

Library availability

Discover UIUC Full Text

Cite this

@article{9c47aded80114cc2aaac7e19420058d1,

title = "Linear-Space Data Structures for Range Minority Query in Arrays",

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.",

keywords = "Data structures, Least frequent element, Minority, Range queries",

author = "Chan, {Timothy M.} and Stephane Durocher and Matthew Skala and Wilkinson, {Bryan T.}",

note = "Publisher Copyright: {\textcopyright} 2014, Springer Science+Business Media New York.",

year = "2015",

month = aug,

day = "19",

doi = "10.1007/s00453-014-9881-9",

language = "English (US)",

volume = "72",

pages = "901--913",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "4",

}

TY - JOUR

T1 - Linear-Space Data Structures for Range Minority Query in Arrays

AU - Chan, Timothy M.

AU - Durocher, Stephane

AU - Skala, Matthew

AU - Wilkinson, Bryan T.

PY - 2015/8/19

Y1 - 2015/8/19

N2 - 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.

AB - 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.

KW - Data structures

KW - Least frequent element

KW - Minority

KW - Range queries

UR - http://www.scopus.com/inward/record.url?scp=84931575574&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84931575574&partnerID=8YFLogxK

U2 - 10.1007/s00453-014-9881-9

DO - 10.1007/s00453-014-9881-9

M3 - Article

AN - SCOPUS:84931575574

SN - 0178-4617

VL - 72

SP - 901

EP - 913

JO - Algorithmica

JF - Algorithmica

IS - 4

ER -

Linear-Space Data Structures for Range Minority Query in Arrays

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this