Transcript Handout
Hierarchical Constraint Satisfaction
in Spatial Database
Dimitris Papadias, Panos Kalnis And Nikos
Mamoulis
Purpose of the Paper
• Show how systematic and local search make
use of hierarchical decomposition of space.
• To efficiently guide search.
• Show conditions when hierarchical constraint
satisfaction outperforms traditional methods
Hierarchical Constraint Satisfaction
• Helps solves queries in spatial database and
geographical information systems.
• For e.x. a user is searching for a residential
area that covers a commercial center and the
commercial center meets a park.
Introduction
•
•
•
•
Content based queries can be modeled as CSP.
All objects in query variables.
relation between variables constraints.
The domain of the variables consists of objects
in the database.
• For e.x. find residential areas(v1) that cover
commercial centers(v2) that meets a park(v3).
Topological Relations
x1
x2
Disjoint(x1, x2)
x1
x2
Equal(x1, x2)
x1
x2
Meet(x1, x2)
x1 x2
Contain(x1, x2)
x2
x1
x1 x2
Overlap(x1, x2)
Cover( x1, x2)
x2 x1
x2 x1
Covered-by(x1, x2)
Inside(x1, x2)
R-trees are used by CSP algorithms to accelerate
search.
Minimum Bounding Rectangles(MBR) are actual
area objects on the map the R-tree is built by
grouping rectangles at the lower level.
R-tree
• Are an extension of B+-trees to many dimensions.
• B+-trees is a balanced search tree which maintains
an ordered set of data and in which the keys are
stored in a the leaves
• Is a height Balanced Tree that consists of
intermediate and leaf nodes corresponding to disk
in secondary memory.
• If h is the height of the tree the root is at level h-1
and the leaf is at the level 0.
• The intermediate levels are built by grouping
rectangles at lower level.
• There is a R-tree for each type of object.
R-tree
R-tree
• Used for window queries.
• Two Steps are involved.
• Filter Step – retrieve a set of candidates that
includes all the results and some false hits.
• Refinement Step – each candidate is examined
and false hits are eliminated.
• The method can be extended for topological
relations.
R-tree
R-trees Join (RTJ)
• The most influential algorithm for processing
intersection joins using R-trees.
• Based on enclosure property.
• Like window queries, in order to process arbitrary
topological relations using RTJ we need to define
conditions for intermediate nodes.
• The problem is viewed as a multi-way spatial join
and processed by computing the result of one
pair-wise join and joining the result with v3.
Hierarchical CSPs using R-trees
• A set of variables v1,v2,v3…vn.
• Domain di for variable vi is
for level 0 : {xi,1,…… xi,ci}
for level 1 to h-1:{Xi,1,…… Xi,ci}
• For each pair of variables the binary constraint is
for level 0 : Cij is a disjunction of topological
relations as specified by the query.
for level 1 to h-1: Cij is derived by replacing each
relation in Cij by the corresponding condition for
intermediate nodes in Table 2.
Table 2
Hierarchical CSPs using R-trees
• Two preprocessing heuristic
– Space Restriction.
– Path Consistency
• Space Restriction – scans the domains of all
variables, removing the entries that cannot
satisfy the query constraints given their
positions w.r.t. to other nodes.
• Path Consistency – is a form of semantic query
optimization to discard inconsistent queries.
Hierarchical CSPs using R-trees
• Using systematic and local search algorithms
there are three cases :
– Hierarchical systematic search.
– Hierarchical local search.
– Hierarchical local/systematic search.
Experiments
• Problems were randomly generated by
modifying the paramters n,m,p1, p2.
• n = number of variables.
• m = size of datasets
• p1 = is the probability that a random pair of
variables is constrained (network density).
• p2 = is the probability that assignment for a
constrained pair is inconsistent (tightness).
•
•
•
•
•
•
Typical values takes for the problem
m = 104
|x| = .0045
d .2( typical value for real datasets)
h=3
C=50-200
Using these values problems were randomly
generated.
Hierarchical Systematic Search
• Using Forward Checking with fail first
dynamic variable ordering heuristic.
• 50 randomly generated problems.
• P1 = 1.
• n=5.
• m=104
• D 0.2
Hierarchical Systematic Search
• Two searches were used
– Forward Checking (FC)
– Hierarchical FC (H-FC)
• Three types of problems were tested
– Varying P2 without disjoint
– Varying P2 with disjoint
– Varying n with one solution
Hierarchical Systematic Search
Results
• Varying P2 without disjoint
– H-FC outperforms FC by two orders of
magnitude.
• Varying P2 with disjoint
– For dense graphs the H-FC outperforms FC by two
orders of magnitude.
– As tightness decreases the performance converges.
Hierarchical Systematic Search
Results
• Varying n with one solution
– The performances converges as the number of
variables increases.
– For n>25 FC outperforms H-FC.
Hierarchical Local Search
• Local search used is Hill Climbing with minconflicts(MC) heuristic.
• Following Variations used
–
–
–
–
–
Flat MC
Hierarchical uninformed MC (HU-MC)
Hierarchical informed MC (HI-MC)
Hierarchical root MC (HR-MC)
Hierarchical root MC/FC (HR-MC/FC)
Hierarchical Local Search
• Problems created with the parameters
– n=5
– m=103, 104, 105.
• All algorithms were executed 10 times for
every setting.
• Their execution was terminated is solution
could not be obtained after 109 checks.
Hierarchical Local Search
Results
• HR-MC outperforms HU-MC by at least one
order of magnitude.
• HI-MC’s performance is between HR-MC and
HU-MC.
• When m= 103 MC is better than hierarchical
local search
• When m= 105 HR-MC outperforms MC by one
order of magnitude.
Hierarchical Local Search
Results
• Due to large number of sultions at the upper
level hierarchical local search succeeds fast but
spends more time trying to find a soultion at
the leaf level this motivated the replacement of
MC at leaf level with FC
• For larger domains HR-MC/FC outperforms
HR-MC by almost an order of magnitude.
Conclusion
• Provides a methodology for hierarchical
constraint satisfaction in spatial database using
R-trees.
• Systematic search is significantly faster in the
case of hierarchical CSPs for m 104 and n10
• Hierarchical local search is better for very
large domains.
• Provides hints to improve performance.