

(1) Ranger page (slide1.c)

"Ranger
 A program for exploring algorithms and data structures 
 for nearest neighbor and orthogonal range queries in high 
 dimensional spaces"

(2) Names and affiliations page (slide2.c)
   "Michael Murphy 
        and 
    Steven Skiena
    Department of Computer Science
    State University of New York
    Stony Brook"       


(3) Menus and action example  (15 seconds)

Nearest neighbor search is one of the fundamental problems
in computational geometry.
Traditional Voronoi diagram-based methods lose appeal
in higher dimensions, in favor of multidimensional search trees.
{\em Ranger} is a tool we have developed at SUNY Stony Brook
for visualizing and experimenting with
nearest neighbor and orthogonal range queries in high-dimensional data sets,
using multidimensional search trees.

This video demonstrates {\em Ranger}'s capabilities,
and explores the performance of four multi-dimensional data structures
designed to obtain sublinear query time without extensive preprocessing
or storage.


(4) Displaying and understanding multi-dimensional data  (10 seconds)

{\em Ranger} includes generators for point sets under a variety of different
distributions, including uniform in a ball or cube, as well as several
degenerate distributions which tend to frustrate heuristic data structures.

(1000 points from henon attractor in 4-dimensions)

To gain a feeling for the structure in a given higher-dimensional data set,
{\em Ranger} provides the complete set of all two-dimensional orthographic
projections. This gives a $d \times d$ matrix of projections,
where the $i$th row and $j$th column is the projection into the $i$-$j$ plane.
In this representation, each projection along the main diagonal of this matrix
corresponds to a one-dimensional projection of the data.

(show projection dimensions 1,2)

Should we discover an interesting projection,
we can enlarge it to get a closer look.
  
(show projection dimensions 1,4)


(5) Other Distributions (30 seconds)

Annulus in 5 dimensions

Spokes in 5 dimensions

Sphere in 25 dimensions


(6) Displaying data structures 

The heuristic data structures Ranger supports define heirarchical
decompositions of space.
For k-d trees, the decomposition is defined by a tree of hyperplanes.

  a)   (Ball in two dimensions 500 points)

     (Algorithm naivekd)

For each type of search structure, {\em Ranger} allows us to look at a
representation of the underlying tree.
Here is the original k-d tree as described in Bentley's original 1976 paper.

     (display data structure)

     (Algorithm optkd). 

For best performance, the space decomposition should be as balanced as possible.

More sophisticated k-d tree algorithms, such as the median $k-d$ tree,
selects the cut-value based on the median and the dimension based on the
maximum spread of the coordinates.
This yields a data structure with a more balanced space paritition.

     (Algorithm sproullkd)   

In Sproull's variant of $k$-d trees, the cut-planes are not
not necessarily orthogonal to the axies, but based on the
principle eigenvalues of the covarience matrix of the points.
 
     (Algorithm vptree)

The vantage point tree is a recently developed data structure that choses 
vantage points to perform a spherical decomposition of the search space.
Yianilos claims this method is suited for 
non-Minkowski metrics (unlike $kd$-trees)
and for lower dimensional objects embedded 
in a higher dimensional space.


  b) (100 cubediam)

The benefits of Sproull's k-d tree become apparent for
degenerate data sets, such as when all points lie on a diagonal.
This should reduce to a one-dimensional searching problem.  However
 
     (naive k-d)

The Naive k-d tree is not sophisticiated enough to see this.

      (optkd)

Nor, really, is the more refined, median k-d tree.

   
      (sproull k-d tree)

The sproull kdtree, is however, more adaptive and clearly reduces the
two-dimensional searching problem into a one dimensional one.
      
      (vptree)

The resulting space decomposition for VP-trees is certainly striking,
although it does not adapt to this distribution as nicely as Sproull's.


   c) There certain distributions, however, when it is not entirely obvious
      which method will do well.
      (annulus 200p) 
      (quickly naivekd,optkd,sproullkd)


(2:00)

(7) Animation of data structures 2d

   a) Good (sphere  30)

{\em Ranger} can also be used to animate the nearest neighbor search process,
by highlighting each region in yellow as it is visited.
If the nearest neighbor can potentially lie in this region, it must be
explored, otherwise the search can be prunned.

a)  When we search for the nearest neighbor to the origin, in the center of the screen,
	only certain cells above the first division need be visited.


b)   When we ask for the three nearest neighbors, it becomes necessary to visit
	both half-spaces.

 	In any search each leaf node is visited at most once.   We highlight all visited leaves in green.

  	Any cell which is further from the origin than the nearest neighbors to date are pruned.

c)  For degenerate distributions, k-d trees may perform poorly.  In finding
	the nearest neighbor to the center of these points on a circle, all leaf-nodes
	in the tree must be visited.
	


(1:30)

(8) Animation of data structures 3d 

{\em Corners(d)} - $x_1, x_2$ drawn uniformly around $(0,2)$, $(2,0)$,
$(0,0)$, and $(2,2)$ with
$x_3, \ldots, x_d$ from {\em uniform(1)}.  

Here {\em Ranger} animates a nearest neighbor search around the origin
for a 4-corners distribution in three dimensions, using a median k-d tree.
Because the origin is roughly equidistant between the four corners,
each eventually is eventually visited.
As the dimension increases, each cell has more neighbors to check, which
limits the effectiveness of $k-d$ tree structures to moderate dimensional
spaces.

CUT THIS SHORT!!



(9) Nearest neighbor search with different metrics.  

Ranger can be used to illustrate some of the subtleties of proximity search
It supports orthogonal range queries and nearest neighbor search in up to 25 dimensions
for all Minkowski metrics.

(Ball 10,000)
Here, for 10,000 points uniform in a sphere, {\em Ranger} finds the 1000
nearest neighbors to the origin, highlighted in red.
Observe how the shape of the highlighted region changes as we move from
the L1 or  Manhattan metric, to L2 or Euclidean metric L_3, the  L_5,
and finally to the L_Infinity metric. 

(0:20 seconds max).



(10) Collapsing Spheres


Our intuition easily fails us in higher dimensions,
Here we present 10,000 points, selected uniformly within a hyper-sphere,
with the 5000 points closest to the origin, according to the Eulidian metric will be shaded in red.

2D - 
In two dimensions, the projection shows that the nearest neighbors 
clearly define a circle about the origin.

3D - 
However, in a two dimensional projection of points from a 3D sphere, we can see the
	red region start to diffuse among the more distant points.

4D -
With a 4D-sphere, the projection causes the distribution of points to appear non-uniform,
and the red-region diffuses further.


10D -
When we reach 10D, the distribution has clearly collapsed toward the center of the ball.


25D - 

By the time we search 25 dimensions, the nearest neighbors appear scattered
uniformly in the ball.
Watching as the nearest neighbors diffuse as the
dimensionality increases illustrates why proximity queries become
more difficult in higher-dimensional spaces.



(11) closing acknowlegments (slide3.c)
    "Special thanks to Lisa S., Rick Avila, and 
     Brian Tria for their assistance in the making of this video" 

In conclusion, we believe that Ranger is an interesting tool for investigating
higher dimensional geometric algorithms and data.

0:10 seconds


