Algoritmo para números 'k' 'que ocorrem com mais frequência

Eu tenho procurado pelo algoritmo (streaming ??) mais eficiente que me diz os 'k' elementos que ocorrem com mais frequência em um fluxo de dados a qualquer momento. Este post: "Divida e conquiste" algoritmos de fluxo de dados me interessaram.

Por exemplo, suponha que haja números: (4,3,5,1,6,2,4,3,3,8,9,1) e eu pesquise os 3 números que ocorrem com mais frequência (digamos), então devo get (3,4,1) como resposta.

Tentei pesquisar on-line, mas não consegui encontrar nenhum lugar que dê uma abordagem e diga que esse é o melhor. Uma solução trivial seria usar uma pilha ou uma árvore binária equilibrada, mas acho que há uma maneira melhor e eu queria saber se está documentada em algum lugar.

Editar: estou procurando um algoritmo que sempre dê a resposta correta em oposição a um algoritmo de aprovação (muitos dos quais aparecem nos resultados de pesquisa) que dependem da distribuição de dados de uma maneira ou de outra

ds.algorithms online-algorithms data-streams dhruvbird
fonte

Na verdade, existem três tipos de algoritmos: exato, aproximado e "dependente de dados". Você descartou o último tipo, mas algoritmos aproximados que NÃO dependem da distribuição de dados são permitidos? como indiquei, se não, você está com problemas por causa dos limites inferiores conhecidos para esse problema em uma configuração de fluxo.

Suresh Venkat

Fiquei curioso para saber se os algoritmos que usam memória limitada (algoritmos de streaming) podem realmente fazer o que eu queria e parece que eles não podem, como você apontou. Também se é conhecido um algoritmo exato sem streaming que resolve o problema em O (n) tempo garantido no pior caso, mencionado aqui (citado pelo artigo de Cormode e Hadjileftheriou no link que você forneceu): citeseerx.ist.psu. edu / viewdoc / summary? doi = 10.1.1.106.7889

dhruvbird

Respostas:

Há uma extensa literatura sobre esse problema. Em primeiro lugar, mesmo para , o problema é difícil: como Alon, Matias e Szegedy mostram, você não pode obter uma aproximação fatorial melhor que a constante do elemento mais popular no espaço, mesmo que você está disposto a ser randomizado. $k=1$ $o(n)$

No entanto, se você tiver certeza de que um elemento ocorre estritamente mais de 50% do tempo, existe um truque simples que usa espaço constante e o encontra (essa é uma pergunta popular do Google Puzzle). De maneira mais geral, é possível encontrar elementos que ocorrem mais de vezes usando uma generalização desse truque. $n/k$

Uma pesquisa definitiva sobre o que se sabe sobre o problema é o artigo de Cormode e Hadjileftheriou da VLDB 2008 . Abrange os métodos acima e muitos dos métodos mais recentes. a ideia geral é que você possa gerar uma lista aproximada dos principais itens de (onde aproximado aqui significa que você pode obter itens cujas contagens estão próximas das contagens dos principais itens de ). $k$ $k$

Suresh Venkat
fonte

+1. Eu acho que a> 50% do algoritmo de tempo é um bem conhecido (elemento algoritmo maioria) como você mencionou

dhruvbird

Obrigado!! O artigo de Cormode e Hadjileftheriou que você mencionou cita este artigo: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.7889, que tem a mesma técnica em que eu estava pensando. Mantém 2 listas vinculadas; um por frequência e dentro dele outra lista de todos os elementos com a mesma frequência.

Dhruvbird

você pode elaborar o algoritmo de mais de 50%? e o quebra-cabeça do google? Não posso seguir esse raciocínio desleixado, pois você acabou de abordá-lo e não se dedicar totalmente ao "truque bem conhecido". Obrigado.

Aqui está um link: userweb.cs.utexas.edu/users/misra/scannedPdf.dir/…

Suresh Venkat

Este é um comentário (não é suficiente reputação) no link userweb.cs.utexas.edu/users/misra/scannedPdf.dir/… do Suresh Venkat : Parece que o algoritmo apresentado lá requer uma segunda passagem pelos dados, o que não é permitido aqui. De fato, não vejo como um algoritmo de uma passagem com requisitos de espaço O (1) possa existir.

TonyK

Também recomendo a leitura da seção 8.1.3 "Mineração de padrões freqüentes em fluxos de dados" do livro a seguir:

Jiawei Han, Micheline Kamber. Data Mining --- Conceitos e Técnicas, Segunda Edição, Morgan Kaufmann Publishers , 2006.

Ele apresenta um algoritmo, conhecido como contagem com perdas , que aproxima itens frequentes (itens cujo suporte está acima de algum suporte mínimo ) com precisão arbitrária.

Não é exatamente o que você quer, mas achei que poderia ajudar.

MS Dousti
fonte

talvez você possa me ajudar com a minha pergunta aqui #

Ben