Research Article
Radix Priority Search Tree in Circular Range Searching for GIS
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 109 - Issue 9 |
| Published: January 2015 |
| Authors: Linn Linn Phway, Myint Myint Sein |
10.5120/19218-0980
|
Linn Linn Phway, Myint Myint Sein . Radix Priority Search Tree in Circular Range Searching for GIS. International Journal of Computer Applications. 109, 9 (January 2015), 25-29. DOI=10.5120/19218-0980
@article{ 10.5120/19218-0980,
author = { Linn Linn Phway,Myint Myint Sein },
title = { 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 },
doi = { 10.5120/19218-0980 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2015
%A Linn Linn Phway
%A Myint Myint Sein
%T Radix Priority Search Tree in Circular Range Searching for GIS%T
%J International Journal of Computer Applications
%V 109
%N 9
%P 25-29
%R 10.5120/19218-0980
%I Foundation of Computer Science (FCS), NY, USA
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
Index Terms
Keywords