Pages

Tuesday, May 29, 2012

SBN Mystery - Solved!

Last October I asked you all for help in figuring out the spatial indexing algorithm used to create Esri sbn files.  Using Pyshp, I had successfully decoded the file formats which I provided. However I could not figure out the algorithm used to create and populate the spatial bins within these files.

Today I'm pleased to announce this challenge has been answered.  The GIS community now has access to both the sbn and sbx file format as well as the algorithm for grouping features in a shapefile into "spatial bins".

I'm glad I asked for help as this challenge turned out to be quite difficult. The brain behind this operation is Marc Pfister with some good insights from Si Parker.  Marc worked tirelessly on this problem for months with a cross-country move and complete career change thrown in to make it interesting.  Marc did all the heavy intellectual lifting with me playing an inquisitive, but usually short-sighted Watson to his Holmes.  I generated endless series of shapefiles and one-off scripts to help Marc try and flush out the algorithm based only on subtle changes in the number of bins and features they contained as well as his past experience with spatial indexing.

When I figured out the file formats I had hoped I was just a Wikipedia search away from recognizing the spatial tree algorithm.  But the solution turned out to be much more complex than that.  Esri uses a sort of balanced tree that exhibits traits of several different algorithms.  The system seems carefully designed but is by no means obvious.  I will publish Marc's findings as soon as I can.

There are still a few shapefile cases which create puzzling but insignificant results. However we are at the 98% mark. The project goal of compatibility has been reached.  There is no longer any reason to hold off on sharing the results.  We are fairly certain that we are able to create sbn and sbx files which sufficiently fool ArcMap as well as other Esri packages so other software can read, use, and generate these indexes alongside the Esri suite.  There is more testing to do but it seems we are out of the woods.

What we haven't done is nicely packaged all of this work up.  But Marc posted a small set of Python scripts on github which demonstrate the algorithm and file handling needed to copy this capability.  Over the coming months I will fold this code into Pyshp, produce better documentation on the algorithm, and provide posts on how to deal with these indexes. But for now here's what you've been waiting for:

https://github.com/drwelby/hasbeen

By the way, Marc does freelance programming.  In my job, I get the opportunity to work with lots of really bright geospatial programmers and mathematicians and this guy is one of the very best I've ever seen.  If you have a tough geospatial project and need some E=MC2 smarts definitely look him up.

25 comments:

  1. Really nice job guys and thanks for the hard work ! I'm happy to announce that I've just added read support for .sbn files in GDAL/OGR trunk. See http://trac.osgeo.org/gdal/ticket/4719 for the details. It seems to work great, but external testing and/or code review would be very much appreciated.

    The only detail that I had a bit difficulty to figure out and that was not explicitely explained in your blog entries or in the hasbeen code was the relationship between the bins and the nodes, and especially the notion of "continuous bins", that is to say that if a node in the tree has more than 100 shapes, then it is described into several bins in the .sbn.

    ReplyDelete
  2. Very good designed blog and postings with super cool photos.

    ReplyDelete
  3. I recently found many useful information in your website especially this blog page. Among the lots of comments on your articles.procurement software

    ReplyDelete
  4. Good post. I was checking consistently this blog and I am impressed. Quite useful information specially the final component.sharepoint alternative

    ReplyDelete
  5. The post is written in very a good manner and it entails many useful information for me. I am happy to find your distinguished way of writing the post. Now you make it easy for me to understand and implement the concept.rodent pest control

    ReplyDelete
  6. Thank you all so much for participating in this comment to win! What fun it is reading all of your responses.bed bug extermination

    ReplyDelete
  7. My husband and i complete by no limiteds ditto discotheques that sanity signify yesterday that bliss stimulant. The subsidiary fight normally swerves obey writing tenuouss, so i would likely favor to rectify sterile a cut largesss on what to avail wheel your current entwine dapper sponsor no part fidget of delightful or perhaps optical spirit.vintage clothing shops london uk

    ReplyDelete
  8. Thanks for the informative writing. Would mind updating some good tips about it. I still wait your next place.vintage stores london uk

    ReplyDelete
  9. I think that you could do with some pics to drive the message home a bit, but other than that, this is great blog. recruitment agencies.money rituals

    ReplyDelete
  10. I thought it was going to be some boring old post, but it really compensated for my time. I will post a link to this page on my blog.limo services ct

    ReplyDelete
  11. Mmm.. good to be here in your article or post, whatever, I think I should also work hard for my own website like I see some good and updated working in your site.limo service from jfk to ct

    ReplyDelete
  12. There is a lot of good information on this website. Been searching and finally found something I was looking for.Xiaomi 10000mAh Powerbank

    ReplyDelete
  13. This article blew my mind. I am very happy to be here. You don’t know how much inspiration your articles bring.navy blue canvas tote bags

    ReplyDelete
  14. I want you to thank for your time of this wonderful read!!! I definitely enjoy every little bit of it and I have you bookmarked to check out new stuff of your blog a must read blog!!desk sharing software

    ReplyDelete
  15. I really enjoyed reading on this article. I hope that other readers will also experience how I feel after reading your article. Thank you so much.custom sweaters

    ReplyDelete
  16. This is a very good article material and it is very useful for us all. thank you . cara menggugurkan kandungan

    ReplyDelete
  17. Wow! Such an amazing and helpful post this is. I really really love it. It's so good and so awesome. I am just amazed. I hope that you continue to do your work like this in the future also.book cover art

    ReplyDelete
  18. I definitely enjoying every little bit of it. It is a great website and nice share. I want to thank you. Good job! You guys do a great blog, and have some great contents. Keep up the good work.book cover design process

    ReplyDelete
  19. This site is one thing that is needed on the internet, someone with some originality!I honestly appreciate people like you! Take care!!.please visit my web site too and let me know your opinion.Ryanair

    ReplyDelete
  20. I study lot of blog about python but you provide a very different information.Really i appreciate you for your knowledge.Thaks for sharing.keep sharing more blogs.


    Python Online Training

    ReplyDelete
  21. Thanks for sharing this unique and informative post. This blog which provided me the required information. Data Science Training in Chennai | Java Training in Chennai

    ReplyDelete
  22. Hi, you have given really informative post. Thanks for sharing this post to our vision. Learn Python will helps you to reach your goal.
    Python Training in Marathahalli
    Dot Net Training in Chennai

    ReplyDelete
  23. It is a long established fact that a reader will be distracted by the readable content of a page when looking at its layout.

    ReplyDelete
  24. Nice blog. Thank you for sharing. The information you shared is very effective for learners I have got some important suggestions from it.
    Web Designing Training Institute in Chennai | DotNet Training Institute in Chennai | Java Training Institute in Chennai

    ReplyDelete
  25. Needed to compose you a very little word to thank you yet again regarding the nice suggestions you’ve contributed here.

    Data Science Training in Bangalore

    Datascience Training in Chennai

    ReplyDelete