Sublinear algorithms in the external memory model

DOI10.1007/978-3-642-16367-8_15MaRDI QIDQ4933373zbMATH OpenOpenAlexFDO

Authors Alexandr Andoni, Krzysztof Onak, Ronitt Rubinfeld, Piotr Indyk

Publication date 12 October 2010

Published in Property Testing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-16367-8_15

zbMATH Keywords

distribution testingexternal memorysampling

Mathematics Subject Classification ID

Distribution theory (60E99) Nonparametric hypothesis testing (62G10) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• External Sampling
• Range partitioning within sublinear time in the external memory model
• Range partitioning within sublinear time: algorithms and lower bounds
• scientific article; zbMATH DE number 1792107

Cites work

• scientific article; zbMATH DE number 1819631 (Why is no real title available?)
• On testing expansion in bounded-degree graphs
• Sampling algorithms: lower bounds and applications
• Testing Graph Isomorphism
• Testing Properties of Sets of Points in Metric Spaces

Cited in

(4)

• Range partitioning within sublinear time in the external memory model
• Range partitioning within sublinear time: algorithms and lower bounds
• Sublinear Computation Paradigm
• Algorithms for the transportation problem in geometric settings

This page was built for publication: Sublinear algorithms in the external memory model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4933373)