#! /bin/sh
# This is a shell archive.  Remove anything before the line above, then unpack
# it by saving it into a file and typing "sh file".  To overwrite existing
# files, type "sh file -c".  You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g..  If this archive is complete, you
# will see the following message at the end:
#		"End of shell archive."
# Contents:  sample.tex per.sty 9pt.sty
# Wrapped by dfk@zealand on Thu Sep 25 13:19:04 1997
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'sample.tex' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'sample.tex'\"
else
echo shar: Extracting \"'sample.tex'\" \(6655 characters\)
sed "s/^X//" >'sample.tex' <<'END_OF_FILE'
X\documentstyle[twocolumn,9pt,per]{article}
X
X
X\newcommand {\bi}{\begin{itemize}}
X\newcommand {\ei}{\end{itemize}}
X\newcommand {\bd}{\begin{description}}
X\newcommand {\ed}{\end{description}}
X\newcommand {\be}{\begin{enumerate}}
X\newcommand {\ee}{\end{enumerate}}
X\newcommand {\bc}{\begin{center}}
X\newcommand {\ec}{\end{center}}
X
X\begin{document}
X
X\title{ PAPER:  A Brilliant Discourse on Nothing }
X
X\author{ Author 1 Name \hspace{4ex} Author 2 Name \hspace{4ex} Author 3 Name \hspace{4ex}  \\
X\small Computer Science Department \\
X\small Little University \hspace{2ex} Denver, CO 80208-0189 \\
X\small {\em \{addr1,addr2,addr3\}@cs.du.edu}  
X}
X\date{}
X
X\maketitle
X
X\begin{abstract}
X
XIn this paper we present the results from an extensive
Xcomparison study of three R-tree packing algorithms, including
Xa new easy to implement algorithm.
XThe algorithms are evaluated using both synthetic
Xand actual data from various application domains including
XVLSI design, GIS (tiger), and computational fluid dynamics.
XOur studies also consider the impact that various
Xdegrees of buffering have on query performance.
XExperimental results indicate that none of the algorithms
Xis best for all types of data.
XIn general, our new algorithm requires
Xup to 50\% fewer disk accesses than the best
Xpreviously proposed algorithm for point and region queries
Xon uniformly distributed or mildly skewed point and region data,
Xand approximately the same for highly skewed point and region data.
X\end{abstract}
X
X
X\section{Introduction}
X
XR-trees are a common indexing technique for spatial data and 
Xare widely used in spatial and multi-dimensional databases.
XBy storing the bounding boxes of arbitrary geometric objects,
Xsuch as points, polygons, or more complex objects,
XR-trees can be used to determine which objects intersect
Xa given query region.
XTypical applications include computer-aided design, geographic
Xinformation systems, computer vision and robotics,
Xmulti-keyed indexing for traditional databases, temporal
Xand scientific databases.
XR-trees are dynamic structures, in the sense that their contents
Xcan be modified without reconstructing the entire tree,
Xand Guttman
Xprovides efficient routines for insertion and deletion of
Xobjects.
X
XUnfortunately, building an R-tree by inserting one object
Xat a time as specified by Guttman has several
Xdisadvantages: (a) high load time, (b) sub-optimal space utilization,
Xand, most important, (c) poor R-tree structure requiring the retrieval
Xof an unduly large number of nodes in order to satisfy a query.
XOther dynamic algorithms improve the quality of the R-tree,
Xbut still are not competitive with regard to query time when
Xcompared to loading algorithms that are allowed to preprocess the data
Xto be stored. Preprocessing is particularly reasonable for applications
Xwhere the data is fairly static (i.e., does not change often)
Xor available a priori and, when done properly, results in R-trees
Xwith nearly 100\% space utilization and improved query times (due
Xto the fact that fewer nodes need to be accessed while performing a
Xquery). Such {\em packing algorithms\/} were first proposed by
XRoussopoulos and later by
XKamel and Faloutsos. 
X
XKamel and Faloutsos propose a packing algorithm
Xbased on the Hilbert Curve ordering, and compare it with the
XNearest-X algorithm proposed by Roussopoulos. The latter is
Xsimpler to implement and in some cases results in better trees
Xfor point queries.
XHowever, due to the smaller perimeter
Xof the bounding rectangles at internal nodes,
Xthe algorithm of 
Xsignificantly outperforms that of for region queries. 
XConsequently, the Hilbert-based packing algorithm is usually
Xthe preferred choice for region queries while remaining competitive
Xfor point queries.
X
X
XIn this paper we propose a new packing algorithm (Sort-Tile-Recursive)
Xthat is simple to implement and  compare it with the Hilbert and Nearest-X
Xpacking algorithms for a wide range of data and buffer sizes.
XIn addition to area and perimeter metrics,
Xwe provide experimental 
Xevidence based on real implementations utilizing an LRU buffer on 
XVLSI design, GIS, computational fluid dynamics, and synthetic
Xdata sets.
XWe know of no other work that has considered such a wide
Xrange of data set types and the effect they have on packing
Xperformance.
XIn real databases some portion of the tree is buffered
Xin main memory.  This buffering of portions of the tree can
Xsignificantly affect performance as shown in.
XConsequently, our experimental studies utilize a buffer as
Xdescribed in Section~3.
X%Our data set sizes vary from 10,000 to 300,000 rectangles
X%and our buffer sizes vary form 10 to 500 pages.
X
XThe rest of the paper is organized as follows.  In Section~2
Xwe provide background information on R-trees and describe the
Xthree packing algorithms considered in this paper.
XIn Section~3 we present our experimental methodology.
XSection~4 contains results from our experiments and
XSection~5 concludes.
X
X
X\section{Now test sub and subsub section}
X
XThe following shows how the headers of subsections look.
XThe following shows how the headers of subsections look.
XThe following shows how the headers of subsections look.
XThe following shows how the headers of subsections look.
XThe following shows how the headers of subsections look.
X
X\subsection{Test of subsection}
X
XThis is a test to see how it looks.
XThis is a test to see how it looks.
XThis is a test to see how it looks.
XThis is a test to see how it looks.
XThis is a test to see how it looks.
XThis is a test to see how it looks.
XThis is a test to see how it looks.
XThis is a test to see how it looks.
XThis is a test to see how it looks.
XThis is a test to see how it looks.
XThis is a test to see how it looks.
XThis is a test to see how it looks.
XThis is a test to see how it looks.
XThis is a test to see how it looks.
XThis is a test to see how it looks.
X
X
X\subsubsection{Test of subsubsection}
X
XThis is a test to see how it looks.
XThis is a test to see how it looks.
XThis is a test to see how it looks.
XThis is a test to see how it looks.
XThis is a test to see how it looks.
XThis is a test to see how it looks.
XThis is a test to see how it looks.
XThis is a test to see how it looks.
XThis is a test to see how it looks.
XThis is a test to see how it looks.
XThis is a test to see how it looks.
XThis is a test to see how it looks.
XThis is a test to see how it looks.
XThis is a test to see how it looks.
XThis is a test to see how it looks.
X
X
X\section{Conclusions}
X
XAll other work pales in comparison to ours.
XIn fact, we expect any day for a Nobel prize in 
Xcomputer science to be created simply so they can
Xreward our work appropriately.
X
X\bibliographystyle{plain}
X
X\end{document}
X
X
X
X
END_OF_FILE
if test 6655 -ne `wc -c <'sample.tex'`; then
    echo shar: \"'sample.tex'\" unpacked with wrong size!
fi
# end of 'sample.tex'
fi
if test -f 'per.sty' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'per.sty'\"
else
echo shar: Extracting \"'per.sty'\" \(4771 characters\)
sed "s/^X//" >'per.sty' <<'END_OF_FILE'
X%%%
X%%%                        Usage:
X%%%                         \documentstyle[..,Xpt,simple]{article}
X%%%                         \author{..}
X%%%                         \title{..}
X%%%                         \maketitle
X%%%                         \begin{keywords}...\end{keywords}
X%%%                         ...
X%%%                         \end{document}
X
X%
X% All margin dimensions measured from a point one inch from top and side
X% of page.  Dimensions shrink by about 2 percent
X
X
X\topmargin      0.2in
X\oddsidemargin  0.1in
X\evensidemargin 0.1in
X\textheight     8.7in
X\textwidth      6.3in
X\parindent        2.0em
X\headsep          0.0in
X\headheight       0.0in
X\lineskip           1pt
X\normallineskip     1pt
X%\def\baselinestretch{1.3}
X
X%  NO page numbers, please pencil the page numbers on the back
X\pagestyle{empty}
X
X
X%% FONT DEFINITION: avoids having to read in font files.
X%%
X%% Check if we have selected 9 points
X\def\@tempa{9}\ifx\@ptsize\@tempa
X\typeout{-- This is a 9 point document}
X\def\@normalsize{\@setsize\normalsize{10.7pt}\ixpt\@ixpt
X\abovedisplayskip 1em plus2pt minus5pt\belowdisplayskip \abovedisplayskip
X\abovedisplayshortskip \z@ plus3pt\belowdisplayshortskip .6em plus3pt minus3pt}
X\def\small{\@setsize\small{9.12pt}\viiipt\@viipt}
X\def\footnotesize{\@setsize\footnotesize{8.15pt}\viipt\@vipt}
X\def\scriptsize{\@setsize\scriptsize{8pt}\vipt\@vpt}
X\def\tiny{\@setsize\tiny{5pt}\vpt\@vpt}
X\def\large{\@setsize\large{12pt}\xpt\@xpt}
X\def\Large{\@setsize\Large{14pt}\xiipt\@xiipt}
X\def\LARGE{\@setsize\LARGE{18pt}\xivpt\@xivpt}
X\def\huge{\@setsize\huge{22pt}\xviipt\@xviipt}
X\def\Huge{\@setsize\Huge{25pt}\xxpt\@xxpt}
X\fi
X%%
X%% Check if we have selected 10 points
X\def\@tempa{10}\ifx\@ptsize\@tempa
X\typeout{-- This is a 10 point document}
X\def\@normalsize{\@setsize\normalsize{11.9pt}\xpt\@xpt
X\abovedisplayskip 1em plus2pt minus5pt\belowdisplayskip \abovedisplayskip
X\abovedisplayshortskip \z@ plus3pt\belowdisplayshortskip .6em plus3pt minus3pt}
X\def\small{\@setsize\small{9.2pt}\viiipt\@viiipt}
X\def\footnotesize{\@setsize\footnotesize{8.8pt}\viiipt\@viiipt}
X\def\scriptsize{\@setsize\scriptsize{8pt}\viipt\@viipt}
X\def\tiny{\@setsize\tiny{6pt}\vpt\@vpt}
X\def\large{\@setsize\large{14pt}\xiipt\@xiipt}
X\def\Large{\@setsize\Large{18pt}\xivpt\@xivpt}
X\def\LARGE{\@setsize\LARGE{22pt}\xviipt\@xviipt}
X\def\huge{\@setsize\huge{22pt}\xxpt\@xxpt}
X\def\Huge{\@setsize\Huge{28pt}\xxvpt\@xxvpt}
X\fi
X%%
X%% Check if we have selected 11 points
X\def\@tempa{11}\ifx\@ptsize\@tempa
X\typeout{-- This is an 11 point document}
X\def\@normalsize{\@setsize\normalsize{13.6pt}\xipt\@xipt
X\abovedisplayskip 1em plus2pt minus5pt\belowdisplayskip \abovedisplayskip
X\abovedisplayshortskip \z@ plus3pt\belowdisplayshortskip .6em plus3pt minus3pt}
X\def\small{\@setsize\small{12pt}\xpt\@xpt}
X\def\footnotesize{\@setsize\footnotesize{11pt}\ixpt\@ixpt}
X\def\scriptsize{\@setsize\scriptsize{9.5pt}\viiipt\@viiipt}
X\def\tiny{\@setsize\tiny{7pt}\vipt\@vipt}
X\def\large{\@setsize\large{14pt}\xiipt\@xiipt}
X\def\Large{\@setsize\Large{18pt}\xivpt\@xivpt}
X\def\LARGE{\@setsize\LARGE{22pt}\xviipt\@xviipt}
X\def\huge{\@setsize\huge{25pt}\xxpt\@xxpt}
X\def\Huge{\@setsize\Huge{30pt}\xxvpt\@xxvpt}
X\fi
X%%
X%% Check if we have selected 12 points
X\def\@tempa{12}\ifx\@ptsize\@tempa
X\typeout{-- This is a 12 point document}
X\def\@normalsize{\@setsize\normalsize{14pt}\xiipt\@xiipt
X\abovedisplayskip 1em plus3pt minus6pt\belowdisplayskip \abovedisplayskip
X\abovedisplayshortskip \z@ plus3pt\belowdisplayshortskip .6em plus4pt minus4pt}
X\def\small{\@setsize\small{11.4pt}\xpt\@xpt}
X\def\footnotesize{\@setsize\footnotesize{10pt}\ixpt\@ixpt}
X\def\scriptsize{\@setsize\scriptsize{9pt}\viiipt\@viiipt}
X\def\tiny{\@setsize\tiny{8pt}\vipt\@vipt}
X\def\large{\@setsize\large{18pt}\xivpt\@xivpt}
X\def\Large{\@setsize\Large{22pt}\xviipt\@xviipt}
X\def\LARGE{\@setsize\LARGE{25pt}\xxpt\@xxpt}
X\def\huge{\@setsize\huge{30pt}\xxvpt\@xxvpt}
X\let\Huge=\huge
X\fi
X
X
X
X\def\abstract{
X  \begin{center}\vspace{-0.8em}\small\bf Abstract\end{center}\small\begin{em}
X}
X
X\def\endabstract{\thispagestyle{empty}\vspace{0.6em}\par\end{em}\normalsize\rm\par }
X
X
X
X\def\@maketitle{\begin{center}
X  \vskip0.2em{\Large\@title\par}\vskip1.0em
X  {\lineskip.5em\large\@author\par}
X  \end{center}\par\vskip 1.4em
X}
X
X
X%% SECTIONS
X%%
X\def\section{\@startsection {section}{1}{\z@}{1.5ex plus .5ex minus .3ex}
X    {1.5ex plus .5ex minus .3ex} {\large\bf} }
X\def\subsection{\@startsection {subsection}{1}{\z@}{1.5ex plus .5ex minus .3ex}
X    {1.5ex plus .5ex minus .3ex} {\normalsize\bf} }
X\def\subsubsection{\@startsection {subsubsection}{1}{\z@}{1.5ex plus .5ex minus .3ex}
X    {1.5ex plus .5ex minus .3ex} {\normalsize\bf} }
X
X%  NO page numbers, please pencil the page numbers on the back
X\pagestyle{empty}
X\thispagestyle{empty}
X
END_OF_FILE
if test 4771 -ne `wc -c <'per.sty'`; then
    echo shar: \"'per.sty'\" unpacked with wrong size!
fi
# end of 'per.sty'
fi
if test -f '9pt.sty' -a "${1}" != "-c" ; then 
  echo shar: Will not clobber existing file \"'9pt.sty'\"
else
echo shar: Extracting \"'9pt.sty'\" \(16 characters\)
sed "s/^X//" >'9pt.sty' <<'END_OF_FILE'
X\def\@ptsize{9}
END_OF_FILE
if test 16 -ne `wc -c <'9pt.sty'`; then
    echo shar: \"'9pt.sty'\" unpacked with wrong size!
fi
# end of '9pt.sty'
fi
echo shar: End of shell archive.
exit 0