2 ms·
The problem is less with the mathematics, but efficient storage and retrieval of a large number of points (i.e. index won't fit in memory) from disk. Doing a se
by falcolas 12y ago
The problem is less with the mathematics, but efficient storage and retrieval of a large number of points (i.e. index won't fit in memory) from disk. Doing a search across a tree rendered to disk is really slow.
Even with mathematically sound storage trees as indexes, locations which are close in space could easily be split between two arms of the tree, making proximity searches quite expensive - you would have to traverse the entire tree to ensure that you do not miss data separated by a poor splitting plane.
There are a number of theoretically efficient solutions to this, but they are all become remarkably inefficient when you add in a hard drive.
- gobengo 12y agoI think if you're going to be doing sufficiently 'biggish data' with those kind of retrieval charcteristics, you've got to just give up on disk and use flash only.
- falcolas 12y agoFlash solves the "added overhead for random access" portion of the problem, but the overhead for any access at all is still remarkably high, particularly when compared to main memory. Perhaps when we get more "flash connected to the main bus" options (there are a few commercial options which sit in PCI Express, AGP, and even DRAM slots), we can begin discounting the overhead more and more, but we're not there quite yet.
- joe_the_user 12y agoWell, supposedly, cache-oblivious algorithms exist to deal with this kind of thing - by grouping related data together regardless of exactly what cache-scale you are at.