Quad Tree Index for Spatial Data
Dear Sirs/Madams: We are interested in implementing a secondary access method using a quad tree data structure for managing spatial data. Does anyone know of any resources, examples, or demos out there that we can learn from. Thank you for your advice. George Lam
lamck@navair.navy.mil wrote: > Dear Sirs/Madams: > We are interested in implementing a secondary access method using a > quad tree data structure for managing spatial data. Does anyone know of any > resources, examples, or demos out there that we can learn from. Thank you > for your advice. Whilst recognizing that Quad-Trees are a venerable and well understood access method for point data, might I respectfully suggest that you avoid this line of attack. If you do undertake it, you will need to answer the following questions: 1. How to make the quad-tree recoverable. (What happens if the computer crashes just as you were splitting a page). 2. How to make the tree highly concurrent. (You want more than one reader and writer active in the tree at the same time: how to lock pages.) 3. How to make the structure dynamic and bulk buildable (What happens when the data is unevenly distributed i.e. skewed and how can you build the index efficiently i.e. without simply doing a repeated insert into the structure.) If you feel you would like to persist, by all means do. Information on VII is to be found on http://www.informix.com/idn. Once you're done, try comparing the performance of your quad-tree with the built-in R-Tree implementation. You will probably find -- as most experimenters who have looked at the subject have -- that the R-Tree is at least as good as the quad-tree for single user point operations, and that the R-Tree works better for skewed data (which is most of it), in systems demanding high concurrency (which is most of them), and for other kinds of data type (polygons, periods of time) at reasonable dimensions. http://citeseer.nj.nec.com/context/15831/27947 Contains a very long list of references in the area. Just an opinion, but I would guess that using the R-Tree -- or better yet, simply getting one of the pre-cooked spatial extensions like the (bundled) ESRI spatial or the Geodetic -- will more than meet your requirements. Hope this helps! KR Pb