{"entities":{"Q7361460":{"pageid":31519919,"ns":120,"title":"Item:Q7361460","lastrevid":105366638,"modified":"2026-10-07T13:36:41Z","type":"item","id":"Q7361460","labels":{"en":{"language":"en","value":"Verification of the CVM algorithm with a New Recursive Analysis Technique"}},"descriptions":{"en":{"language":"en","value":"AFP entry CVM_Distinct_Elements"}},"aliases":{},"claims":{"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8c19e8d3b6737238f536dfaf57fe06185e9cb09a","datavalue":{"value":"https://isa-afp.org/entries/CVM_Distinct_Elements.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q7361460$A4137BBD-82DB-4814-89C3-5035501012FD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4eadad38579231afe6fd5d0ce960f90944b60efd","datavalue":{"value":{"time":"+2025-02-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q7361460$E94FF517-ACD9-481D-8F5F-A0D99755791F","rank":"normal"}],"P43":[{"mainsnak":{"snaktype":"value","property":"P43","hash":"08e34730e8843d863438c2ad5795ad3f0ee72024","datavalue":{"value":"Emin Karayel","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361460$8CE9C389-DD1C-4BB9-892F-81A7EFC4475D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"b0fed39dfeba4f0e7b7348526029268a1d6bc9b3","datavalue":{"value":"Derek Khu","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361460$8E21E38B-8D0D-49E4-A160-A6CD82E91215","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"cc1154c60094c33df1c352195921cc25d0aa443b","datavalue":{"value":"Kuldeep S. Meel","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361460$299277BA-AB84-47D9-A9BF-E0192C393890","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"d9ef184945389dfe82f21c38f697f4e88ed3433f","datavalue":{"value":"Yong Kiam Tan","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361460$83FDC90E-5C9F-4474-937A-09D3A030F346","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"8f52072c0e2227197b15981bb8e70f05a1629eb5","datavalue":{"value":"Seng Joe Watt","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361460$BC36C9EA-7AC2-4FF4-AFF0-B76B7ECA925D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"af1a0182e7eb31f6042292968849766000af654b","datavalue":{"value":{"text":"Verification of the CVM algorithm with a New Recursive Analysis Technique","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q7361460$8D79C093-0739-4D35-92D1-6F106034179E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4f366dd27ad6b16160ce90d62324e79a878a4742","datavalue":{"value":"In 2022, Chakraborty et al. published a streaming algorithm (henceforth, the CVM algorithm) for the distinct elements problem, that deviated considerably from the state-of-the art, due to its simplicity and avoidance of standard derandomization techniques, while still maintaining a close to optimal logarithmic space complexity. In this entry, we verify the CVM algorithm's correctness using a new technique which simplifies the analysis considerably compared to the orignal proof by Chakraborty et al. The main idea is based on a probabilistic invariant that allows us to derive concentration bounds using the Cram\u00e9r-Chernoff method. This new technique opens up the possible algorithm design space, and we introduce a new variant of the CVM algorithm, that is total, and also has an additional property in addition to concentration: unbiasedness. This means the expected result of the algorithm is exactly equal to the desired result. The latter is also a new property, that neither the original CVM algorithm nor classic algorithms for the distinct elements problem possess.","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361460$9C9B8350-1D91-4DB9-B90C-DFB233C2B5F8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7370dd51ea10b3286bcdacb82f7c7809db2343c","datavalue":{"value":{"entity-type":"item","numeric-id":6969649,"id":"Q6969649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361460$4528CFAF-1A13-4DB5-88F7-5B04F141F2A1","rank":"normal"}],"P37":[{"mainsnak":{"snaktype":"value","property":"P37","hash":"9a21a8eebe97539644aa32b24dda137c12e751dc","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361460$AD7D0BD2-96BF-4B49-8588-407F13E85200","rank":"normal"}],"P585":[{"mainsnak":{"snaktype":"value","property":"P585","hash":"e1b73618a61402a5b82d73704cc79ca873e09101","datavalue":{"value":{"entity-type":"item","numeric-id":7361684,"id":"Q7361684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361460$D8E0987A-8E3A-4C28-8AF4-AB3DE655812C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"578256d84e19da5698645d1ccf3bebddac8d4ec2","datavalue":{"value":{"entity-type":"item","numeric-id":7361325,"id":"Q7361325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361460$B40BB938-F453-4625-B027-538CE9F7594F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"db2f027ce37e64078e30403d319f909accdb9142","datavalue":{"value":{"entity-type":"item","numeric-id":7361146,"id":"Q7361146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361460$BB9E83A3-F835-4F4C-9C43-D5D49A015AA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"568df032e4fa5e393d3cafa654f178d211e1f6f1","datavalue":{"value":{"entity-type":"item","numeric-id":7361689,"id":"Q7361689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361460$30261466-66C0-4717-961D-275ACF548330","rank":"normal"}],"P2651":[{"mainsnak":{"snaktype":"value","property":"P2651","hash":"83587c66a63f16aa6d09e1e557ca61651a36a985","datavalue":{"value":{"entity-type":"item","numeric-id":7360782,"id":"Q7360782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361460$3EC7E207-8198-40B9-A722-8BF91C3AEBDC","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"908c3454b3659c4b140ccce33c5aee31081edc8d","datavalue":{"value":{"entity-type":"item","numeric-id":5976450,"id":"Q5976450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361460$8FAD1127-BD99-4660-9241-072B4A38F24A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Verification of the CVM algorithm with a New Recursive Analysis Technique","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Verification_of_the_CVM_algorithm_with_a_New_Recursive_Analysis_Technique"}}}}}