doi: 10.7763/IJCTE.2012.V4.603
Performance Improvement of MX-CIF Quadtree by Reducing the Query Results
Wei Yusi1
,
ShojiroTanaka2
- 1Computer Science, Graduate School of Science and Engineering, Shimane University Matsue, Japan.
- 2Computer Science, Faculty of Science and Engineering, Shimane University Matsue, Japan.
Abstract
An MX-CIF quadtree is a variant of quadtree which is for efficient spatial query such as whether objects are included by a spatial area. When query objects are indexed, a primary result with candidates which may intersect the query rectangle will be reported to have a successional precise inspection. We saved time from inspecting each of the objects intensively. The fewer the candidates are reported to the exact query; the less the time is used to accomplish a query. In this paper, we propose an improved MX-CIF quadtree, compared with the original MX-CIF quadtree. A filter with our structure will decrease the failure rate of result, that is, a query will get fewer uncertain objects, the mechanism of which accelerates the secondary query. Compare to original MX-CIF quadtree, with polygon data given by JTS Topology Suite (JTS)[1], 42.1%~67.5% incorrect results were filtered out by our improved MX-CIF quadtree, and its cost of tree-building time is only slightly higher than the original MX-CIF quadtree.
Keywords
- Distributed systems
- recursive algorithm
- spatial data structure
- spatial index
How to Cite
Wei Yusi and ShojiroTanaka, "Performance Improvement of MX-CIF Quadtree by Reducing the Query Results," International Journal of Computer Theory and Engineering, vol. 4, no. 6, pp. 902-906, 2012. https://doi.org/10.7763/IJCTE.2012.V4.603
Copyright & License
Copyright © 2012 by the authors. This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited (CC BY 4.0).