Performance Improvement of MX-CIF Quadtree by Reducing the Query Results
Yusi Wei, Shojiro Tanaka · International Journal of Computer Theory and Engineering · 2012
An MX-CIF quadtree is a variant of quadtreewhich is for efficient spatial querysuch as whether objects are included by a spatial area. When query objects are indexed, a primary result withcandidates which may intersect the query rectanglewill be reported to have asuccessional precise inspection.We saved time from inspecting each of the objectsintensively.The fewer the candidates are reported to the exact query; the less the timeis 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 resultswere filtered outby our improved MX-CIF quadtree,and its cost of tree-building timeis only slightly higher than the original MX-CIF quadtree.