Pre-Print (2017)

Submitted Submitted; Published Published

Toward Metric Indexes for Incremental Insertion and
Querying
Edward Raff

edraff@lps.umd.edu

arXiv:1801.05055v1 [] 12 Jan 2018

Laboratory for Physical Sciences
Booz Allen Hamilton
University of Maryland, Baltimore County

Charles Nicholas

nicholas@umbc.edu

University of Maryland, Baltimore County

Abstract
In this work we explore the use of metric index structures, which accelerate nearest neighbor
queries, in the scenario where we need to interleave insertions and queries during deployment.
This use-case is inspired by a real-life need in malware analysis triage, and is surprisingly
understudied. Existing literature tends to either focus on only final query efficiency, often
does not support incremental insertion, or does not support arbitrary distance metrics.
We modify and improve three algorithms to support our scenario of incremental insertion
and querying with arbitrary metrics, and evaluate them on multiple datasets and distance
metrics while varying the value of k for the desired number of nearest neighbors. In doing
so we determine that our improved Vantage-Point tree of Minimum-Variance performs best
for this scenario.
Keywords: nearest neighbor, incremental, search, metric index, metric space.

1. Introduction
Many applications are built on top of distance metrics and nearest neighbor queries, and
have achieved better performance through the use of metric indexes. A metric index is a
data structure used to answer neighbor queries that accelerates these queries by avoiding
unnecessary distance computations. The indexes we will look at in this work require the use
of a valid distance metric (i.e., obeys triangle inequality, symmetry, and indiscernibility) and
returns exact results.
Such indexes can be used to accelerate basic classification and similarity search, as well
as many popular clustering algorithms like k-Means (Lloyd, 1982; Kanungo et al., 2002),
density based clustering algorithms like DBSCAN (Biçici and Yuret, 2007; Campello et al.,
2013), and visualization algorithms like t-SNE (van der Maaten, 2014; Maaten and Hinton,
2008; Tang et al., 2016; Narayan et al., 2015). However, most works assume that the data to
be indexed is static, and that there will be no need to update the index over time. Even
when algorithms are developed with incremental updates, the evaluation of such methods
is not done in such a context. In this work we seek to evaluate metric indexes for the case
of incremental insertion and querying. Because these methods are not readily available, we
modify three existing indexes to support incremental insertion and querying.

1

Raff and Nicholas

Our interest in this area is particularly motivated by an application in malware analysis,
where we maintain a database of known malware of interest. Malware may be inserted into
the database with information about malware type, method of execution, suspected origin,
or suspected author. When an analyst is given new malware to dissect, the process can be
made more efficient if a similar malware sample has already been processed, and so we want
to efficiently query the database to retrieve potentially related binaries. This triaging task is
a common problem in malware analysis, often related to malware family detection (Hu et al.,
2013; Gove et al., 2014; Walenstein et al., 2007; Jang et al., 2011). Once done, the analyst
may decide the binary should be added to the database. In this situation our index would
be built once, and have insertions into the database regularly intermixed with queries. This
read/write ratio may depend on workload, but is unfortunately not supported by current
index structures that support arbitrary distance metrics. This scenario inspires our work
to build and develop such indexes, which we test on a wider array of problems than just
malware. We do this in part because the feature representations that are informative for
malware analysis may change, along with the distance metrics used, and so a system that
works with a wide variety of distance measures is appropriate.
To emphasize the importance of such malware triage, we note it is critical from a time
saving perspective. Such analysis requires extensive expertise, and it take an expert analysis
upward of 10 hours to dissect a single binary (Mohaisen and Alrawi, 2013). Being able to
identify a related binary that has been previously analyzed may yield significant time savings.
The scale of this problem is also significant. A recent study of 100 million computers found
that 94% of files were unique (Li et al., 2017), meaning exact hashing approaches such as
MD5 sums will not help, and similarity measures between files are necessary. In terms of
incremental addition of files, in 2014 most anti-virus vendors were adding 2 to 3 million new
binaries each month (Spafford, 2014).
Given our motivation, we will review the related work to our own in section 2. We will
review and modify three algorithms for incremental insertion and querying in section 3,
followed by the evaluation details, datasets and distance metrics in section 4. Evaluations of
our modifications and their impact will be done in section 5, followed by an evaluation of
the incremental insertion and querying scenario in section 6. Finally, we will present our
conclusions in section 7.

2. Related Work
There has been considerable work in general for retrieval methods based on k nearest neighbor
queries, and many of the earlier works in this area did support incremental insertion and
querying, but did not support arbitrary distance metrics. One of the earliest methods was
the Quad-Tree(Finkel and Bentley, 1974), which was limited to two-dimensional data. This
was quickly extended with the kd-tree, which also supported insertions, but additionally
supported arbitrary dimensions and deletions as well(Bentley, 1975). However, the kd-tree
did not support arbitrary metrics, and was limited to the euclidean and similar distances.
Similar work was done for the creation of R-trees, which supported the insertion and querying
of shapes, and updating the index should an entry’s shape change(Guttman, 1984). However
improving the query performance of R-trees involved inserting points in a specific order,

2

Toward Metric Indexes for Incremental Insertion and Querying

which requires having the whole dataset available from the onset(Kamel and Faloutsos, 1994),
and still did not support arbitrary metrics.
The popular ball-tree algorithm was one of the first efforts to devise and evaluate multiple
construction schemes, some which required all the data to be available at the onset, while
others which could be done incrementally as data became available (Omohundro, 1989).
This is similar to our work in that we devise new incremental insertion strategies for two
algorithms, though Omohundro (1989) do not evaluate incremental insertions and querying.
This ball-tree approach was limited to the euclidean distance primarily from the use of a
mean data-point computed at every node. Other early work that used the triangle inequality
to avoid distance computations had this same limitation (Fukunage and Narendra, 1975).
While almost all of these early works in metric indexes supported incremental insertion,
none contain evaluation of the indexes under the assumption of interleaved insertions and
queries. These works also do not support arbitrary distance metrics.
The first algorithm for arbitrary metrics was the metric-tree structure (Uhlmann, 1991a,b),
which used the distance to a randomly selected point to create a binary tree. This was
independently developed, slightly extended, and more throughly evaluated to become the
Vantage-Point tree we explore in this work(Yianilos, 1993). However, these methods did not
support incremental insertion. We will modify and further improve the Vantage-Point tree
in section 3.
Toward the creation of provable bounds for arbitrary distance metrics, the concept of
the expansion constant c was made by Karger and Ruhl (2002). The expansion constant is
a property of the current dataset under a given metric, and describes a linear relationship
between the radius around a point, and the number of points contained within that radius.
That is to say, if the radius from any arbitrary point doubles, the number of points contained
within that radius should increase by at most a constant factor. Two of the algorithms we
look at in this work, as discussed in section 3, make use of this property.
The first practical algorithm to make use of the expansion constant was the Cover-tree
(Beygelzimer et al., 2006), which showed practical speed-ups across multiple datasets and
values of k ∈ [1, 10]. Their results were generally shown under Lp norm distances, but
also included an experiment using the string edit distance. Later work then simplified the
Cover-tree algorithm and improved performance, demonstrating its benefit on a wider variety
of dataset and distance metrics (Izbicki and Shelton, 2015). Of the algorithms for metric
indexes, the Cover-tree is the only one we are aware of with an incremental construction
approach, and so we consider it one of our metrics of interest in section 3. While the
Cover-tree construction algorithm is described as an incremental insertion process, the more
efficient variant proposed by Izbicki and Shelton (2015) includes a bound which requires
the whole dataset in advance to calculate bounds, preventing the efficient interleaving of
insertions and queries1 .
Another algorithm we consider is the Random Ball Cover (RBC), which was designed for
making effective use of GPUs with the euclidean distance (Cayton, 2012). Despite testing
on only the euclidean distance, the algorithm and proof does not rely on this assumption –
and will work with any arbitrary distance metric. We consider the RBC in this work due to
its random construction, which allows us to devise an incremental construction procedure
1. The original Cover-tree did not have this issue, and so would meet our requirements for incremental
insertion. We consider the newer variant since it is the most efficient.

3

Raff and Nicholas

that closely matches the original design and maintains the same performance characteristics.
While the Random Ball Cover has inspired a number of GPU based follow ups (Li and
Amenta, 2015; Kim et al., 2013; Gieseke et al., 2014), we do not assume that a GPU will be
used in our work.
Li and Malik (2016) develop an indexing scheme that supports incremental updates,
but only works for the euclidean distance. They also do not evaluate the performance as
insertions and queries are interleaved.

3. Metric Indexes Used
Given the existing literature of metric indexes there appear to be no readily available methods
that suit our needs. For this reason we take three algorithms and modify them for incremental
index construction and querying. In particular, we adapt the Random Ball Cover, Vantage
Point tree, and Cover-tree algorithms for incremental insertion. As classically presented, the
first two methods methods are not designed for this use case. While the original cover tree
algorithm did support incremental insertions, its improved variants do not. More importantly,
as we will show in section 5, the Cover-tree has worse than brute-force performance with
one of our distance metrics. With our modifications we satisfy three goals that have not yet
been achieved in a single data structure:
1. New datapoints can be added to the index at any point
2. We can efficiently query the index after every insertion
3. The index can be efficiently used with any distance metric

(a) Cover-trees produce a heiarchy (b) Vantage-Point trees divide the (c) RBC selects a subset of repof circles, but each node may space using a hierarchy of circles.
have a variable number of children. The in/outside of each space acts as
Each node has a radius that up- a hard boundary when subdividing.
per bounds the distance to all of its
children, and may partially overlap.

resentatives, and each point is assigned to its nearest representative
(relationships marked with dashed
blue line).

Figure 1. Example partitionings for all three algorithms. Red circles indicate the radius from which
one node covers out in the space.

4

Toward Metric Indexes for Incremental Insertion and Querying

While the latter point would seem satisfied by the original Cover-tree algorithm, our
results indicate a degenerate case where the Cover-tree performs significantly worse than a
brute force search. For this reason we consider it to have not satisfied our goals.
We also contribute improvements to both the Random Ball Cover and Vantage Point
Tree structures that further reduce the number distance computations needed by improving
the rate at which points are pruned out. These improvements can dramatically increase their
effective pruning rate, which leads us to alter our conclusions about which method should be
used in the general case.
In the below descriptions, we will use S to refer to the set of points currently in the
index, and n = |S| as the number of such points. A full review of all details related to the
three methods is beyond this scope of this work, but we will provide the details necessary to
understand what our contributions are to each approach.
3.1 Cover Tree
The Cover-tree (Beygelzimer et al., 2006) is a popular method for accelerating nearest
neighbor queries, and one of the first practical metric indexes to have a provable bound
using the expansion constant c (Karger and Ruhl, 2002). The Cover-tree can be constructed
in O(c6 n log n) time, and answer queries in O(c12 log n) time. Izbicki and Shelton (2015)
developed the Simplified Cover Tree, which reduces the practical implementation details and
increases efficiency in both runtime and avoiding distance computations.2 To reproduce the
Simplified Cover Tree algorithm without any nearest-neighbor errors, we had to make two
slight modifications to the algorithm as originally presented. These adjustments are detailed
in section A.
The Cover-tree algorithm, as its name suggests, stores the data as a tree structure where
each node represents only one data point and may have any number of children nodes3 . The
tree is constructed via incremental insertions, which means we require no modifications to
the construction algorithm to support our use case. However, at query time it is necessary
for each node p in the tree to compute a maxdist, which is the maximum distance from the
point represented by node p to any of its descendant nodes. This maxdist value is used at
every level of the tree to prune children nodes from the search path. Insertions can cause
re-organizations of the tree, resulting in the need to re-compute maxdist bounds. For this
reason the Simplified Cover-tree can not be used to efficiently query the index between
consecutive insertions.
Because of the re-balancing and re-organization that occurs during tree construction, it is
not trivial to selectively update the maxdist value based on the changes that have occurred.
Instead we will use an upper bound on the value of maxdist. Each node in the tree maintains
a maximum child radius of the form 2l , where l is an integer. This also upper bounds the
maxdist value of any node by 2l+1 (Izbicki and Shelton, 2015). This will allow us to answer
queries without having to update maxdist, but results in a loosening of the bound. The
performance of this upper bounded version of the Cover-tree we will refer to as CoverB , and
is more naturally suited to the use case of interleaved insertions and queries.
2. Izbicki and Shelton also introduced a Nearest Ancestor Cover Tree, but we were unable to replicate these
results. The reported performance difference between these two variants was not generally large, and so
we use only the simplified variant.
3. The maximum number of children is actually bounded by the expansion constant c.

5

Raff and Nicholas

We note as well that this relaxation on the maxdist based bound represents a compromise
between the simplified approach proposed by Izbicki and Shelton and the original formulation
by Beygelzimer et al.. In the later case, the 2l+1 bound is used to prune branches, but all
branches are traversed simultaneously. In the former, the maxdist bound is used to descend
the tree one branch at a time, and the nearest neighbor found so far is used to prune out
new branches. By replacing maxdist with 2l+1 , we fall somewhere in-between the approaches.
Using a looser bound to prune, but still avoiding traversing all branches. In our extensive
tests of these algorithms, we discovered two issues with the original specification of the
simplified Cover-tree. These are detailed in section A, along with our modifications that
restore the Cover-tree’s intended behavior.
3.2 Vantage Point Tree
The Vantage Point tree (Yianilos, 1993; Uhlmann, 1991a) (VP-tree) is one of the first data
structures proposed for accelerating neighbor searches using an arbitrary distance metric.
The construction of the VP-tree results in a binary tree, where each node p represents one
point from the dataset, the "vantage point". The vantage point splits its descendant into a
low and high range based on their distance from the aforementioned vantage point, with half
of the child vectors in each range. For each range, we also have a nearest and farthest value,
and an example of how these are used is given in Figure 2.

Figure 2. Example of a node in a vp-tree, with the vantage point in the center. The low-near bound
is in red, the distance to the point closest to the center. The low-far (blue) and high-near (green)
braket the boundry of the median. No points can fall between these bounds. The farthest away point
provides the high-far bound in orange.

This tree structure is built top-down, and iteratively splits the remaining points into
two groups at each node in the tree. Rather than continue splitting until each node has
no children, there is instead a minimum split size b. This is because there are likely too
few points for which we can obtain good low/high bounds. Instead, once the number of
datapoints is ≤ b, we create a "bucket" leaf node that stores the points together and uses
the distance from each point to its parent node to do additional pruning.
At construction time, since each split is done by breaking the tree in half, the maximum
depth of the tree is O(log n) and construction takes O(n log n) time. Assuming the bounds
are successful in pruning most branches, the VP-tree then answers queries in O(log n) time.
6

Toward Metric Indexes for Incremental Insertion and Querying

The bucketing behavior can provide practical runtime performance improvements as
well. Some of this comes from better caching behavior, as bucket values will be accessed in
a sequential pattern, and avoids search branches that can be more difficult to accurately
predict for hardware with speculative execution. This can be done for the VP-tree because
its structure is static as it is created, where the Cover-tree cannot create bucket nodes due
to the re-balancing done during construction.
3.2.1 Incremental Construction
While the Cover-tree required minimal changes since its construction is already incremental,
we must define a new method to support such a style for the VP-tree. To support incremental
insertions into a VP-tree, we must first find a location with which to store the new datapoint
x. This can be done quite easily by descending the tree via the low/high bounds stored for
each point, and updating the bounds as we make the traversal. One we reach a leaf node, x
is simply inserted into the bucket list. However, we do not expand the leaf node when its
size exceeds b.
Ideally, these bounds will be changed infrequently as we insert new points. Getting a
better estimate of the initial bound values should minimize this occurrence. For this reason
we expand a bucket b once it reaches a size of b2 . This gives us a larger sample size with
which to estimate the four bound values. We use the value b2 as a simple heuristic that
follows our intuition that a larger sample is needed for better estimates, allows us to maintain
the fast construction time of the VP algorithm, and results in an easy to implement and
replicate procedure.
Algorithm 1 Insert into VP-tree
Require: vp-tree root node p, and new datapoint x to insert into tree.
1: while p is not a leaf node do
2:
dist ← d(x, p.vp)
3:
if dist < (p.lowfar + p.highnear )/2 then
4:
p.lowfar ← max (dist, p.lowfar )
5:
p.lownear ← min (dist, p.lownear )
6:
p ← p.lowChild
7:
else
8:
p.highfar ← max (dist, p.highfar )
9:
p.highnear ← min (dist, p.highnear )
10:
p ← p.highChild
11: Add x to bucket leaf node p
12: if |p.bucket| > b2 then
13:
Select vantage point from p.bucket and create a new split, adding two children nodes to p.
14: return

Thus our insertion procedure is given in Algorithm 1, and is relatively simple. Assuming
the tree remains relatively balanced, we will have an insertion time of O(log n). This will
also maintain the query time of O(log n).

7

Raff and Nicholas

3.2.2 Faster Search
We also introduce a new modification to the VP-tree construction procedure that reduces
search time by enhancing the ability of the standard VP-tree search procedure to prune out
branches of the tree. This is done by using an extension of the insight from subsubsection 3.2.1,
that we want to make our splits only when we have enough information to do so. That is,
once we have enough data to make a split, choosing the median distance from the vantage
point may not be the smartest split.
Better split

vp

Original split

Figure 3. Example on how the split can be improved, with vantage point in black and other points
sorted by distance to it. Colors correspond to Figure 2.

Instead, we can use the distribution of points from the vantage point to choose a split
that better bifurcates the data based on the distribution. An example of this is given in
Figure 3, where the data may naturally form a binary split. This increases the gap between
the lowfar and highnear bounds, which then allows the search procedure to more easily prune
one of the branches.
To do this quickly, so to minimize any increase in construction time, we borrow from the
CART algorithm used to construct a regression tree(Breiman et al., 1984). Given a set of
n distances to the vantage-point, we find the split that minimizes the weighted variance of
each split
2
2
arg min s · σ1:s
+ (n − s) · σs:n

(1)

s

2 indicates the variance of the points in the range of [s, n) when sorted by
Where σs:n
distance to the vantage point. Because (1) can be solved with just two passes over the n
points (Welford, 1962; Chan et al., 1983), we can solve this quickly with only an incremental
increase in runtime.
The original VP tree selects the median distance of all points from the vantage point.
This requires n distance computations, and an O(n) quick-select search. Finding the split
of median variance still requires n distance computations, so that cost remains unchanged.
However, a sort of O(n log n) must be done to find the split of minimum variance.

3.3 Random Ball Cover
The Random Ball Cover (Cayton, 2012) (RBC) algorithm was originally proposed as an
accelerating index that would make efficient use of many-core systems, such as GPUs.
This was motivated by the euclidean distance metric, which can be computed with high
efficiency when computing multiple distances simultaneously. This can be done by exploiting
a decomposition of the euclidean distance into matrix operations, for which optimized BLAS
routines are readily available. To exploit batch processing while also pruning distances, the
8

Toward Metric Indexes for Incremental Insertion and Querying

RBC approach organizes data into large groups and uses the triangle inequality sparingly to
prune out whole groups at a time. Compared to the VP and Cover Tree, the RBC algorithm
√
is unique in that it aims to answer queries in O( n) time and perform construction in
√
O(n n) time.
√
The training procedure of the RBC algorithm is to randomly select O( n) centers from
the dataset, and denote that set of points as R. These are the R random balls of the
algorithm. Each representative ri ∈ R will own, or cover, all the datapoints for which it is
the nearest neighbor, arg minx d(x, ri )∀x ∈ S \ R, which is denoted as Lri . It is expected
√
that each ri will then own O( n) datapoints. Querying is done first against the subset of
points R, from which many of the representatives are pruned. Then a second query is done
against the points owned by the non-pruned representatives. To do this pruning, we need
the representatives to be sorted by their distance to the query point q. We will denote this
(q)
as ri , which would be the i’th nearest representative to q. Pruning for k nearest neighbor
queries is then done using two bounds,
(q)

d(q, ri ) < d(q, rk ) + ψri
(q)

d(q, ri ) < 3 · d(q, rk )

(2)
(3)

Where ψri = maxx∈Lri d(ri , x) is the radius of each representative, such that all datapoints
fall within that radius. Each bound must be true for any ri to have the k’th nearest neighbor
to query q, and the overall procedure is given in Algorithm 2. Theoretically the RBC bounds
are interesting in that they provide a small dependency on the expansion constant c of the
√
data, where queries can be answered in O(c3/2 n) time. This is considerably smaller than
√
the c12 term in cover trees, but has the larger n dependence on n instead of logarithmic.
√
However, the RBC proof depends on setting the number of representatives |R| = O(c3/2 n)
√
as well, which we would not know in advance in practice. Instead we will use |R| = n in
all experiments.
Algorithm 2 Original RBC Search Procedure
Require: Query q, desired number of neighbors k
(q)
1: Compute sorted order ri ∀r ∈ R by d(r, q)
2: FinalList ← ∅
3: for all ri ∈ R do
4:
if Bounds (2) and (3) are True then
5:
FinalList ← FinalList ∪ Lri
6: k-NN ← BruteForceSearch(q, R ∪ FinalList) .distances for R do not need to be re-computed
7: return k-NN

3.3.1 Incremental Construction
If our goal was to build a static index, the random selection of R may lead to a sub-optimal
selection. It is possible that different representatives will have widely varying numbers of
members. For our goal of incrementally adding to an index, this stochastic construction
becomes a benefit. Because the representatives are selected randomly without replacement,
9

Raff and Nicholas

it is possible to incrementally add to the RBC index while maintaining the same quality of
results.
Algorithm 3 Insert into RBC Index
Require: RBC representatives R, associated lists Lr , ∀r ∈ R, and new datapoint x to add to RBC.
(x)
1: Compute sorted order ri ∀r ∈ R by d(r, x)
2: Lr(x) ← Lr(x) ∪ x
1
1 

(x)
3: ψr(x) ← max d(r1 , x), ψr(x)
.keep radius information correct
1
1
√ 2
4: if ceil ( n) 6= n then
5:
return
.else, expand R set
S
6: select randomly a datapoint lnew from ∀r∈R Lr
7: let rold be the representative that owns lnew , i.e., lnew ∈ Lrold
8: Lrold ← Lrold \ lnew
9: rnew ← lnew
10: potentialChildren ← RadiusSearchRBC(rnew , arg maxr,∀r∈R ψr )
11: Lrnew ← ∅
12: R ← R ∪ rnew
13: ψrnew ← 0
14: for all y ∈ potentialChildren do
15:
Let ry be the representative that owns y
16:
if d(y, ry ) > d(y, rnew ) then
.change ownership
17:
Lry ← Lry \ y
18:
Lrnew ← Lrnew ∪ y
19:
ψry ← arg max∀z∈Lry d(ry , z)
.update radius info
20:
ψrnew ← max (ψrnew , d(y, rnew ))

The details of our approach are given in Algorithm 3. Whenever we add a new datapoint
to the index, we find its representative and add it to the appropriate list L. This can be
√
done in O( n) time, consistent with the query time of RBC. Once the closest representative
is found, the radius to the farthest point may need to be updated, which is trivial. For the
√
majority (n − n) of insertions, this is all the work that needs to be done.
√
For the remaining n insertions, the total number of datapoints will reach a size such
that we should have a new representative. The new representative will be selected randomly
from all the points in S \ R. We can find the all the datapoints that may belong to this
new representative using a "range" or "radius" search. A radius search is given a query and
radius, and returns all datapoints within the specified radius of the query. In this case we
give the new representative as the query and specify the range as the maximum ψr in the
RBC so far. This is by definition the maximum distance of any point to its representative,
so any point that will be owned by the new representative must have a smaller distance. In
the worst case scenario, we cannot prune any points using a radius search. This means at
√
most n other points must be considered. But since this scenario can only occur n times,
√
we maintain the same construction time complexity of O(n n) in all cases. We can also
√
state that this approach yields an amortized O∗ ( n) insertion time.

10

Toward Metric Indexes for Incremental Insertion and Querying

3.3.2 Faster Search
While the original RBC search is fast and efficient on GPUs and similar many-core machines,
it is not as efficient for our use case. Our scenario of interleaved insertions and queries means
will be querying with only a few datapoints at a time. This means we will not obtain a
large enough group of queries points to obtain the batch and SIMD efficiencies that were
the original goal of Cayton (2012). Further, when we consider arbitrary distance metrics,
we can not expect the same efficient method of grouping calculations as can be done with
the euclidean distance. Thus we have developed an improved querying method for the RBC
search to make it more efficient in our incremental insertion and querying scenario. Our
improvements to the RBC search procedure can be broken down into three steps.
First, we modify the search to create the k-NN list incrementally as we visit each
representative r ∈ R. In particular we can improve the application of bound (2) by doing
(q)
this. First, we note that in (2), the d(q, rk ) term serves as an upper bound on the distance
to the k’th nearest neighbor. By building the k-NN list incrementally, we can instead use
the current best candidate for k’th nearest neighbor as a bound on the distance to the k’th
nearest neighbor. This works intuitively, as the true k’th neighbor, if not yet found, must by
definition have a smaller distance than our current candidate.
Second, when visiting the points owned by each representative, l ∈ Lr , we can apply this
bound again and tighten the bound further. This is done by replacing the ψri term of (2) by
the distance of l to its representative r. Since this distance d(l, r) had to be computed when
building the RBC in the first place, these distances can simply be cached at construction —
avoiding any additional overhead.
Third, to increase the likelihood of finding the k’th neighbor earlier in the process, we
visit the representatives in sorted order by their distance to the query. Because our first
modification tightens the bound as we find better k’th candidates, this will accelerate the
rate at which we tighten the bound.
The complete updated procedure is given in Algorithm 4. A similar treatment can
improve the RBC search procedure for range queries. We note that one lines 2 through
4, we add all the children points of the closest representative Lr(q) unconditionally. This
1
satisfies requirements of the RBC search algorithm’s correctness in the k nearest neighbor
case, rather than just one nearest neighbor. We refer the reader to Cayton (2012) for details.
The essence of its purposes is to pre-populate the k-NN list with values for the bounds checks
done in lines 8 and 10.
The first step of our new algorithm must still compute the distances for each ri , and
√
(q)
|R| = n. In addition, we add all the children of the closest represent r1 , which is expected
√
√
to own O( n) points. Thus this modified RBC search is still an O( n) search algorithm.
Our work does not improve the algorithmic complexity but does improve its effectiveness at
pruning.

4. Datasets and Methodology
We use a number of datasets and distance metrics to evaluate our changes and the efficiency
of our incremental addition strategies. For all methods we have confirmed that the correct
nearest neighbors are returned compared to a naive brute-force search. Our evaluation will

11

Raff and Nicholas

Algorithm 4 New RBC Search Procedure
Require: Query q, desired number of neighbors k
(q)
1: Compute sorted order ri ∀r ∈ R by d(r, q)
(q)
2: k-NN ← {r1 }
.sorted list implicitly maintains max size of k
.Add the children of the nearest representative
3: for all l ∈ Lr(q) do
1
4:
k-NN ← k-NN ∪ l
5: for i ∈ 2 . . . |R| do
.visit representatives in sorted order
(q)
6:
qr ← d(q, ri )
(q)
(q)
7:
Add tuple ri , d(ri , q) to k-NN
8:
if qr < k-NN[k].dist + ψri and (3) are True then
9:
for all l ∈ Lr(q) do
i

(q)

if qr < k-NN[k].dist + d(l, ri ) then
Add tuple l, d(l, q) to k-NN
12: return k-NN

10:
11:

(q)

.d(l, ri ) is pre-computed

cover multiple aspects of performance, such as construction time, query time, and the impact
of incremental insertions of index efficiency. We will use multiple values of k in the nearest
neighbor search so that our results are relevant to multiple use-cases. Toward this end we
will also use multiple datasets and distance metrics to further validate our findings.
4.1 Evaluation Procedure
The approach used in most prior works to evaluate metric indexes is to create the index
from all of the data, and then query each datapoint in the index search for the single nearest
neighbor (Izbicki and Shelton, 2015). For consistency we replicate this experiment style, but
do not use every datapoint as a query point. This results in worst case O(n2 ) runtime for
some of our tests, preventing us from comparing on our larger datasets. Since our interest is
in if the index allows for faster queries, we can instead determined this the average pruning
efficiency with extreme accuracy by using only small sample of query points. In tests using
a sample of 1000 points for testing, versus using all data points, we found no difference in
conclusions or results4 . Thus we will use 1000 test points in all experiments. This will allow
us to run any individual test in under a week, and evaluate the insertion-query performance
in a more timely manner.
When using various datasets, if the dataset has a standard validation set, it will not
be used. Instead points from the training set will be used for querying. This is done for
constituency since not every dataset has a standard validation or testing set. Our experiments
will be performed searching for the k nearest neighbors with k ∈ {1, 5, 25, 100}. Evaluating
for multiple values of k is often ignored in most works, which focus on the k = 1 case in their
experiments (e.g. Izbicki and Shelton, 2015; Cayton, 2012; Yianilos, 1993), or will test on
only a few small value of k ≤ 10 (Beygelzimer et al., 2006). This is despite many applications,
such as embeddings for visualization (Tarlow et al., 2013; Maaten and Hinton, 2008; van der
Maaten, 2014; Tang et al., 2016), using values of k as large as 100. By testing a range of
4. The largest observed discrepancy was of 0.3 percentage points

12

Toward Metric Indexes for Incremental Insertion and Querying

values for k we can determine if one algorithm is uniformly better for all values of k, or if
different algorithms have an advantage in one regime over the others.
To evaluate the impact of incremental index construction on the quality of the final index,
each index will be constructed in three different ways. Differences in performance between
these three versions of the index will indicate the relative impact that incremental insertions
have.
1. Using the whole dataset and performing the classic batch construction method, by
which we mean the original index construction process for each algorithm (referred to
as batch construction)
2. Using half the dataset to construct an initial index using the classic batch method, and
incrementally inserting the second half of the data (referred to as half-batch)
3. Constructing the entire dataset incrementally (referred to as incremental).
For these experiments, the Cover-tree is excluded — as its original batch construction is
already incremental (though does not support efficient queries between insertions). In our
results we will expect the RBC algorithm to have minimal change in performance, due to
the stochastic nature of representative selection. The expected performance impact of the
VP-tree is unknown, though we would expect the tree to perform best in batch construction,
second best when using half-batch construction, and worst when fully incremental. Results
will consider both the number of distance computations when including and excluding
distanced performed during index construction. We note that runtime of all methods and
tests correlates directly with number of distance computations done for our code. Comparing
distance computations is preferred so that we observe the true impact of pruning, rather
than efficiency of micro optimizations, and is thus comparable to implementations written in
other languages.
We will also test the effectiveness of each method when interleaving queries and insertions.
This will be evaluated in a manner analogous to common data structures, where we have
different number of possible read (query) and write (insert) ratios.
4.2 Data and Distances Used
Now that we have reviewed how we will evaluate our methods, we will list the datasets and
distance metrics used in such evaluations. A summary of which is presented in Table 1.
Datasets and distance metrics were selected to cover a wide range of data and metric types,
include common baselines, and so that experiments would finish within a one-week execution
window.
Our first three datasets will all use the familiar euclidean distance(4). The first of which
is the well known MNIST dataset (Lecun et al., 1998), which is a commonly used benchmark
for machine learning in general. Due to its small size we also include a larger version of the
dataset, MNIST8m, which contains 8 million points produced by random transformations to
the original dataset (Loosli et al., 2007). We also evaluate the Forest Cover Type (Covtype)
datasets (Blackard and Dean, 1999), which has historically been used for metric indexes.
d(x, y) = kx − yk
13

(4)

Raff and Nicholas

Dataset

Samples

Distance Metric

MNIST
MNIST8m
Covtype
VxHeaven
VirusShare5m
ILSVRC 2012 Validation
IMDB Movie Titles

60,000
8,000,000
581,012
271,095
5,000,000
50,000
143,337

Euclidean
Euclidean
Euclidean
LZJD
LZJD
EMD
Levenshtein

Table 1. Datasets used in experiments, including the number of points in each dataset and the
distance metric used.

Finding nearest neighbors and similar examples is important for malware analysis (Jang
et al., 2011; Hu et al., 2009). The VxHeaven corpus has been widely used for research in
malware analysis (vxh), and so we use it in our work for measuring the similarity of binaries.
VxHeaven contains 271k binaries, but malware datasets are routinely reaching the hundreds
of millions to billions of samples. For this reason we also select a random 5 million element
set from the VirusShare corpus (Roberts, 2011), which shares real malware with interested
researchers. As the distance metric for these datasets, we will use the Lempel-Ziv Jaccard
Distance (LZJD) (Raff and Nicholas, 2017a), which was designed for measuring binary
similarity and is based upon the Jaccard distance. LZJD uses the Lempel-Ziv algorithm to
break a byte sequence up into a set of sub-sequences, and then uses the Jaccard distance (5)
to measure the distance between these sets. Recent work has used LZJD for related tasks
such as similarity digests for digital forensics, where prior tools could not be accelerated in
the same manner since they lacked the distance metric properties (Raff and Nicholas, 2017b).
d(A, B) = 1 −

|A ∩ B|
|A ∪ B|

(5)

One of the metrics measured in the original Cover-tree paper was the a string edit
distance (Beygelzimer et al., 2006). They compared to the dataset and methods used in
Clarkson (2002), however the available data contains only 200 test strings. Instead we use
the Levenshtein edit distance on IMDB movie titles (Behm et al., 2011), which contains both
longer strings and is three orders of magnitude larger.
The simplified Cover-tree paper evaluated a larger range of distance metrics (Izbicki
and Shelton, 2015), including the Earth Mover’s Distance (EMD) (Rubner et al., 2000).
The EMD provides a distance measure between histograms, and was originally proposed
for measuring the similarity of images. We follow the same procedure as for using the
"thresholded" EMD (Pele and Werman, 2009), except we use the RGB color space5 . We use
the 2012 validation set of the ImageNet challenge (Russakovsky et al., 2015) for this distance
metric, as it is the most computationally demanding metric of the ones we evaluate in this
work.
5. Our software did not support the LabCIE color space previously used, and we did not notice any significant
difference in results for other color spaces.

14

Toward Metric Indexes for Incremental Insertion and Querying

5. Evaluation of Construction Time and Pruning Improvements
We first evaluate the impact of our changes to each of the three algorithms. For RBC and
VP-trees, we have made alterations that aim to improve the ability of these algorithms to
avoid unnecessary distance computations at query time. For the Cover-tree, we have made
a modification that will negatively impact its ability to perform pruning, but will make it
viable for interleaved insertions and queries. We will evaluate the impact of our changes on
construction time, query efficiency under normal construction, and the impact incremental
construction has on the efficiency of the complete index.
5.1 Impact on Construction Time
To determine the impact of the incremental construction and our modifications, we will
compare each algorithm in terms of the number of distance computations needed to construct
the index. We will do this for all three construction options, batch, half-batch, and incremental,
as discussed in section 4. The time for only constructing the indices in these three ways
are shown in Figure 4. We note that there is no distinction between the Cover and CoverB
construction times, and that the cover-tree is always incremental in construction. For this
reason we only show one bar to represent Cover and CoverB across all three construction
scenarios to avoid graph clutter.
Here we see the two performance characteristics observed. On datasets like MNIST,
where we use the euclidean distance, RBC is the slowest to construct. This is expected, as it
√
also has the highest complexity at O(n n) time. We also note that the RBC radius search
is not as efficient at pruning, and fails to do so on most datasets. Only on datasets that
are most accelerated, such as the Covtype dataset, does the RBC incremental construction
avoid distance computations during construction. This empirically supports the theoretical
justification that we maintain the same construction time for the RBC algorithm, as discussed
in subsubsection 3.3.1.
The second slowest to construct is the Cover-tree, followed by the VP-trees which is fastest.
On the VxHeaven dataset, with the LZJD metric, the construction time performance of the
Cover-tree degrades dramatically, using two orders of magnitude more distance computations
than the RBC. We believe this performance degradation is an artifact of the expansion
constant c that occurs when using the LZJD metric. The VP tree has no construction time
impact with c, and the RBC algorithm has a small O(c3/2 ) dependency compared to the
Cover-tree’s O(c6 ) dependence. On the VirusShare5m dataset, the Cover-tree couldn’t be
constructed given over a month of compute time. We also note that the Cover-tree had
degraded construction performance on the IMDB Movies dataset using the Levenshtein
distance. These results present a potential weakness in the Cover-tree algorithm.
Barring the performance behavior of the Cover-tree, both the RBC and VP-tree have
more consistent performance on various datasets. We note of particular interest that the
incremental construction procedure for the RBC results in almost no change in the number
of distance computations needed to build the index6 . The radius search is rarely able to do
any pruning for the RBC algorithm, and so the brute force degrades to the same number of
6. The same cannot be said for wall clock time, which is expected.

15

Raff and Nicholas

MNIST

MNIST8m

VxHeaven
1010

107

Batch
Half-Batch
Incremental

1010
109

108

109
106

107

Covtype

R

V

IMDB Movies

ov
er
C

P

M
V

P
V

p
Im

BC

ov
er

R
BC

V

C

P

M

V

P
V

p
Im

BC
R

R
BC

C
ov
er

V

P

M

V

P
V

p
Im

R
BC

R
BC

108

ILSVRC
107

107.5
108
107

106

106.5

ov
er
C

V

P

M

V

P
V

p
Im

BC
R

BC
R

ov
er
C

V

P

M

V

P
V

Im
p

BC
R

BC
R

ov
er
C

V

P

M

V

P
V

p
Im

BC
R

R

BC

107

Figure 4. Construction performance for each algorithm on each dataset. The y-axis represents
the number of distance computations performed to build each index. Each algorithm is plotted
three times, once using classic batch construction, half-batch, and incremental. The Cover-tree’s
construction algorithm is equivalent in all scenarios, so only one bar is shown.

distance computations as the batch insertion. The Covtype dataset is the one for which each
algorithm was able to do the most pruning, and thus has the most pronounced effect of this.
The VPMV variant of the VP-tree also matches the construction profile of the standard
VP-tree on each dataset, with slightly increased or decreased computations depending on
the dataset. This is to be expected, as the standard VP-tree always produces balanced splits
during batch construction. The incremental construction can also cause lopsided splits for
both the VP and VPMV -tree, which results in a longer recurrence during construction, and
thus increased construction time and distances. The VPMV -tree may also encourage such
lopsided splits, increasing the occurrence of this behavior. Simultaneously, the incremental
construction requires fewer distance computations to determine early splits, and so can result
in fewer overall computations if the splits happen to come out near balanced. The data
and metric dependent properties will determine which impact is stronger for a given case.
The impact of incremental construction on the VP-trees is also variable, and can increase or
decrease construction time. In either direction, the change in VP construction time is minor
relative to the costs for Cover-trees and the RBC algorithm.
Overall we can draw the following conclusions about construction time efficiency. 1) that
the VP-trees are fastest in all cases, and the proposed VPMV variant has no detrimental
impact. 2) the RBC algorithms are the most consistent, but often slowest, and that the
16

Toward Metric Indexes for Incremental Insertion and Querying

RBCImp has no detrimental impact. 3) the Cover-tree is not consistent in its performance
relative to the other two algorithms, but when it works well, is in the middle of the road.
5.2 Impact on Batch Query Efficiency
We now look at the impact of our changes to the three search procedures on querying the
index, when the index is built in the standard batch manner. This isolates the change in
performance to only our modifications of the three algorithms. Our goal here is to show that
RBCImp and VPMV are improvements over the standard RBC and VP-tree methods. We
also want to quantify the negative impact of using the looser bounds in CoverB that will
allow for incremental insertion and querying, which is not easy with the standard simplified
Cover-tree due to its use of the maxdist bound and potential restructuring on insertions
(Izbicki and Shelton, 2015).
RBC

RBCImp

VP

VPMV

Cover

CoverB
VxHeaven

MNIST8m

MNIST
100

1

Fraction of Distance Computations Needed

1.2

0.8

10−1

0.6

10−2

1.1

1

0.9
100

101

102

100

Covtype

101

102

100

IMDB Movies

100

101

102

ILSVRC
100

1

10−1
0.8
10−2

10−1
0.6

10−3
10−4

100

101
k

102

100

101
k

102

100

101
k

102

Figure 5. Number of distance computations needed as a function of the desired number of neighbors
k. The y-axis is the ratio of distance computations compared to a brute-force search (shown at 1.0
as a dotted black line).

Considering only batch construction, we can see the query efficiency of these methods in
Figure 5, where we look at the fraction of distance computations needed compared to a bruteforce search. This figure factors in the distance computations needed during construction
time, so the query efficiency is with respect to the whole process.
We remind the reader that this plot is construed from a random sample of 1000 randomly
selected query points, and then scaled to have the same weight as if all test points were used.
That is to say, if a corpus as n data points, we compute the average number of distance
17

Raff and Nicholas

computations from a sample of 1000 points. The total number of distance computations
is then treated as this average times n. This closely mimics the same results that would
have been achieved by using all n points as queries, but keeps runtime manageable given our
compute resources. In extended testing on corpora where it is feasible to compute this for all
n points, just 100 samples reliably estimated the ratio to two significant figures, so our 1000
point estimates should allow us to reach the same conclusions with confidence.
One can see that for the RBC and VP-tree algorithms, our enchantments to the search
procedure are effective. For the RBC algorithm in particular, more distance computations
were done than the brute force search in most cases, but RBCImp dramatically improves
the competitiveness of the approach. This comes at a loss of compute efficiency when using
the euclidean metric, which is where the RBC obtains its original speed improvements. But
our work is looking at the general efficiencies of the RBC for arbitrary distance metrics,
which may not have the same efficiency advantages when answering queries in batches. In
this respect the pruning improvements of RBCImp are dramatic and important if the RBC
algorithm is to be used.
The VPMV reduces the number of computations needed compared to the standard VPtree in all cases. The amount of improvement varies by dataset, ranging from almost no
improvement, to nearly an order of magnitude less distance computations for the Covtype
dataset. Given these results our choice to produce unbalanced splits during construction is
empirically validated.
As expected, the CoverB variant of the simplified Cover-tree had a detrimental impact
on efficiency, as it is relaxing the bound to the same one used in the original Cover-tree
work(Beygelzimer et al., 2006). Among all tests, the CoverB -tree required 1.6 to 6.7 times
as many distance computations as the standard Cover-tree, with the exact values given in
Table 2 for all tested values of k. The few distance computations avoided for determining
the tighter bound clearly make up for a considerable portion of the simplified Cover-tree’s
improved performance.
Table 2. For each dataset, the this table shows the multipler on the number of distance computations
CoverB had to perform compared to a normal Cover-tree.

Dataset
k

MNIST

MNIST8m

ILSVRC

Covtype

IMDB

VxHeaven

1
5
25
100

1.57
1.38
1.25
1.16

6.73
5.71
2.75
2.44

2.07
1.96
1.81
1.67

2.27
2.16
1.97
1.73

1.70
1.44
1.29
1.20

0.97
0.98
0.98
0.98

While the Cover-tree was the most efficient at avoiding distance computations on the
MNIST dataset, the Cover-tree is the worst performer by far on the VxHeaven dataset.
The increased construction time results in the Cover-tree performing 20% more distance
computations than would be necessary with the brute force approach. We also see an
interesting artifact that more distance computations were done on VxHeaven when using
the tighter maxdist bound than the looser CoverB approach. This comes from the extra
computations needed to obtain the maxdist bound in the first place, and indicates that more
18

Toward Metric Indexes for Incremental Insertion and Querying

distances computations are being done to obtain that bound then are saved in more efficient
pruning.
1

0.8

0.6

0.4
100

101
k

102

Figure 6. Query performance on the VirusShare5m dataset.

We also note that the VxHeaven dataset, using the LZJD distance, had the worst query
performance amongst all datasets, with LZJD barely managing to avoid 5% of the distance
computations compared to a brute-force search. By testing this on the larger VirusShare5m
dataset, as seen in Figure 6, we can see that increasing the corpus size does lead to pruning
efficiencies. While the Cover-tree couldn’t be built on this corpus, both the RBC and VP
algorithms are able to perform reasonably well. The VPMV did best, avoiding between 57%
and 40% of the distance computations a brute-force search would require.
Viewing these results as a whole, we would have to recommend the VPMV algorithm as
the best choice in terms of query efficiency. In all cases it either prunes the most distances
for all values of k, or is a close second to the Cover-tree (which has an extreme failure case
with LZJD).
5.3 Impact of Incremental Construction on Query Efficiency
For the last part of this section, we examine the impact on query pruning based on how the
index was constructed. That is to say, does half-batch or incremental construction of the
index negatively impact the ability to prune distance computations, and if so, by how much?
Such evaluation will be shown for only the more efficient RBCImp and VPMV algorithms
that we will further evaluate in section 6. We do not consider the Cover-tree variants in this
portion. As noted in subsection 3.1, the Cover-tree’s construction is already incremental.
Thus these indexes will be equivalent when given the same insertion ordering. The only
change in Cover-tree efficiency would be from random variance caused by changes in insertion
order.
The difference between the ratio of distance computations done for Half-Batch (H)
and Incremental (I) index construction is shown in Figure 7. That is to say, if rH =
Distance Computations with Half-Batch
Distance Computations Brute Force , and rB has the same definition but for the Batch construction, then the y-axis of the figure shows rB − rH . This is also plot for the difference between
19

Raff and Nicholas

6

·10−2

MNIST8m

MNIST

4

·10−2

VxHeaven
RBCImp , H
RBCImp , I
VPMV , H
VPMV , I

10−1
3
4

10−2
2
10−3

2
1

10−4
0

0

10−5
100

·10−3

101
k

0

102

20

40

60

80

100

100

k

Covtype

·10−2

IMDB Movies

·10−2

101
k

102

ILSVRC

1

2
6

0.8
1

0.6

4

0.4
2

0

0.2
0

0
100

101
k

102

100

101
k

102

100

101
k

102

Figure 7. Difference in the number of distance computations needed as a function of the desired
number of neighbors k. The y-axis is the difference in the ratio of distance computations compared
to a brute-force search. We note that the scale on the y-axis is different for various figures, and the
small scale indicates that incremental construction has little impact on query efficiency.

incremental construction, i.e., rB − rI . When this value is near zero, it means that both the
Batch and Half-Batch or Incremental construction approaches have avoided a similar number
of distance computations.
We remind the reader that Half-Batch is where the dataset is constructed using the
standard batch construction approach for the first n/2 data-points, and the remaining n/2
are inserted incrementally. Incremental construction builds the index from empty to full
using only the incremental insertions.
Positive values indicate an increase in the number of distance queries needed. Negative
values indicate a reduction in the number of distance queries needed, and are generally an
indication of problem variance. That is to say, when the difference in ratios can go negative,
it’s because the natural variance (caused by insertion order randomness) is greater than
the impact of the incremental construction. Such scenarios would generally be considered
favorable, as it would indicate that our modifications have no particular positive or negative
impact.
We first note a general pattern in that the difference in query efficiency can go up or
down with changes in the desired number of neighbors k. This will be an artifact of both the
dataset and distance metric used, and highlights the importance of testing metric structures

20

Toward Metric Indexes for Incremental Insertion and Querying

over a large range of k. Testing over a wide range of k has not been historically done in
previous works, usually performing only the 1 − nn search.
In our results we can see that the RBC algorithm performs best in these tests. The
RBCImp approach’s pruning ability is minimally impacted by changes in construction for all
datasets and values of k. The largest increase is on MNIST for k = 1, where the Half-Batch
insertion scenario increases from 59.4% to 60.6%, an increase of only 1.2 percentage points.
It makes sense that the RBCImp approach would have a consistent minimal degradation in
query efficiency, as the structure of the RBC is coarse, and our incremental insertion strategy
closely matches the behavior of the batch creation strategy.
The VPMV -tree does not perform as well as the RBCImp , and we can see that incremental construction always has a more larger, but still small, impact on its performance
for all datasets. The only case where this exceeds a two percentage point difference is on
the MNIST8m dataset, where a ≈ 7.6% point gap occurs for incremental and half-batch
construction. The larger impact on the VPMV ’s performance is understandable given that
our insertion procedure does not have the same information available for choosing splits,
which may cause sub-optimal choices.
Our expectation would be that the VPMV ’s performance would degrade more when using
incremental (I) insertion rather than half-batch (H), as the half-batch insertion will get
to use more datapoints to estimate the split point for nodes higher up in the tree. Our
results generally support this hypothesis, with VPMV (I) causing more distance queries to
be performance than the (H) case. However, for MNIST8m, VxHeaven, and ILSVRC, the
performance gap is not that large across the tested values of k. This suggests that the
loosened bounds during insertion may also be an issue impacting the efficiency after insertions.
One possible way to reduce this impact would be to add multiple vantage points dynamically
during insertion, to avoid impacting the existing low/high bounds of the VP-tree. Such
Multi-Vantage-Point (MVP) trees have been explored previously(Bozkaya and Ozsoyoglu,
1999) in a batch construction context. We leave research in exploiting such extensions to to
future work.
Regarding the impact on query efficiency given incremental insertions, we can confidently
state that the RBC approach is well poised to this part of the problem, with almost no
negative impact to efficiency. The VP-tree does not fair quite as well, but is still more efficient
than the RBCImp algorithm in all of these cases after construction from only incremental
insertions.
Overall, we can draw some immediate conclusions with respect to our proposed changes
to Cover-trees, VP-trees, and the RBC index. First, that VP-trees in general strike a strong
balance between construction time cost and query time efficiency across many datasets with
differing metrics. For both the RBC and VP tree, we can improve their query time efficiency
across the board. These improvements come with minimal cost, and so we can consider
them exclusively in section 6 where we look at incremental insertions and querying. We also
observe that the Cover-tree is significantly degraded at insertion/construction time by when
using the LZJD distance.

21

Raff and Nicholas

6. Evaluation of Incremental Insertion-Query Efficiency
At this point we have shown that RBCImp and VPMV are improvements over the original
RBC and VP-tree algorithms in terms of query efficiency, with no significant impact on the
construction time. We have also shown that the indexes constructed by them are still effective
are pruning distance computations, which encourages their use. We can now evaluate their
overall effectiveness when we interleave insertions and queries in a single system.
In this section we now consider the case of evaluating each index from the context of
incremental insertion and querying. Contrasting with the standard scenario, where we
build an index and immediately query it (usually for k-nearest neighbor classification, or
some similar purpose), we will be building an index and evaluating the number of distance
computations performed after construction. This scenario corresponds to many realistic use
cases, where a large training set is deployed for use, and new data added to the index over
time.
Given a dataset with n items in it, our evaluation procedure will consider r queries (or
"reads") and w insertions (or "writes") to the index. The naive case, where we perform
brute force search, there is no cost to writing to the index, only when we perform a query.
This brute force approach also represents our baseline for the maximum number of distance
computations needed to answer the queries.
Similar to data structures for storing and accessing data and concurrency tools, we may
also explore differing ratios of reads to writes. In our experiments we evaluated insert/query
ratios from 100:1 to 1:100. In all cases, we found that the most challenging scenario was when
we had 100 insertions for each query. This is not surprising, as all of our data structures
have a non-zero cost for insertions, and in the case of RBC and Cover-trees, can be quite
significant. Thus, below we will only present results for the case where we have 100 insertions
for each query, and our tests will limited to 1000 insertions due to runtime constraints7 . We
construct each initial index on half of the data points, using the batch construction method.
For the Cover-tree, only CoverB produces reasonable insertion/query performance, as the
maxdist bound can’t be maintained when re-balancing occurs. Using the original loose bound
causes a considerable reducing in efficiency at query time. By recording the multiplicative
difference between the tighter bound Cover-tree and the original looser bound in CoverB in
Table 2, we can plot the performance of the ideal Cover-tree as a function of CoverB . This
gives us a measure of what the best possible performance of the Cover-tree would be in
this scenario, as it ignores all overheads in any potential scheme for selectively updating the
Cover-tree bound as items are inserted that would cause re-balancing. We will indicate this
ideal Cover-tree as CoverI .
The results of our methods are presented in Figure 8. Amongst the RBCImp , VPMV , and
CoverB algorithms, the VPMV dominates all other approaches. It successfully avoids the
most total distance computations to answer nearest neighbor queries for all values of k on all
datasets. This is not surprising given the cumulative results of section 5, which found the
VPMV to require the fewest distance computations during construction time and was always
either the most efficient at avoiding distance computations, or nearly behind the Cover-tree
approach.
7. We allowed a maximum of one week runtime for tests to complete in this scenario.

22

Toward Metric Indexes for Incremental Insertion and Querying

MNIST8m

MNIST

VxHeaven

100

1

1.2
0.9
0.8
0.7

RBCImp
VPMV
CoverB
CoverI

0.6
0.5

1.1

10−1

100

101
k

1
10−2

102

100

Covtype

101
k

100

102

101
k

102

ILSVRC

IMDB Movies
1

0.25

10−2
0.2
0.8
0.15
10−3

0.1

0.6

5 · 10−2
100

101
k

102

100

101
k

102

100

101
k

102

Figure 8. Fraction of distance computations needed (relative to naive approach) in incremental
scenario, with 100 insertions for every query. Does not include initial construction costs, only
subsequent insertion costs.

If we had an ability to obtain the maxdist bound for free, we can also see that the CoverI
approach is still not very competitive with the VPMV -tree. While CoverI does have better
performance than VPMV on some datasets, it often trails behind on the Covtype by nearly
an order of magnitude. Especially when we consider the failure of the Cover-trees to perform
with the LZJD distance on VxHeaven and VirusShare5m. This variability in performance
makes the Cover-tree less desirable to use for arbitrary distance metrics.
While the VPMV appear to be the best overall fit to our task, we note that our RBCImp
√
also makes a strong showing despite the O( n) complexity target instead of O(log(n)).
RBCImp consistently performs better than random guessing, which can’t be said for the
Cover-tree. On the more difficult datasets, it is often not far behind the VPMV -tree in
performance, though it is an order of magnitude less efficient on the Covtype and ILSVRC
datasets. The biggest weakness of the RBC approach is that the incremental insertions will
√
have an amortized cost, with the insertion time increasing dramatically every n insertions
to expand the representative set. If the number of insertions is known to be bounded, this
may be an avoidable cost – thus increasing the RBC’s practicality. We note as well that in
the case of datasets stored in a distributed index across multiple server’s, the RBC’s coarse
structure may allow for more efficient parallelization. This may be an important factor in
future work when we consider datasets larger than what can be stored on a single machine.

23

Raff and Nicholas

6.1 Discussion
While we have modified three algorithms for our scenario of incremental querying and
insertion, we note that there is a further unexplored area for improvement in the "Read
write" ratio. In our case it was most challenging for all algorithms to handle more "Writes"
per "read", as each insertion required multiple distance computations and the insertions did
not dramatically change the performance at query time. This is in part because we have
modified existing algorithms to support this scenario, and so the performance interleaving
insertions and queries closely follows the performance when we evaluate query by including
the construction cost, as we did in section 5.
Of the algorithms we have tested the VPMV performs best with the lowest construction
time, and is almost always the fastest at query time. This is also in the context of evaluation
in a single-threaded scenario. When we consider a multi-threaded scenario, the VPMV
can utilize multiple threads for index construction using the batch-construction approach.
However, insertion of a single data-point cannot easily be parallelized. The Cover-tree also
has this challenge.
Our RBCImp approach presents a potential advantage over both of these algorithms
when we consider the multi-thread or distributed scenario. As a consequence of how the
√
RBC algorithm achieves its O( n) insertion and query time, we can readily parallelize line
√
1 of Algorithm 3 on up to p processors, requiring only a reduce operation to determine
which processor had the closest representative. It may then be more practical than the
VPMV approach for extremely large indexes if sufficient compute resources are available.
The downside to the RBC algorithm comes when the representative set must be increased,
requiring more work and presenting a insertion cost that will periodically spike. This could
be remedied by amortizing the cost of increasing the representative set across the preceding
insertions, but we leave this to future work as we must consider the real-world efficiency of
an implementation to determine how practical a solution it would be.
In future work we hope to develop new algorithms that are specifically designed for
incremental insertion and querying. We note two potential high level strategies in which one
may develop methods that perform better for read and write heavy use-cases. We consider
these beyond the scope of our current work, which looks at modifying existing algorithms,
but may be fruitful inspiration for specialized methods.
6.1.1 Write & Insert Heavy
When we have multiple datapoints inserted before each query, it may become possible to use
the index itself to accelerate the insertion process. Say that there will be a set of Z points
inserted into the index at a time. We can cluster the members of Z by their density/closeness,
and insert each cluster together as a group. One option may be to find the medoid of the
group and its radius, which can then be used as a proxy point that represents the group
as a whole. One could then insert the sub-groups into the index with a reduced number of
distance computations if the triangle inequality can be used to determine that all members
of the group belong in the same region of the index. The group may then be dissolved as
such macro level pruning becomes impossible, or reduced into smaller sub-groups to continue
the process. The dual-tree query approach (Curtin and Ram, 2014), at a high level, presents
a similar strategy for efficiently answering multiple queries at a time.

24

Toward Metric Indexes for Incremental Insertion and Querying

6.1.2 Read & Query Heavy
Another scenario is that insertions into the index will be relatively rare, compared to the
amount of nearest neighbor queries given to the index. In this case it may be desired to
have the query process itself build and restructure the tree. This notion is in a similar spirit
to splay trees and the union-find algorithm (Tarjan and van Leeuwen, 1984; Tarjan, 1975;
Hopcroft and Ullman, 1973). Insertions to the dataset would be placed in a convenient
location, and their first distances computed when a new query is given. Say that xi was
a previously inserted point. Once we have a new query xq , the distance to the query is
obtained for the xi and for xq ’s nearest neighbors. If d(xi , xq ) ≈ c · d(xq , x(k) ), where x(k) is
xq ’s k’th nearest neighbor and c is some constant, we can then infer that xi should be placed
in a similar location in the index. As multiple insertions are performed, we can use these
distances with respect to the query to determine which points are related and should be kept
close in the index.

7. Conclusions and Future Work
We have now evaluated and improved three different algorithms, Cover Trees, Vantage-Point
Trees, Random Ball Covers, for the use case of incremental insertions and querying. We have
significantly improved the query efficiency of the later two with our new RBCImp and VPMV
variants, and introduced schemes to incrementally add to these collections. Evaluation of all
these methods was done with a number of datasets with varying sizes using four different
distance metrics. In doing so, we can conclude that the VPMV tree provides the best overall
performance for our task. It requires the fewest distance computations during construction,
is consistently one of the fastest at query time, and this balance produces the best overall
results when interleaving insertions and queries.
While already successful, the VPMV tree still has room for improvement. It has the
highest degradation to performance from insertions, which could perhaps be remedied
by a smarter update algorithm or the use of multiple vantage points. While the CoverB
algorithm could be improved by obtaining a better alternative bound than maxdist, it appears
obtaining a computational cheaper version maxdist bound itself is not sufficient to remedy
the performance gap when using the LZJD distance.

References
VX Heaven. URL https://vxheaven.org/.
A. Behm, C. Li, and M. J. Carey. Answering Approximate String Queries on Large Data Sets
Using External Memory. In Proceedings of the 2011 IEEE 27th International Conference
on Data Engineering, ICDE ’11, pages 888–899, Washington, DC, USA, 2011. IEEE
Computer Society. ISBN 978-1-4244-8959-6. doi: 10.1109/ICDE.2011.5767856. URL
http://dx.doi.org/10.1109/ICDE.2011.5767856.
J. L. Bentley. Multidimensional Binary Search Trees Used for Associative Searching. Commun.
ACM, 18(9):509–517, 9 1975. ISSN 0001-0782. doi: 10.1145/361002.361007. URL http:
//doi.acm.org/10.1145/361002.361007.

25

Raff and Nicholas

A. Beygelzimer, S. Kakade, and J. Langford. Cover trees for nearest neighbor. In International
Conference on Machine Learning, pages 97–104, New York, 2006. ACM. URL http:
//www.cs.princeton.edu/courses/archive/spr05/cos598E/bib/covertree.pdf.
E. Biçici and D. Yuret. Locally scaled density based clustering. In B. Beliczynski, A. Dzielinski,
M. Iwanowski, and B. Ribeiro, editors, Adaptive and Natural Computing Algorithms, page
739–748, Warsaw, Poland, 2007. Springer-Verlag. URL http://www.springerlink.com/
index/0116171485446868.pdf.
J. A. Blackard and D. J. Dean. Comparative accuracies of artificial neural networks
and discriminant analysis in predicting forest cover types from cartographic variables. Computers and Electronics in Agriculture, 24(3):131–151, 1999. ISSN 01681699.
doi: 10.1016/S0168-1699(99)00046-0. URL http://www.sciencedirect.com/science/
article/pii/S0168169999000460.
T. Bozkaya and M. Ozsoyoglu. Indexing large metric spaces for similarity search queries.
ACM Transactions on Database Systems (TODS), 24(3):361–404, 1999. URL http:
//dl.acm.org/citation.cfm?id=328959.
L. Breiman, J. Friedman, C. J. Stone, and R. Olshen. Classification and Regression Trees.
CRC press, 1984.
R. J. G. B. Campello, D. Moulavi, and J. Sander. Density-Based Clustering Based on
Hierarchical Density Estimates. In J. Pei, V. Tseng, L. Cao, H. Motoda, and G. Xu,
editors, Advances in Knowledge Discovery and Data Mining, pages 160–172. Springer
Berlin Heidelberg, 2013. ISBN 978-3-642-37455-5. doi: 10.1007/978-3-642-37456-2{\_}14.
URL http://link.springer.com/10.1007/978-3-642-37456-2_14.
L. Cayton. Accelerating Nearest Neighbor Search on Manycore Systems. IEEE 26th
International Parallel and Distributed Processing Symposium, pages 402–413, 5 2012. doi:
10.1109/IPDPS.2012.45. URL http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.
htm?arnumber=6267877.
T. F. Chan, G. H. Golub, and R. J. LeVeque. Algorithms for Computing the Sample
Variance: Analysis and Recommendations. The American Statistician, 37(3):242, 8 1983.
ISSN 00031305. doi: 10.2307/2683386. URL http://www.jstor.org/stable/2683386?
origin=crossref.
K. L. Clarkson. Nearest neighbor searching in metric spaces: Experimental Results for sb(S).
Technical report, Bell Laboratories, Lucent Technologies, New Jersey, 2002.
R. R. Curtin and P. Ram. Dual-tree Fast Exact Max-kernel Search. Statistical Analysis
and Data Mining, 7(4):229–253, 8 2014. ISSN 1932-1864. doi: 10.1002/sam.11218. URL
http://dx.doi.org/10.1002/sam.11218.
R. A. Finkel and J. L. Bentley. Quad Trees a Data Structure for Retrieval on Composite
Keys. Acta Informatica, 4(1):1–9, 3 1974. ISSN 0001-5903. doi: 10.1007/BF00288933.
URL http://dx.doi.org/10.1007/BF00288933.

26

Toward Metric Indexes for Incremental Insertion and Querying

K. Fukunage and P. Narendra. A Branch and Bound Algorithm for Computing k-Nearest
Neighbors. IEEE Transactions on Computers, C-24(7):750–753, 1975. ISSN 0018-9340.
doi: 10.1109/T-C.1975.224297. URL http://ieeexplore.ieee.org/xpl/freeabs_all.
jsp?arnumber=1672890.
F. Gieseke, J. Heinermann, C. Oancea, and C. Igel. Buffer K-d Trees: Processing Massive
Nearest Neighbor Queries on GPUs. In Proceedings of the 31st International Conference on
International Conference on Machine Learning - Volume 32, ICML’14, pages I–172–I–180.
JMLR.org, 2014. URL http://dl.acm.org/citation.cfm?id=3044805.3044826.
R. Gove, J. Saxe, S. Gold, A. Long, and G. Bergamo. SEEM: A Scalable Visualization for
Comparing Multiple Large Sets of Attributes for Malware Analysis. In Proceedings of
the Eleventh Workshop on Visualization for Cyber Security, VizSec ’14, pages 72–79, New
York, NY, USA, 2014. ACM. ISBN 978-1-4503-2826-5. doi: 10.1145/2671491.2671496.
URL http://doi.acm.org/10.1145/2671491.2671496.
A. Guttman. R-trees: a dynamic index structure for spatial searching. In 1984 ACM
SIGMOD international conference on Management of data, pages 47–57, New York, NY,
1984. ACM. ISBN 0897911288. URL http://dl.acm.org/citation.cfm?id=602266.
J. E. Hopcroft and J. D. Ullman. Set Merging Algorithms. SIAM Journal on Computing, 2
(4):294–303, 12 1973. ISSN 0097-5397. doi: 10.1137/0202024. URL http://epubs.siam.
org/doi/10.1137/0202024.
X. Hu, T.-c. Chiueh, and K. G. Shin. Large-scale Malware Indexing Using Function-call
Graphs. In Proceedings of the 16th ACM Conference on Computer and Communications
Security, CCS ’09, pages 611–620, New York, NY, USA, 2009. ACM. ISBN 978-1-60558-8940. doi: 10.1145/1653662.1653736. URL http://doi.acm.org/10.1145/1653662.1653736.
X. Hu, K. G. Shin, S. Bhatkar, and K. Griffin. MutantX-S: Scalable Malware Clustering
Based on Static Features. In Presented as part of the 2013 USENIX Annual Technical
Conference (USENIX ATC 13), pages 187–198, San Jose, CA, 2013. USENIX. ISBN 978-1931971-01-0. URL https://www.usenix.org/conference/atc13/technical-sessions/
presentation/hu.
M. Izbicki and C. R. Shelton. Faster Cover Trees. In Proceedings of the Thirty-Second
International Conference on Machine Learning, volume 37, 2015.
J. Jang, D. Brumley, and S. Venkataraman. BitShred: Feature Hashing Malware for
Scalable Triage and Semantic Analysis. In Proceedings of the 18th ACM conference on
Computer and communications security - CCS, pages 309–320, New York, New York,
USA, 2011. ACM Press. ISBN 9781450309486. doi: 10.1145/2046707.2046742. URL
http://dl.acm.org/citation.cfm?doid=2046707.2046742.
I. Kamel and C. Faloutsos. Hilbert R-tree: An Improved R-tree Using Fractals. In Proceedings
of the 20th International Conference on Very Large Data Bases, VLDB ’94, pages 500–509,
San Francisco, CA, USA, 1994. Morgan Kaufmann Publishers Inc. ISBN 1-55860-153-8.
URL http://dl.acm.org/citation.cfm?id=645920.673001.
27

Raff and Nicholas

T. Kanungo, D. Mount, N. Netanyahu, C. Piatko, R. Silverman, and A. Wu. An efficient
k-means clustering algorithm: analysis and implementation. IEEE Transactions on
Pattern Analysis and Machine Intelligence, 24(7):881–892, 2002. ISSN 0162-8828. doi:
10.1109/TPAMI.2002.1017616.
D. R. Karger and M. Ruhl. Finding Nearest Neighbors in Growth-restricted Metrics.
In Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing,
STOC ’02, pages 741–750, New York, NY, USA, 2002. ACM. ISBN 1-58113-495-9. doi:
10.1145/509907.510013. URL http://doi.acm.org/10.1145/509907.510013.
J. Kim, S.-G. Kim, and B. Nam. Parallel multi-dimensional range query processing with
R-trees on GPU. Journal of Parallel and Distributed Computing, 73(8):1195–1207, 2013.
ISSN 07437315. doi: 10.1016/j.jpdc.2013.03.015. URL http://www.sciencedirect.com/
science/article/pii/S0743731513000592.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document
recognition. Proceedings of the IEEE, 86(11):2278–2324, 11 1998. ISSN 0018-9219. doi:
10.1109/5.726791.
B. Li, K. Roundy, C. Gates, and Y. Vorobeychik. Large-Scale Identification of Malicious
Singleton Files. In 7TH ACM Conference on Data and Application Security and Privacy,
2017.
K. Li and J. Malik. Fast k-Nearest Neighbour Search via Dynamic Continuous Indexing. In
Proceedings of The 33rd International Conference on Machine Learning, pages 671–679,
2016. URL http://arxiv.org/abs/1512.00442.
S. Li and N. Amenta. Brute-Force k-Nearest Neighbors Search on the GPU. In Proceedings
of the 8th International Conference on Similarity Search and Applications - Volume
9371, SISAP 2015, pages 259–270, New York, NY, USA, 2015. Springer-Verlag New
York, Inc. ISBN 978-3-319-25086-1. doi: 10.1007/978-3-319-25087-8{\_}25. URL http:
//dx.doi.org/10.1007/978-3-319-25087-8_25.
S. P. Lloyd. Least squares quantization in PCM. IEEE Transactions on Information
Theory, 28(2):129–137, 3 1982. ISSN 0018-9448. doi: 10.1109/TIT.1982.1056489. URL
http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=1056489.
G. Loosli, S. Canu, and L. Bottou. Training Invariant Support Vector Machines using
Selective Sampling. In L. Bottou, O. Chapelle, D. DeCoste, and J. Weston, editors,
Large Scale Kernel Machines, pages 301–320. MIT Press, Cambridge, MA., 2007. URL
http://leon.bottou.org/papers/loosli-canu-bottou-2006.
L. V. D. Maaten and G. Hinton. Visualizing Data using t-SNE. Journal of Machine Learning
Research, 9:2579–2605, 2008.
A. Mohaisen and O. Alrawi. Unveiling Zeus: Automated Classification of Malware Samples.
In Proceedings of the 22Nd International Conference on World Wide Web, WWW ’13
Companion, pages 829–832, New York, NY, USA, 2013. ACM. ISBN 978-1-4503-2038-2.
doi: 10.1145/2487788.2488056. URL http://doi.acm.org/10.1145/2487788.2488056.
28

Toward Metric Indexes for Incremental Insertion and Querying

K. Narayan, A. Punjani, and P. Abbeel. Alpha-Beta Divergences Discover Micro and Macro
Structures in Data. In Proceedings of The 32nd International Conference on Machine
Learning, pages 796–804, 2015.
S. M. Omohundro. Five Balltree Construction Algorithms. Technical report, International
Computer Science Institute, 1989.
O. Pele and M. Werman. Fast and robust Earth Mover’s Distances. In 2009 IEEE 12th
International Conference on Computer Vision, pages 460–467. IEEE, 9 2009. ISBN 9781-4244-4420-5. doi: 10.1109/ICCV.2009.5459199. URL http://ieeexplore.ieee.org/
lpdocs/epic03/wrapper.htm?arnumber=5459199.
E. Raff and C. Nicholas. An Alternative to NCD for Large Sequences, Lempel-Ziv Jaccard
Distance. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge
Discovery and Data Mining - KDD ’17, pages 1007–1015, New York, New York, USA,
2017a. ACM Press. ISBN 9781450348874. doi: 10.1145/3097983.3098111. URL http:
//dl.acm.org/citation.cfm?doid=3097983.3098111.
E. Raff and C. K. Nicholas. Lempel-Ziv Jaccard Distance, an Effective Alternative to Ssdeep
and Sdhash. arXiv preprint arXiv:1708.03346, 8 2017b. URL https://arxiv.org/abs/
1708.03346.
J.-M. Roberts. Virus Share, 2011. URL https://virusshare.com/.
Y. Rubner, C. Tomasi, and L. J. Guibas. The Earth Mover’s Distance as a Metric for
Image Retrieval. International Journal of Computer Vision, 40(2):99–121, 2000. ISSN
09205691. doi: 10.1023/A:1026543900054. URL http://link.springer.com/10.1023/A:
1026543900054.
O. Russakovsky, J. Deng, H. Su, J. Krause, S. Satheesh, S. Ma, Z. Huang, A. Karpathy,
A. Khosla, M. Bernstein, A. C. Berg, and L. Fei-Fei. ImageNet Large Scale Visual
Recognition Challenge. International Journal of Computer Vision (IJCV), 115(3):211–252,
2015. doi: 10.1007/s11263-015-0816-y.
E. C. Spafford. Is Anti-virus Really Dead? Computers & Security, 44:iv, 2014. ISSN
0167-4048. doi: http://dx.doi.org/10.1016/S0167-4048(14)00082-0. URL http://www.
sciencedirect.com/science/article/pii/S0167404814000820.
J. Tang, J. Liu, M. Zhang, and Q. Mei. Visualizing Large-scale and High-dimensional Data.
In Proceedings of the 25th International Conference on World Wide Web, WWW ’16, pages
287–297, Republic and Canton of Geneva, Switzerland, 2016. International World Wide Web
Conferences Steering Committee. ISBN 978-1-4503-4143-1. doi: 10.1145/2872427.2883041.
URL http://dx.doi.org/10.1145/2872427.2883041.
R. E. Tarjan. Efficiency of a Good But Not Linear Set Union Algorithm. Journal of the
ACM (JACM), 22(2):215–225, 4 1975. ISSN 0004-5411. doi: 10.1145/321879.321884. URL
http://doi.acm.org/10.1145/321879.321884.

29

Raff and Nicholas

R. E. Tarjan and J. van Leeuwen. Worst-case Analysis of Set Union Algorithms. Journal of
the ACM (JACM), 31(2):245–281, 3 1984. ISSN 0004-5411. doi: 10.1145/62.2160. URL
http://doi.acm.org/10.1145/62.2160.
D. Tarlow, K. Swersky, L. Charlin, I. Sutskever, and R. Zemel. Stochastic k-Neighborhood
Selection for Supervised and Unsupervised Learning. In S. Dasgupta and D. McAllester,
editors, Proceedings of the 30th International Conference on Machine Learning, volume 28
of Proceedings of Machine Learning Research, pages 199–207, Atlanta, Georgia, USA, 2013.
PMLR. URL http://proceedings.mlr.press/v28/tarlow13.html.
J. K. Uhlmann. Satisfying general proximity / similarity queries with metric trees. Information
Processing Letters, 40(4):175–179, 11 1991a. ISSN 00200190. doi: 10.1016/0020-0190(91)
90074-R. URL http://linkinghub.elsevier.com/retrieve/pii/002001909190074R.
J. K. Uhlmann. Implementing Metric Trees to Satisfy General Proximity / Similarity Queries.
Technical report, Naval Research Laboratory, Washington, D.C., 1991b.
L. van der Maaten. Accelerating t-SNE using Tree-Based Algorithms. Journal of Machine Learning Research, 15:3221–3245, 2014. URL http://jmlr.org/papers/v15/
vandermaaten14a.html.
A. Walenstein, M. Venable, M. Hayes, C. Thompson, and A. Lakhotia. Exploiting similarity
between variants to defeat malware. In Proc. BlackHat DC Conf, 2007.
B. P. Welford. Note on a Method for Calculating Corrected Sums of Squares and Products.
Technometrics, 4(3):419, 8 1962. ISSN 00401706. doi: 10.2307/1266577. URL http:
//www.jstor.org/stable/1266577?origin=crossref.
P. Yianilos. Data structures and algorithms for nearest neighbor search in general metric
spaces. In Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms,
page 311–321. Society for Industrial and Applied Mathematics, 1993. URL http://dl.
acm.org/citation.cfm?id=313789.

Appendix A. Corrections to Simplified Cover Tree
We encountered two difficulties in replicating the simplified cover tree results of Izbicki
and Shelton (2015). We detail these two issues and their remediations in this section for
completeness and reproducibility. In the below algorithm descriptions we will use the same
terminology and description as the algorithm’s original paper, but note our changes in green.
We now review some of the properties needed to understand our corrections. The
simplistic such property is that each node p in the Cover tree has an associated level l,
which we can obtain as l = level(p). Each child cp of p must also satisfy the property that
level(p) = level(cp ) + 1.
Using a node’s level, we can define its coverdist as coverdist(p) = 2level(p) . Each child cp
of p will satisfy the covering invariant property, d(cp , p) ≤ coverdist(p), ∀cp ∈ children(p).
We also must make use of the maxdist bound discussed in subsection 3.1, which we
make more explicit as: maxdist(p) = arg maxdp ∈descendants(p) d(dp , p). This is the maximum
30

Toward Metric Indexes for Incremental Insertion and Querying

distance from one node p to any descendant note of p. If p is a leaf node, meaning it has no
children, then maxdist(p) = 0.
A.1 Nearest Neighbor Correction
We present the revised nearest neighbor search procedure for the simplified Cover-tree in
Algorithm 5. The green d(x, p) term was originally presented to be d(y, q). We show that
this is not correct using a simple counter example using scalar node values and the euclidean
distance.
Algorithm 5 Cover Tree Find Nearest Neighbor
Require: cover tree p, query point x, nearest neighbor so far y
1: if d(p, x) < d(y, x) then
2:
y←p
3: for each child q of p sorted by distance to x do
4:
if d(y, x) > d(x, q) −maxdist(q) then
5:
y ← findNearestNeighbor(q, x, y)
6: return y

.Original paper used d(y, q)

Consider the Cover-tree with root α, that stores value 5. α has one child, β, which has
the value −2. This is the whole tree.
We would begin on line one of the algorithm, with p ← α and we will use our query point
x to have a value of 0. d(p, x) is 5, and we have no nearest neighbor so far, so y ← p (which
is α) becomes the nearest neighbor so far.
We will obtain q ← β as it is the only child of α, which leads us to evaluate the original
expression
d(y, x) > d(y, q) − maxdist(q)
| {z }
| {z }
| {z }

=5−0=5

=5−(−2)=7

=0

Because 5 > 7 is false, the if statement fails, and we then break from the loop, returning
y as the nearest neighbor to x with a distance of 5. But x’s value is 0, and β’s is −2, which
is a distance of only two away.
A.2 Insertion Correction
We also provide a correction to the insertion procedure of the simplified Cover-tree. Our fixed
version is presented in Algorithm 6, with the green text indicating only added statements to
the algorithm.
The issue with the original procedure occurs when an outlier x is inserted into the index,
the distance from which to any point in the dataset is larger than the largest pairwise distance
of any two points in the existing Cover-tree. This is because the 2coverdist(p) ≥ maxdist(p)
in all cases. If x is farther than the maximum pairwise distance, then the simple bound on
line four may be true for a all points in a valid cover tree. This means the loop will never
exit, and will simply continue re-structuring the tree in search of a non-existing node that
can satisfy the loop condition.

31

Raff and Nicholas

We fix this by keeping track of the points visited in the tree, and only loop while there
is a potential candidate remaining. If no such candidate occurs because we have visited all
possible leaf nodes, the loop must exit so that the outlier may be inserted as the new root of
the tree.
Algorithm 6 Simplified Cover Tree Insertion
Require: Query q, desired number of neighbors k
1: procedure insert(cover tree p, data point x)
2:
if d(p, x) > covdist(p) then
3:
z←∅
4:
while d(p, x) > 2covdist(p) and |descendants(p)| > |z| do
5:
Remove any leaf q from p\z
6:
p0 ← tree with root q and p as only child
7:
p ← p0
8:
return tree with x as root and p as only child
9:
return INSERT_(p, x)
10: procedure insert_(cover tree p, data point x)
11:
for all q ∈ children(p) do
12:
if d(q, x) ≤ covdist(q) then
13:
q 0 ← INSERT_(q, x)
14:
p0 ← p with child q replaced with q 0
15:
return p0
16:
return p with x added as a child

From a practical implementation perspective, we note two additional choices. First,
rather than attempt to remove leaf nodes in the specified form above, it is easier to define
a specific leaf removal order and leaf insertion order. For example, if one always removes
the least recently added leaf node, we will obtain a consistent ordering of the leaf nodes as
we iterate line four of the algorithm. This makes it easy to use simple cycle detection to
determine that the all possible children have been visited, and then escape the loop when
this occurs.
To speed up insertion of outlier points, we also note that the covering invariant can
be used to catch extreme outliers. If d(p, x) > 4covdist(p), then we can skip the loop
entirely and proceed directly to line eight of the algorithm. This bound is easy to see, as
2covdist(p) ≥ maxdist(p). Assuming that there exists a descendant point γ that is maximally
far from p. Let ζ be the point maximally far from γ, and let d(γ, ζ) be the maximal pairwise
distance for all points in the Cover-tree. Direct application of the triangle inequality gives us
d(γ, ζ) ≤ d(γ, p) + d(p, ζ)
This bounds the distance between these points by their distance to the root. The covering
invariant tells us that 2coverdist(p) ≥ maxdist(p). Therefore it must be the case that
d(γ, ζ) ≤ 2coverdist(p) + 2coverdist(p)
Which reduces to the bound d(γ, ζ) ≤ 4coverdist(p). Thus if a new query violates this
bound, we know that no point in the whole tree can satisfy the loop on line 4.

32

