{"entities":{"Q1057061":{"pageid":1058909,"ns":120,"title":"Item:Q1057061","lastrevid":69530109,"modified":"2026-04-13T07:37:58Z","type":"item","id":"Q1057061","labels":{"en":{"language":"en","value":"Approximate counting: a detailed analysis"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3896294"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057061$501FD1FB-48BD-41F0-BACD-455B0BAD059D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6033f02c66300d62710941827641fcb3fa92fe42","datavalue":{"value":{"text":"Approximate counting: a detailed analysis","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1057061$F7AC88FE-4DD0-46F6-8150-F9DFEFC6160A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0a8054fc56e21a3d89d3fae98e19140985b79d4a","datavalue":{"value":"0562.68027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1057061$2B1B4B00-EA1D-48DC-8C5F-A6ED633D47E8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b9fdcf064e2451cf174de29a9129cfac5197426f","datavalue":{"value":"10.1007/BF01934993","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1057061$430BE88A-BA67-46EC-B1D1-C4F788CE6F67","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d4e841897d4c74a0c7a579f2ae2fa0af6ee543a6","datavalue":{"value":{"entity-type":"item","numeric-id":640841,"id":"Q640841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057061$6B77BA96-5F49-4117-AD7C-F7B9B2832ACE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e560271c921b84b65a9b7f0d3fa6830623f8af8b","datavalue":{"value":{"entity-type":"item","numeric-id":188629,"id":"Q188629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057061$81D958C0-30F2-41DD-AD4B-408CB8B463E3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1057061$CF7C3C5D-5939-4292-835A-331001E5E248","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"516d79e0c8a90bba9c974914f211c2d59e18e414","datavalue":{"value":"Approximate counting is a probabilistic algorithm proposed by \\textit{R. Morris} [Commun. ACM 21, 840-842 (1978; Zbl 0386.68035)] that allows the storage of (many) large counts in small counters. The algorithm allows counting up to some integer n in space \\(\\approx \\log_ 2\\log_ 2n+\\delta\\) with a constant expected relative accuracy that is \\(O(2^{- \\delta /2})\\). For instance, using only 8 bits, one can count up to \\(2^{16}=65536\\) with an accuracy of about 15 \\%. The paper presents a complete analysis of the algorithm which is equivalent to a pure birth process with discrete time and birth probabilities of the form \\(2^{- k}\\). The probability distribution of the approximate result is characterized exactly and is also shown to tend to a limiting distribution. Mean and variance of the result are estimated asymptotically using a combination of: (i) combinatorial identities in the theory of integer partitions; (2) Mellin transform techniques. The paper concludes with a comparison of approximate counting with direct sampling methods. One should also note that related methods appear in the space-efficient simulation of deterministic machines by probabilistic machines (Freivalds, Gill).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1057061$D4E0B782-BFD1-4B98-9527-C7CC87ABD51D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1057061$34957A62-6364-418A-9704-11AE7C4F6FAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9ed1e3c6cced595a05b8ae19055521b22405b78a","datavalue":{"value":"68W99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1057061$350E37B1-23DD-459C-BCDF-04EE13921F14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ec3769495799f08479987ac368adf64f125a2b66","datavalue":{"value":"68N25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1057061$FEBAD1E9-DD5E-40C1-8D3E-02CF398F8DA0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f6597add48ccde20bf7f2b46ed4f0d43ba5fdf95","datavalue":{"value":"3896294","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1057061$70F610BD-908E-48FE-97C2-A14E4A390A4F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90bc349d6d55eb8026148892e900ce256ffdd986","datavalue":{"value":"analysis of algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1057061$C1EE8BFD-47A9-44EF-BBCD-5B12CE762201","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb5a9c7e00e3e0a60ce1f321dc845779527523a4","datavalue":{"value":"combinatorial analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1057061$48D929B9-F2FD-4E7D-9AD5-189357FE8438","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"98b1a0adf4594e4a246bb06d28df41a4332eb77d","datavalue":{"value":"estimation methods","type":"string"},"datatype":"string"},"type":"statement","id":"Q1057061$CC2A1254-0EB7-416E-AA5E-AC0EC9CFD4F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"39067a815709c092a11d330d2b17e40f9f205e81","datavalue":{"value":"probabilistic algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1057061$9F0CDDE8-84AB-4E84-BF21-1C2E9EF37F30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea67f58db3915bfaa48b97edb2da21c82e510843","datavalue":{"value":"birth process","type":"string"},"datatype":"string"},"type":"statement","id":"Q1057061$AF263B76-5B05-420A-A92D-A0598E7733FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ef99431d77b1ef758195f0ff12c978bae2746ca","datavalue":{"value":"Mellin transform","type":"string"},"datatype":"string"},"type":"statement","id":"Q1057061$F83B2C10-14DE-4DEB-A00F-8C6EAD9DB9C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90b8a09be57ae85ca4701e8363941e782083b4db","datavalue":{"value":"approximate counting","type":"string"},"datatype":"string"},"type":"statement","id":"Q1057061$C789C8E1-2076-4538-A0B1-0E3C330585E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53be23f79b8a43df438be76f5801e0e1024ea7b0","datavalue":{"value":"direct sampling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1057061$ABECA4B3-FD32-49A9-9140-DD2A6489C280","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"29a72efcc1cd20fb342bf2c8acf5cd1030ea8474","datavalue":{"value":"Q57482531","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1057061$1F79AD2D-D604-489D-9008-C8899C3BF2A7","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057061$62128768-6963-4676-ADF2-6C236DC4265A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9de3b29bb5c9f720a2b77119f7bc890f7e8f1200","datavalue":{"value":{"entity-type":"item","numeric-id":5850027,"id":"Q5850027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057061$47D40855-0AA8-4EAE-92E6-30BA7A260B67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3fa90bf11e04487b48a872f3c997442fb817587","datavalue":{"value":{"entity-type":"item","numeric-id":4184761,"id":"Q4184761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057061$CEBC7067-F51F-489C-AFE6-83D9B1CA9AD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57a6c0e7a26949a8957779ce100a4ad0c151e7ea","datavalue":{"value":{"entity-type":"item","numeric-id":4134686,"id":"Q4134686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057061$4DBB981A-FFEB-432B-9E0F-FFC92E41F5AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff81489e80366438468bf6dfe10c7a159bc3ea8c","datavalue":{"value":{"entity-type":"item","numeric-id":4057549,"id":"Q4057549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057061$30C722B7-56CF-4DB9-BE2B-D6256CC079A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c9d4d8ce94357a0e5da9ae60a11d798e22a7ac4","datavalue":{"value":{"entity-type":"item","numeric-id":3905196,"id":"Q3905196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057061$587E4BBF-D969-4F54-BEFE-2DEA86FBFCF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1df672fbbe25f8544c9b4a7e90aeef67bbbe756","datavalue":{"value":{"entity-type":"item","numeric-id":4167561,"id":"Q4167561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1057061$3FA1DCA4-8234-4E17-B7B7-1A3124EE57A3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b0d3d2908c6ba02b2feb2a7b3ea079115e4abc8d","datavalue":{"value":"https://doi.org/10.1007/bf01934993","type":"string"},"datatype":"url"},"type":"statement","id":"Q1057061$7A275F17-9E3B-4406-BC50-F049A8D0F377","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"eb81e02d56668956fbf68486ace687ffb4b24767","datavalue":{"value":"W2166332856","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1057061$7C80C5FC-D2DC-4E06-9449-14E80ADACC8E","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"456eb6cf2e4dab7e6637ba900e6e308f0df41664","datavalue":{"value":"journals/bit/Flajolet85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1057061$132ED482-10AE-46BA-9139-EA32CFEC90F7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2d3d946f394f862478865e653a51f88a6e06520","datavalue":{"value":{"entity-type":"item","numeric-id":441872,"id":"Q441872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eed46389ee2af6fd36854f17cd8dc45c4968a1eb","datavalue":{"value":{"amount":"+0.9327924","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1057061$5B6CD121-A1E4-497E-B942-E6182318F858","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bde3537933afa0952c0c966f099870cfc9fa12e4","datavalue":{"value":{"entity-type":"item","numeric-id":3358234,"id":"Q3358234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b846ef76e042d78249da0023cf81e9101437890","datavalue":{"value":{"amount":"+0.93217736","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1057061$9DE84B29-F2F8-41CA-85DC-786DDE295407","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69b60ff8f09c47344749f029ef232382afd54498","datavalue":{"value":{"entity-type":"item","numeric-id":2474230,"id":"Q2474230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa3a782b7d1834c9c8f3bc59a45c74759b0f455c","datavalue":{"value":{"amount":"+0.91385424","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1057061$44742888-6C63-4278-A2B7-1DCFB90B050F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c5032e3bbe0a8231a4821c7a55eeebb44711373","datavalue":{"value":{"entity-type":"item","numeric-id":307930,"id":"Q307930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ac5771a7d8742e8199f16ccc2a87fe8360c7b16","datavalue":{"value":{"amount":"+0.9081203","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1057061$86031CDA-CB51-4F04-800D-8797909DC3A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a25bd6cad9fb2eac922649fbf9d3976dfee8ef69","datavalue":{"value":{"entity-type":"item","numeric-id":3800016,"id":"Q3800016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d39bf58a39a4e843c735a2a6b4daee64c0536f38","datavalue":{"value":{"amount":"+0.8955461","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1057061$57259E3F-A0FE-42B8-8897-17195FBDA86C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f163bc679675f8122ea64b25472f5bb694b607e9","datavalue":{"value":{"entity-type":"item","numeric-id":1114675,"id":"Q1114675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d39bf58a39a4e843c735a2a6b4daee64c0536f38","datavalue":{"value":{"amount":"+0.8955461","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1057061$44D5ACB8-5A3E-4248-9C43-C234B51508FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05b630f5fc5c31b82dd2e8d4efb70d78fbf17b8a","datavalue":{"value":{"entity-type":"item","numeric-id":5422312,"id":"Q5422312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"528ae66c8bb410f2fdabbe0c9769d9ef1d96477b","datavalue":{"value":{"amount":"+0.89453256","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1057061$810B80EF-B995-40AE-A3EA-AC261827E395","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"806868755af376e21bf0a343101e9573e6fafb57","datavalue":{"value":{"entity-type":"item","numeric-id":6161056,"id":"Q6161056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71701b77e88e2c1c7147f3a7182385a84d20e02a","datavalue":{"value":{"amount":"+0.89391017","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1057061$49A279C2-64CD-44D1-8200-DA2587AD03CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"404f42d77497a35434e66b015049beb91f8e54ed","datavalue":{"value":{"entity-type":"item","numeric-id":4352952,"id":"Q4352952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"593eb6770c6b9a85fa495e8db2cbe606136b9e4e","datavalue":{"value":{"amount":"+0.8931315","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1057061$F7DDC5A8-8ADA-4457-9C38-129FB3139772","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dfa797513efdfb2c08d31b0b11e283a086adaa43","datavalue":{"value":{"entity-type":"item","numeric-id":4358435,"id":"Q4358435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3383f79ea67fb8c213f5dfac4a1341415a063d33","datavalue":{"value":{"amount":"+0.8878325","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1057061$AD63B024-6C49-435F-AE65-35CC80145ACE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Approximate counting: a detailed analysis","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Approximate_counting:_a_detailed_analysis"}}}}}