Edmon Begoli created KAFKA-6152:
-----------------------------------
Summary: 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
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)
