More Web Proxy on the site http://driver.im/

research-article

Range selection and median: tight cell probe lower bounds and adaptive data structures

Authors:

Allan Grønlund Jørgensen,

Kasper Green LarsenAuthors Info & Claims

SODA '11: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms

Pages 805 - 813

Published: 23 January 2011 Publication History

Abstract

Range selection is the problem of preprocessing an input array A of n unique integers, such that given a query (i, j, k), one can report the k'th smallest integer in the subarray A[i], A[i + 1],..., A[j]. In this paper we consider static data structures in the word-RAM for range selection and several natural special cases thereof.

The first special case is known as range median, which arises when k is fixed to ⌊(j -- i + 1)/2⌋. The second case, denoted prefix selection, arises when i is fixed to 0. Finally, we also consider the bounded rank prefix selection problem and the fixed rank range selection problem. In the former, data structures must support prefix selection queries under the assumption that k ≤ κ for some value κ ≤ n given at construction time, while in the latter, data structures must support range selection queries where k is fixed beforehand for all queries. We prove cell probe lower bounds for range selection, prefix selection and range median, stating that any data structure that uses S words of space needs Ω(log n/log(Sw/n)) time to answer a query. In particular, any data structure that uses nlog^O(1) n space needs Ω(log n/log log n) time to answer a query, and any data structure that supports queries in constant time, needs n^1+Ω(1) space. For data structures that uses n log^O(1) n space this matches the best known upper bound.

Additionally, we present a linear space data structure that supports range selection queries in O(log k/log log n + log log n) time. Finally, we prove that any data structure that uses S space, needs Ω(log κ/log(Sw/n)) time to answer a bounded rank prefix selection query and Ω(log k/log(Sw/n)) time to answer a fixed rank range selection query. This shows that our data structure is optimal except for small values of k.

References

[1]

P. Afshani, L. Arge, and K. D. Larsen. Orthogonal range reporting in three and higher dimensions. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, pages 149--158, 2009.

Digital Library

[2]

M. J. Atallah and H. Yuan. Data structures for range minimum queries in multidimensional arrays. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 150--160, 2010.

Digital Library

[3]

M. J. Atallah and H. Yuan. Optimal succinctness for range minimum queries. In Proceedings of the 9th Latin American Theoretical Informatics Symposium, pages 150--160, 2010.

Digital Library

[4]

P. Bose, E. Kranakis, P. Morin, and Y. Tang. Approximate range mode and range median queries. In Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science, pages 377--388, 2005.

Digital Library

[5]

G. S. Brodal and A. G. Jørgensen. Data structures for range median queries. In Proceedings of the 20th International Symposium on Algorithms and Computation, pages 822--831, 2009.

Digital Library

[6]

T. M. Chan. Persistent predecessor search and orthogonal point location in the word RAM. In Proceedings of the 22nd ACM/SIAM Symposium on Discrete Algorithms (SODA), 2011. to appear.

Digital Library

[7]

T. M. Chan and M. Petraşcu. Counting inversions, offline orthogonal range counting, and related problems. In Proceedings of the 21st ACM/SIAM Symposium on Discrete Algorithms (SODA), pages 161--173, 2010.

Digital Library

[8]

B. Chazelle. A functional approach to data structures and its use in multidimensional searching. SIAM Journal of Computing, 17:427--462, 1988.

Digital Library

[9]

B. Chazelle. Lower bounds for orthogonal range searching: I. the reporting case. Journal of the ACM, 37(2):200--212, 1990.

Digital Library

[10]

B. Chazelle. Lower bounds for off-line range searching. Discrete & Computational Geometry, 17(1):53--65, 1997.

[11]

D. Comer. Ubiquitous B-tree. ACM Computing Survey, 11(2):121--137, 1979.

Digital Library

[12]

E. D. Demaine, G. M. Landau, and O. Weimann. On cartesian trees and range minimum queries. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming, pages 341--353, 2009.

Digital Library

[13]

R. W. Floyd and R. L. Rivest. Expected time bounds for selection. Communications of the ACM, 18(3):165--172, 1975.

Digital Library

[14]

G. N. Frederickson and D. B. Johnson. The complexity of selection and ranking in X+Y and matrices with sorted columns. Journal of Computer and System Sciences, 24(2):197--208, 1982.

[15]

T. Gagie, S. J. Puglisi, and A. Turpin. Range quantile queries: Another virtue of wavelet trees. In Proceedings of the 16th String Processing and Information Retrieval Symposium, pages 1--6, 2009.

Digital Library

[16]

B. Gfeller and P. Sanders. Towards optimal range medians. In Proceedings of the 36th International Colloquium on Automata, Languages and Programming, pages 475--486, 2009.

Digital Library

[17]

M. Greve, A. G. Jørgensen, K. D. Larsen, and J. Truelsen. Cell probe lower bounds and approximations for range mode. In Proceedings of the 37th International Colloquium on Automata, Languages and Programming, pages 605--616, 2010.

Digital Library

[18]

S. Har-Peled and S. Muthukrishnan. Range medians. In Proceedings of the 16th Annual European Symposium on Algorithms, pages 503--514, 2008.

Digital Library

[19]

D. Harel and R. E. Tarjan. Fast algorithms for finding nearest common ancestors. SIAM Journal of Computing, 13(2):338--355, 1984.

Digital Library

[20]

J. JáJá, C. W. Mortensen, and Q. Shi. Space-efficient and fast algorithms for multidimensional dominance reporting and counting. In Proceedings of the 15th International Symposium on Algorithms and Computation, pages 558--568, 2004.

Digital Library

[21]

D. Krizanc, P. Morin, and M. H. M. Smid. Range mode and range median queries on lists and trees. Nordic Journal of Computing, 12(1):1--17, 2005.

Digital Library

[22]

J. Matoušek. Reporting points in halfspaces. Computational Geometry: Theory and Applications, 2(3):169--186, 1992.

Digital Library

[23]

P. B. Miltersen, N. Nisan, S. Safra, and A. Wigderson. On data structures and asymmetric communication complexity. Journal of Computer and System Sciences, 57(1):37--49, 1998.

Digital Library

[24]

M. Petraşcu. Lower bounds for 2-dimensional range counting. In Proceedings of the 39th ACM Symposium on Theory of Computing, pages 40--46, 2007.

Digital Library

[25]

M. Petraşcu. (Data) STRUCTURES. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, pages 434--443, 2008.

Digital Library

[26]

M. Petraşcu and M. Thorup. Higher lower bounds for near-neighbor and further rich problems. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, pages 646--654, 2006.

Digital Library

[27]

H. Petersen. Improved bounds for range mode and range median queries. In Proceedings of the 34th Conference on Current Trends in Theory and Practice of Computer Science, pages 418--423, 2008.

Digital Library

[28]

H. Petersen and S. Grabowski. Range mode and range median queries in constant time and sub-quadratic space. Information Processing Letters, 109(4):225--228, 2008.

Digital Library

[29]

C. Sommer, E. Verbin, and W. Yu. Distance oracles for sparse graphs. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, pages 703--712, 2009.

Digital Library

[30]

D. E. Willard. Log-logarithmic worst-case range queries are possible in space Theta(n). Information Processing Letters, 17(2):81--84, 1983.

Cited By

Larsen KWeinstein OYu HDiakonikolas IKempe DHenzinger M(2018)Crossing the logarithmic barrier for dynamic Boolean data structure lower boundsProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188790(978-989)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188790
Larsen KWilliams RKlein P(2017)Faster online matrix-vector multiplicationProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039828(2182-2189)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039828
Grossi RIacono JNavarro GRaman RSatti S(2017)Asymptotically Optimal Encodings of Range Data Structures for Selection and Top-k QueriesACM Transactions on Algorithms10.1145/301293913:2(1-31)Online publication date: 6-Mar-2017
https://dl.acm.org/doi/10.1145/3012939
Show More Cited By

Range selection and median: tight cell probe lower bounds and adaptive data structures

Recommendations

Improved bounds for range mode and range median queries
SOFSEM'08: Proceedings of the 34th conference on Current trends in theory and practice of computer science

We investigate the following problem: Given a list of n items and a function defined over lists of these items, generate a bounded amount of auxiliary information such that range queries asking for the value of the function on sub-lists can be answered ...
Data Structures for Range Median Queries
ISAAC '09: Proceedings of the 20th International Symposium on Algorithms and Computation

In this paper we design data structures supporting range median queries, i.e. report the median element in a sub-range of an array. We consider static and dynamic data structures and batched queries. Our data structures support range selection queries, ...
Towards optimal range medians

We consider the following problem: Given an unsorted array of n elements, and a sequence of intervals in the array, compute the median in each of the subarrays defined by the intervals. We describe a simple algorithm which needs O(nlogk+klogn) time to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '11: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms

January 2011

1785 pages

Program Chair:
Dana Randall
Georgia Institute of Technology

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 23 January 2011

Check for updates

Qualifiers

Research-article

Conference

SODA '11

Sponsor:

SIGACT

SODA '11: 22nd ACM-SIAM Symposium on Discrete Algorithms

January 23 - 25, 2011

California, San Francisco

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
82
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Larsen KWeinstein OYu HDiakonikolas IKempe DHenzinger M(2018)Crossing the logarithmic barrier for dynamic Boolean data structure lower boundsProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188790(978-989)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188790
Larsen KWilliams RKlein P(2017)Faster online matrix-vector multiplicationProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039828(2182-2189)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039828
Grossi RIacono JNavarro GRaman RSatti S(2017)Asymptotically Optimal Encodings of Range Data Structures for Selection and Top-k QueriesACM Transactions on Algorithms10.1145/301293913:2(1-31)Online publication date: 6-Mar-2017
https://dl.acm.org/doi/10.1145/3012939
He MMunro JZhou G(2016)Data Structures for Path QueriesACM Transactions on Algorithms10.1145/290536812:4(1-32)Online publication date: 16-Aug-2016
https://dl.acm.org/doi/10.1145/2905368
Chan TWilkinson B(2016)Adaptive and Approximate Orthogonal Range CountingACM Transactions on Algorithms10.1145/283056712:4(1-15)Online publication date: 2-Sep-2016
https://dl.acm.org/doi/10.1145/2830567
Babenko MGawrychowski PKociumaka TStarikovskaya TIndyk P(2015)Wavelet trees meet suffix treesProceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/2722129.2722168(572-591)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.5555/2722129.2722168
Nekrich Y(2014)Efficient range searching for categorical and plain dataACM Transactions on Database Systems10.1145/254392439:1(1-21)Online publication date: 6-Jan-2014
https://dl.acm.org/doi/10.1145/2543924
Navarro G(2014)Spaces, Trees, and ColorsACM Computing Surveys10.1145/253593346:4(1-47)Online publication date: 1-Mar-2014
https://dl.acm.org/doi/10.1145/2535933
Yi KWang LWei Z(2014)Indexing for summary queriesACM Transactions on Database Systems10.1145/250870239:1(1-39)Online publication date: 6-Jan-2014
https://dl.acm.org/doi/10.1145/2508702
Chan TWilkinson BKhanna S(2013)Adaptive and approximate orthogonal range countingProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627835(241-251)Online publication date: 6-Jan-2013
https://dl.acm.org/doi/10.5555/2627817.2627835
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten