DOI: 10.7763/IJCTE.2012.V4.603
Performance Improvement of MX-CIF Quadtree by Reducing the Query Results
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.
Index Terms—Distributed systems, recursive algorithm, spatial data structure, spatial index.
W. Yusi is with the Computer Science, Graduate School of Science and Engineering, Shimane University Matsue, Japan (e-mail: wayis@live.com).
S. Tanaka is with the Computer Science, Faculty of Science and Engineering, Shimane University Matsue, Japan (e-mail: tanaka@cis.shimane-u.ac.jp).
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.