[jira] [Created] (KAFKA-6152) Support ExpanderSketch algorithm for space and time efficient stream processing.

["Edmon Begoli (JIRA)" <ji...@apache.org>]

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)