# Efficient Similarity Indexing and Searching in High Dimensions

I found this recent document, containing simple algorithm that properly indexes high dimensional vectors for binary search later.

Algorithm basically uses random partition forest that randomly divides high dimensional vector space into cells of convex hyper polyhedrons bounded by hyper-planes. Explanation might sound difficult, but the algorithm is quite simple I believe.

# Algorithm in General

Explanation:

The underlying idea of the algorithm is to search random convex hyper polyhedral neighborhoods of a query for its closest neighbors. In particular, each of the random neighborhoods is deliberately constructed to contain a controlled number of database points – neither too many, nor too few, for indexing accuracy and efficiency. We use an easily computed partitioning technique to randomly divide the high dimensional feature space into non-overlapping cells of convex hyper polyhedrons bounded by hyper-planes.

- Note 1.0

Parameters:

There are four parameters in the algorithm, namely, $$L$$, the number of random partitions used, $$r$$ , the split ratio, and capacity $$C$$, the maximum number of database points in a leaf node, and $$K$$, the number of indices

- Note 1.1

Notations:

The database $$P = \{p_0, p_1, p_2, ...,p_{N-1}\}$$ consists of $$N$$ data points in $$d$$-dimensional space where $$p_i=\{p_{i \, 0}, p_{i \, 1}, ... p_{i \, d-2}, p_{i \, d-1}\}$$ (so that data point is basically $$d$$-dimensional vector).

Then we define a random binary partition forest $$F$$ of size $$L$$, split ratio $$r$$ where $$(0 < r \leq 0.5)$$ and capacity $$C$$ as a set of $$L$$ random binary partition trees $$F=\{T_0,T_1,...,T_{t-1}\}$$ where the $$j-th$$ internal node of tree $$T^i$$ contains a binary test $$t_j ^ i$$ and each leaf node contains between $$r \cdot C$$ to $$C$$ database points. These parameters might be better explained in Note 1.1.

Random Testing:

Next important aspect is random testing, which helps us to partition tree data into smaller nodes.

We design a simple random test at each internal tree node to assign an incoming data point to one of its two children. The test is based on subspace projections of high dimensional features. Suppose the node $$l_i$$ contains $$n_i$$ data points $$\{x_0, x_1, ...,x_{n_{i} - 1}\}$$.

We randomly select an index set $$I_i = \{d_{i0}, d_{i1}, ..., d_{ik - 1}\}$$ of size $$K$$ $$(K \leq d)$$ where $$d_{ij} \in (0, 1,...,d_1)$$ and random coefficients $$\Xi = \{\xi_{i0}, \xi_{i1}, ...,\xi_{ik-1} \}$$ where $$\xi_{ij} \in [0, 1]$$, and compute for every feature vector $$x_j$$, a scale value $$y_j = \sum_{k=0}^{K-1} x_{jd_{ik}} \, \xi_{ik}$$ for $$j=0, ..., n_i - 1$$.

We then sort the $$y_js$$ and denote the sorted sequence as $$\{\tilde{y_{j}} \}$$. Randomly select $$\psi_i$$ between the $$100 \cdot > r$$ and $$100 \cdot (1-r)$$ percentile of points $$\{\tilde{y_{j}} \}$$, i.e., $$\psi_i \in [\tilde{y}_{n_i \cdot r}, \tilde{y}_{n_i \cdot > (1-r)}]$$. The random test $$t_i(x) = \sum_{k=0}^{K-1} x_{d_{ik}} - > \psi_i \geq 0$$ (Eq. 1) defines a hyper-plane which splits the polyhedron at node $$l_{i}$$ into two polyhedrons each containing no less than $$r \cdot n_i$$ points.

- Note 1.2

Algorithm steps (building random partition forest):

1. Randomly select without replacement a database data point $$p_i$$
2. Drop $$p_i$$ down the tree until it reaches a leaf node based on the tests at the internal nodes it encounters;
3. If the number of database points at the leaf node exceeds $$C$$, split the node into two children using a random hyper-plane generated according to Eq. 1. Save the random test with the now internal node.
4. Repeat the above steps until all data points have been inserted in the tree.

An ensemble of $$L$$ such trees are generated to form $$L$$ random partitions of the feature space. The trees, including random tests at the internal nodes and indices of database points at the leaf nodes, are saved for efficient search and query of the database.

- Note 1.3

Pseudo code:

TrainTrees(TreeNode T[], DataPoint X[])
{
for(i=0; i<L;i++)
TrainOneTree(T[i], X);
}
TrainOneTree(TreeNode T, DataPoint X[])
{
randomly_for_each(i in 0:N-1)
{
TreeNode node = T;
while (!node.IsLeaf())
{
if(node. randomTest (X[i]) == true)
node = node.leftChild;
else
node = node.rightChild;
}
if(node.GetNumerOfDataPoint() > C)
{
RandomTest t = RandomTest (node.GetDataPoints(), r);
node.randomTest = t;
TreeNode left(t.GetPassDataPoints(node.GetDataPoints()));
TreeNode right(t.GetFailDataPoints(node.GetDataPoints()));
node.leftChild = left;
node.rightChild = right;
node.ClearDataPoints();
}
}
}


# Python implementation

I basically took the most important parts from book, and tried to implement a simple node object with random test method:

class Node(object):
def __init__(self, dimension, capacity, ratio, indices):
self.left = None
self.right = None
self.dimension = dimension
self.capacity = capacity
self.ratio = ratio
self.indices = indices
self.data_points = []

def random_test(self, X):
self.data_points.append(X)
index_set = range(0, self.dimension)[:self.indices]
random.shuffle(index_set)
random_coefficients = [random.choice([0, 1]) for i in range(0, self.indices)]
scale_values = sorted([np.inner(data_point[:self.indices],
random_coefficients) for data_point in self.data_points])
test_bias = random.choice([np.percentile(scale_values, 100 * self.ratio),
np.percentile(scale_values, 100 * (1 - self.ratio))])
return (np.inner(self.data_points[self.dimension - 1], random_coefficients) - test_bias) >= 0


As visible, instead of summation, I've utilized inner product which I believe is appropriate. But something is missing from the code, which stops it from working properly.

# Problem

Document has few complexities which I do not understand at all, let's say we start from the root node, where we have the whole vector space. Are data points in root node the whole vector space itself? Also in Note 1.2, they mention that we take percentile of points, I've used np.percentile for this purpose, is it correct? Any help will be much appreciated.

Thank you!