3 ms·
Fantastic project, and this absolutely sounds like an embarrassingly parallel processing task. To the original itch, so to speak- "Then he plotted the Islamist
by corresation 14y ago
Fantastic project, and this absolutely sounds like an embarrassingly parallel processing task. To the original itch, so to speak-
"Then he plotted the Islamist indicators from 40 million tweets, ranging from August 2011 through March 2012, against 5,000 political districts from the Egyptian census."
So the core problem is that you have 5,000 non-overlapping polygons and you want to determine from an x,y which they fall within? I have to confess that I'm surprised that just 40 million such points would take several days.
- Someone 14y agoLet's assume a naive approach. Also, assume each point falls within a polygon. For every point to test, you need, on average, to test half the polygons. Testing a point against a polygon means testing the point against, on average, about half the polygon's edges. Each of those tests takes a multiplication, an addition, and a comparison. That's 4E7 points times 2500 polygons times, at least, 1.5 edges. Total: 1.5E11 multiplications, additions, and comparisons. With 100-sided polygons, it would be 1E13 or so multiplications/addition/comparison steps. Memory pressure is dominated by polygon storage. 5000 poly's, 100 points each, is 500,000 edges at two doubles each, or 4MB. That fits comfortably in cache. So, 1E9 multiplications/addition/comparison steps a second should be possible. That's 10,000 seconds or 3 hours. => Should be doable on one CPU in hours (famous last words)
- corresation 14y agoIt really is a fascinating sounding problem and I'd really like to see the source data (regions and points), if I'm understanding the problem right, to discern alternative approaches.