| dbo:abstract
|
- The Flajolet–Martin algorithm is an algorithm for approximating the number of distinct elements in a stream with a single pass and space-consumption logarithmic in the maximal number of possible distinct elements in the stream (the count-distinct problem). The algorithm was introduced by Philippe Flajolet and in their 1984 article "Probabilistic Counting Algorithms for Data Base Applications". Later it has been refined in "LogLog counting of large cardinalities" by and Philippe Flajolet, and "HyperLogLog: The analysis of a near-optimal cardinality estimation algorithm" by Philippe Flajolet et al. In their 2010 article "An optimal algorithm for the distinct elements problem", Daniel M. Kane, Jelani Nelson and David P. Woodruff give an improved algorithm, which uses nearly optimal space and has optimal O(1) update and reporting times. (en)
- L'algorithme de Flajolet et Martin est un algorithme donnant une estimation du nombre d'éléments distincts dans un flot, en une seule passe et avec une complexité logarithmique en mémoire, proportionnelle au nombre maximum d'éléments distincts. Cet algorithme a été inventé en 1984 par Philippe Flajolet and G. Nigel Martin, puis amélioré par Marianne Durand et Philippe Flajolet. C'est un algorithme de fouille de flots de données (streaming). En 2010, Daniel M. Kane, Jelani Nelson et David P. Woodruff ont proposé un algorithme avec une complexité spatiale presque optimale et un coût de modification en O(1). (fr)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 7604 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- The Flajolet–Martin algorithm is an algorithm for approximating the number of distinct elements in a stream with a single pass and space-consumption logarithmic in the maximal number of possible distinct elements in the stream (the count-distinct problem). The algorithm was introduced by Philippe Flajolet and in their 1984 article "Probabilistic Counting Algorithms for Data Base Applications". Later it has been refined in "LogLog counting of large cardinalities" by and Philippe Flajolet, and "HyperLogLog: The analysis of a near-optimal cardinality estimation algorithm" by Philippe Flajolet et al. (en)
- L'algorithme de Flajolet et Martin est un algorithme donnant une estimation du nombre d'éléments distincts dans un flot, en une seule passe et avec une complexité logarithmique en mémoire, proportionnelle au nombre maximum d'éléments distincts. Cet algorithme a été inventé en 1984 par Philippe Flajolet and G. Nigel Martin, puis amélioré par Marianne Durand et Philippe Flajolet. C'est un algorithme de fouille de flots de données (streaming). (fr)
|
| rdfs:label
|
- Algorithme de Flajolet et Martin (fr)
- Flajolet–Martin algorithm (en)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
