Indexforcitytrajectories.ppt

Index for city trajectories;城市路网的特点：;;两个解决的方法;;;Group moving objects;AU index Architecture;AU index Architecture (cont.);R-tree（A. Guttman SIGMOD’1984） ;R-tree的特点;R-tree的典型算法;R-tree的典型算法;R*-Tree（N. Beckmann SIGMOD’1990） ;R*-tree;The R*-tree (cont.);current-AU ;past-AU ;Current-AU Past-AU;Indexing Moving Objects;What is data stream ?;数据流;Type Definition;current-AU operations;Query;Related work;MON-Tree index;MON-Tree index (cont.);SEB-tree (Start/End time stamp B-tree) (MDM2003);An interesting property about the history records is that the tuples are sorted by their end time stamps, To index the history records, the first step is to construct a 2-dimensional space where the start time stamp and the end time stamp are the horizontal and the vertical axes. Each record are mapped to a point in the space. Since in each record ts te, the points are all in upper-left half of the plane.;Three steps are executed when we insert a new point: 1) check the start stamp list and find the column where the point is inserted; 2) check the end stamp list and find the last node in the column. If the node is full, create a new node in the column; 3) insert the point into the node. The cost for each step is O(logB N), O(1) and O(1), and the overall cost for one insertion is O(logB N).;The query becomes to retrieve all points in the polygon. Observe that if a leaf node is inside the polygon, the points in the node must be in the query results; and if a leaf node is intersected with the polygon, the points in it require further check. The total query cost is O((logB N) + ((n logB n)/B) + ((n + B)/B) + (t/B)), where t is the size of the results. The first part logB N is for searching the columns that contains t1 and t2; the second part (n logB n)/B is for searching one node of each n/B 4 columns before column i; the third part (n+B)/B is for searching column j and the fourth part t/B is for retrieving the nodes that fall into the query range. ;TPR-Tree;Query future location