Range partitioning within sublinear time: algorithms and lower bounds

DOI10.1016/J.TCS.2021.01.017zbMath1477.68284OpenAlexW3120050508MaRDI QIDQ2220789

Baoling Ning, Shouxu Jiang, Jian-Zhong Li

Publication date: 25 January 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2021.01.017

zbMATH Keywords

lower boundssublinear algorithmexternal memory modelrange partitioning

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computational aspects of data analysis and big data (68T09)

Cites Work

• Tree size reduction with keeping distinguishability
• Strongly minimal MapReduce algorithms: a terasort case study
• The hardness of resilience for nested aggregation query
• Sublinear Time Algorithms
• Sampling lower bounds via information theory
• External Sampling
• Sampling algorithms
• Probability and Computing
• Elements of Information Theory
• Samplesort: A Sampling Approach to Minimal Storage Tree Sorting
• On Information and Sufficiency

This page was built for publication: Range partitioning within sublinear time: algorithms and lower bounds