Radix Priority Search Tree in Circular Range Searching for GIS
|
10.5120/19218-0980 |
Linn Linn Phway and Myint Myint Sein. Article: Radix Priority Search Tree in Circular Range Searching for GIS. International Journal of Computer Applications 109(9):25-29, January 2015. Full text available. BibTeX
@article{key:article,
author = {Linn Linn Phway and Myint Myint Sein},
title = {Article: Radix Priority Search Tree in Circular Range Searching for GIS},
journal = {International Journal of Computer Applications},
year = {2015},
volume = {109},
number = {9},
pages = {25-29},
month = {January},
note = {Full text available}
}
Abstract
This paper presents a method for circular range searching in 2D geographical data for GIS. The proposed is based on the priority search tree (PST) developed by Edvard T. McCreight in the mid eighties. The Priority Search Tree is a data structure used for performing semi-infinite range queries. In the solution presented in this paper, the two operation of PST, Insert operation and EnumerateRectangle are combined for getting all data-points in a circular range. A query in this new data structure returns all points in circlular range. The proposed circular range searching is the querying of all datapoints P which are the subset of dataset R and also locating in the circular range with the radius and the center is query point.
References
- Edward M. McCreight "Priority Search Tree" (Society for Industrial and Applied Mathematics Journal, Vol. 14, No. 2, May 1985. )
- Haibo Hu and Dik Lun Lee "Range Nearest-Neighbor Query" (IEEE Transactions on Knowledge and Data Engineering, Vol. 18, No. 1, January 2006. ) 24)
- Jon Louis Bentley, Jerome H. Friedman, "Data Structures for Range Searching" (Computing Surveys, Voi. 11, No. 4, December 1979)
- M. de Berg, J. Gudmundsson, M. Hammar, M. Overmars, "On R-trees with low query complexity", (Computational Geometry, Volume 24, Issue 3, April 2003, Pages 179–195)
- Minati De, Anil Maheshwari, Subhas C. Nandy, Michiel Smid "An In-Place Min-Max Priority Search Tree" (23rd Canadian Conference on Computational Geometry, 2011)
- Robin Y. Flatland, Charles V. Stewart "Extending range queries and nearest neighbors" (Computational Geometry 17 (2000).
- Arya, David M. Mount "Approximate Range Searching" (Computational Geometry: Theory and Applications, 17 (2000), 135-163. )
- http://en. wikipedia. org/wiki/Range_searching
- http://www. movable-type. co. uk/scripts/ latlong- vincenty-direct. html
- http://en. wikipedia. org/wiki/Binary_search_tree