search

max-mapper / geojson2rtree

generate a static rtree (using terraformer) from a set of geojson features
9 stars 0 forks source link

slows down after about 100K inserts #1

Open max-mapper opened 10 years ago

max-mapper commented 10 years ago

to reproduce, convert ftp://ftp02.portlandoregon.gov/CivicApps/Building_Footprints_pdx.zip to geojson:

ogr2ogr -f GeoJSON -t_srs crs:84 buildings_pdx.geojson Building_Footprints_pdx/PortlandBuildings\\Building_Footprints_pdx.shp

then do geojson2rtree buildings_pdx.geojson and watch it slow down at around 100K

max-mapper commented 10 years ago

cc @jerrysv

calvinmetcalf commented 10 years ago

that is likely an issue with rtree not terreformer

max-mapper commented 10 years ago

oops meant to cc @jerrysievert

JerrySievert commented 10 years ago

agreed with @calvinmetcalf, this rtree implementation starts to slow down on inserts as it attempts to balance the tree.

https://github.com/mourner/rbush may be a bit faster on some imports - but it currently only appears to support search, whereas the version supported by terraformer supports both search and within.

JerrySievert commented 10 years ago

either way, it's still much quicker than my reference rtree implementation that was built to be extremely naive :)

calvinmetcalf commented 10 years ago

the big problem with rbush in this context is that it only supports matching and removing based on reference, not any sort of id, which is annoying when it comes to persisting stuff.

On Fri, Apr 11, 2014 at 2:05 PM, Jerry Sievert notifications@github.comwrote:

either way, it's still much quicker than my reference rtree implementation that was built to be extremely naive :)

Reply to this email directly or view it on GitHubhttps://github.com/maxogden/geojson2rtree/issues/1#issuecomment-40236007 .

-Calvin W. Metcalf

JerrySievert commented 10 years ago

interesting to know about rbush, i hadn't dived in that deep yet.

i've been considering writing a very fast reference implementation of rtree, but have been having trouble finding the time - maybe we can talk while foss4g is going on.

i've also used a ton of other spatial indexes that have been more custom to the data.