Algoritmos de fluxo de dados "Divida e conquiste"

Quais algoritmos úteis existem que funcionam em enormes fluxos de dados e também seus resultados são razoavelmente pequenos e pode-se calcular o resultado para uma mistura de dois fluxos, de alguma forma, mesclando seus resultados?

Eu posso citar alguns:

• Coisas óbvias como soma, mínimo, máximo, contagem, top-K etc.
• Algoritmos de fluxo "baseados em esboço" aproximados para histogramas, contando itens distintos ou quantis de computação

Que outros existem?

(Estou interessado porque estou escrevendo um projeto de hobby para monitorar sistemas distribuídos cuja utilidade é diretamente determinada pela utilidade de tais algoritmos)

Guha et al. '03 fornece um algoritmo de aproximação para k-median clustering no modelo de streaming. O algoritmo deles divide os dados em partes separadas, encontra O (k) centros para cada parte separada e, em seguida, combina os resultados para obter os k centros. Este parece ser o tipo de algoritmo que você está procurando.

$\varepsilon$$\varepsilon$$i^{\text{th}}$$(i-1)^{\text{th}}$nível de fluxo e o nível 0 é o fluxo original). Essa é essencialmente uma renderização de baixo para cima de uma estratégia de dividir e conquistar. com atualizações ao longo da "borda" da árvore de recursão. Em estrutura, é muito semelhante ao artigo de Guha et al mencionado por Lev.

Eu encontrei um documento ( "Distribuindo cálculos de fluxo de dados dependentes da frequência" ) que diz que todas as funções da distribuição de frequência do fluxo são mescláveis (embora não forneçam uma construção explícita e eficiente para a operação de mesclagem). E a prova parece ser muito interessante, envolvendo alguma teoria dos anéis. É necessário ler o artigo anterior do mesmo autor ( "Limites inferiores na estimativa de frequência de fluxos de dados" ) cujo principal resultado é usado como base para este.

Isso me lembra o Terceiro Teorema do Homomorfismo ...

A pesquisa em linguagens de consulta de fluxo contínuo pode fornecer algumas dicas. Uma dessas linguagens é o CQL , que acredito estar sendo adotada pela Oracle. Os idiomas permitem que as funções sejam computadas em janelas deslizantes do fluxo (incluindo janelas de tamanho 1). Esta tese de bacharel fornece uma visão geral recente do idioma, incluindo alguns exemplos. Este artigo fornece uma visão geral de algumas linguagens de processamento de fluxo, que devem ser úteis para encontrar links para outras pesquisas relacionadas.

Sei que isso não responde diretamente à sua pergunta, mas deve colocá-lo em contato com pesquisas feitas por pessoas que partem do mesmo ponto de partida.

Esta pergunta parece um pouco circular para mim. Se o problema tiver a propriedade que você deseja, existe um algoritmo baseado em desenho e mesclagem para ele. Como mencionado acima, há trabalho em cluster, aproximações e conjuntos de cores que fornecem isso. Além disso, a maioria dos algoritmos de streaming permite a fusão de fluxos concatenando apenas (conceitualmente) um fluxo ao outro.

Além disso, não tenho certeza de que os algoritmos top-k de streaming sejam mescláveis ​​- mas posso estar errado.

Desculpe por não ser necromante disso, mas pensei que você poderia querer examinar alguns trabalhos sobre monitoramento contínuo distribuído em fluxos, onde você recebe vários fluxos e o objetivo é monitorar algumas estatísticas agregadas em um site central de monitoramento, minimizando a comunicação. O modelo me parece intimamente relacionado à sua motivação. Veja as referências no livro de Muthu . Um artigo é esse .

O artigo de Ganguly também é muito interessante.