4 ms·
Ask HN: What are your favourite geospatial algorithms?
I'm developing with a metric ton of polygon data. As with anything in our field I've been tasked with making our products faster / more scalable.
I don't want to reinvent the wheel and I want to see what algorithms are out there for my perusal. I'd prefer original published papers if you've got links like that.
- ghotli 16y agoHere's a good one I read the other day. Optimal Partitioning for Efficient I/O in Spatial Databases "It is desirable to design partitioning techniques that minimize the I/O time incurred during query execution in spatial databases. In this paper, we explore optimal partitioning techniques for spatial data for different types of queries, and develop multi-disk allocation techniques that maximize the degree of I/O parallelism obtained during the retrieval. We show that hexagonal partitioning has optimal I/O cost for circular queries compared to all possible non-overlapping partitioning techniques that use convex regions. For rectangular queries, we show that although for the special case when queries are rectilinear, rectangular grid partitioning gives superior performance, hexagonal partitioning has overall better I/O cost for a general class of range queries. We then discuss parallel storage and retrieval techniques for hexagonal partitioning using current techniques for rectangular grid partitioning." http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.8088 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.8...
- mattew 16y agoWhat are you currently using for storing/accessing your spatial data?
- ghotli 16y agoDepends on the purpose. Our GIS department uses PostGIS for one off analysis. Our interactive mapping engine uses Shapefiles with quadtree indexes.
- oomkiller 16y agoIf you are new to GIS, PostGIS would probably be a good implementation to review.