publication . Preprint . 2020

Asymmetric scale functions for $t$-digests

Ross, Joseph;
Open Access English
  • Published: 19 May 2020
Abstract
The $t$-digest is a data structure that can be queried for approximate quantiles, with greater accuracy near the minimum and maximum of the distribution. We develop a $t$-digest variant with accuracy asymmetric about the median, thereby making possible alternative tradeoffs between computational resources and accuracy which may be of particular interest for distributions with significant skew. After establishing some theoretical properties of scale functions for $t$-digests, we show that a tangent line construction on the familiar scale functions preserves the crucial properties that allow $t$-digests to operate online and be mergeable. We conclude with an empir...
Subjects
free text keywords: Computer Science - Data Structures and Algorithms
Download from

Beyer B, Jones C, Petoff J, Murphy NR (2016). Site Reliability Engineering: How Google Runs Production Systems. ” O'Reilly Media, Inc.”.

Chen F, Lambert D, Pinheiro JC (2000). “Incremental quantile estimation for massive tracking.” In Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 516-522. ACM.

Dunning T (2018). “The t-digest Library.” https://github.com/tdunning/t-digest/. [Online; accessed 8-August-2019]. [OpenAIRE]

Dunning T (2019a). “Conservation of the t-digest Scale Invariant.” arXiv preprint arXiv:1903.09919.

Dunning T (2019b). “The Size of a t-Digest.” arXiv preprint arXiv:1903.09921.

Dunning T, Ertl O (2019). “Computing extremely accurate quantiles using t-digests.” arXiv preprint arXiv:1902.04023. [OpenAIRE]

Gan E, Ding J, Tai KS, Sharan V, Bailis P (2018). “Moment-based quantile sketches for efficient high cardinality aggregation queries.” Proceedings of the VLDB Endowment, 11(11), 1647-1660.

Greenwald M, Khanna S, et al. (2001). “Space-efficient online computation of quantile summaries.” ACM SIGMOD Record, 30(2), 58-66.

Munro JI, Paterson MS (1980). “Selection and sorting with limited storage.” Theoretical computer science, 12(3), 315-323. [OpenAIRE]

Ross J (2019a). “SignalFx fork of Ted Dunning's t-digest Library.” https://github. com/signalfx/t-digest/tree/asymmetric/docs/asymmetric. [Online; accessed 13- September-2019].

Shrivastava N, Buragohain C, Agrawal D, Suri S (2004). “Medians and beyond: new aggregation techniques for sensor networks.” In Proceedings of the 2nd international conference on Embedded networked sensor systems, pp. 239-249. ACM.

Sloss BT, Dahlin M, Rau V, Beyer B (2017). “The Calculus of Service Availability.” Queue, 15(2), 40.

Abstract
The $t$-digest is a data structure that can be queried for approximate quantiles, with greater accuracy near the minimum and maximum of the distribution. We develop a $t$-digest variant with accuracy asymmetric about the median, thereby making possible alternative tradeoffs between computational resources and accuracy which may be of particular interest for distributions with significant skew. After establishing some theoretical properties of scale functions for $t$-digests, we show that a tangent line construction on the familiar scale functions preserves the crucial properties that allow $t$-digests to operate online and be mergeable. We conclude with an empir...
Subjects
free text keywords: Computer Science - Data Structures and Algorithms
Download from

Beyer B, Jones C, Petoff J, Murphy NR (2016). Site Reliability Engineering: How Google Runs Production Systems. ” O'Reilly Media, Inc.”.

Chen F, Lambert D, Pinheiro JC (2000). “Incremental quantile estimation for massive tracking.” In Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 516-522. ACM.

Dunning T (2018). “The t-digest Library.” https://github.com/tdunning/t-digest/. [Online; accessed 8-August-2019]. [OpenAIRE]

Dunning T (2019a). “Conservation of the t-digest Scale Invariant.” arXiv preprint arXiv:1903.09919.

Dunning T (2019b). “The Size of a t-Digest.” arXiv preprint arXiv:1903.09921.

Dunning T, Ertl O (2019). “Computing extremely accurate quantiles using t-digests.” arXiv preprint arXiv:1902.04023. [OpenAIRE]

Gan E, Ding J, Tai KS, Sharan V, Bailis P (2018). “Moment-based quantile sketches for efficient high cardinality aggregation queries.” Proceedings of the VLDB Endowment, 11(11), 1647-1660.

Greenwald M, Khanna S, et al. (2001). “Space-efficient online computation of quantile summaries.” ACM SIGMOD Record, 30(2), 58-66.

Munro JI, Paterson MS (1980). “Selection and sorting with limited storage.” Theoretical computer science, 12(3), 315-323. [OpenAIRE]

Ross J (2019a). “SignalFx fork of Ted Dunning's t-digest Library.” https://github. com/signalfx/t-digest/tree/asymmetric/docs/asymmetric. [Online; accessed 13- September-2019].

Shrivastava N, Buragohain C, Agrawal D, Suri S (2004). “Medians and beyond: new aggregation techniques for sensor networks.” In Proceedings of the 2nd international conference on Embedded networked sensor systems, pp. 239-249. ACM.

Sloss BT, Dahlin M, Rau V, Beyer B (2017). “The Calculus of Service Availability.” Queue, 15(2), 40.

Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue