Linear-space data structures for range minority query in arrays

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

doi:10.1007/978-3-642-31155-0_26

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 proceeding › Conference 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 language	English (US)
Title of host publication	Algorithm Theory, SWAT 2012 - 13th Scandinavian Symposium and Workshops, Proceedings
Pages	295-306
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-31155-0_26
State	Published - 2012
Externally published	Yes
Event	13th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2012 - Helsinki, Finland Duration: Jul 4 2012 → Jul 6 2012

Publication series

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

Other

Other	13th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2012
Country/Territory	Finland
City	Helsinki
Period	7/4/12 → 7/6/12

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Online availability

10.1007/978-3-642-31155-0_26

Library availability

Discover UIUC Full Text

Cite this

Chan, T. M., Durocher, S., Skala, M., & Wilkinson, B. T. (2012). Linear-space data structures for range minority query in arrays. In Algorithm Theory, SWAT 2012 - 13th Scandinavian Symposium and Workshops, Proceedings (pp. 295-306). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7357 LNCS). https://doi.org/10.1007/978-3-642-31155-0_26

Linear-space data structures for range minority query in arrays. / Chan, Timothy M.; Durocher, Stephane; Skala, Matthew et al.
Algorithm Theory, SWAT 2012 - 13th Scandinavian Symposium and Workshops, Proceedings. 2012. p. 295-306 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7357 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Chan, TM, Durocher, S, Skala, M & Wilkinson, BT 2012, Linear-space data structures for range minority query in arrays. in Algorithm Theory, SWAT 2012 - 13th Scandinavian Symposium and Workshops, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7357 LNCS, pp. 295-306, 13th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2012, Helsinki, Finland, 7/4/12. https://doi.org/10.1007/978-3-642-31155-0_26

Chan TM, Durocher S, Skala M, Wilkinson BT. Linear-space data structures for range minority query in arrays. In Algorithm Theory, SWAT 2012 - 13th Scandinavian Symposium and Workshops, Proceedings. 2012. p. 295-306. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-31155-0_26

@inproceedings{f954947485b4439290b89889fe61d9ad,

title = "Linear-space data structures for range minority query in arrays",

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

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

note = "Funding Information: Work supported in part by the Natural Sciences and Engineering Research Council of Canada (NSERC).; 13th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2012 ; Conference date: 04-07-2012 Through 06-07-2012",

year = "2012",

doi = "10.1007/978-3-642-31155-0_26",

language = "English (US)",

isbn = "9783642311543",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "295--306",

booktitle = "Algorithm Theory, SWAT 2012 - 13th Scandinavian Symposium and Workshops, Proceedings",

}

TY - GEN

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.

N1 - Funding Information: Work supported in part by the Natural Sciences and Engineering Research Council of Canada (NSERC).

PY - 2012

Y1 - 2012

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

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

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

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

U2 - 10.1007/978-3-642-31155-0_26

DO - 10.1007/978-3-642-31155-0_26

M3 - Conference contribution

AN - SCOPUS:84863109306

SN - 9783642311543

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 295

EP - 306

BT - Algorithm Theory, SWAT 2012 - 13th Scandinavian Symposium and Workshops, Proceedings

T2 - 13th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2012

Y2 - 4 July 2012 through 6 July 2012

ER -

Linear-space data structures for range minority query in arrays

Abstract

Publication series

Other

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this