Rechercher des éléments qui sont dans au moins

11

Considérez ensembles de valeurs (représentés comme des tableaux triés sans doublons et avec une taille connue (c'est-à-dire que la taille peut être obtenue en O (1)). Les valeurs peuvent être testées pour l'égalité en temps O (1). Je veux pour obtenir l'ensemble des valeurs présentes dans au moins k ensembles différents parmi les n .nkn

L'algorithme évident pour ce faire est de parcourir tous les ensembles, de compter le nombre d'occurrences de chaque valeur et de renvoyer ceux dont le nombre est supérieur à . Pourtant, dans certains cas, vous pouvez faire mieux: par exemple, lorsque n = k = 2 et lorsqu'un ensemble S 1 est beaucoup plus petit que l'autre ensemble S 2 , il est plus efficace de regarder tous les éléments de S 1 et d'effectuer une recherche binaire pour chacun d'eux dans S 2 : l'approche de recherche binaire coûte O ( | S 1 | log ( | S 2 |kn=k=2S1S2S1S2 alors que l'approche naïve coûte O ( | S 1 | + | S 2 | ) qui est pire lorsque | S 1 | < < | S 2 | .O(|S1|log⁡(|S2|))O(|S1|+|S2|)|S1|<<|S2|

Dans cet esprit, dans quelles situations peut-on faire mieux que l'algorithme naïf? (S'il s'agit d'un problème bien connu, je serais heureux de connaître son nom habituel et d'avoir des références.)

ds.algorithms a3nm
la source
3
Cela relève de la catégorie générale des résultats "top-K", ou "gros frappeurs". Ce dernier est plus proche de ce que vous recherchez. La plupart des travaux dans cet espace se concentrent sur les grands ensembles de données et les restrictions de mémoire sublinéaires.
Suresh Venkat
9
La méthode "rechercher tous les emplacements de S1 dans S2" que vous donnez peut être exécutée dans le temps , toujours au moins aussi bonne que la linéaire naïve algorithme de temps. O(|S1|log⁡(|S2|/|S1|))
David Eppstein

Réponses:

2

OK, je pense avoir trouvé quelque chose de pertinent: cet article mentionne un "problème d'occurrence T" dans la section III (p. 2) qui est exactement notre problème (où est ce que nous avons appelé k ), caché derrière un jargon spécifique au domaine. L'algorithme ScanCount qu'ils proposent est l'approche naïve que j'ai suggérée dans ma question. L'algorithme MergeOpt est une généralisation de l'astuce de recherche binaire. Leur proposition principale (DivideSkip) est une combinaison de cette astuce de recherche binaire et d'une astuce différente (MergeSkip) pour ignorer plusieurs valeurs. Il semble même qu'expérimentalement, les approches intelligentes sont bien meilleures que les approches naïves (regardez la colonne "Pas de filtres" à la page 8, les filtres sont des heuristiques pour leur substance propre au domaine).Tk

Cela peut être combiné avec l'astuce de David Eppstein pour rendre plusieurs recherches binaires dans plus efficaces, et avec l'idée d'utiliser la recherche par interpolation au lieu de la recherche binaire (une idée de cet autre article du même domaine ).S2

a3nm
la source
1

Votre problème est similaire au problème d'exploration de données de la recherche de jeux d'éléments fréquents , également appelé apprentissage des règles d'association . Si j'ai bien compris, votre problème peut être réduit à trouver des ensembles fréquents d'éléments de cardinalité 1 (c'est-à-dire des singletons) avec un support > = k . Bien sûr, les algorithmes disponibles (tels que Apriori, Eclat, D-CLUB, etc.) pour le problème permettent également de déterminer des ensembles fréquents de cardinalité> 1.

Massimo Cafaro
la source