I’m having fun posting this from my iPhone, in NYC. Nate Irwin and I are working on implementing r-tree spatial indexing in Javascript.
Some quick testing proved that building an index clientside was too slow, so we’re building the r-tree serverside and serializing to Json.
On a 6500 feature dataset we’re getting .01s (FF) to .03s (IE) search times — fast enough for on-mouse-move GUI response.
The only caveat is that JSON nodes consisting of integer IDs and double-precision bounding-boxes run ~85 bytes per feature. Above 2500 features you must consider wire-size. Including attribute data would quickly bring this over the top.
However, optimizing the leaf node structure for point data and g-zipping the r-trees should run <3 bytes per feature — making clientside indexing of 100,000+ features within reason.
October 12, 2008 at 6:15 pm |
Quite reasonable numbers. Thanks.
What do you exactly mean under ‘wire-size’? Throughput of the comm channel?
October 13, 2008 at 12:25 am |
yup. Wire time = download time / bandwidth costs.
October 29, 2008 at 9:10 pm |
It looks like my thoughts on compressed rtree sizes were a bit ambitious. Point-optimized leaf nodes and g-zip compression yeilded ~30 bytes/feature using decimal degree data.
Either I dropped a zero in my initial musings, or we’re seeing wildly different gzip compression ratios with demical degrees vs UTM data.
That said, 10k features might be the limit of reason for this technique, depending on how many digits of precision your bounding boxes require.
November 3, 2008 at 2:52 pm |
[...] rtrees, part 2 In my previous post, I talked about using r-trees in JavaScript for fast client-side spatial indexing. The idea is a [...]
November 25, 2008 at 10:42 pm |
Interesting…
Could Google’s polyline encoding help here?
http://code.google.com/apis/maps/documentation/polylinealgorithm.html
It does wonders for volumes of spatial data. I’ve got it wired up to test VE and Google Maps and can squeeze Greater Sydney’s suburb polygons into ~60k of dynamically generated javascript code. I’m using SQL Server 2008 at the back for the spatial query and dynamic DP thinning of the nodes. Doing the spatial query in the front end would be awesome – then you could just pull pre-thinnned, encoded polygons as required – fast would not be the word…
http://www.minus34.com/cgtest/encoded.htm (panning isn’t quite 100% yet)