Nearest neighbour queries on commercial databases

• Main Author: Lin, Xinzhen.
• Other Authors: School of Computer Engineering
• Format: Final Year Project
• Language: English
• Published: 2012
• Subjects: DRNTU::Engineering::Computer science and engineering::Information systems::Information storage and retrieval
• Online Access: http://hdl.handle.net/10356/48694
• Institution: Nanyang Technological University

When you are in need of cash now, how can you quickly find the two nearest ATMs around you that are within one km? This can also be thought of as a k-nearest neighbour (KNN) problem. To help solving the problem, the objective of the project is to develop an application that allows users to search for a number of locations of a particular place type that are nearest to a given point on the map. In addition, the application also involves finding a suitable formula that calculates the shortest distance between two points on the Earth in terms of speed and accuracy. The Spherical Law of Cosines, the Haversine and the Vincenty’s inverse formula were tested in the experiments. It was found that the Spherical Law of Cosines had the fastest speed due to its algorithm which involves only a few trigonometry operations. On the other hand, the Vincenty’s inverse formula was found to have the highest accuracy since it views the Earth as an ellipsoid rather than a sphere. In the context of the application, the Spherical Law of Cosines will still have a satisfactory accuracy since the application does not require super large value inputs like the ones used in the experiments. On the contrary, the Vincenty’s inverse formula does not meet the acceptable speed requirement for the application. As a result, the Spherical Law of Cosines is the most suitable formula for the application given its high speed and good accuracy.