Parallel Cover Trees and their Applications
Yan Gu, Zachary NaPier, Yihan Sun, L. Wang
Abstract
The cover tree is the canonical data structure that efficiently maintains a dynamic set of points on a metric space and supports nearest and k-nearest neighbor searches. For most real-world datasets with reasonable distributions (constant expansion rate and bounded aspect ratio mathematically), single-point insertion, single-point deletion, and nearest neighbor search (NNS) only cost logarithmically to the size of the point set. Unfortunately, due to the complication and the use of depth-first traversal order in the cover tree algorithms, we were unaware of any parallel approaches for these cover tree algorithms.
Topics & Concepts
Tree traversalCover (algebra)Tree (set theory)k-nearest neighbors algorithmMetric (unit)Computer scienceMetric spaceSet (abstract data type)Point (geometry)AlgorithmBounded functionNearest neighbor searchSet cover problemTheoretical computer scienceMathematicsData miningDiscrete mathematicsArtificial intelligenceCombinatoricsGeometryEconomicsOperations managementMathematical analysisEngineeringMechanical engineeringProgramming languageData Management and AlgorithmsAdvanced Image and Video Retrieval TechniquesComputational Geometry and Mesh Generation