View Full Document

Five Balltree Construction Algorithms



View the full content.
View Full Document
View Full Document

6 views

Unformatted text preview:

Five Balltree Construction Algorithms STEPHEN M OMOHUNDRO International Computer Science Institute 1947 Center Street Suite 600 Berkeley California 94704 Phone 415 643 9153 Internet om icsi berkeley edu November 20 1989 Abstract Balltrees are simple geometric data structures with a wide range of practical applications to geometric learning tasks In this report we compare 5 different algorithms for constructing balltrees from data We study the trade off between construction time and the quality of the constructed tree Two of the algorithms are on line two construct the structures from the data set in a top down fashion and one uses a bottom up approach We empirically study the algorithms on random data drawn from eight different probability distributions representing smooth clustered and curve distributed data in different ambient space dimensions We find that the bottom up approach usually produces the best trees but has the longest construction time The other approaches have uses in specific circumstances 1 2 Introduction Introduction Many tasks in robotics vision speech and graphics require the construction and manipulation of geometric representations Systems which build these representations by learning from examples can be both flexible and robust We have developed a data structure which we call the balltree which is well suited to geometric learning tasks Balltrees tune themselves to the structure of the represented data support dynamic insertions and deletions have good average case efficiency deal well with high dimensional entities and are easy to implement In this report we compare five different algorithms for building these structures from data We discuss the trade off between the efficiency of the construction algorithm and the efficiency of the resulting structure Two of the algorithms are on line two analyze the data in a top down fashion and one analyzes it in a bottom up manner The balltree structure is related to other hierarchical representations



Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Five Balltree Construction Algorithms and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Five Balltree Construction Algorithms and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?