library.html

SR-tree is an index structure for high-dimensional nearest neighbor queries

</pre>
</td></tr>
</table>
See also <a href="classes.html#HnPoint">HnPoint</a>,
<a href="classes.html#HnDataItem">HnDataItem</a>.
</blockquote>

Only the point having the same coordinates and the same attribute
value is removed from the index file. Points with different attributes
are intact.

</blockquote>
</li>

</ul>

<hr>

<a name="static"></a><h3>2. Static construction method</h3>

<blockquote>
The following functions build an index file for a given data set and
return the pointer to a data structure associated with that file. You
can apply the insertion and the deletion methods described above to
the index file built by these functions.

The static construction method is not covered by the original paper of
the SR-tree [<a href="references.html#KS97">KS97</a>]. The following
functions employ the static construction method proposed for the
VAMSplit R-tree [<a href="references.html#WJ96-1">WJ96-1</a>]. Since
the SR-tree is a variant of the R-tree, it is straightforward to apply
the static construction method of the VAMSplit R-tree to the
SR-tree. The difference between the VAMSplit R-tree and the SR-tree
built with these functions lies in the internal structure of non-leaf
nodes. While the R-tree employs a minimum bounding rectangle in order
to specify the region of a node, the SR-tree employs not only a
minimum bounding rectangle but also a bounding sphere whose center is
the centroid of the points in the subtree. The bounding sphere plays
an important role in the dynamic construction method. Its
effectiveness was originally presented in the paper of the SS-tree [<a
href="references.html#WJ96-2">WJ96-2</a>]. Thus, a non-leaf node of
the SR-tree contains the information on bounding spheres of child
nodes in addition to the information on bounding rectangles of
them. This reduces the number of children to be accommodated in a
non-leaf node, i.e., this reduces the fanout of a non-leaf node. The
reduction of the fanout could increase the search cost. However, by
virtue of bounding spheres, the SR-tree supports both the dynamic and
the static construction methods efficiently, while the VAMSplit R-tree
supports only the static construction method.

<blockquote>
<table border=1 bgcolor=lightyellow cellpadding=10>
<tr><td>
<pre>
(C++) HnSRTreeFile new_HnSRTreeFile(const char *path,
                                    int dimension,
                                    int attributeSize,
                                    HnPointVector &amp;points,
                                    HnDataItemVector &amp;dataItems,
                                    const HnProperties &amp;properties);

(C  ) HnSRTreeFileSt *HnSRTreeFileSt_build(const char *path,
					   int dimension,
                                           int attributeSize,
                                           const HnPointVectorSt *points,
                                           const HnDataItemVectorSt *dataItems,
			     	           const HnPropertiesSt *properties);

        path          : the name of an index file.
        dimension     : the dimensionality of the search space.
        attributeSize : the size of an attribute associated with each data
                        point (in bytes).
        points        : points being stored.
        dataItems     : attributes being stored with each point.
        properties    : properties of the index.
</pre>
</td></tr>
</table>
See also <a href="classes.html#HnPointVector">HnPointVector</a>,
<a href="classes.html#HnDataItemVector">HnDataItemVector</a>,
<a href="classes.html#HnProperties">HnProperties</a>.
</blockquote>

The details of the arguments, `attributeSize' and `properties', can be
found in the description of
``<a href="#create">Creating an empty index</a>''.

</blockquote>

<hr>

<a name="search"></a><h3>3. Search methods</h3>

<ul>
<li><b>Running nearest-neighbor search with an index.</b>

<blockquote>
These functions run nearest neighbor search with an index, i.e., these
functions search an index file for a given number of points that are
the nearest to the query point. The returned points are sorted in
ascending order of the distance to the query point.

<blockquote>
<table border=1 bgcolor=lightyellow cellpadding=10>
<tr><td>
<pre>
(C++) void file.getNeighbors(const HnPoint &amp;queryPoint,
			     int numNeighbors,
			     HnPointVector *points_return,
			     HnDataItemVector *dataItems_return);

(C  ) void HnSRTreeFileSt_getNeighbors(HnSRTreeFileSt *file,
                                       const HnPointSt *queryPoint,
				       int numNeighbors,
			               HnPointVectorSt **points_return,
			               HnDataItemVectorSt **dataItems_return);

	file             : the pointer to a data structure associated with
                           an index file.
	queryPoint       : the query point.
        numNeighbors     : the number of points to be found.
	points_return    : the nearest points to the query point.
	dataItems_return : the attributes of the nearest points.
</pre>
</td></tr>
</table>
See also <a href="classes.html#HnPoint">HnPoint</a>,
<a href="classes.html#HnDataItem">HnDataItem</a>,
<a href="classes.html#HnPointVector">HnPointVector</a>,
<a href="classes.html#HnDataItemVector">HnDataItemVector</a>,
<a href="examples.html#fetchNN">Example</a>.
</blockquote>

<p>
The `<code>numNeighbors</code>' is not necessarily the maximum number
of points to be obtained. If the farthest point of a result set has
multiple points at the same rank, they are also included in the result
set.
</p>

<p>
When using the C language interface, the data objects returned through
the arguments `<code>points_return</code>' and
`<code>dataItems_return</code>' need to be deleted by the caller as
follows:
</p>

<blockquote>
<pre>
HnPointVectorSt *points;
HnDataItemVectorSt *dataItems;

 . . .

HnSRTreeFileSt_getNeighbors(file, queryPoint, numNeighbors,
			    &amp;points, &amp;dataItems);

 . . .

/* work with `points' and `dataItems' */

 . . .

HnPointVectorSt_freeElements(points);
HnPointVectorSt_free(points);
HnDataItemVectorSt_freeElements(dataItems);
HnDataItemVectorSt_free(dataItems);
</pre>
</blockquote>

</blockquote>
</li>

<li><b>Running colored nearest-neighbor search with an index.</b>

<blockquote>
(in preparation as of version 2.0 beta 1).
</blockquote>

<li><b>Running range search with an index.</b>

<blockquote>
The following functions run range search, i.e., these functions search
an index file for such points that reside in a given region specified
by a (hyper)rectangle or a (hyper)sphere.

<blockquote>
<table border=1 bgcolor=lightyellow cellpadding=10>
<tr><td>
<pre>
(C++) void file.getFirst(const HnRect &amp;queryRect,
      			 HnPoint *point_return,
                         HnDataItem *dataItem_return);
      void file.getFirst(const HnSphere &amp;querySphere,
      			 HnPoint *point_return,
                         HnDataItem *dataItem_return);
      void file.getNext(HnPoint *point_return,
                        HnDataItem *dataItem_return);

(C  ) void HnSRTreeFileSt_getFirstInRect(HnSRTreeFileSt *file,
			                 const HnRectSt *queryRect,
			                 HnPointSt **point_return,
			                 HnDataItemSt **dataItem_return);
      void HnSRTreeFileSt_getFirstInSphere(HnSRTreeFileSt *file,
			                   const HnSphereSt *querySphere,
			                   HnPointSt **point_return,
			                   HnDataItemSt **dataItem_return);
      void HnSRTreeFileSt_getNext(HnSRTreeFileSt *file,
			          HnPointSt **point_return,
			          HnDataItemSt **dataItem_return);

        file            : the pointer to a data structure associated with
                          an index file.
        queryRect       : the query rectangle.
        querySphere     : the query sphere.
        point_return    : the obtained point.
        dataItem_return : the attribute of the obtained point.
</pre>
</td></tr>
</table>
See also 
<a href="classes.html#HnRect">HnRect</a>,
<a href="classes.html#HnSphere">HnSphere</a>,
<a href="classes.html#HnPoint">HnPoint</a>,
<a href="classes.html#HnDataItem">HnDataItem</a>,
<a href="examples.html#fetchInRect">Example</a>.
</blockquote>

<p>
Search starts by the invocation of the function
`<code>getFirst()</code>'.  The query region is specified by the
argument `<code>queryRect</code>' or `<code>querySphere</code>'.
The first result will be returned
through the arguments `<code>point_return</code>' and
`<code>dataItem_return</code>'. When no point is found in the query
region, the following null values are returned:

<blockquote>
<pre>
(C++) point_return    :  HnPoint::null
      dataItem_return :  HnDataItem::null

(C  ) point_return    :  NULL
      dataItem_return :  NULL 
</pre>
</blockquote>

<p>
The second and more result will be returned by the invocation of
`<code>getNext()</code>'. When every result is returned, the null
values will be returned in the arguments `<code>point_return</code>'
and `<code>dataItem_return</code>'.
</p>

<p>
When the following null values are assigned to the argument
`<code>queryRect</code>', every point in an index file will be
obtained:
</p>

<blockquote>
<pre>
(C++) HnRect::null
(C  ) NULL
</pre>
</blockquote>

<p>
Similarly, when the following null values are assigned to the argument
`<code>querySphere</code>', every point in an index file will be
obtained:
</p>

<blockquote>
<pre>
(C++) HnSphere::null
(C  ) NULL
</pre>
</blockquote>

<p>
When using the C++ language interface, the following function can be
used as the abbreviation of setting `<code>HnRect::null</code>' to the
argument `<code>queryRect</code>'.
</p>
<blockquote>
<pre>
(C++)
    void file.getFirst(HnPoint *point_return, HnDataItem *dataItem_return);
</pre>
</blockquote>

For convenience, the following functions are also provided.  These
functions invoke the above functions `<code>getFirst()</code>' and
`<code>getNext()</code>' internally and return the points and
attributes through the arguments `<code>points_return</code>' and
`<code>dataItems_return</code>'. The returned point-attribute pairs
are sorted in the lexicographical order to preserve the identity of
the search result.

<blockquote>
<table border=1 bgcolor=lightyellow cellpadding=10>
<tr><td>
<pre>
(C++)
    void file.getInRect(const HnRect &amp;queryRect,
                        HnPointVector *points_return,
                        HnDataItemVector *dataItems_return);
    void file.getInSphere(const HnSphere &amp;querySphere,
                          HnPointVector *points_return,
                          HnDataItemVector *dataItems_return);

(C  )
    void HnSRTreeFileSt_getInRect(HnSRTreeFileSt *file,
                                  const HnRectSt *queryRect,
                                  HnPointVectorSt **points_return,
                                  HnDataItemVectorSt **dataItems_return);
    void HnSRTreeFileSt_getInSphere(HnSRTreeFileSt *file,
                                    const HnSphereSt *querySphere,
                                    HnPointVectorSt **points_return,
                                    HnDataItemVectorSt **dataItems_return);

        file             : the pointer to a data structure associated with
                           an index file.
        queryRect        : the query rectangle.
        querySphere      : the query sphere.
        points_return    : the obtained points.
        dataItems_return : the attributes of the obtained points.
</pre>
</td></tr>
</table>
See also 
<a href="classes.html#HnRect">HnRect</a>,
<a href="classes.html#HnSphere">HnSphere</a>,
<a href="classes.html#HnPointVector">HnPointVector</a>,
<a href="classes.html#HnDataItemVector">HnDataItemVector</a>.
</blockquote>

</blockquote>
</li>
</ul>

<hr>

<a name="misc"></a><h3>4. Miscellaneous methods</h3>

<ul>
<li><b>Obtaining profile information of an index manipulation.</b>

<blockquote>
The following functions take the snapshot of the profile information
collected by the library.

<blockquote>
<table border=1 bgcolor=lightyellow cellpadding=10>
<tr><td>
<pre>
(C++) void file.copyProfileInto(HnSRTreeProfileSt *profile);

(C  ) void HnSRTreeFileSt_copyProfileInto(HnSRTreeFileSt *file,
                                          HnSRTreeProfileSt *profile);

        file    : the pointer to a data structure associated with an
	          index file.
        profile : an object of the type `HnSRTreeProfileSt' into which
	          the current profile is to be written.
</pre>
</td></tr>
</table>
See also <a href="classes.html#HnSRTreeProfileSt">HnSRTreeProfileSt</a>.
</blockquote>

<p>
The profile information is collected for each index file. It is
accumulative since the file is opened. However, you can initialize it
by calling the following function:
</p>
<blockquote>
<pre>
(C++) void file.resetProfile(void);

(C  ) void HnSRTreeFileSt_resetProfile(HnSRTreeFileSt *file);
</pre>
</blockquote>

</blockquote>
</li>
</ul>

<hr>
[<a href="index.html">TOC</a>]
[<a href="library.html">Library</a>]
[<a href="classes.html">Classes</a>]
[<a href="commands.html">Commands</a>]
[<a href="examples.html">Examples</a>]
[<a href="references.html">References</a>]

<p>
<i>Any feedback is appreciated (corrections, suggestions, etc.).</i>
</p>
<address>
Norio KATAYAMA
&lt;<a href="mailto:[e-mail]">[e-mail]</a>&gt;
</address>

</body>