«Diviser et conquérir» les algorithmes de flux de données

Quels algorithmes utiles existent-ils qui fonctionnent sur d'énormes flux de données et aussi leurs résultats sont assez petits et on peut calculer le résultat pour un mélange de deux flux en fusionnant en quelque sorte leurs résultats?

Je peux en nommer quelques-uns:

• Les choses évidentes comme sum, min, max, count, top-K etc.
• Algorithmes de flux dits "basés sur des croquis" approximatifs pour les histogrammes, comptant des éléments distincts ou calculant des quantiles

Quels autres sont là?

(Je suis intéressé parce que j'écris un projet de loisir pour la surveillance de systèmes distribués dont l'utilité est directement déterminée par l'utilité de tels algorithmes)

Guha et al. '03 donne un algorithme d'approximation pour le clustering k-médian dans le modèle de streaming. Leur algorithme divise les données en morceaux disjoints, trouve les centres O (k) pour chaque morceau disjoint, puis combine les résultats pour obtenir les k centres. Cela semble être le type d'algorithme que vous recherchez.

$\varepsilon$$\varepsilon$$i^{\text{th}}$$(i-1)^{\text{th}}$-level stream, et le niveau 0 est le flux d'origine). Il s'agit essentiellement d'un rendu ascendant d'une stratégie de division et de conquête. avec des mises à jour le long du "bord" de l'arbre de récursivité. Dans sa structure, il est très similaire à l'article de Guha et al mentionné par Lev.

J'ai trouvé un article ( "Distribution des calculs de flux de données dépendants de la fréquence" ) qui dit que chaque fonction de la distribution de fréquence du flux est fusionnable (bien qu'elle ne donne pas une construction explicite et efficace pour l'opération de fusion). Et la preuve semble être très intéressante, impliquant une théorie des anneaux. Besoin de lire l'article précédent du même auteur ( "Limites inférieures sur l'estimation de fréquence des flux de données" ) dont le résultat principal est utilisé comme base pour celui-ci.

Cela me rappelle le troisième théorème de l'homomorphisme ...

La recherche sur les langages de requête de flux continu pourrait fournir des informations. Un tel langage est CQL , qui je crois est en cours d'adoption par Oracle. Les langages permettent de calculer des fonctions sur des fenêtres coulissantes du flux (y compris des fenêtres de taille 1). Cette thèse de licence donne un aperçu récent de la langue, y compris quelques exemples. Cet article donne un aperçu de certains langages de traitement de flux, qui devraient être utiles pour trouver des liens vers d'autres recherches connexes.

Je sais que cela ne répond pas directement à votre question, mais cela devrait vous mettre en relation avec des recherches effectuées par des personnes partant du même point de départ.

Cette question me semble un peu circulaire. Si le problème a la propriété souhaitée, il existe un algorithme basé sur l'esquisse et la fusion. Comme mentionné ci-dessus, il existe des travaux sur le clustering, les approximations et les coresets qui vous fournissent cela. De plus, la plupart des algorithmes de streaming permettent de fusionner des flux en concaténant simplement (conceptuellement) un flux à l'autre.

De plus, je ne suis pas sûr que les algorithmes de streaming top-k soient fusionnables - mais je peux me tromper.

Désolé d'être nécromancé à ce sujet, mais j'ai pensé que vous pourriez vouloir examiner certains travaux sur la surveillance continue distribuée sur les flux, où vous disposez de plusieurs flux et l'objectif est de surveiller certaines statistiques agrégées sur un site de surveillance central tout en minimisant la communication. Le modèle me semble étroitement lié à votre motivation. Regardez les références dans le livre de Muthu . Un document est ce .

Le document de Ganguly est également très intéressant.