


                 An Implementation of the SR-tree for
              the Sixth DIMACS Implementation Challenge


                             Version 1.0
                           August 28, 1998

                Norio Katayama <katayama@rd.nacsis.ac.jp>
            (National Center for Science Information Systems)

          $Id: README,v 1.5 1998/08/28 16:30:03 katayama Exp $


About this archive:

	This archive contains an implementation of the SR-tree
        conforming to the development guide of the Sixth DIMACS
	Implementation Challenge.

	This archive is an extension of the library package of the
	SR-tree, which is freely distributed at our web site
        (http://www.rd.nacsis.ac.jp/~katayama/homepage/research/srtree).
        The source codes specific to the Implementation Challenge are
        placed in the directory `challenge6'. The original document of
        the library package can be found in `README.LIB'.

	If you have any comments, suggestions, or problems in
        compiling source codes, please feel free to contact me.


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

	If the compilation is successful, an executable file `search'
        should be found in the directory `challenge6'.


How to run:

	The usage of the search program, i.e., `challenge6/search', is
	the same with that of the sample template written by Prof
	Michael Goldwasser. Please, refer to the help message which
	will be printed when the program is invoked with the option
	`-help'.

	When you start the program, it will read points from a dataset
	oracle, and then build an SR-tree index in the preprocessing
	step. The SR-tree is a disk-based index structure. The index
	will be created in a file whose name is `srtree.tmp'.

	In the search step, queries will be processed with utilizing
	the index. Costs are measured in terms of the real time
	(i.e., wall clock time) and the CPU time. The program will
	print cost summary on the termination as follows:

        =====================================================================
        Cost of Preprocessing
           Point reading: realTime=30.2, cpuTime=17.9 (user=6.8, system=11.2)
           Tree building: realTime=7.9, cpuTime=7.8 (user=7.4, system=0.37)
        Overall preprocessing cost: 38
        Cost of Queries
           realTime: avg=0.543744, min=0.146255, max=1.73336, std=0.455898
           cpuTime: avg=0.542, min=0.14, max=1.73, std=0.455781
           userTime: avg=0.541, min=0.14, max=1.73, std=0.455597
           systemTime: avg=0.001, min=0, max=0.01, std=0.003
        Overall query cost: 5
        =====================================================================

	The unit of the measurements is the second. The `Overall
	preprocessing cost' indicates the overall elapsed time in the
	preprocessing step, and the `Overall query cost' indicates
	the overall elapsed time in the search step. They are rounded
	to integers, for they have the type `int'.


History:

    08/28/98
	Version 1.0 is released.
