piercelbrooks / hnsrtree Goto Github PK

=========================================================================

    HnSRTree: the SR-tree library
    Version 2.0 (beta 6) Mar. 9, 2010 Norio KATAYAMA <[email protected]>

    Copyright (C) 1997,1998,1999,2000,2002,2003,2010 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.17 2010/03/10 03:01:52 katayama Exp $

=========================================================================

Introduction:

    This is an implementation of the SR-tree. The SR-tree is a
    multidimensional index structure designed for the acceleration of
    the nearest-neighbor search of high-dimensional points in the
    Euclidean space. The SR-tree is a disk-based index structure and
    applicable to large data sets, say, a database containing more
    than 10,000 points.

    The efficiency of the SR-tree depends on multiple factors, i.e.,
    data distribution, dimensionality of points, etc. According to our
    experimental evaluation, the SR-tree provides satisfactory
    performance for the data sets containing more than 40,000 points
    in 24 to 48 dimensional space which are feature vectors (color
    histograms) of natural photo images.

    The major part of this library is written in C++. However, the
    interface for the C language programs is also provided.

    This library provides the following features:

        1. Dynamic construction methods:

            * creating an empty index file.
            * opening an existing index file.
            * closing an index file.
	    * storing a data point into an index file.
	    * removing a data point from an index file.

        2. Static construction methods:

            * building an index for a given data set.

        3. Search methods:

            * running nearest-neighbor search with an index.
            * running colored nearest-neighbor search with an index.
            * running range search (window search) with an index.

	4. Miscellaneous methods:

	    * obtaining profile information of an index manipulation.

    The usage of the library is described in the HTML files contained
    in the `doc' directory. Please, refer to `doc/index.html' for
    details.


Tested platforms:

    (1) Hardware         : Sun Blade 2500
        Operating System : SunOS 5.9
        Compiler         : GCC 4.1.2, Sun C++ 5.9 (Sun Studio 12)

    (2) Hardware         : Dell PowerEdge 6950
        Operating System : Red Hat Enterprise Linux 5 (Linux kernel 2.6.18)
        Compiler         : GCC 4.1.2

    (3) Hardware         : Dell Precision 670
        Operating System : Windows XP (32bit)
        Compiler         : Visual C++ 9.0 (Visual Studio 2008)

    (4) Hardware         : Sony VAIO RX75
        Operating System : Windows XP (32bit)
        Compiler         : Visual C++ 6.0 (Visual Studio 6.0)


How to compile:

  A. UNIX

    (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

  B. Windows

    (0) set up Visual C++ to work in the command line interface.

        This library is intended to be compiled in the command line
        interface, i.e., `Command Prompt window' (or `DOS window').
        On using Visual C++ in the command line interface, please be
        sure that the environment variables (e.g., PATH, INCLUDE, LIB)
        have been set appropriately.  When you installed Visual C++ on
        your computer, a batch file named `VCVARS32.BAT' should have
        been generated in the `bin' directory of Visual C++,
        e.g., `C:\Program Files\Microsoft Visual Studio 9.0\VC\bin'.
        This file defines the environment variables necessary to use
        Visual C++ in the command line interface.  Please run this batch
        file before using Visual C++ in the `Command Prompt' window.
        Alternatively, you can set the environment variables as
        `user environment variables' in the control panel.

    (1) change the working directory to the top of the source tree,
        i.e., the directory containing this README file.

          C:> cd ...wherever...\HnSRTree-2.0beta6

    (2) run `nmake' as follows:

          C:> nmake


How to install:

  A. UNIX

	% make install

    The destination of the header files and the object code library
    can be specified by setting options to the command `configure'.
    Usage of `configure' will be shown by running `configure --help'.

    By default, the header files will be copied into
    `/usr/local/include/HnSRTree' and the object code library will be
    copied into `/usr/local/lib'.

  B. Windows

    The header file directory (`include/HnSRTree') and the library file
    `lib/libHnSRTree.lib' should be placed in a directory which is
    included in the search paths of the C/C++ compiler.  Generally,
    the search paths are specified by the `INCLUDE' and `LIB'
    environment variables.  On execution, the dynamic link library
    'lib/libHnSRTree.dll' should be placed in a directory which is
    included in the command search path.


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.bat' on Windows).

	% doTest


How to use:

    Please refer to the HTML file `doc/index.html'.


History:

    10/15/1996
	Version 1.0 is released.

    11/22/1996
	The range query functions, HnSRTreeGetFirst() and
	HnSRTreeGetNext(), is added to the C language interface.

    11/22/1996
	Version 1.1 is released.

    12/09/1996
	The access mode is permitted and the diagnosis is returned on
	opening files.

    12/09/1996
	Version 1.2 is released.

    06/02/1997
	The GNU Library General Public License is applied.

    06/02/1997
	Version 1.3 is released.

    12/02/1997
	The file `README' is slightly modified.
	Version 1.3.1 is released.

    06/10/2000
	Version 2.0 (beta 1) is released.
	    * The source code is refined with respect to CPU time.
	    * The breadth-first NN-search is implemented.
	    * The profiling capability is implemented.
	    * The colored NN-search is implemented.
	    * The static construction method based on the VAMSplit is
	      implemented.

    09/29/2000
	Version 2.0 (beta 2) is released.
	    * The description on the static construction method is
	      added.

    12/01/2000
	Version 2.0 (beta 3) is released.
	    * Minor bugs are fixed:
		- The library crashes when an index file is empty and
		  the query rectangle of the method ``getFirst()'' is
		  ``NULL''.
		- The library crashes when the argument ``properties''
		  of the index construction methods (e.g.,
                  ``HnSRTreeFileSt_create()'' and
                  ``HnSRTreeFileSt_build()'') is ``NULL''.

    12/15/2000
	Version 2.0 (beta 4) is released.
	    * A minor bug is fixed. `checkIndex' might have crashed
	      when the library is compiled by GCC on x86 due to the
	      side effect of round-off error.

    09/14/2002
	Version 2.0 (beta 5) is released.
	    * The source code is adapted to FreeBSD and Windows.
	    * The spherical range search is implemented.

    04/30/2003
	Version 2.0 (beta 5a) is released.
	    * The memory initialization of HnStringBuffer is corrected.

    03/09/2010
	Version 2.0 (beta 6) is released.
	    * Adapted to GCC 4 and Visual C++ 9.0.