This topic is currently earmarked, and may no longer be available!

VP-Trees are an important in-memory index for accelerating metric similarity search, based on a balanced binary split of the data based on the distance to a refernce point (called the "vantage point").

In this Bachelor thesis, the goal is to implement and evaluate enhancements of the VP-tree:

• Generalized Hyperplane Tree (gh-tree)
• VPk-Trees, using k-fold splits
• Monotonous Bisector Trees

Initial readings:

• Jeffrey K. Uhlmann. "Satisfying general proximity / similarity queries with metric trees." Information Processing Letters 40.4 (1991)
• Noltemeier, Hartmut, Knut Verbarg, and Christian Zirkelbach. "Monotonous Bisector* Trees—a tool for efficient partitioning of complex scenes of geometric objects." Data structures and efficient algorithms (1992)

Good Java and data structures (in particular: search trees) knowledge is a must.

As efficiency and performance is important, code quality is integral for a successful implementation.

The implementation is to be done as an extension to ELKI, which already contains many reference methods such as the basic VP-tree and the GNAT.