Searching nearest neighbor in high dimensional space

Searching nearest neighbor in high dimensional space is an interesting and complex problem in computer science. As the dimension increases, the complexity to find the nearest neighbor also increases. In one dimension we can find the nearest point very efficiently. But when the dimension increases, the search efficiency depends on how many points we have to search. In this paper, we propose a simple and efficient technique on how to organize the points in high dimensional space which also allows searching the nearest point efficiently. We have used a memory efficient database organization of the points in high dimension and the searching algorithm is based on limiting the search within some particular indexes of the database. A comparative analysis reveals that our database organization is faster than R-tree [23], K-d tree [25] and the searching algorithm is also very efficient.