Encontre itens que estejam em pelo menos de conjuntos

11

Considere conjuntos de valores (representados como matrizes classificadas sem duplicatas e com um tamanho conhecido (ou seja, o tamanho pode ser obtido em O (1)) .Os valores podem ser testados quanto à igualdade no tempo O (1). para obter o conjunto de valores presentes em pelo menos conjuntos diferentes entre os . $n$ $k$ $n$

O algoritmo óbvio para fazer isso é percorrer todos os conjuntos, contar o número de ocorrências de cada valor e retornar aqueles com uma contagem maior que . No entanto, em alguns casos, você pode fazer melhor: por exemplo, quando e quando um conjunto é muito menor que o outro conjunto , é mais eficiente examinar todos os itens de e realizar uma pesquisa binária para cada um deles em : a abordagem de pesquisa binária custa enquanto a abordagem ingênua custa que é pior quando. $k$ $n = k = 2$ $S_1$ $S_2$ $S_1$ $S_2$ $O(|S_1| \log(|S_2|))$ $O(|S_1| + |S_2|)$ $|S_1| << |S_2|$

Com isso em mente, em quais situações podemos fazer melhor que o algoritmo ingênuo? (Se esse for um problema conhecido, ficarei feliz em saber o nome usual e ter referências.)

ds.algorithms a3nm
fonte

3

Isso se enquadra na categoria geral de resultados "top-K" ou "rebatedores pesados". O último está mais próximo do que você está procurando. A maioria dos trabalhos neste espaço se concentra em grandes conjuntos de dados e restrições de memória sublinear.

Suresh Venkat

9

O método "pesquisar todos os locais de S1 em S2" pode ser executado no tempo , sempre pelo menos tão bom quanto o algoritmo de tempo linear ingênuo .

O (| S_{1} | \log (| S_{2} | / | S_{1} |))

$O(|S_1|\log(|S_2|/|S_1|))$

David Eppstein

2

OK, acho que encontrei algo relevante: este artigo menciona um "problema de ocorrência de T" na seção III (p. 2), que é exatamente o nosso problema (onde é o que chamamos de ), escondido atrás de algum jargão específico do domínio. O algoritmo ScanCount que eles propõem é a abordagem ingênua que sugeri na minha pergunta. O algoritmo MergeOpt é uma generalização do truque de pesquisa binária. Sua principal proposta (DivideSkip) é uma combinação desse truque de pesquisa binária e um truque diferente (MergeSkip) para ignorar vários valores. Até parece que experimentalmente as abordagens inteligentes são muito melhores do que as abordagens ingênuas (veja a coluna "Sem filtros" na página 8, os filtros são heurísticos para itens específicos de domínio). $T$ $k$

Isso pode ser combinado com o truque de David Eppstein para tornar várias pesquisas binárias em mais eficientes e com a idéia de usar a pesquisa de interpolação em vez da pesquisa binária (uma idéia deste outro artigo do mesmo campo ). $S_2$

a3nm
fonte

1

Seu problema é semelhante ao problema de mineração de dados de encontrar conjuntos de itens frequentes , também conhecido como aprendizado de regras de associação . Se entendi corretamente, seu problema pode ser reduzido para encontrar conjuntos frequentes de cardinalidade 1 (isto é, singletons) com suporte > = k . Obviamente, os algoritmos disponíveis (como Apriori, Eclat, D-CLUB etc.) para o problema também permitem determinar conjuntos de itens frequentes de cardinalidade> 1.

Massimo Cafaro
fonte

Encontre itens que estejam em pelo menos de conjuntos

Respostas: