Research On K Nearest Neighbor Query Based On Data Transformation

K nearest neighbor query is used widely in many fields such as G eographical Information Systems,Image Databases and Bioinformatics.Therefore,the efficient processing of k nearest neighbor query is a hotspot on the researches of commercial multimedia databases.In this paper,we focus on improving k nearest neighbor query based on data transformation method,and the main contents are as follows.Firstly,the data is stored in the form of Minimum Bounding Rectangles(MBRs) which are indexed by R-tree in present databases. However, range query based on L1 distance will produce a rhombus search box during the distance calculation.In query processing, the geometric conflict between the rhombus search box and the rectangle node causes problems as computational complexity and inefficiencies. To solve this problem,we present a data transformation scheme,which transforms the feature space into a new feature space such that range queries in the original space are mapped into equivalent box queries in the transformed space.In 2-dimensional case,this transformation is precise,but for higher dimensional transformation may produce false positives.Therefore,we present a transformed box query algorithm.A theoretical model for the proposed data transformation is presented,and we provide detailed theoretical analysis to demonstrate the transformed box queries have better performance than range queries in the original space.Secondly,we show that k nearest neighbor query can be considered as a special case of range query and the data transformation method is effictive for the k nearest neighbor query.Based on this,we proposed a k nearest neighbor query based on data transformation algorithm(TKNN).Meanwhile,we present that the proposed algorithm provides better performance than those commonly used for k nearest neighbor queries using R-tree type index structures.Finally,experimental results demonstrated the effectiveness of the propos ed transformation scheme and efficient performance of the proposed k nearest neighbor query algorithm.The comparative analysis of the original algorithm is present.