Simple QSF-trees
Byunggu Yu, Ratko Orlandić, Martha W. Evens · 1999
The development of high-performance spatial access methods that can support complex operations of large spatial databases continues to attract considerable attention. This paper introduces QSF-trees, an efficient and scalable structure for indexing spatial objects, which has some important advantages over R*-trees. QSF-trees eliminate overlapping of index regions without forcing object clipping or sacrificing the selectivity of spatial operations. The method exploits the semantics of topological relations between spatial objects to further reduce the number of index nodes visited during the search. A series of experiments involving randomly-generated spatial objects was conducted to compare the structure with two variations of R*-trees. The experiments show QSF-trees to be more efficient and more scalable to the increase in the data-set size, the size of spatial objects, and the number of dimensions of the spatial universe.