\documentstyle[twocolumn,9pt,per]{article}


\newcommand {\bi}{\begin{itemize}}
\newcommand {\ei}{\end{itemize}}
\newcommand {\bd}{\begin{description}}
\newcommand {\ed}{\end{description}}
\newcommand {\be}{\begin{enumerate}}
\newcommand {\ee}{\end{enumerate}}
\newcommand {\bc}{\begin{center}}
\newcommand {\ec}{\end{center}}

\begin{document}

\title{ PAPER:  A Brilliant Discourse on Nothing }

\author{ Author 1 Name \hspace{4ex} Author 2 Name \hspace{4ex} Author 3 Name \hspace{4ex}  \\
\small Computer Science Department \\
\small Little University \hspace{2ex} Denver, CO 80208-0189 \\
\small {\em \{addr1,addr2,addr3\}@cs.du.edu}  
}
\date{}

\maketitle

\begin{abstract}

In this paper we present the results from an extensive
comparison study of three R-tree packing algorithms, including
a new easy to implement algorithm.
The algorithms are evaluated using both synthetic
and actual data from various application domains including
VLSI design, GIS (tiger), and computational fluid dynamics.
Our studies also consider the impact that various
degrees of buffering have on query performance.
Experimental results indicate that none of the algorithms
is best for all types of data.
In general, our new algorithm requires
up to 50\% fewer disk accesses than the best
previously proposed algorithm for point and region queries
on uniformly distributed or mildly skewed point and region data,
and approximately the same for highly skewed point and region data.
\end{abstract}


\section{Introduction}

R-trees are a common indexing technique for spatial data and 
are widely used in spatial and multi-dimensional databases.
By storing the bounding boxes of arbitrary geometric objects,
such as points, polygons, or more complex objects,
R-trees can be used to determine which objects intersect
a given query region.
Typical applications include computer-aided design, geographic
information systems, computer vision and robotics,
multi-keyed indexing for traditional databases, temporal
and scientific databases.
R-trees are dynamic structures, in the sense that their contents
can be modified without reconstructing the entire tree,
and Guttman
provides efficient routines for insertion and deletion of
objects.

Unfortunately, building an R-tree by inserting one object
at a time as specified by Guttman has several
disadvantages: (a) high load time, (b) sub-optimal space utilization,
and, most important, (c) poor R-tree structure requiring the retrieval
of an unduly large number of nodes in order to satisfy a query.
Other dynamic algorithms improve the quality of the R-tree,
but still are not competitive with regard to query time when
compared to loading algorithms that are allowed to preprocess the data
to be stored. Preprocessing is particularly reasonable for applications
where the data is fairly static (i.e., does not change often)
or available a priori and, when done properly, results in R-trees
with nearly 100\% space utilization and improved query times (due
to the fact that fewer nodes need to be accessed while performing a
query). Such {\em packing algorithms\/} were first proposed by
Roussopoulos and later by
Kamel and Faloutsos. 

Kamel and Faloutsos propose a packing algorithm
based on the Hilbert Curve ordering, and compare it with the
Nearest-X algorithm proposed by Roussopoulos. The latter is
simpler to implement and in some cases results in better trees
for point queries.
However, due to the smaller perimeter
of the bounding rectangles at internal nodes,
the algorithm of 
significantly outperforms that of for region queries. 
Consequently, the Hilbert-based packing algorithm is usually
the preferred choice for region queries while remaining competitive
for point queries.


In this paper we propose a new packing algorithm (Sort-Tile-Recursive)
that is simple to implement and  compare it with the Hilbert and Nearest-X
packing algorithms for a wide range of data and buffer sizes.
In addition to area and perimeter metrics,
we provide experimental 
evidence based on real implementations utilizing an LRU buffer on 
VLSI design, GIS, computational fluid dynamics, and synthetic
data sets.
We know of no other work that has considered such a wide
range of data set types and the effect they have on packing
performance.
In real databases some portion of the tree is buffered
in main memory.  This buffering of portions of the tree can
significantly affect performance as shown in.
Consequently, our experimental studies utilize a buffer as
described in Section~3.
%Our data set sizes vary from 10,000 to 300,000 rectangles
%and our buffer sizes vary form 10 to 500 pages.

The rest of the paper is organized as follows.  In Section~2
we provide background information on R-trees and describe the
three packing algorithms considered in this paper.
In Section~3 we present our experimental methodology.
Section~4 contains results from our experiments and
Section~5 concludes.


\section{Now test sub and subsub section}

The following shows how the headers of subsections look.
The following shows how the headers of subsections look.
The following shows how the headers of subsections look.
The following shows how the headers of subsections look.
The following shows how the headers of subsections look.

\subsection{Test of subsection}

This is a test to see how it looks.
This is a test to see how it looks.
This is a test to see how it looks.
This is a test to see how it looks.
This is a test to see how it looks.
This is a test to see how it looks.
This is a test to see how it looks.
This is a test to see how it looks.
This is a test to see how it looks.
This is a test to see how it looks.
This is a test to see how it looks.
This is a test to see how it looks.
This is a test to see how it looks.
This is a test to see how it looks.
This is a test to see how it looks.


\subsubsection{Test of subsubsection}

This is a test to see how it looks.
This is a test to see how it looks.
This is a test to see how it looks.
This is a test to see how it looks.
This is a test to see how it looks.
This is a test to see how it looks.
This is a test to see how it looks.
This is a test to see how it looks.
This is a test to see how it looks.
This is a test to see how it looks.
This is a test to see how it looks.
This is a test to see how it looks.
This is a test to see how it looks.
This is a test to see how it looks.
This is a test to see how it looks.


\section{Conclusions}

All other work pales in comparison to ours.
In fact, we expect any day for a Nobel prize in 
computer science to be created simply so they can
reward our work appropriately.

\bibliographystyle{plain}

\end{document}




