Snip

Approximate box decomposition trees


Categories 


For Snip 
loading snip actions ... 

For Page 
loading url actions ... 
Arya et al. [4] have presented an optimal algorithm for approximate nearest neighbor search. They use a balanced box decomposition tree (bdtree) as their primary data structure. This tree combines two important properties of geometric data structures: First, as in the dtree case, the set of points is exponentially reduced. Second, the aspect ratio of the tree edges are bounded by a constant. Not even the optimized dtree is able to make this assurance, but quadtrees show this characteristic [4]. The actual box decomposition search tree is composed of splits and shrinks. Fig. (c) shows the general structure and Fig. presents two slices within this search tree.
HTML 
<h2><a name="SECTION00052000000000000000"> Approximate box decomposition trees</a> </h2> <p> Arya et al. [<a href="node21.html#Arya_1998">4</a>] have presented an optimal algorithm for approximate nearest neighbor search. They use a balanced box decomposition tree (bdtree) as their primary data structure. This tree combines two important properties of geometric data structures: First, as in the <img src="img1.png" alt="$ k$" align="bottom" border="0" height="14" width="13">dtree case, the set of points is exponentially reduced. Second, the aspect ratio of the tree edges are bounded by a constant. Not even the optimized <img src="img1.png" alt="$ k$" align="bottom" border="0" height="14" width="13">dtree is able to make this assurance, but quadtrees show this characteristic [<a href="node21.html#Arya_1998">4</a>]. The actual box decomposition search tree is composed of splits and shrinks. Fig. <a href="#epsilonApx"><img alt="[*]" src="file:/usr/share/latex2html/icons/crossref.png" align="bottom" border="1"></a> (c) shows the general structure and Fig. <a href="#bd_tree"><img alt="[*]" src="file:/usr/share/latex2html/icons/crossref.png" align="bottom" border="1"></a> presents two slices within this search tree.</p> 
