Communications of the ACM
Best-Ever Algorithm Found For Huge Streams of Data
Researchers last fall created a near-perfect streaming algorithm that operates by recalling only enough of what it has seen to relate what it has observed most frequently.
Credit: Antoine Dor/Quanta Magazine
A multi-institutional research team last fall created a near-perfect streaming algorithm that operates by recalling only enough of what it has seen to relate what it has observed most frequently.
The researchers note a key principle of previous streaming algorithms is dividing them into sub-algorithms. "Instead of spending 50 million units of time looping over the entire universe, you only have four algorithms spending 100 units of time," says Harvard University's Jelani Nelson. However, he notes the main drawback to this approach is the difficulty of extracting the right small numbers to recombine in order to yield the correct big number.
Nelson and colleagues instead package each two-digit block with a small tag that consumes little memory while permitting the algorithm to properly reassemble the two-digit pieces.
The researchers also use an expander graph to boost the likelihood of correctly connecting the chain of two-digit blocks into the right number.
From Quanta Magazine
View Full Article
Abstracts Copyright © 2017 Information Inc., Bethesda, Maryland, USA
No entries found