DOC PREVIEW
GT CS 4440 - Indexing the Past, Present, and Anticipated Future Positions of Moving Objects

This preview shows page 1-2-20-21 out of 21 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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.1132870Introduction: MeIntroduction: ArticlePosition of moving objectsRelated Work: Past PositionRecord of Movement: 1-DRelated Work: Present and Future PositionIndexing Past separately from the PresentNew IdeasTypes of TPBRsStraightforward TPBRSlide 12Optimized TPBRSlide 14Double TPBR: a head and a tailSlide 16Double TPBR: static headsRPFF-treeFuture ResearchArticle CritiqueSlide 21Indexing the Past, Present, and Anticipated Future Positions of Moving ObjectsMindaugas Pelanis, Simonas Saltenis, and Christian S. Jensenhttp://portal.acm.org/citation.cfm?id=1132863.1132870Kathy PhamCS 4440August 31, 2007Introduction: 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 profileso Doctor comparing Magnetic Resonance Images (MRIs)o Emergency response determining quickest route to victimo Mobile phone companies tracking phone usagePosition 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 PositionEphemeral 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 temporalRecord of Movement: 1-DLinear prediction of future movementRecorded polylineu2u3u4CTxxxtimeChristian S. JensenTrajectory of 1-dimentional moving objectRelated Work: Present and Future PositionPartially 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 PresentLeft: To bridge gap, updates stored in near-past structure. Gap becomes arbitrarily large. Partially persistence index thatdisregards 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-treeo 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 proposalsTypes of TPBRs•Straightforward TPBRsThe calculation of coordinates of bounding rectangles is modified: the TPBR is computed to be minimum at its insertion time t├•Optimized TPBRsMinimizes 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 TPR-tree TPBR.Two types of double TPBRs:–“heads” are optimized TPBRs–“heads” are static (zero speed)Straightforward TPBRCTThe calculation of the coordinates of the bounding rectangles is modified: the TPBR is computed to be minimum at its insertion time t├.CTTime of last updateTPBR in TPR-treeINSERTDELETEINSERTTPBR in TPR-treeStraightforward TPBRCons:•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.CT CTINSERTTime spiltDead entry Alive entryOptimized TPBRCTINSERTDELETEINSERTCTTime spiltDead entry Alive entryMinimizes 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 TPBRPros:•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”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.CTINSERTDELETEINSERTCTDouble entryDouble entryDouble TPBR: a head and a tailINSERTTime spiltDead entryDouble TPBR: static headsinsert Iinsert 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


View Full Document

GT CS 4440 - Indexing the Past, Present, and Anticipated Future Positions of Moving Objects

Download Indexing the Past, Present, and Anticipated Future Positions of Moving Objects
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Indexing the Past, Present, and Anticipated Future Positions of Moving Objects and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Indexing the Past, Present, and Anticipated Future Positions of Moving Objects 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?