HnRStar-1.0
=========================================================================
HnRStar: an implementation of the R*-Tree index structure
Version 1.0 12/02/97 katayama@rd.nacsis.ac.jp
Copyright (C) 1997 Norio Katayama
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Library General Public
License as published by the Free Software Foundation; either
version 2 of the License, or (at your option) any later version.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Library General Public License for more details.
You should have received a copy of the GNU Library General Public
License along with this library; if not, write to the Free
Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
MA 02111-1307, USA
$Id: README,v 1.2 1997/12/04 03:19:48 katayama Exp $
=========================================================================
Tested platforms:
(1) Hardware : SPARCstation-20
Operating System : SunOS 5.4, SunOS 5.5
Compiler : GNU C++ 2.7.2, SPARCompiler 4.0
(2) Hardware : SPARCstation-2
Operating System : SunOS 4.1.3
Compiler : GNU C++ 2.7.2.3
How to compile:
(1) run `configure' in this directory.
% ./configure
You can specify the initial values for variables by setting
them in the environment. For example, you can specify the name
of the C and C++ compilers by setting them to the variable
`CC' and `CXX' respectively.
(sh)
$ CC=cc CXX=CC ./configure
(csh)
% env CC=cc CXX=CC ./configure
(2) run `make' as follows:
% make includes
% make all
How to install:
% make install
How to test:
(0) compile source files by following the above instructions.
(1) change the working directory to the `test' directory.
% cd test
(2) run the `doTest' script.
% doTest
How to use:
Sorry, no documentation is available. Please, refer to the
following descriptions and the sample programs contained in
the `c++-samples' and the `c-samples' directories.
(1) header files
(C ) HnRStar.h
(C++) HnRStarFile.hh
This library has two language interfaces:
the C language interface and the C++ language interface.
The header file `HnRStar.h' is provided for the C users
and `HnRStarFile.hh' is for the C++ users.
(2) libraries
(C and C++) libHnRStar.a
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.
(3) creating an R*-tree file
(C ) HnRStar *HnRStarCreate(const char *path,
int dimension,
int dataSize,
int blockSize,
int splitFactor,
int reinsertFactor
);
(C++) HnRStarFile new_HnRStarFile(const char *path,
int dimension,
int dataSize,
int blockSize,
int splitFactor,
int reinsertFactor
);
These functions create an R*-tree file and return the
pointer to a data structure associated with that file.
path : the name of an R*-tree file
dimension : the dimensionality of the search space
dataSize : the size of an attribute associated
with each leaf entry
blockSize : the size of a block (or bucket)
(typically 8192)
splitFactor : the minimum utilization factor of a
block (specified in percent)
(typically 40)
reinsertFactor : the percentage of entries to be reinserted
on a forced reinsertion
(typically 30)
The function `new_HnRStarFile()' of the C++ interface is
not equivalent to the expression `new HnRStarFile()'
which invokes the `new' operator. `new_HnRStarFile()' is
a special function to instantiate an object of the class
`HnRStarFile'. This library takes the Java semantics for
object instantiation. The variables are allocated only for
referencing objects and objects are instantiated only by
special constructors whose name starts with the string
`new_'. The instantiated objects are automatically
reclaimed on losing references to themselves.
(4) opening an R*-tree for reading or updating
(C ) HnRStar *HnRStarUpdate(const char *path);
HnRStar *HnRStarOpen(const char *path);
(C++) HnRStarFile new_HnRStarFile(const char *path,
const char *mode);
These functions open an R*-tree file for reading or updating.
path : the name of an R*-tree file
mode : the access mode for opening an R*-tree file
In the C language interface, the function `HnRStarUpdate()'
opens an R*-tree file for updating. On the other hand, the
function `HnRStarOpen()' opens an R*-tree file for reading.
Upon successful completion, both return the pointer to a
data structure associated with that file. Otherwise,
a null pointer is returned and errno is set to indicate
the error.
In the C++ language interface, the variable `mode'
specifies the access mode for opening an R*-tree file.
Mode "r" is for reading and mode "rw" is for updating.
Upon successful completion, the function returns an object
of the class `HnRStarFile' which is associated with that
opened file. Otherwise, the constant `HnRStarFile::null'
is returned and errno is set to indicate the error.
(5) closing an R*-tree file
(C ) void HnRStarClose(HnRStar *file);
(C++) void file.close(void);
These functions close an R*-tree file.
file : the pointer to a data structure associated with
an R*-tree file
(6) storing a rectangle into an R*-tree file.
(C ) void HnRStarStore(HnRStar *file,
const HnRStarRange ranges[],
const void *ptr,
int size
);
(C++) void file.store(const HnRect &rect,
const HnData &data
);
These functions store a rectangle into an R*-tree file.
The current implementation imposes no restriction for
duplication. This reduces the overhead on insertion.
The same rectangle-attribute pairs can be duplicated.
Duplication does not harm the functionality of this
library.
file : the pointer to a data structure associated with
an R*-tree file
ranges : the ranges of a rectangle at each dimension
ptr : the pointer to an attribute to be stored
with a rectangle
size : the size of an attribute
rect : a rectangle being stored
data : an attribute being stored
In the C language interface, the type `HnRStarRange' is
used. It is defined in the header file `HnRStar.h' as
follows:
typedef struct {
double min;
double max;
} HnRStarRange;
where `min' is the lowest bound and `max' is the highest
bound of a range.
In the C++ language interface, the class `HnRect' is
used. An object of the class `HnRect' can be created in
the following way:
HnRect rect;
rect = new_HnRect(dimension);
for (i=0; i<dimension; i++)
rect.setRange(min[i], HnRange::INCLUSIVE,
max[i], HnRange::INCLUSIVE,
i);
where it is supposed that the dimensionality of the object
is given by the variable `dimension' and its range of each
dimension is given by the arrays `min[]' and `max[]'.
An object of the class `HnData' can be created in the
following way:
HnData data;
data = new_HnData(ptr, size);
where it is supposed that the content of the object is
given by a byte string whose location is `ptr' and whose
size is `size'.
(7) removing a rectangle from an R*-tree file.
(C ) void HnRStarRemove(HnRStar *file,
const HnRStarRange ranges[],
const void *ptr,
int size
);
(C++) void file.remove(const HnRect &rect, const HnData &data);
These functions remove a rectangle from an R*-tree file.
Only a rectangle having the same coordinates and the same
attribute is removed. Rectangles with different attributes
are intact.
file : the pointer to a data structure associated with
an R*-tree file
ranges : the ranges of a rectangle to be removed
ptr : the pointer to an attribute to be removed
with a rectangle
size : the size of an attribute to be removed
rect : a rectangle being removed
data : an attribute being removed
(8) running a nearest neighbor search
(C ) void HnRStarGetNeighbors(HnRStar *file,
const double coords[],
int numNeighbors,
HnRStarRecord **records_return,
int *numRecords_return
);
(C++) void file.getNeighbors(const HnPoint &point,
int numNeighbors,
HnRectArray *rects_return,
HnDataArray *values_return
);
These functions run a nearest neighbor search, i.e., they
search the given number of rectangles that are the nearest to
a given point.
file : the pointer to a data structure
associated with an R*-tree file
coords : the coordinates of a target point
numNeighbors : the number of rectangles to be found
records_return : records of nearest rectangles
numRecords_return : the number of nearest rectangles
point : the target point
rects_return : nearest rectangles
values_return : attributes of nearest rectangles
The `numNeighbors' is not necessarily the maximum number
of rectangles to be obtained. If the farthest rectangle of
a result set has multiple rectangles at the same rank,
they are also included in the result set.
In the C language interface, the type `HnRStarRecord' is
used. It is defined in the header file `HnRStar.h' as
follows:
typedef struct {
HnRStarRange *ranges;
void *data;
int size;
} HnRStarRecord;
where `ranges' is the array of ranges of a rectangle,
`data' is the pointer to its attribute, and `size' is the
size of the attribute. Records being returned by the
function `HnRStarGetNeighbors()' are allocated by that
function and released on its next invocation.
For example, the coordinates and the attributes of nearest
rectangles can be obtained as follows:
HnRStar *file;
double coords[DIMENSION];
int numNeighbors;
HnRStarRecord *records;
int numRecords;
int i, j;
...
(open an R*-tree and set `coords' and `numNeighbors')
...
HnRStarGetNeighbors(file, coords, numNeighbors,
&records, &numRecords);
for (i=0; i<numRecords; i++) {
double minCoords[DIMENSION];
double maxCoords[DIMENSION];
void *data;
int size;
for (j=0; j<DIMENSION; j++) {
minCoords[j] = records[i].ranges[j].min;
maxCoords[j] = records[i].ranges[j].max;
....
}
....
data = records[i].data;
size = records[i].size;
....
}
In the C++ language interface, the class `HnRectArray'
and `HnDataArray' are used. The former is the array of
instances of the class `HnRect' and the latter is the
array of instances of the class `HnData'.
For example, the coordinates and the attributes of nearest
rectangles can be obtained in the following way:
HnRStarFile file;
HnPoint target;
int numNeighbors;
HnRectArray rects;
HnDataArray values;
int i, j;
...
(open an R*-tree and set `target' and `numNeighbors')
...
file.getNeighbors(target, numNeighbors, &rects, &values);
for (i=0; i<rects.length(); i++) {
double minCoords[DIMENSION];
double maxCoords[DIMENSION];
char *data;
int size;
for (j=0; j<DIMENSION; j++) {
minCoords[j] = rects[i].getRange(j).getMin();
maxCoords[j] = rects[i].getRange(j).getMax();
....
}
....
data = values[i].chars();
size = values[i].length();
....
}
(9) running a range search
(C ) void HnRStarGetFirst(HnRStar *file,
const HnRStarRange ranges[],
HnRStarRecord **record_return
);
void HnRStarGetNext(HnRStar *file,
HnRStarRecord **record_return
);
(C++) void file.getFirst(HnRect *rect_return,
HnData *value_return
);
void file.getFirst(const HnRect ®ion,
HnRect *rect_return,
HnData *value_return
);
void file.getNext(HnRect *rect_return,
HnData *value_return
);
These functions run a range search, i.e., they search
rectangles within a given region.
file : the pointer to a data structure associated
with an R*-tree file
ranges : the array of a range of the target region
record_return : a record of an obtained rectangle
region : the target region
rect_return : an obtained rectangle
value_return : the attribute of an obtained rectangle
Records returned by the function `HnRStarGetFirst()' and
`HnRStarGetNext()' are allocated by these functions and
released on their next invocation.
For example, the coordinates and the attributes of
rectangles within a region can be obtained as follows:
HnRStar *file;
HnRStarRange ranges[DIMENSION];
HnRStarRecord *record;
int i;
...
(open an R*-tree and set `ranges')
...
HnRStarGetFirst(file, ranges, &record);
while (record != NULL) {
double minCoords[DIMENSION];
double maxCoords[DIMENSION];
void *data;
int size;
for (i=0; i<DIMENSION; i++) {
minCoords[i] = record->ranges[i].min;
maxCoords[i] = record->ranges[i].max;
....
}
....
data = record->data;
size = record->size;
....
HnRStarGetNext(file, &record);
}
If the NULL is given to the second argument of
`HnRStarGetFirst()', every rectangle in a tree is obtained.
With the C++ language interface, the coordinates and the
attributes of the rectangles within a region can be
obtained in the following way:
HnRStarFile file;
HnRect region;
HnRect rect;
HnData value;
int i;
...
(open an R*-tree and set `region')
...
file.getFirst(region, &rect, &value);
while (rect != HnRect::null) {
double minCoords[DIMENSION];
double maxCoords[DIMENSION];
char *data;
int size;
for (i=0; i<DIMENSION; i++) {
minCoords[i] = rect.getRange(i).getMin();
maxCoords[i] = rect.getRange(i).getMax();
....
}
....
data = value.chars();
size = value.length();
....
file.getNext(&rect, &value);
}
If the function `getFirst(&rect, &values)' is used
instead of the function `getFirst(region, &rect, &value)',
every rectangle in a tree is obtained.
History:
12/02/97
Version 1.0 is released.