tag:blogger.com,1999:blog-6555947.post6573494347228384192..comments2024-09-11T05:56:17.068-06:00Comments on The Geomblog: Finding the right reference for finding the majority elementSuresh Venkatasubramanianhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-6555947.post-87666489985892704782011-09-25T16:55:22.055-06:002011-09-25T16:55:22.055-06:00@Anonymous: finding the most frequent elements is ...@Anonymous: finding the most frequent elements is certainly not trivial in the streaming model, i.e., when the algorithm is allowed to make a single pass and use limited storage. Misra-Gries algorithm, although simple, is an elegant solution to this problem.Piotrhttp://people.csail.mit.edu/indyk/noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-84025574958475131602011-09-25T16:11:27.400-06:002011-09-25T16:11:27.400-06:00It is true that the algorithm is not particularly ...<i>It is true that the algorithm is not particularly time-efficient:</i><br /><br />...and that is exactly the problem. Finding the most frequent element is trivial if time & space are not extremely limited.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-59327642567501260772011-09-25T14:08:53.371-06:002011-09-25T14:08:53.371-06:00@Anonymous: I am not sure why you believe that the...@Anonymous: I am not sure why you believe that the Misra-Gries algorithm, as proposed in the paper, does not work in the streaming model. <br />The algorithm (4) on page 5 of the <br /><a href="http://www.ecommons.cornell.edu/bitstream/1813/6345/1/82-505.pdf" rel="nofollow">technical report</a> considers all elements in the stream, in arbitrary order, and for each element performs the appropriate counter updates. <br /><br />It is true that the algorithm is not particularly time-efficient: processing each element takes time O(k) or so. Still, this leads to roughly O(1/eps) update time when searching for elements that appear at least eps n times. This is not too bad if eps is not too small. Of course, we do know now how to do this much faster, as per the references you mentioned.Piotrhttp://people.csail.mit.edu/indyk/noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-10903925710613985512011-09-24T10:26:18.494-06:002011-09-24T10:26:18.494-06:00It should be observed that the generalization of t...It should be observed that the generalization of the majority algorithm for k counters as proposed by Misra-Gries doesn't work in the data stream model. <br /><br />As Graham points out Karp et al. discussed this issue and Demaine et al. actually propose data structures to make the updates happen in O(1) time. <br /><br />For tight bounds on the performance of the generalized algorithm we have those in Demaine et al. in the stochastic model and the those of Bose et al. for the adversarial model, both of which are tight. <br /><br />This is clearly a case where single authorship (except for the vanilla majority algorithm which clearly belongs to Booyer and Moore) is hard to assign to a single group.<br /><br />The k-counter algorithm as we use it today would be best described as the Misra-Gries-Karp-Papadimitriou-Shenker-Demaine-Lopez-Ortiz-Munro-Bose-Kranakis-Morin-Tang frequent items algorithm [or MGKPSDLMBKMT for "short" :) ]Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-4089028856761415622011-09-24T03:18:39.986-06:002011-09-24T03:18:39.986-06:00Cool. What's interesting also is the connectio...Cool. What's interesting also is the connection between Boyer/Moore and Misra/Gries, as outlined in the link.Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-6555947.post-69303376095327173132011-09-24T03:16:21.451-06:002011-09-24T03:16:21.451-06:00I did my best to reconstruct the history surroundi...I did my best to reconstruct the history surrounding this area when I surveyed the topic. See Sections 3.1 and 3.2 of <br />http://www.dimacs.rutgers.edu/~graham/pubs/papers/freqvldbj.pdf<br /><br />GrahamHughhttps://www.blogger.com/profile/08767952337717767032noreply@blogger.com