Institute for Systems Research Technical Reports

Finally, we implemented our method on a network of workstations and we compared the experimental and the theoretical results. The conclusions are that (a) our formula for the response time is accurate (the maximum relative error was 30%; the typical error was in the vicinity of 10-15%) (b) the Hilbert-based declustering consistently outperforms a random declustering (c) most importantly, although the optimal chunk size depends on several factors (database size, size of the query, speed of the network), a safe choice for it is 1 page (whichever is the page size of the operating system). We show analytically and experimentally that a chunk size of 1 page gives either optimal or close to optimal results, for a wide range of the parameters.

We validate our claims for the efficiency of our new techniques by analyzing and, comparing four indexing structures: the Time Index$^{+}$, the Time Index, the, Packed R--Tree~[RoLe85, KaFa93], and the Parameterized R--Tree. Our simulation identifies important parameters, and shows how they affect the performance of the four considered indexing structures. These include mean of version lifespan, block size, query time interval length, and total number of versions. Our simulation results show that: (1) The Time Index+ requires on average 60% less storage than the the Time Index but 50% more storage than the Packed R--Tree and the Parameterized R--Tree and (2) the Time Index+ provides an improvement in search time of 10% over the Time Index, of an order of magnitude over the Packed R--Tree, and of at least 100% over the Parameterized R--Tree.

Armed with this tool, we then show its practical use in predicting the performance of spatial access methods, and specifically of the R-trees. We provide the first analysis of R- trees for skewed distributions of points: We develop a formula that estimates the number of disk accesses for range queries, given only the fractal dimension of the point set, and its count. Experiments on real data sets show that the formula is very accurate: the relative error is usually below 5%, and it rarely exceeds 10%.

We believe that the fractal dimension will help replace the uniformity and independence assumptions, allowing more accurate analysis for any spatial access method, as well as better estimates for query optimization on multi-attribute queries.

For a static database, the proposed ordering achieves superior packing, outperforming older packing methods [25], and the best dynamic method (R*-trees [3]). The savings are as high as 36% on real data.

more importantly, we introduce a dynamic variation, the Hilbert R- tree: : Given the ordering, every node has a well- defined set of sibling nodes; thus, we can deploy the deferred splitting algorithms of the B* -trees. By adjusting the split policy, the Hilbert R-tree can achieve as high utilization as desired. We show that a '3-to-4' split policy achieves good results, consistently outperforming the R* -trees, with up to 28% savings on real data.