Re:Fast Database Emerges from MIT Class, GPUs and Student’s ...
by corresation on Tuesday April 23, 2013 @08:18PM
(#5598832)
It 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.
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)