Stories
Slash Boxes
Comments

SoylentNews is people

posted by martyb on Monday January 08 2018, @05:07PM   Printer-friendly
from the YAA!-Yet-Another-Algorithm! dept.

From Quanta Magazine:

To efficiently analyze a firehose of data, scientists first have to break big numbers into bits.

Computer programs that perform these kinds of on-the-go calculations are called streaming algorithms. Because data comes at them continuously, and in such volume, they try to record the essence of what they've seen while strategically forgetting the rest. For more than 30 years computer scientists have worked to build a better streaming algorithm. Last fall a team of researchers invented one that is just about perfect. "We developed a new algorithm that is simultaneously the best" on every performance dimension, said Jelani Nelson, a computer scientist at Harvard University and a co-author of the work with Kasper Green Larsen of Aarhus University in Denmark, Huy Nguyen of Northeastern University and Mikkel Thorup of the University of Copenhagen. This best-in-class streaming algorithm works by remembering just enough of what it's seen to tell you what it's seen most frequently. It suggests that compromises that seemed intrinsic to the analysis of streaming data are not actually necessary. It also points the way forward to a new era of strategic forgetting.

Small numbers are easier to keep track of than big numbers.

Imagine, for example, that you're monitoring a stream of numbers between zero and 50,000,000 (a task similar to logging internet users by their IP addresses). You could keep track of the numbers using a 50,000,000-term index, but it's hard to work with an index that size. A better way is to think of each eight-digit number as four two-digit numbers linked together. Say you see the number 12,345,678. One memory-efficient way to remember it is to break it into four two-digit blocks: 12, 34, 56, 78. Then you can send each block to a sub-algorithm that calculates item frequencies: 12 goes to copy one of the algorithm, 34 goes to copy two, 56 goes to copy three, and 78 goes to copy four. Each sub-algorithm maintains its own index of what it's seen, but since each version never sees anything bigger than a two-digit number, each index only runs from 0 to 99. An important feature of this splitting is that if the big number — 12,345,678 — appears frequently in your overall data stream, so will its two-digit components. When you ask each sub-algorithm to identify the numbers it has seen the most, copy one will spit out 12, copy two will spit out 34, and so on. You'll be able to find the most frequent members of a huge list just by looking for the frequent items in four much shorter lists.

I wonder if any Soylenters have heard of similar solutions.

Full Article
The paper at arxiv.org


Original Submission

 
This discussion has been archived. No new comments can be posted.
Display Options Threshold/Breakthrough Mark All as Read Mark All as Unread
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
  • (Score: 0) by Anonymous Coward on Monday January 08 2018, @09:14PM

    by Anonymous Coward on Monday January 08 2018, @09:14PM (#619706)

    Each guy on the assembly line only knows about the part he is making. He doesn't see the final product. But he knows every detail of that bracket he just made down to the millimeter. Maybe the word is specialization. Delegation? But where context matters, you can't lose sight of the peripheral outside your cubicle. Computers can handle indefinite number of inputs at once, and filter out a lot less than the brain has to. Inside, this is how the brain functions anyway. Unfortunately it does too good a job, so we have to build these infernal contraptions (frequency shifters, compressor/expanders is all they are) to see and hear all the "invisible/silent" shit! We wouldn't need them if we would just open our minds to the cacophony around us, the beeping and flashing lights, beeping, and flashing, I can't take it anymore!