DEIM Forum 2013 A9-3

ガウス分布に対する確率的範囲問合せのための索引手法の評価
董テイテイ†

郭

茜††

肖

川†

石川 佳治†† 名古屋大学情報科学研究科†† 香港中文大学システム工学及び工学管理学科
E-mail: †dongtt@db.itc.nagoya-u.ac.jp, ††guoxi022@gmail.com, †††{chuanx,y-ishikawa}@nagoya-u.ac.jp

Evaluating an Index Method for Probabilistic Range Queries
on Gaussian Distributions
Tingting DONG† , Xi GUO†† , Chuan XIAO† , and Yoshiharu ISHIKAWA†† Graduate School of Information Science, Nagoya University†† Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong
E-mail: †dongtt@db.itc.nagoya-u.ac.jp, ††guoxi022@gmail.com, †††{chuanx,y-ishikawa}@nagoya-u.ac.jp
Abstract Recently uncertain data is attracting more and more attention in many fields and has become a major
topic in the database research community. In this paper, we develop and evaluate our preliminary work, an index
method for probabilistic range queries on Gaussian distributions. This method assumes that uncertain data items
stored in the database are represented by multi-dimensional Gaussian distributions (Normal distributions), while
the query object can be a point or a Gaussian distribution. We propose an index structure and several filtering
techniques to support probabilistic range queries. In this work, we conduct experiments using both synthetic data
and real data and examine the eﬃciency and eﬀectiveness of this index method.
Key words uncertain data, probabilistic databases, range queries, spatial databases

1. Introduction

robot moving in an environment as shown in Fig. 1. The
robot builds a map of the environment by observing nearby

In recent years, uncertain data is gaining more and more

landmarks using devices such as sonars and laser range find-attention in the database community and has involved aers. Due to the inherent limitation of measurement accuracy

large variety of real-world applications, ranging from mo-and unavoidable signal noises, the information acquired frombile robotics and sensor networks to location-based service.

measuring devices (e.g., the location of a landmark) is always

Uncertainty can be inherent properties of the data caused by

not precisely correct. At the same time, the moving robot

measurement limitations and noises (e.g., Gaussian errors inalso conducts probabilistic localization [18] to estimate its

GPS readings), or may be introduced to preserve the privacy

location autonomously by integrating its movement historyof the source data.

and the landmark information. This can result in imprecise-

For instance, in the area of location-based mobile advertis-

ness in the location information of the robot, too.

ing, operators typically provide services such as the delivery

During the movement, the robot may request informationof mobile coupons or discounts to nearby mobile users using

about nearby landmarks and issue a query such as “find land-

their location information (e.g., The Coupons App). The

marks within 5 meters from my current location”. In the tra-exact current location of users may not be available due toditional spatial database setting, this kind of query can be

privacy preservation or delayed updates from users. In thiseasily answered by performing a range query with the range

case, a query like “find customers currently in the downtown

specified as 5 meters. Nevertheless, it is diﬃcult to processarea” cannot be fully evaluated and answered.

this query exactly in this situation, because locations of both

As another example, consider a self-navigated mobile

the query object (i.e., the robot) and the target objects (i.e.,nearby landmarks) are inexact. And if the obtained imprecise data is directly used to answer queries, it may result inerroneous answers and navigation failures.

2. 2 Spatial Data Indexing
The traditional spatial database has been well studied andmany indexing methods have been proposed [1], [8], [12] tosupport spatial query processing. The well-known one is Rtree [8] and its extension R*-tree [1], which index objects byderiving their minimum bounding rectangle (MBR). TPRtree [20] and TPR*-tree [17] are proposed to index moving
objects. But none of them can be applied directly to index
Gaussian objects directly for our problem.
2. 3 Uncertain Data Indexing

図 1 A motivating example

In terms of probabilistic range queries in a multi-

To remedy this kind of problem, the data records are typ-dimensional space, Tao et al. propose U-tree [16]. It is dif-

ically represented by probability density functions instead offerent from our tree here in that our tree indexes Gaussian

deterministic values. Typically, uncertain data is modeled

distribution in the infinite space. As an index structure forby multi-dimensional Gaussian distributions [7]. The Gaus-

Gaussian distributions, Gauss-tree is proposed for probabilis-

sian distribution, also called the normal distribution, is a

tic identification query in [2]. What is problematic with theprobability distribution widely used in various fields such

Gauss-tree lies in that it constructs its index structure basedas pattern recognition, statistical analysis, etc.. We discusson the assumption that all Gaussian distributions are prob-

the problem based on the assumption that the uncertainties

abilistically independent in each dimension. In other words,of target objects’ location information in the database areeach distribution axis of a Gaussian function should be par-described by multi-dimensional Gaussian distributions withallel to a dimension axis. This imposes heavy restriction on

diﬀerent parameters for indicating their diﬀerences in uncer-

the generality of the approach and the overall accuracy oftainty. We consider two cases for a query object: a certain

the query result is limited.

point and an uncertain location represented by a Gaussian
distribution.

In our preliminary work [10], we propose several query processing techniques for probabilistic range queries, assuming

Furthermore, queries here search for target objects withinthat the location of the query object is only uncertain andsome specified range (i.e. the radius) from the query objects

described by a Gaussian distribution, and target objects inwith high probabilities. Such a query is called a probabilis-

the database are multi-dimensional points and are managed

tic range query (PRQ), an extension of the standard range

by a conventional spatial index such as an R-tree. Moreover,query in the traditional spatial database. In the case of thein our precedent work [11] of this research, we also present anforgoing scenarios, an example query can be “find customers

index method for Gaussian distributions. The approach pro-currently located 50 meters around the shopping center with aposed in [11] is consistent theoretically, but not easy to im-probability more than 40%” or “find landmarks lying within

plement practically and is greatly aﬀected by computational

5 meters from my current location with a probability at least

errors. In this paper, we present stronger query processing80%”. This kind of queries can provide more meaningfultechniques and a novel index structure to solve the problem.

answers to users.

2. Related Work

3. Problem Definition
Uncertain target objects here are assumed to follow multi-

2. 1 Uncertain Data Management

dimensional Gaussian distributions with diﬀerent parame-

A number of approaches for managing uncertain data haveters. A probabilistic range query (PRQ) is to retrieve objects

been proposed. Early research primarily focuses on queries

among them located within some specific range from thein a moving object database model [5], [13], [19], [21]. Cheng

query object (a certain point or an uncertain object repre-

et al. classify several types of probabilistic queries including

sented by a Gaussian distribution) with probabilities greater

probabilistic range queries based upon uncertain data andpresent algorithms for solving them in [4]. In another study,

than a probability threshold. We define the problem in ad (d >= 2)-dimensional space. The one-dimensional case will

Cheng et al. develop several solutions for probabilistic range

not be discussed here since it is exceptional and can be solved

queries [6]. However, they target the one-dimensional space

easily.

only. Moreover, a range query processing method for thecase where both target objects and a query object are im-

3. 1 Gaussian Distributions
Definition 1 (Gaussian objects). The probability that an ob-

precise is proposed in [3]. But they assume that each object

ject oi ∈ D is located at xi is defined by a d-dimensional Gaus-

exists within a rectangular area.

sian probability density function

pi (xi ) =1d2(2π) |Σi |

1
2

[
]
1
exp − (xi − oi )t Σ−1i (xi − oi )2(1)and cannot be computed directly. To evaluate the probability, numerical integration (the Monte Carlo method) is
employed actually. To be specific, the eﬃcient importance

where D is a set of target objects, oi is the mean of oi and Σi
is a d × d covariance matrix. |Σi | is the determinant of Σi andsampling [14] approach can be used: generate xi with a probability pi (xi ), and increment the count when Eq. (3) is sat-

Σ−1is the inverse matrix of Σi . xt represents a transpositioniisfied. Finally, we can get the integrated probability through2

dividing the count by the number of samples (e.g., 100000)

of a vector x.

generated. However, the Monte Carlo integration has an ex-

3. 2 Definition of Queries

tremely high cost even though using the importance sampling

In this paper, we consider two types of query objects:

approach. For this reason, we propose an eﬀective approach（ 1 ） The query object is a fixed point, namely,

to reduce the number of candidate objects.

q = (x1q , x2q , . . , xdq )t .
（ 2 ） The query object follows a d-dimensional Gaussian dis-tribution, namely,
]
[
1
1
t −1
(x
−
q)
(x
−
q)
Σ
pq (xq ) =
exp
−
q
q
q
d
1
2
(2π) 2 |Σq | 2
where q is the mean, and Σq is a d × d covariancematrix.
3. 2. 1 Probabilistic Range Query with Point Query Object (PRQ-P)
Definition 2 (PRQ-P). Given a query object q represented by

3. 2. 2 Probabilistic Range Query with Gaussian Query
Object (PRQ-G)
Definition 3 (PRQ-G). Given a query object q represented
by a Gaussian distribution, a distance threshold δ, and a probability threshold θ (0 < θ < 1), a probabilistic range querywith Gaussian query object (PRQ-G) is defined as follows:
PRQ-G(q, δ, θ) = {oi | oi ∈ D, Pr(∥xi − xq ∥ <= δ) >= θ},
where Pr(∥xi − xq ∥ <δ is defined as follows:=∫∫Pr(∥xi − xq ∥ <δ)=χδ (xi , xq ) · pi (xi ) · pq (xq )dxi dxq={

a vector q, a distance threshold δ, and a probability thresholdθ (0 < θ < 1), a probabilistic range query with point querywhereχδ (xi , xq ) =object (PRQ-P for short) is defined as follows:

if ∥xi − xq ∥ <=δ0otherwise

is a thresholding function.
2
To compute the numerical integration in Eq. (4), although

PRQ-P(q, δ, θ) = {oi | oi ∈ D, Pr(∥xi − q∥ <= δ) >= θ}
where ∥xi − q∥ represents the Euclidean distance between xi
and q.
Pr(∥xi − q∥ <= δ) is defined∫ as follows:<Pr(∥xi − q∥ = δ) = χδ (xi , q) · pi (xi )dxi
(2){
1 if ∥xi − q∥ <=δwhere
χδ (xi , q) =(3)0 otherwise
is used to enforce the distance-based threshold.

(4)
1

2

we can simply generate random numbers for the two Gaussian distributions pi (xi ) and pq (xq ) respectively, a more eﬃcient method for handling this kind of numerical integrationis shown in [11]. It constructs a 2d-dimensional Gaussian
distribution by combining two d-dimensional Gaussian distributions together.

4. Filtering Based on Approximated Regions
Evaluating the two types of queries defined in Eq. (2) andEq. (4) requires “expensive” numerical integration. To reduce query processing cost, it is essential to reduce the number of candidate Gaussian objects which need numerical integration. In this section, we propose several filtering techniques based on a probability region (called ρ-Region) and
its approximation (called bounding box ) of a Gaussian distri-

図 2 An illustration of PRQ-P queryFig. 2 shows an illustration of a PRQ-P query. The Gaus-

bution to prune as many non-candidate objects as possible.
4. 1 ρ-Region

sian object oi exists in the space with a decreasing proba-

Definition 4 (ρ-region). Consider the integration of thebility as spreading away from the center oi , i.e., the mean.

probability density function pi (xi ) over an ellipsoidal region< 2(xi − oi )t Σ−1i (xi − oi ) = r . Let rρ be the value of r for which

The changing colors describe this diminishing trend of theprobability. A PRQ-P query attempts to find Gaussian ob-

the result of∫ the integration exactly becomes ρ:jects located near the query point with a high probability.
Computing the probability using Eq. (2) corresponds to integrating the probability density function of oi within theslash area around q.
However, the integration in Eq. (2) is not in a closed-form−1(xi −oi )t Σi2(xi −oi )<= rρ

pi (xi )dxi = ρ.

We call the ellipsoidal region< 2(xi − oi )t Σ−1i (xi − oi ) = rρdefined by rρ the ρ-region.

2

Nevertheless, it is costly to compute ρ-regions for arbitrary Gaussian distributions (with diﬀerent oi , Σi ) directly.
To cope with this problem, an approach that transforms theintegration over an ellipsoidal region to an integration overa d-dimensional sphere region is proposed in [10]. To begin
with, let us introduce the normalized Gaussian distribution
図 4 Image of Bounding Box bbi

defined by assigning oi = 0 and Σi = I in Eq. (1).
[
]
1
1
2
pnorm (x) = N (0, I) =
exp
−
∥x∥
2
(2π)d/2

4. 3 Filtering for PRQ-P Queries

Based on this probability density function, we can derive
the following property.
Property 1. Consider integration of pnorm (x) over the re2gion ∥x∥2 <= r , which is a sphere with the origin as its center

4. 3. 1 Strategy 1: RR Method
Here we detail the idea of bounding box-based filtering
techniques for the PRQ-P query. The first filtering processing approach is an extension of the rectlinear-region-based

and the radius r. For the given ρ (0 < ρ < 1), let r̃ρ be theapproach (RR) proposed in our paper [10], except that in [10]radius with which the integration result becomes ρ:∫pnorm (x)dx = ρ.
2
∥x∥2 <=r̃ρ

the target objects are certain points and the query object is(5)

For a given ρ,(6)rρ = r̃ρa Gaussian distribution.
Case 1: θ < 0.5.

holds.
The proof is shown in [10]. The property indicates that if
the rρ (= r̃ρ ) value is calculated for a given ρ value using
Eq. (5), we can use it for our context using the equality in
Eq. (6).
dρrρ

図 5 RR Method (ρ = 1 − 2θ, θ < 0.5)

2 0.98 2.75
.
.
.
..
..
..

Consider four kinds of target objects o1 , o2 , o3 , o4 as shownin Fig. 5. First, let’s consider o4 . Since the probability that

図 3 (ρ, rρ )-Tableo4 is located inside its ellipsoidal ρ-region is ρ, the probabil-That is, if a table like Fig. 3 is constructed beforehand

ity that o4 is located outside bb4 (ρ) region is definitely less(numerical integration is necessary), we can easily obtainthan 1 − ρ. Furthermore, given the line symmetry of a Gaus-

the corresponding rρ for the ρ value in this table and hence

sian distribution, the probability that o4 is located inside thederive the ρ-region. However, due to the ellipsoidal shape of

sphere region of q is at most (1 − ρ)/2. For example, supposethe ρ-region, it is not suitable to be used for filtering process-that ρ = 20%, then (1 − ρ)/2 = 40% is the upper-bounding. We will derive the bounding box which tightly bounds

probability. Hence, if (1 − ρ)/2 = θ; i.e.,the ρ-region.

ρ = 1 − 2θ

4. 2 Deriving Bounding Box
Definition 5 (Bounding Box). Given the parameter ρ (0 <is true, when bb4 (ρ) and the sphere are disjoint (that is, con-

ρ < 1), the rectangular region which tightly bounds the ρ-region

nected or separated), the probability that the target objectof Gaussian object oi is called the ρ-bounding box of oi , ando4 is within the δ range of query object q will be less than θ.

represented by bbi (ρ). For simplicity, we sometimes omit ρOn the contrary, if bb4 (ρ) and the sphere query region haveand call it bounding box directly and abbreviate it to bbi .

2intersection, this probability is possible to reach θ.

Fig. 4 shows the image of the bounding box bbi in j-th di-

For o1 and o3 , since their mean locations are inside themension and k-th dimension. Let the width of the box fromspherical query region, it is obvious that their bounding

the object center oi along the j-th dimension and k-th di-boxes will intersect with the query region. Therefore, we

mension be wj and wk respectively. The following property

can add them to the candidate list without deriving theirholds [10].

bounding boxes. On the other hand, we have to derive theProperty 2. The value of wj (j = 1, 2, . . . , d) is given as

bounding box bb2 (ρ) of o2 to check whether it intersects with

wj = σj rρ

(7)

the spherical region. If they have intersection, then o2 will
be selected as a candidate object.

where σj corresponds to the standard deviation for the j-thdimension√
σj = (Σi )jj
where (Σi )jj represents the (j, j) entry of Σi .

Moreover, for all candidate objects, we also derive theirbounding boxes of θ-regions by letting ρ = θ. If the queryregion contains the θ-valued bounding box as o3 , this object

4. 4 Filtering for PRQ-G Queries

is undoubtedly a query result. We will return this kind of

For PRQ-G queries, we obtain both of their bounding

target objects as result objects directly without ”expensive”

boxes of ρ-regions. As shown in Fig. 8, consider the situ-

numerical integration.
Case 2: θ >= 0.5. Let ρ = θ.

ation that the distance between the bounding boxes of two
ρ-region is exactly δ. Since q and oi are located inside theirρ-regions respectively both with probability ρ, the probability that each of them exists within individual ρ-region at thesame time is ρ2 , assuming that they are independent in thespace. In this case, obviously the distance between q and oi
is very likely to be larger than δ. Specifically, the distance
between q and oi becomes less than δ with a probability at
most 1 − ρ2 .

図 6 RR Method (ρ = θ, θ >= 0.5)

that a target object exists within the spherical query region

For a given probability threshold θ of the query, letting√
1 − θ, we can compute ρ. For ex√
ample, if θ = 5%, then ρ = 1 − 0.05 = 0.9747. Construct

to reach 0.5, the mean location of a target object should lo-

the bounding boxes of ρ-regions dynamically for q, oi withcate inside the query region. Otherwise, the probability isthe ρ value. And we can exclude oi from the candidate list

We show our idea in Fig. 6. For the integrated probability

1 − ρ2 = θ, that is, ρ =definitely less than 0.5. In this way, o2 and o4 can be pruned.

if the minimum distance between bbi (ρ) and bbq (ρ) is more

Similarly, o3 can be returned as a result object without nu-

than δ.

merical integration.
4. 3. 2 Strategy 2: OR Method
In [10], the oblique-region-based approach (OR) method is
proposed besides the RR method. This method can also be
extended for our query processing. The idea is shown in
Fig. 7.
図 8 Filtering for PRQ-G Queries

図 7 OR Method

Consider the rectangle paralleled to the axes of the ρregion ellipsoid. The distance between the rectangle and theρ-region is at least δ. Obviously when oi is located inside the

図 9 Filtering for PRQ-G Queries: validation

Moreover, if the maximum distance of bbi (ρ) and bbq (ρ) is√
θ) will guaranteeρ-region (with a probability ρ), the distance between oi andless than δ, assigning ρ2 = θ (i.e., ρ =q2 will be more than δ. If ρ = 90%, the probability that oithat the target object oi is located inside the δ range fromwill be located outside the rectangle is at most 10%. Further-

the query object q with a probability greater than θ. Hence,

more, given the line symmetry, the probability that oi exists

oi can be validated as a result object directly.

within δ range of q2 is no more than 5%. This means that
we can obtain the filtering condition by letting (1 − ρ)/2 = θ,i.e., ρ = 1 − 2θ. On the other hand, oi becomes a candidate
object for query q1 .
Since it is diﬃcult to determine the relation between aTo eﬃciently process queries over databases consisting
thousands of or millions of target objects, we propose a dynamic index structure which stores bounding boxes of all
objects instead of deriving their bounding boxes on-the-fly.
We will describe this index structure in the next section.

point and an oblique rectangular region, the oblique regionis transformed into an axis-parallel rectangle actually. The
transformation is implemented by deriving the correspond-

5. Index Structure
5. 1 Overall Index Structure

ing point y i for a given d-dimensional point xi which sat-

The overall index structure is a balanced hierarchical tree.

isfies xi = Ey i . Here E is a diagonal matrix consisting of

Entries in leaf nodes contain target Gaussian objects in thethe eigenvectors of Σ−1
i . The proof of this property is shownin [10]. In this work, the OR method is applied to further
refine candidate objects returned by the RR method.

form of oi = (idi , oi , Σi , bbi ), where idi is the object id, oi , Σi
are the mean value (average location) and the covariancematrix of the Gaussian distribution, and bbi is the bounding

If rρ is within the range (0, r1 ], the left bound of bound-box of ρ-region for oi . In a non-leaf node, an entry contains

ing box bb in j-th dimension is determined by the object o1 ,a pointer to a subtree and a bounding box that encloses thewhile the object o3 turns out to be the left bound object ofleaf bounding boxes or other internal bounding boxes in thatbb if rρ is in (r1 , +∞]. Also, when rρ increases over r2 , theright bound object of bb changes from o4 to o2 . In Fig. 11,

subtree.
As discussed in Section 4. 2, for an object oi centered at

the upper bold polyline illustrates the left side of the bound-⟨x1i , . . , xdi ⟩ in the d-dimensional space, the bounding box bbi

ing interval of the bounding box bb, while the lower boldof oi is a rectangle parameterized with rρ . Its extent (i.e.,polyline shows the right side of that. For this purpose, aleft bound and right bound) in j-th dimension can be repre-

bounding box is represented by several combined segments,

sented as

each of which has a diﬀerent left bound or right bound on

bbji = [xji − wij , xji + wij ] = [xji − σij rρ , xji + σij rρ ].

certain interval value of rρ , corresponding to the polyline in
Fig. 11.

We denote bbji as the bounding interval of the bounding box
bbi in the j-th dimension. Specifically, bbi is represented asa query probability range [θmin , θmax ]. Then rρ is actually

bbi = (⟨x1i , σi1 ⟩, . . , ⟨xdi , σid ⟩).

within a range [rmin , rmax ]. In this way, the overall index

In our implementation setting, we allow users to specify

structure can be more compact and more eﬃcient for query
In order to achieve best filtering performance, a leaf
bounding box should tightly enclose its child bounding boxes.
The challenge is that target objects always have diﬀerent covariance matrices, and their bounding boxes can scale up or
down in diﬀerent rates (i.e., diﬀerent standard deviations)processing. In j-th dimension, the left bound of a (both leaf
and non-leaf) node bounding box is in the form ofbbjl = (⟨xj1 , σ1j , [rmin , r1j ]⟩, . . , ⟨xji , σij , (rkj , rmax ]⟩)according to Eq. (7). So the left bound or right bound of the

Now we can obtain the corresponding j-th dimensionalbounding interval of the bounding box for objects o1 , o2 ,bounding box of a leaf node is determined by diﬀerent childo3 and o4 illustrated in Fig. 10 and Fig. 11, and derive thetarget objects in diﬀerent rρ values.

entry in j-th dimension bbj as
bbjl = (⟨xj1 , σ1j , [rmin , r1 ]⟩, ⟨xj3 , σ3j , (r1 , rmax ]⟩)bbjr = (⟨xj4 , σ4j , [rmin , r2 ]⟩, ⟨xj2 , σ2j , (r2 , rmax ]⟩)5. 2 Filtering at Non-Leaf Level
5. 2. 1 Processing PRQ-P Queries
Consider filtering on the non-leaf node for a PRQ-P query

図 10 Bounding boxes of o1 , o2 , o3 and o4

as shown in Fig. 12 (θ < 0.5). Assume that the sphere centered at q with the radius δ is exactly contiguous with bb(ρ).
As discussed in Section 4. 3, if ρ = 1 − 2θ, among objects o1 ,o2 and o3 inside bb(ρ), none of them can satisfy the query
condition. In other words, bb(ρ) can be removed from thesearching list if its distance from q is more than δ.

図 11 Bounding intervals of o1 , o2 , o3 and o4

図 12 Filtering for PRQ-P Queries on Non-Leaf Nodes

Fig. 10 illustrates this problem. This figure shows thechanging bound objects of the bounding box for four objects
o1 , o2 , o3 and o4 as rρ increases. Fig. 11 shows their corresponding bounding intervals in j-th dimension. For eachobject, the pairs of symmetrical lines in Fig. 11 describe theextension of the left and right bounds as rρ increases. Lines
have diﬀerent slopes because the standard deviations of o1 ,o2 , o3 and o4 in j-th dimension diﬀer from each other.

図 13 Filtering for PRQ-G Queries on Non-Leaf Nodes5. 2. 2 Processing PRQ-G Queries

integral computation occupies most of the runtime. This im-

Filtering on a non-leaf node for a PRQ-G query is veryplies that it is important to find eﬀective query processing

similar with that of a PRQ-P query. Fig. 13 illustrates the√idea. Let ρ = 1 − θ, if the distance between the nodetechniques and to avoid computing the exact probability bybounding box and the query bounding box is larger than δ,

candidate filtering is only about one to three milliseconds

this node can be deleted from the searching list of the query.

on average. And it does not show any sharp increase as thenumerical integration as much as possible. Time used fordataset size enlarges. This demonstrates the eﬃciency and6. Experiments

scalability of our approach. The similar trend can also be

We implemented the index structure by extending the spa-

observed in the case of PRQ-G queries.

tial index library SaiL [9]. This C++ library can be down-

Excluding the time part of integral computation, we show

loaded from [15] for free. We conducted experiments using

the time comparison of filtering processing and other opera-a PC with Intel Core 2 Duo CPU E8500 (3.16GHz), RAM

tions in Fig. 15. For a PRQ-P query, the time used for fil-

4GB and OS Fedora 12.

tering processing is no more than half of that used for otherWe generate 5 two-dimensional synthetic datasets in a1000 × 1000 space with size 10000, 30000, 50000, 80000, andoperations in all cases. This diﬀerence is greater and moreevident in a PRQ-G query.

100000, referred as 10K, 30K, 50K, 80K and 100K respec-

In the following experiments, we will use both the two real

tively. For the real data, we used road line segment data

datasets and the synthetic dataset 50K. While 50K is ran-of Long Beach, California and Montgomery, Maryland. We

domly generated and its data actually follows the uniform

extracted the midpoint of each line segment as the mean anddistribution, The data in MG and LB is bias-distributed,

generate the corresponding covariance matrix randomly. The

and many points are concentrated within an area. For thetwo extracted real datasets (called ”LB” and ”MG”) contain

convenience of performance comparison, we utilize the first39, 226 and 50, 747 items respectively and are normalized to

50K of LB (50, 747) and call it LB50K.

the 1000 × 1000 space.

6. 2 Range Trend

The query dataset is also generated randomly within the

The average result of 10 queries is used for performance

The query range is a random value

evaluation. The experimental result of PRQ-G queries by

within [5, 25] and the query probability threshold lies withinvarying δ is very similar to that of PRQ-P queries. So we[0.01, 0.99] for both PRQ-P and PRQ-G queries. We run 100

just take the result of PRQ-P queries for explanation. The

queries for each experimental setting and use the average re-average query processing time (including integral computa-

sult to evaluate the performance.

tion and filtering processing) of three datasets for PRQ-P
queries is shown in Fig. 16(a).

6. 1 Performance Analysis
Integration

0.002

10

11.7270.00179.53050.000945.331520.00070.98520.00278
10K

0

3.58
0.00251
30K

0.0077680K

0.002660
50
0.002240

80.31664.173830

0.001220

39.4383
23.86930.00058.06290.0078110K

00.00782
100K

MG(a) PRQ-P

0.0119330K

0.0201750K

0.0462380K

0.03573

10

20

50K

100

350

80
60
40

300
250
200
150
100

20
50
0

0
5

10

20

25

50

5

25

50

図 16 Range Trend: PRQ-P vs. δ
Other

Generally, as δ increases, more query processing time is

Filtering

0.05
0.0028

0.002

0.008
0.0017

0.006
0.004

0.007760.00070.00090.002780.00251

10K

30K

0.00782

0.00562

Response Time (s)0.01

Response Time (s)

LB50K

400

0.06

0.012

0.002

MG
450

(a) Average Query Processing Time (b) Average Candidate Number(b) PRQ-G

Filtering

50K

100K

図 14 Response Time
Other

LB50K

120

0.0029100.0056250K

Filtering70

0.00288
6Integration

80

Response Time (s)Response Time (s)OtherFiltering#Candidate

Other
12

Query Processing TIme (s)same data space.

needed. That’s because more and more target objects will0.00260.04

0.00290.00220.02

0.046230.035730.00120.01

0.00050.00781

50K

80K

100K

10K

cost. When δ reaches so large (20 in Fig. 16(a)) that many

0.02017potential candidates can be identified as result objects di-

0.0119300

become candidates, leading to more integral computation

0.03

30K

50K

80K

100K

rectly without integration. Then the query processing time(a) PRQ-P(b) PRQ-G

turns from a gradually rising trend into a steady state and

図 15 Response Time: filtering vs. othermay decrease slightly. This reveals the great power of our

The average response time of 100 random PRQ-P and

result-validation techniques. But if δ continues to increase,

PRQ-G queries is shown in Fig. 14. The overall runtime

the integral computation cost dominates over all factors and(i.e., wall clock time) consists of three components: inte-

the query processing time raises rapidly. An interesting thinggral computation, filtering processing, and the rest for otheris that the line chart in Fig 16(b) of candidate number almost

operations (e.g., reading data from files).Clearly in all cases

precisely matches that of query processing time in Fig 16(a).

This again demonstrates that probability integration dominates overall query processing cost.

8. Acknowledgements

Although the real dataset MG has less data items (about

This research was partly supported by KAKENHI

39K) than LB50K and 50K, it retrieves more data objects(23650047) and Funding Program for World-Leading Inno-and thus results in more query processing time, because its

vative R&D on Science and Technology (First Program).

data distribution is highly biased, and many data objects are
文

located around the central area.
6. 3 Probability Trend
We use 20 as a default query range in this subsection to
study the probability trend.

We run the same query 10

times and use the average result for performance evaluation.
Fig. 17 (Fig. 18) shows the query processing time (candidate
number) for PRQ-P and PRQ-G queries respectively.
MG

LB50K

MG

50K

Query Processing TIme (s)Query Processing Time (s)

LB50K

50K

120

50
40
30
20
10
0

100
80
60
40
20
0

0.05 0.15 0.25 0.35 0.45 0.55 0.65 0.75 0.85 0.95

0.05 0.15 0.25 0.35 0.45 0.55 0.65 0.75 0.85 0.95(a) PRQ-P(b) PRQ-G

図 17 Average Query Processing Time vs. θ
MG
MG

LB50K

LB50K

50K

50K

200

#Candidate#Candidate

250
200
180
160
140
120
100
80
60
40
20

150
100
50
0

0.05 0.15 0.25 0.35 0.45 0.55 0.65 0.75 0.85 0.95(a) PRQ-P

0.05 0.15 0.25 0.35 0.45 0.55 0.65 0.75 0.85 0.95(b) PRQ-G

図 18 Average Candidate Number vs. θ

For PRQ-P queries, the query processing time (candidate
number) decreases as the probability threshold θ increases
first, then the time (number) increases when θ >= 0.5. It
precisely matches the computing policy of parameter ρ as
discussed in Section 4. 3. This is because that ρ decides thesize of all bounding boxes. When ρ is large, bounding boxes
are very large, so they have weaker filtering power on objects. If ρ is small, bounding boxes are very small, and they
have strong power of filtering. PRQ-G queries work in thesimilar way with PRQ-P queries, except that their policy ofcomputing ρ is diﬀerent.

7. Conclusion and Future WorkIn this paper, by modeling uncertain data with multidimensional Gaussian distributions, we propose query processing techniques for two types of probabilistic range
queries: PRQ-P and PRQ-G. We further propose a novel index structure to support queries for Gaussian distributions.
We implement the index structure and examine its eﬃciency
and eﬀectiveness with experiments. In the future, we will extend its generality and enhance it to be applicable to othertypes of uncertainty models and queries.

献[1] N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger.
The R*-tree: an eﬃcient and robust access method for points
and rectangles. In Proc. ACM SIGMOD, 1990.
[2] C. Böhm, A. Pryakhin, and M. Schubert. The Gauss-tree:
Eﬃcient object identification in databases of probabilisticfeature vectors. In Proc. ICDE, 2006.
[3] J. Chen and R. Cheng. Eﬃcient evaluation of imprecise
location-dependent queries. In Proc. ICDE, 2007.
[4] R. Cheng, D. V. Kalashnikov, and S. Prabhakar. Evaluating probabilistic queries over imprecise data. In Proc. ACM
SIGMOD, 2003.
[5] R. Cheng, D. V. Kalashnikov, and S. Prabhakar. Querying
imprecise data in moving object environments. IEEE TKDE,
16(9):1112–1127, 2004.
[6] R. Cheng, Y. Xia, S. Prabhakar, R. Shah, and J. S. Vitter.
Eﬃcient indexing methods for probabilistic threshold queries
over uncertain data. In Proc. VLDB, 2004.
[7] R. O. Duda, P. E. Hart, and D. G. Stork. Pattern Classification. Wiley, 2nd edition, 2000.
[8] A. Guttman. R-trees: A dynamic index structure for spatial
searching. In Proc. ACM SIGMOD, pages 47–57, 1984.
[9] M. Hadjieleftheriou, E. Hoel, and V. J. Tsotras. Sail: A spatial index library for eﬃcient application integration. GeoInformatica, 9:367–389, 2005.
[10] Y. Ishikawa, Y. Iijima, and J. X. Yu. Processing spatial range
queries for objects with imprecise Gaussian-based location
information. In Proc. ICDE, pages 676–687, 2009.
[11] K. Kodama, T. Dong, and Y. Ishikawa. An index structure
for spatial range querying on Gaussian distributions. In Proc.
Fifth International Workshop on Management of Uncertain
Data (MUD 2011), pages 1–7, 2011.
[12] Y. Manolopoulos, A. Nanopoulos, A. N. Papadopoulos,
and Y. Theodoridis. R-Trees: Theory and Applications.
Springer, 2005.
[13] D. Pfoser and C. S. Jensen. Capturing the uncertainty ofmoving-object representations. In Proc. 6th Intl. Symp. on
Advances in Spatial Databases (SSD’99), 1999.
[14] W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P.
Flannery. Numerical Recipies: The Art of Scientific Computing. Cambridge University Press, 3rd edition, 2007.
[15] Spatial Index Library. http://libspatialindex.github.com/.
[16] Y. Tao, R. Cheng, X. Xiao, W. K. Ngai, B. Kao, and S. Prabhakar. Indexing multi-dimensional uncertain data with arbitrary probability density functions. In Proc. VLDB, 2005.
[17] Y. Tao, D. Papadias, and J. Sun. The TPR∗ -tree: An optimized spatio-temporal access method for predictive queries.
In Proc. VLDB, pages 790–801, 2003.
[18] S. Thrun, W. Burgard, and D. Fox. Probabilistic Robotics.
The MIT Press, 2005.
[19] G. Trajcevski, O. Wolfson, K. Hinrichs, and S. Chamberlain.
Managing uncertainty in moving objects databases. ACM
TODS, 29(3):463–507, 2004.
[20] S. Šaltenis, C. S. Jensen, S. T. Leutenegger, and M. A. Lopez.
Indexing the positions of continuously moving objects. In
Proc. ACM SIGMOD, pages 331–342, 2000.
[21] O. Wolfson, A. P. Sistla, S. Chamberlain, and Y. Yesha. Updating and querying databases that track mobile units. Distributed and Parallel Databases, 7(3):257–287, 1999.