Transcript kathyPham

Indexing the Past, Present, and
Anticipated Future Positions of
Moving Objects
Mindaugas Pelanis, Simonas Saltenis, and Christian S. Jensen
http://portal.acm.org/citation.cfm?id=1132863.1132870
Kathy Pham
CS 4440
August 31, 2007
Introduction: Me
• 5th Year Computer Science, graduating December!
• Loved CS 4400
• Wonder how the world operated before database systems
• Initial interest in databases: mySQL and PHP
• No background in database theory yet
• Christian S. Jensen: “But, as you may have discovered, this is
fairly complex stuff to present... Good luck with the presentation!”
Introduction: Article
• E-services to provide context-aware functionality to individual
users
• Feasibility of storing all position information online
• Efficient indexing techniques required
• Current techniques index past or current/future positions
• Proposed technique to capture position of moving objects at all
points in time by combining and extending past research.
Examples of users (from class):
o Insurance risk manager considering location risk profiles
o Doctor comparing Magnetic Resonance Images (MRIs)
o Emergency response determining quickest route to victim
o Mobile phone companies tracking phone usage
Position of moving objects
• Two objects in 1-D space.
• One index supports solid, other supports dashed.
• Problem: no existing method indexes time between most
recent sample and current time.
Related Work: Past Position
Ephemeral data structures do not record history of changes
(B+ and R-trees were briefly discussed in class)
• B+ trees: single dimensional indexes
• R-tree: better than B+ trees, balanced on insert and delete
N-dimensional extension of B+ trees.
• TB-tree
• STR-tree
• MV3R-tree: combined R-tree with partially persistent R-tree
can index past trajectory data
• SETI: two-level indexign that separates spatial and
temporal
Record of Movement: 1-D
xx
Linear prediction of
future movement
Recorded polyline
u
u
u
CT
2
3
4
Trajectory of 1-dimentional moving object
time
Christian S. Jensen
Related Work: Present and Future Position
Partially persistence data structures record history changes
• PMR-Quadtrees
• Time-Parameterized R-tree (TPR): Based of R*-tree,
index current/future, positions in 1-d, 2-d, 3-d
• REXP-tree: extends TPR-tree to accommodate data with expiration
times
• BBx-tree: past, present and future positions indexed,
but no trajectory segment corrections so
disconnected trajectories are indexed.
Indexing Past separately from the Present
Left: To bridge gap, updates stored in near-past structure.
Gap becomes arbitrarily large. Partially persistence index that
disregards present and future.
Right: Insertion times stored for all entries, no tightening possible,
both must be queried to get past queries (b/c of overlap)
New Ideas
• Apply partial persistence (supports transaction time) to TPR-tree
o For all time points the time-slice query performance should
be asymptotically the same as the time-slice performance
for the ephemeral structure.
o The amount of space used by partial persistence index must
be proportional in terms of the number of updates.
• Modify partial persistence to support valid time for monitoring
applications
• TPR-tree produced TPBR cannot be used in RPPF-tree
• New TPBR proposals
Types of TPBRs
• Straightforward TPBRs
The calculation of coordinates of bounding rectangles is modified:
the TPBR is computed to be minimum at its insertion time t├
• Optimized TPBRs
Minimizes the integral of the area of the bounding rectangle from
t├ to CT+H (where H is a workload-specific parameter.
Adjusted by observing the index workload)
• Double TPBRs
“Head” bounds the segments of the trajectories of objects from
t├ to the time of last update.
“Tail” starts at the time of last update, and it is the regular TPRtree TPBR.
Two types of double TPBRs:
– “heads” are optimized TPBRs
– “heads” are static (zero speed)
Straightforward TPBR
Time of last update
DELETE
INSERT
CT
TPBR in TPR-tree
INSERT
CT
TPBR in TPR-tree
The calculation of the coordinates of the bounding rectangles is modified: the
TPBR is computed to be minimum at its insertion time t├.
Straightforward TPBR
Time spilt
INSERT
CT
CT
Dead entry
Alive entry
Cons:
• These TPBRs may result in bounding rectangles that grow fast and are not
minimum at any point in time.
• Not possible to do ”tightening”.
• Bad bounding rectangles produced by the time split of bad alive bounding
rectangles.
Optimized TPBR
Time spilt
DELETE
INSERT
INSERT
CT
CT
Dead entry
Alive entry
Minimizes the integral of the area of the bounding rectangle from t├ to CT+H.
(The workload-specific parameter H is adjusted by observing the worload.)
Optimized TPBR
Pros:
• After the time split – possible to update the TPBR of the old node.
Cons:
• Computation (using a convex hull) is complex and takes O(mn log
n) time, where n is the number of objects bounded.
• Not possible to do tightening.
Double TPBR: a head and a tail
DoubleDouble
entry entry
DELETE
INSERT
CT
INSERT
CT
”Head” bounds the segments of the trajectories of objects from t├ to the time of
last update. The optimized TPBRs are used.
”Tail” starts at the time of last update, and it is the regular TPBR.
Double TPBR: a head and a tail
Time spilt
INSERT
Dead entry
Double TPBR: static heads
insert I
insert II & time split
“Head” bounds the segments using the TPBR with static (zero speed)
bounds.
Pros:
With respect to double optimized TPBRs, static TPBRs have the following advantages:
• Reduces the size of the index entry
• Omits the zero speeds in the double TPBR representation.
• Computation is as simple as of MBRs in R-tree or TPBRs in TPR-tree.
• Supports “tightening” (not possible in single optimized TPBRs).
Cons:
• Heads may not be optimized. Might cover more space than double optimized TPBRs.
• The time of the last update must be updated for all live ancestors at each update.
Update costs might be higher than using single optimized TPBRs.
RPFF-tree
• Use Double TPBRs with static heads
– Performance comparison of the single and double optimized TPBRs:
• I/O performance is similar, but the computation is much simpler.
• TPBRs are rectangular (not trapezoids), therefore, less corrections of TPBRs
will be done.
• Indexes the past, present, and future positions of moving objects.
• Past positions are captured as polylines.
• Present and future positions are captured as linear functions.
• Uses partial persistence
• Uses novel kinds of time-parameterized bounding rectangles
(TRBR)
Future Research
• Apply partial persistence framework to other indexing
techniques like Bx-trees
• BBx trees can index past, present, future positions but
trajectories from online updates have disconnected
segments. Use this partial persistence and compare to Rppf
tree.
• Different methods of main memory use in Rppf trees.
• Use this Rppf-tree for sensor data (like temperature,
barometric pressure, humidity, etc)
Article Critique
Strengths
• Short summaries inserted for clarification
• Extensive research of previous ideas
• Use of previous ideas
• Build their case
Weaknesses
• Tree discussion is confusing (when pro-ing and
when con-ing)
• Figure labels not well defined
Thoughts?
[email protected]
Thanks to Christian S. Jensen for his notes.