Neighbor Graph

The Neighbor Graph is a data structure that maintains a neighborhood graph on a collection of neighbors and edges between them. Each vertex is associated with a cell of points centered at a single point. Each cell has a cell radius equal to the largest distance from the center to a point in the cell.

The neighbor graph provides for two needs that arise when adding a new point to a greedy permutation (i.e. a new vertex in the neighbor graph). First, it limits which vertices might be considered to move into the new cell. Only the vertices in a neighboring cell will be checked. Second, it helps us quickly find the neighbors of the new cell. These needs translate into the following two conditions.

  1. There is an edge from Cell A to Cell B if a point in B could be moved to the cell of a point in A or vice versa.

  2. If we add a point in A as the center of a new cell. Its neighbors will be a subset of the neighbors of neighbors of A.

These two conditions respectively suffice to guarantee that when a new cell is created, we can find the points in the cell and the neighbors. In practice, we may keep more neighbors, relying on distances to prune away edges that cannot indicate true neighbors according to the conditions above. Specifically, we keep edges \(A\to B\) if the distance from \(A\) to \(B\) is at most the radius of \(A\) plus the radius of \(b\) plus the maximum of the two radii. It’s not hard to check that if this condition does not hold, then, \(A\) and \(B\) cannot be neighbors.

This condition can be relaxed, connecting even more neighbors. By setting the nbrconstant, one \(A\to B\) if the distance from \(A\) to \(B\) is at most the radius of \(A\) plus the radius of \(b\) plus nbrconstant times the maximum of the two radii. The default setting is 1.

It is also possible to modify the neighbor graph to only move points to a new cell if their current cell is no longer an approximate nearest neighbor. This is accomplished by setting the moveconstant when constructing the NeighborGraph. Setting this constant to 1/2 checks if the distance to the new cell center would be at most 1/2 the distance to the current center. As a result, the points are all associated with cells centered at 2-approximate nearest neighbors. The default setting is 1, resulting in exact nearest neighbors. It is required that moveconstant <= nbrconstant.

Cells

The interface to a Cell is as follows.

class Cell(center)
addpoint(p)

Add the point p to the cell.

dist(point)

Return the distance between the center of the cell and point. Note, this allows the cell to be treated almost like a point.

pop()

Remove and return the farthest point in the cell.

Returns None if there there are no points other than the center.

updateradius()

Set the radius of the cell to be the farthest distance from a point to the center.

There are three public attributes:

  • points an iterable collection of points.

  • center the center point.

  • radius the max distance between the center and a point in the cell.

The NeighborGraph

A NeighborGraph is a Graph.

class NeighborGraph(points, root=None, nbrconstant=1, moveconstant=1)
addcell(newcenter, parent)

Add a new cell centered at newcenter.

The parent is a suffciently close cell that is already in the graph. It is used to find nearby cells to be the neighbors. The cells are rebalanced with points moving from nearby cells into the new cell if it is closer.

prunenbrs(u)

Eliminate neighbors that are too far with respect to the current radius.

rebalance(a, b)

Move points from the cell b to the cell a if they are sufficiently closer to a.center.