Skip Navigation eScience Home | ANU Home | Search FEIT | Search ANU

Faculty of Engineering and Information Technology (FEIT)

Dept. of Computer Science (DCS)

eScience Master Project (COMP6720/COMP6702)

---

Title : Nearest Neighbour Searching in High-Dimensional Metric Space

• Status : booked

• Student : David Marshall

• Tutor/Client : Dr. Shyjan Mahamud, Dr. Richard Hartley

• Period : S1/S2 2006

• Keywords : nearest neighbour, high dimensional, metric space, computer vision

• Report (link to the final report, when available)

---

Description

Given one item, finding its closest match within a database of other such items is a task performed in numerous domains. Image matching, data mining, and electroencephalogram data analysis are a few varied examples. The extension of the concept of Euclidean distance in 2D and 3D space to higher dimensional space provides an effective comparison of items in these sorts of domains.

Particular regard will be given to the performance of nearest neighbour searching in a large database of SIFT descriptors. (Scale Invariant Feature Transform) SIFT descriptors are useful in support of many image matching tasks.

There are a number of algorithms, each with there own issues of storage size and search performance. The literature review (COMP6720) will aim to describe the significant algorithms and their performance attributes. The review should also identify opportunities for the enhancement (or enhanced implementation) of existing algorithms for the purposes of computer vision. Such further work would be the subject of the (COMP6702) follow-on project

More Information

• Links to useful information may be provided as this project progresses.