{"entities":{"Q2289007":{"pageid":2299750,"ns":120,"title":"Item:Q2289007","lastrevid":57832437,"modified":"2026-04-02T17:38:16Z","type":"item","id":"Q2289007","labels":{"en":{"language":"en","value":"Distributed monitoring of election winners"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7153677"}},"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":"Q2289007$AB598908-F157-4DA5-BD38-8F216AEEAC3A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"507cc13dcb17bd9982ebbf9ea951fb7a44427da9","datavalue":{"value":{"text":"Distributed monitoring of election winners","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2289007$25CA3CA2-C003-41CC-B4C2-46F63E1CB6AF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1f4fc1b7159b2719ac5cd43694297c170c2cc0f9","datavalue":{"value":"1484.91161","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2289007$2956E7ED-C94F-4B61-9B80-6A3587ED817E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b479147a042cf6f9c77a2c92d2edefdc68c8d73d","datavalue":{"value":{"entity-type":"item","numeric-id":2077381,"id":"Q2077381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2289007$37C014D1-C5C8-438D-B9AC-97C1A9BEDD7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9d25c26f84787ccc5df1c15ff2290a9ade6cde48","datavalue":{"value":{"entity-type":"item","numeric-id":519898,"id":"Q519898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2289007$924EB038-9EC4-47AA-A2B7-81AEDD11C838","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"984e6510ec40a363d20e607cce2cc2f8b07918ae","datavalue":{"value":{"entity-type":"item","numeric-id":72340,"id":"Q72340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2289007$893A1917-6E58-4B5C-AAB7-772438595BF9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1edc8f8d7871fd6125d8f3ee3a75e4a85cf754ac","datavalue":{"value":{"time":"+2020-01-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2289007$D9FEB171-FC33-4D5A-A19D-EB64FBBB8332","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"37b0111517bad87fa6069897cd499f33d497653c","datavalue":{"value":"https://arxiv.org/abs/1805.02206","type":"string"},"datatype":"url"},"type":"statement","id":"Q2289007$4FE90D37-9112-46EF-AD7E-9928D6867FF9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"617e6705d0d52202c568e82e30c8a0a4bf878d80","datavalue":{"value":"This paper presents communication-efficient protocols for maintaining approximate winners in distributed vote streams. The communication complexity of general techniques for designing such protocols (namely, sampling-based protocols, protocols based on checkpoints, and protocols based on counting frequencies) have their communication complexity analyzed. Conditions are established under which, using communication which is logarithmic in the number of voters, upon a query at any time the center can immediately return a candidate which is guaranteed to be an approximate winner with high probability. For various single winner voting rules, including variants of approval voting and scoring rules, tournament-based voting rules, and several round-based voting rules, an analysis of how to choose which protocol to use at which scenario, depending on the specific parameters of the problem at hand, is developed. The effect that the number of voters, the number of candidates, the number of sites and the required approximation have on the communication complexity of the protocols is studied. Lower bounds are obtained. An almost tight lower bound for plurality-winner-tracking is derived. It improves the state-of-the-art lower bound for count-tracking. An almost tight lower bound for deterministic protocols for approval-winner-tracking is also derived.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2289007$EC68D6D0-AAFC-4B9D-9781-10B11A6A8655","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e919993fbff234a6243ebde7af0ab81ee44b2bdc","datavalue":{"value":{"entity-type":"item","numeric-id":588820,"id":"Q588820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2289007$1D262B2A-2BDD-42AE-876A-338A9EEE5EAC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"c965de5e9a4b8d63068ca456eb6ad48746668aea","datavalue":{"value":"91B12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2289007$F423F328-F4E1-4A75-858D-13C4D0CDEAB3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3e2208dbe134e3e4e44390b148306ab4110664b9","datavalue":{"value":"7153677","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2289007$020C8FAF-69B1-4139-8463-CC2565B1DDF3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7d59f9270ba2c0b3161162dab212fcc774a42eba","datavalue":{"value":"communication complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2289007$488022F4-05D5-4F75-8E2E-A155E46FB638","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85f872591a35dfedf46e3b8057ffe18d6ef80dc4","datavalue":{"value":"distributed streams","type":"string"},"datatype":"string"},"type":"statement","id":"Q2289007$AD03E028-60C8-4579-BFE5-F56AA6C3B357","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0928f2054c477626979358315b205e680e881a97","datavalue":{"value":"sublinear algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2289007$7FD71DFE-4F9F-4B07-ACB0-699939272F10","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":"Q2289007$DEB507D8-048F-4218-AECA-3AA883BBA874","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"305c7ca4b494273d06bca9a5f9eb32d2dd5e25ce","datavalue":{"value":"W2965040163","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2289007$D7A0E43F-5EDC-4C57-A550-78DC28FF5CCA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1df4c2f8eb8ce3f51ed5c780219abed56adf5cc","datavalue":{"value":{"entity-type":"item","numeric-id":3638026,"id":"Q3638026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2289007$3CCCB1D3-44F6-49D7-BFDD-79F0725EAEA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2dc2404c7842e00ea438d8c5aea04fcad4fea536","datavalue":{"value":{"entity-type":"item","numeric-id":2321258,"id":"Q2321258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2289007$5F2B9F84-E469-41C8-8A80-DD375EA03550","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6af750574281054e35c24770cf364685fca0c11","datavalue":{"value":{"entity-type":"item","numeric-id":3189003,"id":"Q3189003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2289007$077BC34C-8DD7-4BA7-9D97-C41FBB17A3FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5337c728300fd37468247293df08c676f7d5017d","datavalue":{"value":{"entity-type":"item","numeric-id":5395681,"id":"Q5395681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2289007$87D3B2A0-06E2-42D6-B585-8222ECB0A43D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6475a9e3d85ec158be1961f6ceec5c36ea6a5730","datavalue":{"value":{"entity-type":"item","numeric-id":3648865,"id":"Q3648865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2289007$17354C79-5D83-4C63-8465-02078357C42F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c0064c534ff0dd7ac377ac4809b76055aa8114a","datavalue":{"value":{"entity-type":"item","numeric-id":5133010,"id":"Q5133010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2289007$EC07DD05-1F30-47C1-A8FB-969F01C16482","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f7b624cf5dd8ad7a653a9ca8528414959e851ea","datavalue":{"value":{"entity-type":"item","numeric-id":2289007,"id":"Q2289007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2289007$0234C71E-9D98-41C1-B159-A4568FCAF51B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ec4896edc35f1e12505542682c8c6b6145a21f0","datavalue":{"value":{"entity-type":"item","numeric-id":4875692,"id":"Q4875692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2289007$9DE04671-35B1-4278-90A7-FE76B9A934AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f14494c679f0829d575d128225f740222c3bd2a","datavalue":{"value":{"entity-type":"item","numeric-id":646535,"id":"Q646535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2289007$16AE7CAB-2E3B-4A00-9EAA-0DC6425E9E7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e3c65bbb5ff0ac7741aafe0c47a1d743ba6f77f","datavalue":{"value":{"entity-type":"item","numeric-id":5259198,"id":"Q5259198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2289007$7E0F448B-1B7D-40A6-AC59-AF2B3A5989D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b060c3e2abccf62b44726c04641cd7a02d0640e7","datavalue":{"value":{"entity-type":"item","numeric-id":3095333,"id":"Q3095333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2289007$D80D4797-7048-4D20-A085-8EA3613522A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ff5165449a8d8c026760585d0dbb0cd0eae0eab","datavalue":{"value":{"entity-type":"item","numeric-id":3007558,"id":"Q3007558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2289007$F0040C9B-1A47-464E-82B3-7AEC8E76762D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51a1fd74246e134782e0de40f0b6b4723714a3aa","datavalue":{"value":{"entity-type":"item","numeric-id":1939670,"id":"Q1939670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2289007$19AF3C3F-13F1-4707-9E52-10F1D47362C5","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"87766dbc567c7e27000fb0cad8484c1c75b8535c","datavalue":{"value":"Q127408325","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2289007$B327C795-614E-4244-B476-1BC04D2FBDDE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"42d5cde52d843f2db4fc5ecf7c467e6e3bd6a6d8","datavalue":{"value":"10.1016/J.ARTINT.2019.07.007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2289007$03B4E7D5-12DB-49D6-B0AA-D1B8931D07F3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c5763e1827cab049e1f99b55523138fdc33a662","datavalue":{"value":{"entity-type":"item","numeric-id":3431448,"id":"Q3431448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce26480fad361077804a59444353137f4c77f714","datavalue":{"value":{"amount":"+0.799498975276947","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2289007$9FC4914A-969F-4734-92AF-50CB3B2E80CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ace3642e2284b3032c236aa552701add234428b","datavalue":{"value":{"entity-type":"item","numeric-id":5919369,"id":"Q5919369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d540065b8e674e61843544cc184ea164be0765c9","datavalue":{"value":{"amount":"+0.7667946219444275","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2289007$FF255530-B6B2-42AF-A1D4-1A7A2FD69EE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83db7f2654349783a1d5aaf9dd4c975408ad5fd2","datavalue":{"value":{"entity-type":"item","numeric-id":5919030,"id":"Q5919030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff602f903015176a2c1b37de1eef6f8a9cff826b","datavalue":{"value":{"amount":"+0.7644372582435608","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2289007$32FC1F54-7322-4706-B174-9357120E1245","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"03db5cdcf37494e632c2a0d4c2d751c5787ae4e8","datavalue":{"value":{"entity-type":"item","numeric-id":1761297,"id":"Q1761297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b653c94a556c9be2d09f7278d7cb3b0910634a5","datavalue":{"value":{"amount":"+0.7366544604301453","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2289007$FD93A67D-A1C3-4F21-8CEF-257845851E1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f54eb30389d144acabb46938497a8b361f0d01f","datavalue":{"value":{"entity-type":"item","numeric-id":1617674,"id":"Q1617674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bece084f711866fc0b15e7f0095f85f926f03a5b","datavalue":{"value":{"amount":"+0.7336012721061707","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2289007$C36263EA-8D76-44AF-9A9C-2228DE28799F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2289007","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2289007"}}}}}