The point of the cover tree code is speed. Because the point is speed, the interface to the code differs in two ways from what might be expected.

- Batch operations. The cover tree code does batch tree construction and batch query answering. The return format for a batch query is a vector with on entry per query where each entry is a vector with the first entry equal to the query and the other entries equal to the results.
- Short circuit distance. The distance function has
*3*arguments rather than 2. The third argument is an upper bound on the distance the cover tree cares about. Let distance(q,p,f) must satisfy the triangle inequality and symmetry over q and p. If the distance is d(q,p) > f, then distance(q,p,f) need only return some value greater than f. It*must*be strictly greater.

A: Because it isn't needed. The definition of a point is a computer address, which is already a unique identifier.

**Q: But what if I need to refer to the ith point?**

A: Use pointer arithmetic.

**Q: But what if I want to have my own labeling system?**

A: You'll need to define your own notion of point, which is pretty easy. This includes: defining how you parse a point, defining how you compute the distance between points, and (possibly) defining a function for printing a point. Look at vector.cc and sparse_vector.cc for examples.

A: You are probably using the same dataset for answers and queries.
The first result in any return is the *query* point and other
results are from the answers. If the same dataset is used for both
queries and answers, a point will appear twice.

**Q: What happens if I query for k > the number of answers points?**

A: Don't do that. Currently, the result is invalid.

**Q: Why do I get more than k result points back sometimes?**

A: Because you had a tie for the distance to the kth position.

**Q: How do I insert and remove single points?**

A: That's going to be difficult. There isn't currently code to do this, although it clearly can be written.

**Q: Does the cover tree code actually implement the cover tree datastructure as in the paper?**

A: Not quite. You'll need to set base = 2.0 to get a valid tree. The code uses base=1.3 because it's works better in practice. This parameter controls a softening of the seperation invariant. All of the other optimizations (there are several) do not affect the correctness.

**Q: Are there any known bugs?**

A: There is one performance bug: if many points have distance zero, your performance may be quadratic. There are no known correctness bugs.

**Q: Are you sure?**

A: Triple check your code. Did you use 'abs' instead of 'fabs'? Did you get the semantics of 'upper_bound' right? Did you call the cover tree with k > the number of points? If that fails, email John Langford with the simplest example you can find exhibiting the bug.