An empirical study of moment estimators for quantile approximation

Simple item page
dc.contributor.authorMitchell, Roryen_NZ
dc.contributor.authorFrank, Eibeen_NZ
dc.contributor.authorHolmes, Geoffreyen_NZ
dc.date.accessioned2021-03-24T22:53:50Z
dc.date.available2021-03-24T22:53:50Z
dc.date.issued2021en_NZ
dc.description.abstractWe empirically evaluate lightweight moment estimators for the single-pass quantile approximation problem, including maximum entropy methods and orthogonal series with Fourier, Cosine, Legendre, Chebyshev and Hermite basis functions. We show how to apply stable summation formulas to offset numerical precision issues for higher-order moments, leading to reliable single-pass moment estimators up to order 15. Additionally, we provide an algorithm for GPU-accelerated quantile approximation based on parallel tree reduction. Experiments evaluate the accuracy and runtime of moment estimators against the state-of-the-art KLL quantile estimator on 14,072 real-world datasets drawn from the OpenML database. Our analysis highlights the effectiveness of variants of moment-based quantile approximation for highly space efficient summaries: their average performance using as few as five sample moments can approach the performance of a KLL sketch containing 500 elements. Experiments also illustrate the difficulty of applying the method reliably and showcases which moment-based approximations can be expected to fail or perform poorly.en_NZ
dc.format.mimetypeapplication/pdf
dc.identifier.citationMitchell, R., Frank, E., & Holmes, G. (2021). An empirical study of moment estimators for quantile approximation. ACM Transactions on Database Systems, 46(1), 1–21. https://doi.org/10.1145/3442337en
dc.identifier.doi10.1145/3442337en_NZ
dc.identifier.eissn1557-4644en_NZ
dc.identifier.issn0362-5915en_NZ
dc.identifier.urihttps://hdl.handle.net/10289/14197
dc.language.isoenen_NZ
dc.publisherAssociation for Computing Machinery (ACM)en_NZ
dc.relation.isPartOfACM Transactions on Database Systemsen_NZ
dc.rights© 2021 Copyright held by the author(s). Publication rights licensed to ACM.
dc.subjectcomputer scienceen_NZ
dc.subjectdistributon functionsen_NZ
dc.subjectstatistical softwareen_NZ
dc.subjectdata miningen_NZ
dc.subjectmachine learning algorithmsen_NZ
dc.subjectdensity estimationen_NZ
dc.subjectquantilesen_NZ
dc.subjectdata streamsen_NZ
dc.titleAn empirical study of moment estimators for quantile approximationen_NZ
dc.typeJournal Article
pubs.begin-page1
pubs.elements-id260049
pubs.end-page21
pubs.issue1en_NZ
pubs.organisational-group/Waikato
pubs.organisational-group/Waikato/2024 PBRF
pubs.organisational-group/Waikato/DHECS
pubs.organisational-group/Waikato/DHECS/2024 PBRF - DHEC
pubs.organisational-group/Waikato/DHECS/SCMS
pubs.organisational-group/Waikato/DHECS/SCMS/2024 PBRF - SCMS
pubs.publication-statusPublisheden_NZ
pubs.user.infoHolmes, Geoffrey (geoff@waikato.ac.nz)
pubs.user.infoFrank, Eibe (eibe@waikato.ac.nz)
pubs.volume46en_NZ
uow.verification.statusverified
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
3442337.pdf
Size:
2.92 MB
Format:
Adobe Portable Document Format
Description:
Published version
Thumbnail Image
Name: 3442337.pdf
Size: 2.92 MB
Kind: Adobe PDF
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
Research Commons Deposit Agreement 2017.pdf
Size:
188.11 KB
Format:
Adobe Portable Document Format
Description:
Name: Research Commons Deposit Agreement 2017.pdf
Size: 188.11 KB
Kind: Adobe PDF
Collections
Computing and Mathematical Sciences Papers