The major part of this library is written in C++. In addition, the interface for the C language programs is also provided.
In order to enhance the readability and maintainability of the source code, this library is written in Java-like convention. For example, when we allocate an object of the class `Foo' and invoke its method `bar', then we write the following code:
(C++) { /* variable declaration * * NOTE: * Variables are allocated only for referencing objects. */ Foo foo; /* * object allocation * * NOTE: * An object is instantiated by the special function * whose name is the concatenation of the prefix `new_' * and the class name `Foo'. * The standard operator `new' is not used here. */ foo = new_Foo(); /* method invocation */ foo.bar(); /* * NOTE: * The allocated object will be deleted automatically based on * the reference count. */ } (C ) { /* * variable declaration * * NOTE: * When using the C language interface, the class `Foo' is * represented by the structure whose name is the * concatenation of the class name `Foo' and the suffix `St'. */ FooSt *foo; /* object allocation */ foo = FooSt_allocate(); /* method invocation */ FooSt_bar(foo); /* * NOTE: * When using the C language interface, allocated objects * must be deleted explicitly. */ FooSt_free(foo); }When using the C++ language interface, the object is allocated through `
new_Foo()'. This expression is not equivalent to `new Foo()' which invokes the operator `new'. The function `new_Foo()' is a special function which instantiates an object of the class `Foo'. This special constructor enables us to have the Java semantics for the object instantiation, i.e., variables are allocated only for referencing objects and instantiated objects are automatically reclaimed on losing references to themselves.
This library has two language interfaces: the C++ language interface and the C language interface. The header file `HnSRTreeFile.hh' is provided for the C++ users and `HnSRTreeFileSt.h' is for the C users.(C++) HnSRTree/HnSRTreeFile.hh (C ) HnSRTree/HnSRTreeFileSt.h
Although this library has the C language interface, the body of this library is written in C++. Therefore, a C++ linker is required to link your object files with this library even if your object files are compiled only with the C compiler.(C++ and C) libHnSRTree.a
The following functions create an index file and return the pointer to a data structure associated with that file.See also HnProperties.
(C++) HnSRTreeFile new_HnSRTreeFile(const char *path, int dimension, int attributeSize, const HnProperties &properties); (C ) HnSRTreeFileSt *HnSRTreeFileSt_create(const char *path, int dimension, int attributeSize, 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). properties : properties of the index.The argument `
attributeSize' determines the size of an attribute associated with each data point. The current implementation allocates a fixed-size attribute for each data point stored in an index file. The attribute can be used to store additional information on each data point, e.g., the identifier, the label, etc. Thus, the value of the argument `attributeSize' needs to be large enough to contain the information to be stored along with data points. For example, if you want to store 4-byte integers in the attribute field, the value of the argument `attributeSize' must be 4 at least; if you want to store character strings whose length is up to 128 bytes (including the null terminator), the value of the argument `attributeSize' must be equal to or greater than 128. The smaller attribute size makes the index file more compact. Therefore, it is recommended to make the attribute size as small as possible.The last argument `
properties' is the set of label-value pairs, whose data type is the class HnProperties. This argument is used to override the default properties of the index file. If you want to use the default properties, the following null values can be set to the argument `properties':(C++) HnProperties::null (C ) NULLThe following properties can be specified through the argument `
properties'.HnSRTreeBlockSize : the size of a block (or bucket). (8192 by default) HnSRTreeSplitFactor : the minimum utilization factor of a block. (specified in percent) (40 by default) HnSRTreeReinsertFactor : the percentage of entries to be reinserted on a forced reinsertion. (30 by default)For convenience, the labels of the above properties are defined as macros in the header file as follows:
#define HnSRTreeBlockSize "HnSRTreeBlockSize" #define HnSRTreeSplitFactor "HnSRTreeSplitFactor" #define HnSRTreeReinsertFactor "HnSRTreeReinsertFactor"You can use the above macros instead of the character string constants.
The following functions open an existing index file for reading or updating.
(C++) HnSRTreeFile new_HnSRTreeFile(const char *path, const char *mode); (C ) HnSRTreeFileSt *HnSRTreeFileSt_open(const char *path, const char *mode); path : the name of an index file. mode : the access mode for opening an index file.The argument `
mode' specifies the access mode for opening an index file. Mode"r"is for reading and mode"rw"is for updating. Upon successful completion, the function returns an object of the class `HnSRTreeFile' (or `HnSRTreeFileSt *') which is associated with the opened index file. Otherwise, the following constants are returned and the global variable `errno' is set to indicate the error.(C++ ) HnSRTreeFile::null (C ) NULL
The following functions close an index file.
(C++) void file.close(void); (C ) void HnSRTreeFileSt_close(HnSRTreeFileSt *file); file : the pointer to a data structure associated with an index file.
The following functions store a point into an index file.The current implementation imposes no restriction on the duplication of points and attributes. This reduces the overhead of insertion since the duplication test is avoided. The same point-attribute pairs can be stored in an index file. The duplication of point-attribute pairs does not harm the functionality of this library.See also HnPoint, HnDataItem.
(C++) void file.store(const HnPoint &point, const HnDataItem &dataItem); (C ) void HnSRTreeFileSt_store(HnSRTreeFileSt *file, const HnPointSt *point, const HnDataItemSt *dataItem); file : the pointer to a data structure associated with an index file. point : a point being stored. dataItem : an attribute being stored with the point.
The following functions remove a point from an index file.Only the point having the same coordinates and the same attribute value is removed from the index file. Points with different attributes are intact.See also HnPoint, HnDataItem.
(C++) void file.remove(const HnPoint &point, const HnDataItem &dataItem); (C ) void HnSRTreeFileSt_remove(HnSRTreeFileSt *file, const HnPointSt *point, const HnDataItemSt *dataItem); file : the pointer to a data structure associated with an index file. point : a point being removed. dataItem : an attribute being removed.
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 [KS97]. The following functions employ the static construction method proposed for the VAMSplit R-tree [WJ96-1]. 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 [WJ96-2]. 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.The details of the arguments, `attributeSize' and `properties', can be found in the description of ``Creating an empty index''.See also HnPointVector, HnDataItemVector, HnProperties.
(C++) HnSRTreeFile new_HnSRTreeFile(const char *path, int dimension, int attributeSize, HnPointVector &points, HnDataItemVector &dataItems, const HnProperties &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.
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.See also HnPoint, HnDataItem, HnPointVector, HnDataItemVector, Example.
(C++) void file.getNeighbors(const HnPoint &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.The `
numNeighbors' 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.When using the C language interface, the data objects returned through the arguments `
points_return' and `dataItems_return' need to be deleted by the caller as follows:HnPointVectorSt *points; HnDataItemVectorSt *dataItems; . . . HnSRTreeFileSt_getNeighbors(file, queryPoint, numNeighbors, &points, &dataItems); . . . /* work with `points' and `dataItems' */ . . . HnPointVectorSt_freeElements(points); HnPointVectorSt_free(points); HnDataItemVectorSt_freeElements(dataItems); HnDataItemVectorSt_free(dataItems);
(in preparation as of version 2.0 beta 1).
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.See also HnRect, HnSphere, HnPoint, HnDataItem, Example.
(C++) void file.getFirst(const HnRect &queryRect, HnPoint *point_return, HnDataItem *dataItem_return); void file.getFirst(const HnSphere &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.Search starts by the invocation of the function `
getFirst()'. The query region is specified by the argument `queryRect' or `querySphere'. The first result will be returned through the arguments `point_return' and `dataItem_return'. When no point is found in the query region, the following null values are returned:(C++) point_return : HnPoint::null dataItem_return : HnDataItem::null (C ) point_return : NULL dataItem_return : NULLThe second and more result will be returned by the invocation of `
getNext()'. When every result is returned, the null values will be returned in the arguments `point_return' and `dataItem_return'.When the following null values are assigned to the argument `
queryRect', every point in an index file will be obtained:(C++) HnRect::null (C ) NULLSimilarly, when the following null values are assigned to the argument `
querySphere', every point in an index file will be obtained:(C++) HnSphere::null (C ) NULLWhen using the C++ language interface, the following function can be used as the abbreviation of setting `
HnRect::null' to the argument `queryRect'.For convenience, the following functions are also provided. These functions invoke the above functions `(C++) void file.getFirst(HnPoint *point_return, HnDataItem *dataItem_return);getFirst()' and `getNext()' internally and return the points and attributes through the arguments `points_return' and `dataItems_return'. The returned point-attribute pairs are sorted in the lexicographical order to preserve the identity of the search result.See also HnRect, HnSphere, HnPointVector, HnDataItemVector.
(C++) void file.getInRect(const HnRect &queryRect, HnPointVector *points_return, HnDataItemVector *dataItems_return); void file.getInSphere(const HnSphere &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.
The following functions take the snapshot of the profile information collected by the library.See also HnSRTreeProfileSt.
(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.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:
(C++) void file.resetProfile(void); (C ) void HnSRTreeFileSt_resetProfile(HnSRTreeFileSt *file);
Any feedback is appreciated (corrections, suggestions, etc.).
Norio KATAYAMA <katayama@nii.ac.jp>