This HTML5 document contains 47 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n5https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbthttp://dbpedia.org/resource/Template:
n17https://web.archive.org/web/20160304042036/http:/jupiter.math.nctu.edu.tw/~mfuchs/
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
n19http://algo.inria.fr/flajolet/Publications/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbchttp://dbpedia.org/resource/Category:
dbphttp://dbpedia.org/property/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:List_of_algorithms
dbo:wikiPageWikiLink
dbr:Approximate_counting_algorithm
Subject Item
dbr:Approximate_counting_algorithm
rdf:type
yago:YagoPermanentlyLocatedEntity yago:Activity100407535 yago:PsychologicalFeature100023100 yago:Abstraction100002137 yago:Act100030358 yago:Rule105846932 yago:Procedure101023820 yago:WikicatRandomizedAlgorithms yago:Event100029378 yago:Algorithm105847438
rdfs:label
Approximate counting algorithm
rdfs:comment
The approximate counting algorithm allows the counting of a large number of events using a small amount of memory. Invented in 1977 by Robert Morris (cryptographer) of Bell Labs, it uses probabilistic techniques to increment the counter. It was fully analyzed in the early 1980s by Philippe Flajolet of INRIA Rocquencourt, who coined the name approximate counting, and strongly contributed to its recognition among the research community. When focused on high quality of approximation and low probability of failure, Nelson and Yu showed that a very slight modification to the Morris Counter is asymptotically optimal amongst all algorithms for the problem. The algorithm is considered one of the precursors of streaming algorithms, and the more general problem of determining the frequency moments o
dcterms:subject
dbc:Randomized_algorithms
dbo:wikiPageID
20101191
dbo:wikiPageRevisionID
1096313090
dbo:wikiPageWikiLink
dbr:Randomized_algorithm dbr:HyperLogLog dbr:Exponent dbr:Artificial_intelligence dbc:Randomized_algorithms dbr:Jelani_Nelson dbr:Powers_of_two dbr:Counter_(digital) dbr:Order_of_magnitude dbr:Philippe_Flajolet dbr:INRIA dbr:Bell_Labs dbr:Data_compression dbr:Unbiased_estimator dbr:Pseudo-random dbr:Streaming_algorithm dbr:Robert_Morris_(cryptographer)
dbo:wikiPageExternalLink
n17:approx_count_3.pdf n19:Flajolet85c.pdf
owl:sameAs
n5:4RYT9 wikidata:Q4781762 yago-res:Approximate_counting_algorithm freebase:m.04y678g
dbp:wikiPageUsesTemplate
dbt:Reflist
dbo:abstract
The approximate counting algorithm allows the counting of a large number of events using a small amount of memory. Invented in 1977 by Robert Morris (cryptographer) of Bell Labs, it uses probabilistic techniques to increment the counter. It was fully analyzed in the early 1980s by Philippe Flajolet of INRIA Rocquencourt, who coined the name approximate counting, and strongly contributed to its recognition among the research community. When focused on high quality of approximation and low probability of failure, Nelson and Yu showed that a very slight modification to the Morris Counter is asymptotically optimal amongst all algorithms for the problem. The algorithm is considered one of the precursors of streaming algorithms, and the more general problem of determining the frequency moments of a data stream has been central to the field.
prov:wasDerivedFrom
wikipedia-en:Approximate_counting_algorithm?oldid=1096313090&ns=0
dbo:wikiPageLength
5475
foaf:isPrimaryTopicOf
wikipedia-en:Approximate_counting_algorithm
Subject Item
dbr:Randomized_algorithm
dbo:wikiPageWikiLink
dbr:Approximate_counting_algorithm
Subject Item
dbr:Flajolet_Lecture_Prize
dbo:wikiPageWikiLink
dbr:Approximate_counting_algorithm
Subject Item
wikipedia-en:Approximate_counting_algorithm
foaf:primaryTopic
dbr:Approximate_counting_algorithm