kafka-jira mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Edmon Begoli (JIRA)" <j...@apache.org>
Subject [jira] [Created] (KAFKA-6152) Support ExpanderSketch algorithm for space and time efficient stream processing.
Date Tue, 31 Oct 2017 10:02:00 GMT
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)

Mime
View raw message