Balancing of Quad Tree using Point Pattern Analysis
Point quad tree is considered as one of the most
common data organizations to deal with spatial data & can be used to
increase the efficiency for searching the point features. As the
efficiency of the searching technique depends on the height of the
tree, arbitrary insertion of the point features may make the tree
unbalanced and lead to higher time of searching. This paper attempts
to design an algorithm to make a nearly balanced quad tree. Point
pattern analysis technique has been applied for this purpose which
shows a significant enhancement of the performance and the results
are also included in the paper for the sake of completeness.
[1] H. Samet, "The quadtree and related hierarchical data structures", ACM
Computing Surveys 16, 2(June 1984), pp. 187-260.
[2] R. A. Finkel & J. L. Bentley, "Quad trees - A data structure for retrieval
on composite keys", Acta Inform., vol. 4, no. 1-9, 1974.
[3] G. Keden, "The quad-CIF Tree: A data structure for hierarchical on lone
algorithms", in Proc. 19th Design Automation Conf. , pp. 352-357, June
1982.
[4] Brown R. L. "Multiple storage quad tree : a simpler faster alternative to
bisector list quad trees", " IEEE Trans. Computer Aided Design Vol
CAD-5 pp 413-419, July 1986.
[5] W. Li, S. Legendre & K. Gardiner, " Two-layer quadtree: a data
structure for high-speed interactive layout tools", International
Conference Computer-Aided-Design, pp. 530-533, 1988.
[6] W. Ludo & D. Wim, " Quad List Quad Tree: A geometrical structure
with improved performance for large region queries" Computer -Aided
Design, Vol-8 March 1989.
[7] P. V. Srinivas & V.K. Dwivedi, " YAQT: Yet Another Quad Tree",
IEEE Trans., pp. 302-309, 1991.
[8] S. J. Lu & Y. S. Kuo, " Multicell Quad Trees", IEEE Trans., pp. 147-
151, 1992.
[9] J. A. Orenstein, "Multidimensional tries used for associative searching",
[10] Information Processing Letters 14, 4(June 1982), 150-157.
[11] Pei-Yung Hsiao, "Nearly Balanced Quad List Quad Tree- A Data
Structure for VLSI Lay out Systems", 1996 OPA(Overseas Publishers
Association) Amsterdam B. V.
[12] Pei-Yung Hsiao & Lih-Der Jang, "Using a Balanced Quad List Quad
Tree to speed Up a Hierarchical VLSI Compaction Scheme", IEEE,
1991.
[13] David O-Sullivan & David J. Unwin, " Geographic Information
Analysis", John Wiley and Sons, 2002.
[14] Ralf Hartmut G├╝ting, "An Introduction to Spatial Database Systems",
Special Issue on Spatial Database
[15] A. Klinger, Patterns and Search Statistics , in Optimizing Method in
Statistics, J. S. Rustagi, Ed., Academic Press, New York, 1971, pp. 303-
337.
[16] H. Samet & R.E. Webber, " Storing a collection of polygons using
quadtrees," ACM Transactions on Graphics 4, 3(July 1985), pp. 182-
222(also Proceedings of Computer Vision and Pattern Recognition 88,
Washington, DC, June 1983,pp. 127-132).
[1] H. Samet, "The quadtree and related hierarchical data structures", ACM
Computing Surveys 16, 2(June 1984), pp. 187-260.
[2] R. A. Finkel & J. L. Bentley, "Quad trees - A data structure for retrieval
on composite keys", Acta Inform., vol. 4, no. 1-9, 1974.
[3] G. Keden, "The quad-CIF Tree: A data structure for hierarchical on lone
algorithms", in Proc. 19th Design Automation Conf. , pp. 352-357, June
1982.
[4] Brown R. L. "Multiple storage quad tree : a simpler faster alternative to
bisector list quad trees", " IEEE Trans. Computer Aided Design Vol
CAD-5 pp 413-419, July 1986.
[5] W. Li, S. Legendre & K. Gardiner, " Two-layer quadtree: a data
structure for high-speed interactive layout tools", International
Conference Computer-Aided-Design, pp. 530-533, 1988.
[6] W. Ludo & D. Wim, " Quad List Quad Tree: A geometrical structure
with improved performance for large region queries" Computer -Aided
Design, Vol-8 March 1989.
[7] P. V. Srinivas & V.K. Dwivedi, " YAQT: Yet Another Quad Tree",
IEEE Trans., pp. 302-309, 1991.
[8] S. J. Lu & Y. S. Kuo, " Multicell Quad Trees", IEEE Trans., pp. 147-
151, 1992.
[9] J. A. Orenstein, "Multidimensional tries used for associative searching",
[10] Information Processing Letters 14, 4(June 1982), 150-157.
[11] Pei-Yung Hsiao, "Nearly Balanced Quad List Quad Tree- A Data
Structure for VLSI Lay out Systems", 1996 OPA(Overseas Publishers
Association) Amsterdam B. V.
[12] Pei-Yung Hsiao & Lih-Der Jang, "Using a Balanced Quad List Quad
Tree to speed Up a Hierarchical VLSI Compaction Scheme", IEEE,
1991.
[13] David O-Sullivan & David J. Unwin, " Geographic Information
Analysis", John Wiley and Sons, 2002.
[14] Ralf Hartmut G├╝ting, "An Introduction to Spatial Database Systems",
Special Issue on Spatial Database
[15] A. Klinger, Patterns and Search Statistics , in Optimizing Method in
Statistics, J. S. Rustagi, Ed., Academic Press, New York, 1971, pp. 303-
337.
[16] H. Samet & R.E. Webber, " Storing a collection of polygons using
quadtrees," ACM Transactions on Graphics 4, 3(July 1985), pp. 182-
222(also Proceedings of Computer Vision and Pattern Recognition 88,
Washington, DC, June 1983,pp. 127-132).
@article{"International Journal of Information, Control and Computer Sciences:61321", author = "Amitava Chakraborty and Sudip Kumar De and Ranjan Dasgupta", title = "Balancing of Quad Tree using Point Pattern Analysis", abstract = "Point quad tree is considered as one of the most
common data organizations to deal with spatial data & can be used to
increase the efficiency for searching the point features. As the
efficiency of the searching technique depends on the height of the
tree, arbitrary insertion of the point features may make the tree
unbalanced and lead to higher time of searching. This paper attempts
to design an algorithm to make a nearly balanced quad tree. Point
pattern analysis technique has been applied for this purpose which
shows a significant enhancement of the performance and the results
are also included in the paper for the sake of completeness.", keywords = "Algorithm, Height balanced tree, Point patternanalysis, Point quad tree.", volume = "5", number = "4", pages = "389-4", }
