Cover tree

rdf:langString Cover tree

rdf:langString The cover tree is a type of data structure in computer science that is specifically designed to facilitate the speed-up of a nearest neighbor search. It is a refinement of the Navigating Net data structure, and related to a variety of other data structures developed for indexing intrinsically low-dimensional data. The tree can be thought of as a hierarchy of levels with the top level containing the root point and the bottom level containing every point in the metric space. Each level C is associated with an integer value i that decrements by one as the tree is descended. Each level C in the cover tree has three important properties: * Nesting: * Covering: For every point , there exists a point such that the distance from to is less than or equal to and exactly one such is a parent of . * Separation: For all points , the distance from to is greater than .