PAPER: A Brilliant Discourse on Nothing

Author 1 Name  Author 2 Name  Author 3 Name

Computer Science Department Little University Denver, CO 80208-0189

{addr1,addr2,addr3}@cs.du.edu

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.

1 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, Rtrees 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, multikeyed 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) suboptimal 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 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.

The rest of the paper is organized as follows. In Section 2 we provide background information on Rtrees 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.

2 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.

2.1 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.

2.1.1 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.

3 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.