[
https://issues.apache.org/jira/browse/KAFKA-6152?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Edmon Begoli updated KAFKA-6152:
--------------------------------
Description:
Support a new ExpanderSketch algorithm (Larsen et al., 2016) based on
cluster-preserving clustering and considered the best contemporary streaming
algorithm (Quanta, 2017).
It achieves optimal O(ε^p^_log_n) space, O(_log_n) update time, and fast
O(ε^p^poly(_log_n)) query time, and _whp_ correctness
Larsen, K. G., Nelson, J., Nguyên, H. L., & Thorup, M. (2016, October). Heavy
hitters via cluster-preserving clustering. In Foundations of Computer Science
(FOCS), 2016 IEEE 57th Annual Symposium on (pp. 61-70). IEEE.
https://arxiv.org/abs/1604.01357
Hartnett, K., (2017, October). Best-Ever Algorithm Found for Huge Streams of
Data. Quanta Magazine, October 2017, online at:
https://www.quantamagazine.org/best-ever-algorithm-found-for-huge-streams-of-data-20171024/
was:
Support a new ExpanderSketch algorithm (Larsen et al., 2016) based on
cluster-preserving clustering and considered the best contemporary streaming
algorithm (Quanta, 2017).
It achieves optimal O(ε^{p}log_n) space, O(log_n) update time, and fast
O(ε^{p}poly(log_n)) query time, and whp correctness
Larsen, K. G., Nelson, J., Nguyên, H. L., & Thorup, M. (2016, October). Heavy
hitters via cluster-preserving clustering. In Foundations of Computer Science
(FOCS), 2016 IEEE 57th Annual Symposium on (pp. 61-70). IEEE.
https://arxiv.org/abs/1604.01357
Hartnett, K., (2017, October). Best-Ever Algorithm Found for Huge Streams of
Data. Quanta Magazine, October 2017, online at:
https://www.quantamagazine.org/best-ever-algorithm-found-for-huge-streams-of-data-20171024/
> Support ExpanderSketch algorithm for space and time efficient stream
> processing.
> --------------------------------------------------------------------------------
>
> Key: KAFKA-6152
> URL: https://issues.apache.org/jira/browse/KAFKA-6152
> Project: Kafka
> Issue Type: New Feature
> Components: core
> Reporter: Edmon Begoli
> Attachments: larsen2016.pdf
>
> Original Estimate: 4,368h
> Remaining Estimate: 4,368h
>
> Support a new ExpanderSketch algorithm (Larsen et al., 2016) based on
> cluster-preserving clustering and considered the best contemporary streaming
> algorithm (Quanta, 2017).
> It achieves optimal O(ε^p^_log_n) space, O(_log_n) update time, and fast
> O(ε^p^poly(_log_n)) query time, and _whp_ correctness
> Larsen, K. G., Nelson, J., Nguyên, H. L., & Thorup, M. (2016, October). Heavy
> hitters via cluster-preserving clustering. In Foundations of Computer Science
> (FOCS), 2016 IEEE 57th Annual Symposium on (pp. 61-70). IEEE.
> https://arxiv.org/abs/1604.01357
> Hartnett, K., (2017, October). Best-Ever Algorithm Found for Huge Streams of
> Data. Quanta Magazine, October 2017, online at:
> https://www.quantamagazine.org/best-ever-algorithm-found-for-huge-streams-of-data-20171024/
--
This message was sent by Atlassian JIRA
(v6.4.14#64029)
