Polar Split Tree as a Search Tool in Telecommunication
Subject Areas : Communication Systems & DevicesFarzad Bayat 1 , Zahra Nilforoushan 2 *
1 - Kharazmi University
2 - Kharazmi University
Keywords: split tree , polar split tree , quad tree , polar quad tree , nearest neighbor search,
Abstract :
Tree search algorithms are vital for the search methods in structured data. Such algorithms deal with nodes which can be taken from a data structure. One famous tree data structure is split tree. In this paper, to compute the split tree in polar coordinates, a method has been introduced. Assuming that the algorithm inputs (in form of points) have been distributed in the form of a circle or part of a circle, polar split tree can be used. For instance, we can use these types of trees to transmit radio and telecommunication waves from host stations to the receivers and to search the receivers. Since we are dealing with data points that are approximately circular distributed, it is suggested to use polar coordinates. Furthermore, there are several researches by search algorithms for the central anchor which leads to the assignment of a virtual polar coordinate system. In this paper, the structure of Cartesian split tree will be explained and the polar split tree will be implemented. Then, by doing nearest neighbor search experiments, we will compare the polar split tree and polar quad tree in terms of searching time and amount of distance to the closest neighbor and in the end, better results will be achieved.
[1] Robert Adams and Essex Christopher, Calculus: a complete course (Eighth ed.). Pearson Canada Inc., 2013.
[2] Pablo Alonso Gonzalez, Optimization of antenna coverage in telecommunication systems, AGH University of Science and Technology, 2018.
[3] Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars, Computational Geometry: Algorithms and Applications. Springer, pp. 309-312, 2008.
[4] Cristina Costa, Francesco G.B. De Natale and Fabrizio Granelli, Quality Evaluation and Nonuniform Compression of Geometrically Distorted Images Using the Quadtree Distortion Map, EURASIP Journal on Applied Signal Processing, pp. 1899–1911, 2004.
[5] Ameneh Eskandari, Zahra Nilforoushan and javad ranjbar, A Novel Method to Improve Query in Big Databases Using a Geometric tree Base Algorithm: International Journal of computer & Information Technologies, Volume 5, Issue 1, 2017.
[6] Clara Grima and Alberto Marquez, Computational Geometry on Surfaces: Performing Computational Geometry on the Cylinder, the Sphere, the Torus, and the Cone, Kluwer Academic Publishers, 2001.
[7] Anton Howard, Irl Bivens and Stephen Davis, Calculus (Seventh ed.). Anton Textbooks, Inc., 2002.
[8] Moritz von Looz, Christian L. Staudt, Henning Meyerhenke and Roman Prutkin, Fast generation of dynamic complex networks with underlying hyperbolic geometry, Karlsruhe Reports in Informatics, 2014.
[9] Nimrod Megiddo, Linear-time algorithms for Linear programing in R and related problems .: SIAM Journal on Computing, 12(4): 759-776,1983.
[10] Giri Narasimhan and Michiel Smid, Geometric Spanner Networks.: Cambridge University Press, 2007.
[11] Joseph O'Rourke, Computational Geometry in C, Cambridge University Press,1998.
[12] Rina Panigrahy, An Improved Algorithm Finding Nearest Neighbor Using kd-trees, Latin American Symposium on Theoretical Informatics, pp. 387--398, 2008.
[13] Sudhir Porwal, Quad tree-based level-of-details representation of digital Globe, Defence Science Journal, Vol. 63, No. 1, pp. 89-92, 2013.
[14] Franco P. Preparata and Michael Ian Shamos, Computational Geometry - An Introduction, Springer, 1985.
[15] Javad Ranjbar, Zahra Nilforoushan and Ameneh Eskandari, Improved Fingerprint Matching Speed in Large Databases Using Split Tree, 3rd National Conference on Distributed Computing and Big Data Processing, 2017.
[16] J. R. Sack and J. Urrutia, Handbook of Computational Geometry, Elsevier, 1999.
[17] Hanan Samet, Foundations of Multidimensional and Metric Data Structures, Elsevier, 2006.
[18] S. Saric and Z. Bozanic, R. Svalina: Automation in Developing Technical Documentation of Telecommunication Networks, Promet- Traffic- Traffico, Vol. 16, No. 5, pp. 257-262, 2004.
[19] Ian Stewart and David Tall, Complex Analysis (the Hitchhiker's Guide to the Plane). Cambridge University Press, 1983.
[20] A. M. Sukhov and D. Yu. Chemodanov, The Neighborhoods Method and Virtual Polar coordinates in Wireless Sensor Networks, Network and Communication Technologies, Vol. 2, No. 1, pp. 19-27, 2013.
[21] Waldo Tobler and Zi‐tan Chen, A Quad tree for Global Information Storage, Geographical Analysis, Volume18, Issue4, 1986.
[22] https://www.coursera.org/learn/ml-clustering-and-retrieval/lecture/6eTzw/nn-search-with-kd-rees