Efficient Cost Models for Spatial Queries Using R-Trees.
AbstractSelection and join queries are fundamental operations in Data Base Management Systems (DBMS). Support for nontraditional data, including spatial objects, in an efficient manner is of ongoing interest in database research. Toward this goal, access methods and cost models for spatial queries are necessary tools for spatial query processing and optimization. In this paper, we present analytical models that estimate the cost (in terms of node and disk accesses) of selection and join queries using R-tree-based structures. The proposed formulae need no knowledge of the underlying R-tree structure(s) and are applicable to uniform-like and nonuniform data distributions. In addition, experimental results are presented which show the accuracy of the analytical estimations when compared to actual runs on both synthetic and real data sets.
INTRODUCTION
Supporting large volumes of multidimensional (spatial) data is an inherent characteristic of modern
database applications, such as Geographical Information Systems (GIS), Computer Aided Design (CAD),
Image and Multimedia Databases. Such databases need underlying systems with extended features (query
languages, data models, indexing methods) as compared to traditional databases, mainly due to the
complexity of representating and retrieving spatial data. Spatial Data Base Management Systems
(SDBMS), in general, should (i) offer appropriate data types and query language to support spatial data,
and (ii) provide efficient indexing methods and cost models on the execution of specialized spatial
operations, for query processing and optimization purposes [Gut94].
In the particular field of spatial query processing and optimization, during the last two decades several
data structures have been developed for point and non-point multidimensional objects in low-dimensional
space to meet needs in a wide area of applications, including the GIS and CAD domains. Due to the large
number of spatial data structures proposed (an exhaustive survey can be found in [GG95]) active research
in this field has recently turned to the development of analytical models that could make accurate cost
predictions for a wide set of spatial queries. Powerful analytical models are useful in three ways:
(i) structure evaluation: they allow us to better understand the behavior of a data structure under various
input data sets and sizes.
(ii) benchmarking: they can play the role of an objective comparison point when various proposals for
efficient spatial indexing are compared to each other.
(iii) query optimization: they can be used by a query optimizer in order to evaluate the cost of a complex
spatial query and its execution procedure.
Spatial queries addressed by users of SDBMS usually involve selection (point or range) and join
operations. In the literature, most efforts towards the analytical prediction of the performance of spatial
data structures have focused on point and range queries [FSR87, KF93, PSTW93, FK94, TS96] and,
recently, on spatial join queries [Gun93, HJR97, TSS98]. Some proposals support both uniform-like and
non-uniform data distributions, which is an important advantage keeping in mind that modern database
applications handle large amounts of real (usually non-uniform) multidimensional data.
In this paper we focus on the derivation of analytical formulae for range and join queries based on R-trees
[Gut84]; such models support data sets of any distribution (either uniform-like or non-uniform ones)
and make cost prediction based on data properties only. The proposed formulae are shown to be efficient
for several distributions of synthetic and real data sets with the relative error being around 10%-15% for
any kind of distribution used in our experiments.
The rest of the paper is organized as follows: In Section 2, we provide background information about
hierarchical tree structures for spatial data, in particular R-tree-based ones, and related work on cost
analysis of R-tree-based methods. Section 3 presents cost models for the prediction of the R-tree
performance for selection and join queries. In Section 4, comparison results of the proposed models are
presented with respect to efficient R-tree implementations for different data distributions. An extended
survey of related work appears in Section 5, while Section 6 concludes this presentation. Most of the work
in this paper is based on previous work by the authors [TS96, TSS98].
2. BACKGROUND
The first applications of interest involving multidimensional data included geographical databases (GIS,
cadastral applications, etc.), CAD and VLSI design. Recently, spatial data management techniques have
been applied to a wide area of applications, from image and multimedia databases [Fal96] to data mining
and data warehousing [FJS97, RKR97]. An example of a GIS application is illustrated in Figure 1, where
the geographical database consists of several relations 1
about Europe. In particular, Figure 1a (1b)
illustrates European countries (motorways) on a common workspace.
(a) Relation countries (b) Relation

Figure

1: Example of a spatial application
The most common queries on such databases include point or range queries on a specified relation (e.g.
"find all countries that contain a user-defined point" or "find all countries that overlap a user-defined
query window") or join queries on pairs of relations (e.g. "find all pairs of countries and motorways that
overlap each other").
2.1. SPATIAL QUERIES AND SPATIAL
The result of the select operation on a relation REL 1 using a query window q contains those tuples in
with the spatial attribute standing in some relation q to q. On the other hand, the result of the joinThe example considers a relational database [Cod70]. However, in the rest of the paper, our discussion does not depend on the
specific underlying model of the SDBMS. Other models, such as object-oriented [Kim95] or object-relational [SM96] ones, are
also supported in a straight-forward manner.
operation between a relation REL 1 and a relation REL 2 contains those tuples in the cartesian product REL 1
where the i-th column of REL 1 stands in some relation q to the j-th column of REL 2 .
In conventional (alphanumeric) applications, q is often equality. When handling multidimensional data,
q is a spatial operator, including topological (e.g., overlap), directional (e.g., north), or distance (e.g.,
close) relationships between spatial objects (in the example of Figure 2, the answer sets of the operators
overlap, north, and close with respect to the query object q are {o5}, {o1, o2}, and {o3, o5}, respectively).
close
overlap
north

Figure

2: Examples of spatial operators
For each spatial operator, with overlap being the most common, the query object's geometry needs to
be combined with each data object's geometry. However, the processing of complex representations, such
as polygons, is very costly. For that reason, a two-step 2
procedure for query processing, illustrated in

Figure

3, is usually adopted [Ore89]:
. filter step: an approximation of each object, such as its Minimum Bounding Rectangle (MBR), is used
in order to produce a set of candidates (and, possibly, a set of actual answers), which is a superset of
the answer set consisting of actual answers and false hits.
. refinement step: each candidate is then examined with respect to its exact geometry in order to
produce the answer set by eliminating false hits.Brinkhoff et al. [BKSS94] alternatively propose a three-step procedure which interferes a second step of examining more
accurate approximations, e.g., convex hull or minimum m-corner, in order to further reduce the number of false hits.
false hits
Test on exact
geometry
hits
candidates
Test on object
approximation
hits
query result
Filter step
Refinement step

Figure

3: Two-step spatial query processing
The filter step is usually based on multidimensional indexes that organize MBR approximations of
spatial objects [Sam90]. In general, the relationship between two MBR approximations cannot guarantee
the relationship between the actual objects; there are only few operators (mostly directional ones) that
make the refinement step unnecessary [PT97].
On the other hand, the refinement step usually includes computational geometry techniques for
geometric shape comparison [PS85] and, therefore, it is usually a time-consuming procedure since the
actual geometry of the objects need to be checked. Although techniques for speeding-up this procedure
have been studied in the past [BKSS94] the cost of this step can not be considered as part of index cost
analysis and hence it is not taken into consideration in the following.
Several methods for multidimensional (spatial) indexing have been proposed in the past. They can be
grouped in two main categories: indexing methods for points (also known as point access methods -
PAMs) and indexing methods for non-point objects (also known as spatial access methods - SAMs).
Well-known PAMs include the BANG file [Fre87], and the LSD-tree [HSW89], while, among the
proposed SAMs, the R-tree [Gut84] and its variants (e.g. the R + -tree [SRF87] and the R*-tree [BKSS90])
are the most popular. In the next subsection we describe the R-tree indexing method and its algorithms for
search and join operations.
2.2. THE R-TREE INDEXING METHOD
R-trees were proposed by Guttman [Gut84] as a direct extension of B -trees [Knu73, Com79] in d-
dimensions. The data structure is a height-balanced tree that consists of intermediate and leaf nodes. A leaf
node is a collection of entries of the form
(oid, R)
where oid is an object identifier, used to refer to an object in the database, and R is the MBR
approximation of the data object. An intermediate node is a collection of entries of the form
(ptr, R)
where ptr is a pointer to a lower level node of the tree and R is a representation of the minimum rectangle
that encloses all MBRs of the lower-level node entries.
Let M be the maximum number of entries in a node and let m - M / 2 be a parameter specifying the
minimum number of entries in a node. An R-tree satisfies the following properties:
(i) Every leaf node contains between m and M entries unless it is the root.
(ii) For each entry (oid, R) in a leaf node, R is the smallest rectangle that spatially contains the data
object represented by oid.
(iii) Every intermediate node has between m and M children unless it is the root.
(iv) For each entry (ptr, R) in an intermediate node, R is the smallest rectangle that completely encloses
the rectangles in the child node.
(v) The root node has at least two children unless it is a leaf.
(vi) All leaves appear in the same level.
After Guttman's proposal, several researchers proposed their own improvements on the basic idea.
Among others, Roussopoulos and Leifker [RL85] proposed the packed R-tree, for the case that data
rectangles are known in advance (i.e., it is applicable only to static databases), Sellis et al. [SRF87]
proposed the R + -tree, a variant of R-trees that guarantees disjointness of nodes by introducing redundancy,
and Beckmann et al. [BKSS90] proposed the R*-tree, an R-tree-based method that uses a rather complex
but more effective grouping algorithm. Gaede and Gunther [GG95] offer an exhaustive survey of
multidimensional access methods including several other variants of the original R-tree technique.
As an example, Figure 4 illustrates an set of data rectangles and the corresponding R-tree built on these
rectangles (assuming maximum node capacity


Figure

4: Some rectangles, organized to form an R-tree, and the corresponding R-tree
The processing of any type of spatial query can be accelerated when a spatial index (e.g. an R-tree)
exists. The selection query, for example, retrieves all objects of a spatial relation REL that overlap a query
window q. It is implemented by performing a traversal of the R-tree index: starting from the root node,
several tree nodes are accessed down to the leaves, with respect to the result of the overlap operation
between q and the corresponding node rectangles. When the search algorithm for spatial selection (called
SS and illustrated in Figure 5) reaches the leaf nodes, all data rectangles that overlap the query window q
are added into the answer set.
SS(R1: R_node, q:rect); /* Spatial Selection Algorithm for R-trees */
(all Er1 in R1) DO
IF (overlap(Er1.rect, q)) THEN
04 IF (R1 is a leaf page) THEN
06 ELSE
07 ReadPage(Er1.ptr);

Figure

5: Spatial selection operation using R-trees (algorithm SS)
On the other hand, the join operation between two spatial relations REL 1 and REL 2 can be implemented
by applying synchronized tree traversals on both R-tree indexes. An algorithm based on this general idea,
called originally introduced by Brinkhoff et al. in [BKS93]. Two improvements of this
algorithm were also proposed in the same paper towards the reduction of the CPU- and I/O-cost by taking
into consideration faster main-memory algorithms, and better read schedules for a given LRU-buffer,
respectively. Specifically, for two R-tree indexes rooted by nodes R 1 and R 2 , respectively, the spatial join
procedure (algorithm SJ) is illustrated in Figure 6.
SJ(R1,R2: R_node); /* SpatialJoin Algorithm for R-trees */
(all Er2 in R2) DO
(all Er1 in R1) DO
IF (R1 is a leaf page) AND (R2 is a leaf node)
THEN
06 output(Er1.oid, Er2.oid)
07 ELSE IF (R1 is a leaf node) THEN
is a leaf node) THEN

Figure

operation between two R-trees (algorithm SJ)
In other words, a synchronized traversal of both R-trees is executed, with the entries of nodes R 1 and
playing the roles of data and query rectangles, respectively, in a series of range queries.
For both opeartions, the total cost is measured by the total amount of page accesses in the R-tree index
(procedure ReadPage). Procedure ReadPage either performs an actual read operation on the disk or reads
the corresponding node information from a memory-resident buffer, thus we distinguish between node and
disk accesses 3 in the analysis of Section 3.
3 The distinction between node and disk accesses (denoted by NA and DA, respectively) is a subject related to buffer management.
The inequality DA - NA always stands; the equality stands only for the case where no buffering scheme exists.
3. ANALYTICAL COST MODELS FOR SPATIAL QUERIES
Complex queries are usually transformed by DBMS query optimizers to a set of simpler ones and the
execution procedure takes the partial costs into account in order to schedule the execution of the original
query. Thus query optimization tools that estimate access cost and selectivity of a query are
complementary modules together with access methods and indexing techniques. Traditional optimization
techniques usually include heuristic rules, which however are not effective in spatial databases due to the
peculiarity of spatial data sets (multi-dimensionality, lack of total ordering, etc. Other, more
sophisticated, techniques include histograms and cost models. Although research on multi-dimensional
histograms has recently appeared in the literature [PI97], in the spatial database literature, cost models for
selectivity and cost estimation seem to be the most promising solutions. Proposals in this area include
models for selection [KF93, PSTW93] and join [Gun93] queries.
However, most proposals require knowledge of index properties and make a uniformity assumption,
thus rendering them incomplete tools for the purposes of real query optimization. Appropriate extensions
to solve those problems are presented in the rest of the section. Throughout our discussion we use the list
of symbols that appears in Table 1.
3.1. SELECTION QUERIES
Formally, the problem of the R-tree cost analysis for selection queries is defined as follows: Let d be the
dimensionality of the data space and the d-dimensional unit workspace. Let us assume that
data rectangles are stored in an R-tree index R 1 and a query asking for all rectangles that overlap a
query window needs to be answered. What is sought is a formula that estimates the average
number NA of node accesses using only knowledge about data properties (i.e., without extracting
information from the underlying R-tree structure).
Definition: The density D of a set of N rectangles with average size s (s 1 , s 2 , ., s d ) is the average
number of rectangles that contain a given point in d-dimensional space.
Equivalently, D can be expressed as the ratio of the sum of the areas of all rectangles over the area of
the available workspace. If we assume a unit workspace [0,1) d , with unit area, then the density D(N,s) is
given by the following formula:
d
d
s
s
Symbol Definition
d number of dimensions
minimum R-tree node capacity
maximum R-tree node capacity
f average R-tree node fanout
c average R-tree node capacity (in
R height of the R-tree R i
R number of data rectangles indexed in the R-tree R i
density of data rectangles indexed in the R-tree R i
l
N , number of nodes of the R-tree R i at level l
l
R
D , density of node rectangles of the R-tree R i at level l
average extent of a query rectangle q on dimension k
l
R
s , average extent of node rectangles of the R-tree R i at level l on dimension k
number of node / disk accesses for R-tree R 1 at level l because of the query rectangle q
number of node / disk accesses for R-tree R i at level l because of the node rectangles of the
number of node / disk accesses for a selection query between an R-tree R 1 and a query
rectangle q
number of node / disk accesses for a join query between two R-trees R 1 and R 2

Table

1: List of symbols and definitions
Assume now an R-tree R 1 of height 1
R
(the root is assumed to be at level 1
R
h and leaf-nodes are
assumed to be at level 1). If l
R
is the number of nodes at level l and l
R
is their average size then the
expected number NA_total(R 1 , q) of node accesses in order to answer a selection query using a query
window defined as follows (assuming that the root node is stored in main memory):
_
R
l
l
R
l
R q
s
intsect
R
total
NA (2)
s
intsect l
R
l
R is a function that returns the number of nodes at level l intersected by the
query window q. In other words, Eq. 2 expresses the fact that the expected number of node accesses is
equal to the expected number of intersected nodes at each level l (l
R
Lemma: Given a set of N rectangles r 1 . r N with average size s and a rectangle r with size q, the
average number of rectangles intersected by r is:
d
s
s
Proof: The average number of a set of N rectangles with average size s that intersect a rectangle r with
size q is equal to the number of a second set of N rectangles with average size s' ( k
s
' , "k) that
contain a point in the workspace. The latter one, by definition, equals to the density D' of the second set of
rectangles.
d
s
s
s
intsect
s
intsect'
s
' .
Assuming that rectangle r represents a query window on R 1 , we derive NA_total(R 1 , q) by combining
Eqs. 2 and 3:
_
R
l
d
l
R
l
R q
s
R
total
NA . (4)
In order to reach our goal we have to express Eq. 4 as a function of the data properties
(number of
data rectangles) and 1
R
D (density of data rectangles) or, in other words, to express the R-tree index
properties
R
R
, and k
l
R
s ,
,as functions of the data properties
and 1
R
D .
The height 1
R
h of an R-tree R 1 with average node capacity (fanout) f that stores N R 1
data rectangles is
given by the following formula [FSR87]:
f
f
log
Since a node organizes on the average f rectangles, we can assume that the average number of leaf-nodes
(i.e.,
the average number of their parent nodes (i.e., l = 2) is
f
In general, the average number of nodes at level l is
l
R
l
R
f
A second assumption that we make is that the sizes of the node sides are equal (i.e.,
l
s
s d
l
R
l
,, 1. This squaredness assumption is a reasonable property for a "good" R-tree [KF93].
According to that assumption and Eqs. 1 and 6, the average extent k
l
s ,
, is a function of the density l
R
of node rectangles at level l:
l
R
l
R
d
l
R
R
l
R s
f
s
d
R
l
R
l
R N
f
s,
What remains is an estimation of l
R
D ,using the data properties
and 1
R
D . Suppose that, at level l,
l
R
N ,nodes with average size ( ) d
l
R
s ,
,are organized in 1
l
R
parent nodes with average size ( ) d
l
R
Each parent node groups on the average f child nodes, as illustrated in Figure 7 (d = 2), d
child nodes
being responsible for the size of the parent node along each direction. The centers of the l
R
rectangles' projections are assumed to be equally distanced and this distance (denoted by t l,k ) depends on
d
l
R
,nodes along each direction.
#SDUHQW#QRGH FRQVLVWV#RI#I FKLOG#QRGHV
WO#N
FKLOG#QRGH

Figure

7: Grouping f nodes into 1 parent node
Hence the average size k
R
of a parent node along each direction is given by:
l
R
l
d
l
R s
f
s ,
where t l,k is given by:
d
l
R
and denotes the distance between the centers of two consecutive rectangles' projections on dimension k.
To derive Eq. 9 we divided the (unit) extent of the workspace by the number of different node projections
on dimension k.
Lemma: Given a set of l
R
node rectangles with density l
R
D ,, the density k
l
R
D ,of their projections
is given by the following formula:
d
l
R
l
R
l
R N
R
d
l
R
d
l
R
l
R
d
l
R
l
R
l
R
l
R s
s
s
R
d
l
R
l
R
l
R
d
l
R
d
R D
Using Eqs. 8, 9, and 10, the density 1
l
R
D of node rectangles at level l+1 is a function of the density
l
R
D ,of node rectangles at level l:
d
d
d
l
R
l
R
f
Essentially, by using Eq. 11, the density at each level of the R-tree is calculated as a function of only
the density 1
R
D of the data rectangles (which can be named 0
At this point, the original goal has been reached. By combining Eq. 4, 5, 6, 7 and 11, the following
formula for the expected number NA_total(R 1 , q) can be derived.
f
l
d
d
R
l
l
R
l
R
R
f
f
R
total
log1 1,
Clearly, this formula can be computed by using only the data set properties
and 1
R
D , the typical
R-tree parameter f and the query window q.
3.2. JOIN QUERIES
According to the discussion of subsection 2.2, the processing cost of a join query is equal to the total cost
of a set of appropriate range queries, as the algorithm SJ shown in Figure 6 illustrates. In this subsection
we propose a pair of formulae that estimate the cost of a join query.
Formally, the problem of R-tree cost analysis for join queries is defined as follows: Let d be the
dimensionality of the workspace and the d-dimensional unit workspace. Let us assume two
spatial data sets of cardinality N R 1
and N R 2
, respectively, with the corresponding MBR approximations
being stored in two R-tree indexes R 1 and R 2 , respectively. In correspondence with the goal of Section 3.1,
in this section, the target of our cost analysis is a formula that would efficiently estimate the average
number NA of node accesses needed to process a join query between the two data sets, based on the
knowledge of the data properties only and without extracting information from the corresponding R-tree
structures.
Suppose that the height of a tree index R i is equal to R
h and the two root nodes are stored in
main memory. At each level l i
R
h -1, the tree structure R i contains i
l
R
N , nodes of average size
l
R
s , consisting of a set of entries l
R
E . In order to find which pairs of entries are overlapping and
downwards traverse the two tree structures, we compare entries 1
R
R
(line 04 of the
spatial join algorithm SJ in Figure 6).
The cost, in terms of node accesses, of the above comparison at each level is given by the summation
of two factors which express the respective costs for the two R-trees, namely )
R
R
NA and
R
R
NA . In order to estimate these two factors we consider that the entries of R 1 (R 2 ) play the role
of the data set (a set of query windows q, respectively); then we apply the function 'intsect' from the R-tree
analysis for selection queries in order to estimate the access cost for R 1 (R buffering scheme is
considered for the analytical estimation of node accesses; hence the access costs for both trees R 1 and R 2 at
each level are equal (since equal number of nodes are accessed, as can be extracted by line 14 of algorithm
SJ). The processing of line 04 of the SJ algorithm is repeatedly executed at each level of the two trees
down to the leaf level of the shorter tree R 2 (without loss of generality, we assume that 1
R
R
R
l
R
l
R
l
R
s
s
intsect
l
R
R
l
R
R
d
l
R
l
R
l
R
l
R s
s
l
R
R
l
R
R
R
R h
l
h and 1
l .
In [TSS98] we provide a slightly modified formula: in particular, instead of the factor k
l
R
l
R s
s ,
we use an upper bound (i.e., ( )
{ }
l
R
R s
s ,
workspace, which is assumed during the
whole analysis of Section 3 (Eq. 3, Eq. 4, Eq. 12, and Eq. 13). When the leaf nodes of R 2 are being
processed, l 2 is fixed to value 1 (i.e., denoting the leaf level) and the propagation of R 1 continues down to
its lower h h
levels. Formally, the total cost in terms of node accesses is given by Eq. 14:
_
R
l
l
R
R
l
R
R
R
R
total
R
R
R
R
R
R
R
l
l
l
l -
The involved parameters are:
. i
R
h , which denotes the height of the tree R i and is given by Eq. 5,
. l
R
N , which denotes the average number of nodes of the tree R i at level l i and is given by Eq. 6, as a
function of the actual population N R i
of the data set, and
. k
l
s ,
, , which denotes the average extent of nodes of the tree R i at each dimension k at level l i and is
given by Eq. 7, as a function of the density l
R
D of the node rectangles at level l i , which, in turn, is
given by Eq. 11, as a function of the actual density D R i
of the data set.
Qualitatively, Eq. 14 estimates the cost of a join query between two spatial data sets based on their
primitive properties only, namely number and density of data rectangles , in correspondence with the
relevant analysis for range queries (subsection 3.1). Notice that Eq. 14 is symmetric with respect to the
two indexes R 1 and R 2 . The same conclusion is drawn by studying the algorithm SJ, since the number of
node accesses is equal to the number of ReadPage calls (line 14) which, in turn, are the same for both
trees. The equivalence of the two indexes is not the case when a simple path buffer (i.e., a buffer that
keeps the most recently visited path for each tree structure) is introduced, as we will discuss in the next
subsection.
3.3. INTRODUCING A PATH BUFFER
Extending previous analysis, we introduce a simple buffering mechanism that maintains a path buffer for
the underlying tree structure(s). The existence of such a buffer mainly affects the performance of the tree
index that plays the role of the query set (namely R 2 ), as will be discussed in detail in this subsection,
since the search procedure, algorithm SJ illustrated in Figure 6, reads R 2 entries less frequently than R 1
entries. With respect to that, we assert that the cost of a selection query in terms of disk accesses
almost equal to NA_total(R 1 , q), as formulated in Eq. 12, and therefore provide no
further analysis for path buffering. Moreover, the effect of a buffering mechanism (e.g. an LRU buffer)
has been already addressed in the literature [LL98] and, according to experimental results, very low buffer
size (such as that of a path buffer) causes almost zero impact on point and range query performance. On
the other hand, even a simple path buffer scheme highly affects the actual cost of a join query.
As already mentioned, by examining algorithm SJ we conclude that the existence of such a buffering
scheme mainly affects the computation of the cost for R 2 because its entries constitute the outer loop of the
algorithm and hence are less frequently updated. As for R 1 , since its entries constitute the inner loop of the
algorithm, the respective cost computation is not considerably affected by the existence of a path buffer.
These statements are formally explained by the following alternative cases (illustrated in Figure 8):
(i)Suppose that an entry l
R
of tree R 2 at level l overlaps with m entries of a node 1
l
R
entries of a
different node 1
l
R
etc., of the tree R 1 . l
R
,is kept in main memory during its comparison with all
entries of node 1
l
R
and will be again fetched from disk, hence re-computed in DA(R 2 , R 1 , l) cost,
when its comparison with the entries of 1
l
R
starts. As a result, the number of actual disk accesses of
the node rooted by l
R
,is equal to the number of the nodes of R 1 at level l+1 (i.e., the parent level)
having rectangles intersected by j
R
l
R
l
R
l
R s
s
intsect 1
.
(ii) On the other hand, an entry l
R
of tree R 1 at level l is re-computed in DA(R 1 , R 2 , l) as soon as it
overlaps with an entry l
R
of tree R 2 with only one exception: l
R
,being the last member of the
intersection set of l
R
simultaneously, the first member of the intersection set of its consecutive
l
R
. The above exception rarely happens; moreover, it is hardly modeled since no order exists
among entries of R-tree nodes.
Hypothesis:
overlaps with {D1, E1} and {H1, I1} entries of nodes A1 and B1, respectively
- E2 overlaps with {E1, F1} and {H1} entries of nodes A1 and B1, respectively
case (i): Example of DA(R 2 , R 1 ,l) computation:
hits due to entry D2 (i.e., equal to the number of intersected entries of R 1 at level l+1, namely {A1, B1}).
case (ii): Example of DA(R 1 ,R 2 ,l) computation:
Rule: 2 hits due to entry H1 (i.e., equal to the number of intersected entries of R 2 at level l, namely {D2, E2}).
Exception to the rule: 1 hit due to entry E1 (since the overlapping pairs (E1, D2) and (E1, E2) are consecutively checked)
'#
'#
OHYHO#O#
OHYHO#O

Figure

8: Alternative cases for estimating DA cost for join queries.
Since the cost for the tree that plays the role of the query (data) set is affected in a high (low) degree,
we distinguish between two different cases: the tree R 1 that plays the role of the data set being taller or
shorter than R 2 . In the first case (where h h
> ) the propagation of R 1 down to its lower levels adds no
extra cost (in terms of disk accesses) to the 'query' tree R 2 that has already reached its leaf level. In the
second case (where 2
R h
each propagation of the 'query' tree R 2 down to its lower levels adds equal
cost to the 'data' tree R 1 (denoting that buffer existence does not affect the cost of the `data' tree R 1 ).
Hence, with respect to the above discussion, the access cost of each tree at a specific level l i is
calculated according to the following formulae:
R
R
l
R
R
d
l
R
l
R
l
R
l
R
l
R
l
R
l
R
l
R s
s
s
s
l
R
R
,,,
intsect
and the total cost is given by Eq. 17 (if 2
R h
R h
l
l -
R h
l
l -
{ }
{ } { }
if
if
R
R
l
l
R
R
l
l
l
R
R
DA
l
R
R
DA
l
R
R
DA
l
R
R
DA
l
R
R
DA
l
R
R
DA
R
R
total
R
R
R
R
R
R
R
R
R (17)
Notice that, in contrast to Eq. 14, Eq. 17 is sensitive to the two indexes, R 1 and R 2 . The experimental
results of Section 4 also strengthen this statement.
In the above analysis we have taken two cases into consideration: adopting (a) no, or (b) a simple path
buffer scheme. A more complex buffering scheme (e.g. an LRU buffer of predefined size) would surely
achieve a lower value for DA_total. However, its effect is beyond the scope of this paper (see [LL98] for
related work on selection queries).
3.4. SUPPORT FOR NON-UNIFORM
The proposed analytical model assumes data uniformity in order to compute the density of the R-tree node
rectangles at a level l+1 as a function of the density of the child node rectangles at level l (Eq. 11). In
particular, in order to derive Eq. 8 and Eq. 9, it was assumed that the centers of the l
R
node rectangles'
projections were equally distanced. This uniformity assumption leads to a model that could be efficient for
uniform-like data distributions but hardly applicable to non-uniform distributions of data, which are the
rule when dealing with real applications.
In order to adapt the model in a way that would efficiently support any type of data sets (uniform or
non-uniform ones) we reduce the global uniformity assumption of the analytical model (i.e., consider the
whole workspace) to a local uniformity assumption (by assuming a small sub-area of the workspace)
according to the following idea: The density of a data set is involved in the cost formulae as a single
number D R i
. However, for non-uniform data sets, density is a varying parameter, graphically a surface in
d-dimensional space. Such a surface could show strong deviations from point to point of the workspace,
compared to the average value. For example, in Figure 9, a real data set, called LBeach [Bur91], is
illustrated together with its density surface.
(a) LBeach data set (b) LBeach density surface

Figure

9: A real data set and its density surface
The average density of this data set is D However, as extracted from Figure 9b, actual density
values vary from zero-populated areas, such as the upper-left and bottom-right corners) up to
high-populated areas), with respect to the reference point. It is evident that using the D avg value
in a cost formula would sometimes lead to inaccurate estimations. On the other hand, a satisfactory image
of the density surface provides more accurate D values, with respect to a specified query window q.
Although we refer to dynamic indexing we assume that we can use some data properties for our
prediction, such as the expected number N and average size s of data, since these properties can be usually
computed using a sample of the data set (efficient sampling algorithms have been proposed, among others,
by Vitter in [Vit84, Vit85]).
Based on the above idea, the proposed cost formulae could efficiently support either uniform or non-uniform
data distributions by assuming the following modifications:
(i) the average density D R i
of the data set is replaced by the actual density R
D of the data set within the
area of the specified query window q.
(ii) the amount R
N of the data set is replaced by a transformation R
N of that, computed as
R
R
R
R N
' .
In this section we provided analytical formulae for the cost estimation of selection or join queries on
spatial data sets organized by disk-resident R-tree indexes. The proposed cost models are based on
primitive data properties only, without any knowledge of the corresponding R-trees. In the next section we
evaluate our model by comparing the analytical estimations with experimental results on synthetic and real
data sets in one- and two-dimensional space.
4. EVALUATION OF THE COST MODELS
The evaluation of the analytical formulae proposed in Section 3 was based on a variety of experimental
tests on synthetic and real data sets illustrated in Figure 10. Synthetic one- and two- dimensional data sets
consist of random (Figure 10a) and skewed (Figure 10b) distributions of varying cardinality N (20K - N -
80K) and density D (0.2 - D - 0.8), and have been constructed by using random number generators.
Real two-dimensional data sets are parts of the TIGER database of the U.S. Bureau of Census [Bur91].
In particular, we have used two TIGER data sets:
. LBeach data set: 53,143 line segments (stored as rectangles) indicating roads of Long Beach,
California (Figure 10c).
. MGcounty data set: 39,221 line segments (stored as rectangles) indicating roads of Montgomery
county, Maryland (Figure 10d).
For the experimental tests we built R*-tree indexes [BKSS90] and performed several spatial joins
using the data sets presented before. All experimental results were run on an HP700 workstation with 256
Mbytes of main memory. On the other hand, the analytical estimations of node accesses for selection
queries were based on Eq. 12 and the node (disk) cost estimations for join queries were based on Eq. 14
(Eq. 17) with the average capacity of the tree indexes being set to the typical
4 The average density R
D of a data set is considered to be always R
D > 0, even for point data sets. R
corresponds to zero-
populated areas.
(a) synthetic data: random (uniform-like) distribution (b) synthetic data: skewed (Zipf) distribution
(c) real data: LBeach data set (d) real data: MGcounty data set

Figure

10: Two-dimensional data sets used in our experiments
4.1. UNIFORM-LIKE
We present several test results in order to evaluate the cost estimation of Eq. 12 for selection (point and
range) queries. Figure 11 illustrates the results for two random data sets respectively,
both with density 0.1). The relative error was always below 10% for the two experiments illustrated in

Figure

11 as well as the rest experiments with random data sets.
query size in % of workspace per axis
node
(log
scale)
H[SHU#.
H[SHU#.
DQDO#.

Figure

11: Performance comparison for selection queries on uniform-like data
log scale)
As a further step, we evaluated the analytical formulae for join query estimation, presented in Section
3, on various R-tree combinations. Figure 12 illustrates the experimental and analytical results of node and
disk accesses (denoted by NA and DA) for (a) one- and (b) two-dimensional random data sets,
respectively, for all 1
R
R
combinations.
The non-linearity of the plots in Figure 12b is due to the fact that all R-tree indexes are not of equal
height h; the height of the two-dimensional indexes of cardinality 20K - N - 40K (60K - N - 80K) is
equal to while the height of all one-dimensional indexes is equal to 3. According to our
experiments it also turns out that the cost formulae for the estimation of disk accesses DA are non-symmetric
with respect to the trees R 1 and R 2 , a fact that has been already mentioned during the
presentation of the cost models in Section 3. The comparison results confirm that, for tree indexes of equal
height, the choice of the smaller (larger) index to play the role of the 'query' (`data') tree is the best choice
for the effectiveness of SJ algorithm, which however is not a general rule for trees of different height, as
illustrated in Figure 13 (all areas but AREA 2 and AREA 3 in the two-dimensional case follow the rule).
(a)
N5# / N5# combination
N5# / N5# combination

Figure

12: Experimental vs. analytical NA and DA costs for join queries on uniform-like data
N5# or N5#
DA
N5# or N5#
DA
(a)

Figure

13: Analytical DA costs for join queries on uniform-like data for varying cardinality 1
R
N or 2
R
Summarizing the results for join queries on random (uniform-like) data sets, we conclude the
(i) When no buffering scheme is adopted (i.e., the estimated number of node accesses NA is evaluated)
then the estimation is very accurate, since the relative error never exceeds 10%.
(ii) When a path buffer is adopted then the estimated cost of R 2 is always very close to the actual cost
(relative error usually below 5%), while the estimated cost of R 1 is usually within 10%-15% of the
experimental result. The accuracy of the estimation concerning R 2 (i.e., the tree that plays the role of
the query set) is expected since the existence of a buffer has been taken into account in Eq. 8, while
Eq. 9 assumes that the buffer existence does not affect R 1 (i.e., the tree that plays the role of the data
set), an assumption that lowers the accuracy of the estimation for the access cost of R 1 . However, as
already mentioned in subsection 3.2, the exception to the rule is hardly modeled.
4.2. NON-UNIFORM
As explained in Section 3, a transformation of the actual density of each non-uniform data set is necessary
in order to reduce the impact of the uniformity assumption of the underlying analytical model from global
(i.e., assuming the global workspace) to local (i.e., assuming a small sub-area of the workspace). In other
words, instead of considering the average density D avg of a data set, the cost formulae (Eq. 12, Eq. 14, and
Eq. 17) consider the values of the density surface D(x,y) that correspond to the appropriate areas of the
workspace. For experimentation purposes, we extracted a density surface for each non-uniform data set
using a grid of 40 x 40 cells, i.e., a step of 0.25% of the workspace per axis.
Figure

14 illustrates average results for selection queries on (a) skewed and (b) real data sets. The
analytical results are plotted with dotted lines and the experimental results for R*-trees with solid lines.
The relative error is usually around 10%-15% and this was the rule for all data sets that we tested.20601000.00 0.10 0.20 0.30 0.40
query size in % of work space per axis
node
query size in % of work space per axis
node
(a) Skewed data:
(b) Real data:
LBeach (upper pair) and MGcounty (lower pair)

Figure

14: Performance comparison for selection queries on non-uniform data
(solid lines: experimental results, dotted lines: analytical results)
The flexibility of the proposed analytical model on non-uniform distributions of data, using the
"density surface", is also extracted from the results of our experiments. Figure 15 illustrates the results for
typical point queries around nine representative points on skewed and real
data sets. The analytical results are plotted with dotted lines while the experimental results using R*-trees
are plotted with solid lines. Note that the plotted irregularities are similar for both the analytical and the
experimental values.
1_1 1_2 1_3 2_1 2_2 2_3 3_1 3_2 3_3
representative points (x_y)
node
1_1 1_2 1_3 2_1 2_2 2_3 3_1 3_2 3_3
representative points (x_y)
node
(a) skewed data, point queries (b) skewed data, range queries0,51,52,53,54,5
1_1 1_2 1_3 2_1 2_2 2_3 3_1 3_2 3_3
representative points (x_y)
node
accesses1030501_1 1_2 1_3 2_1 2_2 2_3 3_1 3_2 3_3
representative points (x_y)
node
(c) real data, point queries (d) real data, range queries

Figure

15: Performance comparison for selection queries around representative points
(solid lines: experimental results, dotted lines: analytical results)
The evaluation of the model for join queries also includes a wide set of experiments. Figure 16a
illustrates weighted average 5 costs (denoted by w.NA and w.DA) on two-dimensional skewed data sets for
varying density D. Apart from synthetic data sets we also used real ones from the TIGER database
[Bur91].

Figure

16b illustrates the corresponding experimental and analytical results. The labels lb and mg
(lb' and mg') denote the actual (mirrored with respect to x-, and y- axes) LBeach and MGcounty data
sets, respectively. In general, a relative error below 20% appears for all non-uniform data combinations.The weighted average number of disk (and node) accesses is computed by multiplying each cost with a factor inversely
proportional to the corresponding cardinality:
. i
DA
w where N
w K= , in order to achieve fair portions for both
low- and high- populated indexes.
lb / mg mg lb lb lb' mg / mg'
real data combinations
(a) skewed data (b) real data

Figure

Experimental vs. analytical NA and DA costs for join queries on non-uniform data
Summarizing the results of our tests, we list in Table 2 the average relative errors of the actual results
compared to the predictions of our model.
Relative
Data sets
point
queries
range
queries
join
queries
Random data 0%-10% 0%-5% 0%-10%
Skewed data 0%-15% 0%-10% 0%-20%
Real data 0%-15% 0%-20% 0%-20%

Table

2: Average relative error in estimating access cost for selection and join queries
4.3. THE BENEFIT WHEN USING A PATH BUFFER
As discussed in subsection 3.3, the larger the buffer size in an actual database system, the lower the access
cost for a selection or join query. However, the benefit for spatial selection queries by using a simple path
buffer is not clearly measurable; according to a related work [LL98], when the buffer size is close to zero
then no significant performance gain is achieved. On the other hand, a path buffer clearly affects the
performance of join queries, as the gaps between the lines that represent NA and DA in Figures 12 and
indicate. This gap is illustrated in Figure 17 with NA values being fixed to value 100% and hence DA
values showing the relative performance gain.
A significant savings of 10%-30% appears for one-dimensional data. Recalling that all one-dimensional
data sets of our experiments generated equal height trees, one can observe that the smaller the
'query' tree, the highest the gain becomes. For two-dimensional data sets, the performance gain increases
up to a 50% level. The above conclusion also stands in this case showing, however, a less uniform
behavior, which is due to the different index heights.
(a)
#.
UHODWLYH#SHUIRUPDQFH
(b)
#.
UHODWLYH#SHUIRUPDQFH

Figure

17: Relative performance gain when using a path buffer
5. RELATED WORK
In the survey of this section we present previous work on analytical performance studies for spatial queries
using R-trees. Several conclusions from those proposals have been used as starting points for consequent
studies and our analysis as well.
The earlier attempt to provide an analysis for R-tree-based structures appeared in [FSR87]. Faloutsos et
al. proposed a model that estimates the performance of R-trees and R + -trees for selection queries,
assuming, however, uniform distribution of data and packed trees (i.e., all the nodes of the tree are full of
data). The formulae for the height 1
R
h of an R-tree R 1 as a function of its cardinality N R 1
and fanout f
(Eq. 5) and the average size k
l
R
s ,,
of a parent node as a function of the average size k
l
R
s ,
,of the child
nodes and the average distance t l,k between two consecutive child nodes' projections (Eq. were
originally proposed in [FSR87].
Later, Kamel and Faloutsos [KF93] and Pagel et al. [PSTW93] independently presented a formula
(actually a variation of Eq. 2) that calculates the average number of page accesses in an R-tree index R 1
accessed by a query window q as a function of the average node sizes k
l
R
s ,
,and the query window size q k .
That formula assumes that the R-tree has been built and that the MBR of each node of the R-tree R 1 can be
measured. In other words, the proposed formula is qualitative, i.e., it does not really predict the average
number of disk accesses but, intuitively, presents the effect of three parameters, namely area, perimeter,
and number of objects, on the R-tree performance. In those papers, the influence of the node perimeters
was revealed, thus helping one to understand the efficiency of the R*-tree, which was the first R-tree
variant to take the node perimeter into consideration during the index construction procedure [PSTW93].
Faloutsos and Kamel [FK94] extended the previous formula to actually predict the number of disk
accesses using a property of the data set, called the fractal dimension. The fractal dimension fd of a data
set (consisting of points) can be mathematically computed and constitutes a simple way to describe non-uniform
data sets, using just a single number. The estimation of the number of disk accesses DA(R 1 , q, 1)
at level 1 (i.e., the leaf level) according to the model proposed in [FK94] (f is the average capacity - fanout
- of the R-tree nodes) is given by:
d
R q
s
f
R
DA,,
where
fd
R N
f
The formula constitutes the first attempt to model R-tree performance for non-uniform distributions of
data (including the uniform distribution as a special case: fd = d) superseding the analysis in [FSR87] that
assumed uniformity. However the model is applicable to point data sets only, which are not the majority in
real spatial applications.
Extending the work of [PSTW93], Pagel et al. [PSW95] proposed an optimal algorithm that establishes
a lower bound result for static R-tree performance. They have also shown by experimental results that the
best known static and dynamic R-tree variants, the packed R-tree [KF93] and the R*-tree respectively,
perform about 10%-20% worse than the lower bound. The impact of the three parameters (area,
perimeter, and number of objects) was further discussed in [PS96], where performance formulae for
various kinds of range queries, such as intersection, containment, and enclosure queries, were derived.
Since previous work used the number of nodes visited (NA is our analysis) as a metric of query
performance, the effect of an underlying buffering mechanism has been neglected, although it is a real cost
parameter in query optimization. Towards this direction, Leutenegger and Lopez [LL98] modified the cost
formula of [KF93] introducing the size of an LRU buffer. Comparison results on three different R-tree
algorithms [Gut84, RL85, KF93] showed that the analytical estimations were very close to the
experimental cost measures. A discussion on the appropriate number of R-tree levels to be pinned argued
that pinning may mostly benefit point queries, and even then only under special conditions.
Apart from cost estimation proposals for selection queries, Gunther's proposal [Gun93] was the earliest
attempt to provide an analytical model for estimating the cost of spatial joins. Abstractions of tree indexes,
called "generalization trees", were modeled on the support of q-joins. Implementation algorithms for
general q-joins were presented and evaluated for various probability distributions.
Later, Aref and Samet [AS94] proposed analytical formulae for the execution cost and the selectivity
of spatial joins, based on the R-tree analysis of [KF93]. The basic idea of that work was the consideration
of the one data set as the underlying database and the other data set as a source for query windows in order
to estimate the cost of a spatial join query based on the cost of range queries. Experimental results
showing the accuracy of the selectivity estimation formula were presented in that paper.
Huang et al. [HJR97] recently proposed a cost model for spatial joins using R-trees. Independently to
[TSS98], it is the first attempt to provide an efficient formula for join performance by distinguishing two
cases: considering zero- and non-zero buffer management. Using the analysis of [KF93, PSTW93] as a
starting point, it provides two formulae, one for each of the above cases. The efficiency of the proposed
was shown by comparing analytical estimations with experimental results for varying buffer size
(with the relative error being around 10%-20%). However, contrary to [TSS98], the model proposed in
assumes knowledge of R-tree properties like [KF93, PSTW93] do.
Compared to related work, our model provides robust analytical formulae for selection and join cost
estimation using R-trees,
(i) do not need knowledge of the underlying R-tree structure(s), since they are only based on primitive
data properties (cardinality N and density D of the data set) , and
(ii) are shown to be accurate by performing a wide set of experimental results on both uniform-like and
non-uniform data sets consisting of either point or non-point objects.
6. CONCLUSION
Selection and join queries are the fundamental operations supported by a DBMS. In the spatial database
literature, there exist several access methods for the efficient implementation of both operations mainly
using the R-tree spatial data structure. However, for query optimization purposes, efficient cost models
should be also available in order to make accurate cost estimations under various data distributions
(uniform and non-uniform ones).
In this paper, we presented a model that predicts the performance of R-tree-based structures for
selection (point or range) queries and extended this model to support join queries. The proposed cost
are functions of data properties only, namely, their number N and density D in the workspace,
and, therefore, can be used without any knowledge of the R-tree index properties. They are applicable to
point or non-point data sets and, although they make use of the uniformity assumption, they are also
adaptive to non-uniform (e.g. skewed) distributions, which usually appear in real applications.
Experimental results on synthetic and real [Bur91] data sets showed that the proposed analytical model
is very accurate, with the relative error being usually around 10%-15% when the analytical estimate is
compared to cost measures using the R*-tree, one of the most efficient R-tree variants. In addition, for join
query processing, a path buffer was considered and the analytical formula was adapted to support it. The
performance saving due to the existence of such a buffering mechanism was highly affected by the sizes
(and height) of the underlying indexes and reached up to 50% for two-dimensional data sets. The proposed
formulae and guidelines could be useful tools for spatial query processing and optimization purposes,
especially when complex spatial queries are involved.
In this work we focused on the overlap operator. Any spatial operator could be used instead. For
instance, a topological operator (e.g. meet, covers, contains, etc.) defined by Egenhofer and Fransoza in
[EF91], any of the 13 n possible directional operators between two n-dimensional objects [All83,
PT97], or a distance operator (close, far, etc.) perhaps involving fuzzy information. We have already
adapted the model for selection queries in order to estimate the cost of (a) direction relations between
spatial objects in GIS applications [TPSS98] and (b) spatiotemporal relations between objects in large
Multimedia applications [TVS96], by handling such relations as range queries with an appropriate
transformation of the query window q. We are currently working on appropriate modifications in order to
support join queries as well.
A second issue that arises is whether the overlap operator is representative for the accuracy of a cost
model. Recent research [PS96] has shown that range (window) queries can be widely regarded as
representative for other (e.g., enclosure or containment) queries for a wide range of region sizes. By
considering that work on range queries as a background we could also study the case of join queries and a
wide set of spatial operators.



--R

"Maintaining Knowledge about Temporal Intervals"
"A Cost Model for Query Optimization Using R-Trees"
"Efficient Processing of Spatial Joins Using R-trees"
"The R * -tree: an efficient and robust access method for points and rectangles"
"Multi-Step Processing of Spatial Joins"
Bureau of the Census
"A Relational Model of Data for Large Shared Data Banks"
"The Ubiquitous B-Tree"
"Point Set Topological Relations"
Searching Multimedia Databases by Content
"Recovering Information from Summary Data"
"Beyond Uniformity and Independence: Analysis of R-trees Using the Concept of Fractal Dimension"
"The BANG file: a new kind of grid file"
"Analysis of Object Oriented Spatial Access Methods"
"Multidimensional Access Methods"
"Efficient Computations of Spatial Joins"
"R-trees: a dynamic index structure for spatial searching"
"An Introduction to Spatial Database Systems"
"A Cost Model for Estimating the Performance of Spatial Joins Using R-trees"
"The LSD tree: spatial access to multidimensional point and non point objects"
"On Packing R-trees"
Modern Database Systems: The Object Model
The Art of Computer Programming
"The Effect of Buffering on the Performance of R-Trees"
"Redundancy in Spatial Databases"
Computational Geometry
"Are Window Queries Representative for Arbitrary Range Queries?"
"Towards an Analysis of Range Query Performance"
"Window Query-Optimal Clustering of Spatial Objects"
"Spatial Relations, Minimum Bounding Rectangles, and Spatial Data Structures"
"Cubetree: Organization of and Bulk Updates on the Data Cube"
"Direct Spatial Search on Pictorial Databases Using Packed R-trees"
The Design and Analysis of Spatial Data Structures
The Next Wave
-tree: a dynamic index for multidimensional objects"
"Direction Relations and Two-Dimensional Range Queries: Optimisation Techniques"
"A Model for the Prediction of R-tree Performance"
"Cost Models for Join Queries in Spatial Databases"
"Spatio-Temporal Indexing for Large Multimedia Applications"
"Faster Methods for Random Sampling"
"Random Sampling with Reservoir"
--TR

--CTR
Orlando Karam , Fred Petry, Optimizing distributed spatial joins using R-Trees, Proceedings of the 43rd annual southeast regional conference, March 18-20, 2005, Kennesaw, Georgia
Yufei Tao , Dimitris Papadias, Adaptive index structures, Proceedings of the 28th international conference on Very Large Data Bases, p.418-429, August 20-23, 2002, Hong Kong, China
Yinghua Zhou , Xing Xie , Chuang Wang , Yuchang Gong , Wei-Ying Ma, Hybrid index structures for location-based web search, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany
Jun Zhang , Manli Zhu , Dimitris Papadias , Yufei Tao , Dik Lun Lee, Location-based spatial queries, Proceedings of the ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
Ji-Dong Chen , Xiao-Feng Meng, Indexing future trajectories of moving objects in a constrained network, Journal of Computer Science and Technology, v.22 n.2, p.245-251, March 2007
Bugra Gedik , Kun-Lung Wu , Philip Yu , Ling Liu, Motion adaptive indexing for moving continual queries over moving objects, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
Yufei Tao , Dimitris Papadias , Jimeng Sun, The TPR*-tree: an optimized spatio-temporal access method for predictive queries, Proceedings of the 29th international conference on Very large data bases, p.790-801, September 09-12, 2003, Berlin, Germany
Yong-Jin Choi , Jun-Ki Min , Chin-Wan Chung, A cost model for spatio-temporal queries using the TPR-tree, Journal of Systems and Software, v.73 n.1, p.101-112, September 2004
Yufei Tao , Dimitris Papadias , Qiongmao Shen, Continuous nearest neighbor search, Proceedings of the 28th international conference on Very Large Data Bases, p.287-298, August 20-23, 2002, Hong Kong, China
Xuan Liu , Shashi Shekhar , Sanjay Chawla, Object-Based Directional Query Processing in Spatial Databases, IEEE Transactions on Knowledge and Data Engineering, v.15 n.2, p.295-304, February
Dimitris Papadias , Yufei Tao , Greg Fu , Bernhard Seeger, An optimal and progressive algorithm for skyline queries, Proceedings of the ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
Jianting Zhang , Le Gruenwald, Efficient placement of geographical data over broadcast channel for spatial range query under quadratic cost model, Proceedings of the 3rd ACM international workshop on Data engineering for wireless and mobile access, September 19-19, 2003, San Diego, CA, USA
Bugra Gedik , Aameek Singh , Ling Liu, Energy efficient exact kNN search in wireless broadcast environments, Proceedings of the 12th annual ACM international workshop on Geographic information systems, November 12-13, 2004, Washington DC, USA
Renato Bueno , Agma J. M. Traina , Caetano Traina, Jr., Genetic algorithms for approximate similarity queries, Data & Knowledge Engineering, v.62 n.3, p.459-482, September, 2007
Yufei Tao , Dimitris Papadias, Spatial queries in dynamic environments, ACM Transactions on Database Systems (TODS), v.28 n.2, p.101-139, June
Abhinandan Das , Johannes Gehrke , Mirek Riedewald, Approximation techniques for spatial data, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
Yufei Tao , Dimitris Papadias , Jun Zhang, Cost models for overlapping and multiversion structures, ACM Transactions on Database Systems (TODS), v.27 n.3, p.299-342, September 2002
Dimitris Papadias , Yufei Tao , Greg Fu , Bernhard Seeger, Progressive skyline computation in database systems, ACM Transactions on Database Systems (TODS), v.30 n.1, p.41-82, March 2005
Antonio Corral , Yannis Manolopoulos , Yannis Theodoridis , Michael Vassilakopoulos, Cost models for distance joins queries using R-trees, Data & Knowledge Engineering, v.57 n.1, p.1-36, April 2006
Yufei Tao , Christos Faloutsos , Dimitris Papadias, The power-method: a comprehensive estimation technique for multi-dimensional queries, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA
Dimitris Papadias , Yufei Tao , Kyriakos Mouratidis , Chun Kit Hui, Aggregate nearest neighbor queries in spatial databases, ACM Transactions on Database Systems (TODS), v.30 n.2, p.529-576, June 2005
Yufei Tao , Dimitris Papadias, Historical spatio-temporal aggregation, ACM Transactions on Information Systems (TOIS), v.23 n.1, p.61-102, January 2005
Yufei Tao , Jimeng Sun , Dimitris Papadias, Analysis of predictive spatio-temporal queries, ACM Transactions on Database Systems (TODS), v.28 n.4, p.295-336, December
Hanan Samet, Decoupling partitioning and grouping: Overcoming shortcomings of spatial indexing with bucketing, ACM Transactions on Database Systems (TODS), v.29 n.4, December 2004
Hanan Samet, Object-based and image-based object representations, ACM Computing Surveys (CSUR), v.36 n.2, p.159-217, June 2004
query optimization;spatial databases;access methods;r-trees;cost models