Geo skip list data structure - storing spatial data and efficient search of geographical locations

摘要

Existing data structures which facilitate storage and retrieval of geographical data are R-trees, R* trees, KD trees etc. Most widely used and accepted structure among these is the R-tree. A drawback with R-trees is that it represents regions as fictitious rectangles which do not correspond to actual geographical regions. Also R-trees do not represent the hierarchy very well. For example New York City belongs to state New York and is in country United States of America and is a part of the North America continent. This kind of information is not brought out naturally by R- trees. Moreover, R-trees have problem of merging and splitting when underflow and overflow condition of a rectangle occurs which increases the complexity of this structure. To overcome these problems, we propose a structure called Geo-skip list which is inspired from the skip list data structure. It is simple, dynamic, partly deterministic and partly randomized data structure. We have compared the results of our structure with those of R-tree and have found improvement in the search efficiency.