Beyond uniformity and independence
Published 1 January 1994Open access
Christos Faloutsos, Ibrahim Kamel
Citations242
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is believed 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.
Abstract
We propose the concept of fractal dimension of a set of points, in order to quantify the deviation from the uniformity distribution. Using measurements on real data sets (road intersections of U.S. counties, star coordinates from NASA's Infrared-Ultraviolet Explorer etc.) we provide evidence that real data indeed are skewed, and, moreover, we show that they behave as mathematical fractals, with a measurable, non-integer fractal dimension.
Keywords
Computer SciencePhysics and Astronomy
American Journal of Physics<i>The Fractal Geometry of Nature</i>
21,750 Citations1983Benoît B. Mandelbrot, John Wheeler
R-trees
6,543 Citations1984Antonin Guttman
A dynamic index structure called an R-tree is described which meets this need, and algorithms for searching and updating it are given and it is concluded that it is useful for current database systems in spatial applications.
The R*-tree: an efficient and robust access method for points and rectangles
4,176 Citations1990Norbert Beckmann, Hans‐Peter Kriegel +2 more
The R*-tree is designed which incorporates a combined optimization of area, margin and overlap of each enclosing rectangle in the directory which clearly outperforms the existing R-tree variants.
Very Large Data BasesThe R+-Tree: A Dynamic Index for Multi-Dimensional Objects
1,263 Citations2018Timos Sellis, Nick Roussopoulos +1 more
A variation to Guttman’s Rtrees (R+-trees) that avoids overlapping rectangles in intermediate nodes of the tree is introduced and analytical results indicate that R+-Trees achieve up to 50% savings in disk accesses compared to an R-tree when searching files of thousands of rectangles.
ACM Transactions on Database SystemsThe Grid File
1,149 Citations1984J. Nievergelt, Hans Hinterberger +1 more
This work discusses in detail the design decisions that led to the grid file, present simulation results of its behavior, and compare it to other multikey access file structures.
Communications of the ACMAn effective way to represent quadtrees
639 Citations1982Irene Gargantini
The sorted array of black nodes is referred to as the “linear quadtree” and it is shown that it introduces a saving of at least 66 percent of the computer storage required by regular quadtrees.
On packing R-trees
491 Citations1993Ibrahim Kamel, Christos Faloutsos
An analytical formula is introduced to compute the average response time of a range query as a function of the geometric characteristics of the R-tree, to achieve better ordering of the rectangles and eventually better packing.
ACM SIGMOD RecordSpatial query processing in an object-oriented database system
398 Citations1986Jack Orenstein
Direct spatial search on pictorial databases using packed R-trees
344 Citations1985Nick Roussopoulos, Daniel B. Leifker
This paper presents an efficient initial packing technique for creatmg R-trees to index spatial ObJects since pictorial databases are not update mtensive but rather static, the benefits of this technique are very significant.
On the propagation of errors in the size of join results
266 Citations1991Yannis Ioannidis, Stavros Christodoulakis
This work presents a formal framework based on which the principles of this error propagation can be studied and obtains several analytic results on how the error propagates in general, as well as in the extreme and average cases.
ACM Transactions on Database SystemsImplications of certain assumptions in database performance evauation
241 Citations1984Stavros Christodoulakis
This paper shows that assumptions of uniformity and independence of attribute values in a file, uniformity of queries, constant number of records per block, and random placement of qualifying records among the blocks of a file often result in predicting only an upper bound of the expected system cost.
Towards an analysis of range query performance in spatial data structures
216 Citations1993Bernd-Uwe Pagel, Hans-Werner Six +2 more
This paper motivates four different user defined window query classes and derives a probabilistic model for each of them in terms of the expected number of data bucket accesses needed to perform a window query.
ACM SIGMOD RecordEqui-depth multidimensional histograms
215 Citations1988M. Muralikrishna, David J. DeWitt
Analysis of object oriented spatial access methods
153 Citations1987Christos Faloutsos, Timos Sellis +1 more
It is shown how the transformation of objects to higher dimensions [HINR83] can be effectively used as a tool for the analysis of R- and R+- trees and derive formulas for R-trees and compare the two methods analytically.
Spatial search with polyhedra
97 Citations2002H. V. Jagadish
It is shown how to use multiattribute search structures for polyhedral regions by mappingpolyhedral regions into rectangular regions of a higher dimension and the P-tree (polyhedral tree) is introduced and shown to be an effective multiattribute index structure.
FigshareOn B-tree Indices for Skewed Distributions
39 Citations2018Christos Faloutsos, H. V. Jagadish
This work presents a geometric growth technique to manage postings records in such cases that the set of values over which a B-Tree is constructed has a skewed distribution, and shows that it is better than that of a straightforward fixed length postings list.
QBISM: extending a DBMS to support 3D medical images
37 Citations2002Manish Arya, William F. Cody +3 more
The authors observed that the DBMS' early spatial filtering results in significant performance savings because the system response time is dominated by the amount of data retrieved, transmitted, and rendered.
QBISM: A Prototype 3-D Medical Image Database System.
29 Citations1993Manish Arya, William F. Cody +3 more
Querying and visualizing collections of Machines Inc. query By Interactive, Spatial Magnetic Resonance Imaging shows soft-tissue structural information.