Improving dual-tree algorithms

Machine learning;Computational geometry;Tree-based algorithms;Dual-tree algorithms;Kd-tree;Nearest neighbor search;K-means clustering;Data mining

Curtin, Ryan Ross ; Anderson, David V. Electrical and Computer Engineering Chau, Duen Horng (Polo) Clements, Mark A. Isbell, Charles L. Vuduc, Richard W. ; Anderson, David V.

University:Georgia Institute of Technology

Department:Electrical and Computer Engineering

关键词: Machine learning;    Computational geometry;    Tree-based algorithms;    Dual-tree algorithms;    Kd-tree;    Nearest neighbor search;    K-means clustering;    Data mining;   

Others  :  https://smartech.gatech.edu/bitstream/1853/54354/1/CURTIN-DISSERTATION-2015.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

This large body of work is entirely centered around dual-tree algorithms, aclass of algorithm based on spatial indexing structures that often provide large amounts of acceleration for various problems. This work focuses on understanding dual-tree algorithms using a new, tree-independent abstraction, and using this abstraction to develop new algorithms.Stated more clearly, the thesis of this entire work is that we may improve and expand the class of dual-tree algorithms by focusing on and providing improvements for each of the three independent components of a dual-tree algorithm: the type of space tree, the type of pruning dual-tree traversal, and the problem-specific BaseCase() and Score() functions. This is demonstrated by expressing many existing dual-tree algorithms in the tree-independent framework, and focusing on improving each of these three pieces.The result is a formidable set of generic components that can be used to assemble dual-tree algorithms, including faster traversals, improved tree theory, and new algorithms to solve the problems of max-kernel search and k-means clustering.