Transcript Indexing Trajectory Data.

--Presented By Sudheer Chelluboina.
Professor: Dr.Maggie Dunham
Outline
of
Paper
Introduction
Index
Structures

Due to rapid increase in the use of location based
services applications, large amount of location
data of moving object is recorded. Because of that
efficient indexing techniques are required to
manage these large amounts of trajectory data. All
index structures are focused on either indexing
past, current and future locations. Every indexing
structure or techniques discussed in this paper
will make simpler indexing or it will increase the
overall query processing performance.

Trajectory:

Trajectory Data:

Purpose of Indexing:
◦ It is the path of a moving object or body through space.
◦ In general the position of the moving object is sampled at
discrete times, and the series of straight lines connecting
successive positions represents the movement of the object.
These connected segments is called a Trajectory.
◦ When the moving object or body is continuously moving, and
the update or change in location is recorded and that recorded
data can be called as Trajectory Data.
◦ As the object moves its location constantly changes and there
will large number of update operations.
◦ Requires more space to consider this changing data.
◦ Searching becomes the worst due to enormous data.

Querying in trajectory databases is expensive and
complex because of vast amount of data.
Two types of Queries:

Trajectory based queries:

Applications:

◦ Query about future positions for moving objects.
◦ Query about historical positions for moving objects.
◦ Topological queries
◦ Navigational queries
◦
◦
◦
◦
Fleet Management
Traffic Management
Mobile Communication
Environmental Monitoring System

R-Tree:
◦ MBR’s are used as the data objects.
◦ Index records in leaf node and points to the actual data.

Advantages:
◦ It can handle any kind of data as trajectory.
◦ Each line segment as one MBR.

Problems:
◦ Line segments of each trajectory is not preserved so its
take much time to retrieve the information about one
trajectory.

STR-Tree:
◦ It is an extension of R-Trees.
◦ It has a insert/split algorithm.
◦ The main idea is to keep the spatial closeness by preserving
the trajectories line segments with single trajectory ID.

Advantages:
◦ It can handle any kind of data as trajectory.
◦ Each line segment as one MBR with an additional parameter
as trajectory id.

Problems:
◦ Even though the line segments of each trajectory is preserved,
its take much time to retrieve the information about one
trajectory.

TB-Tree:
◦ It is an extension of STR-Trees, proposed to handle only the
trajectory data.
◦ Here leaf node can only contain the segments belonging to the
same trajectory.
◦ Left most node is the first segment of trajectory and last right
node will be the last segment of trajectory.

Advantages:
◦ It index size is low as compared to previous index structures.

Problems:
◦ The main problem is the segment which is connected can be in
the same leaf node or it may be in another leaf node, by which
the information retrieved will be abnormal.

SETI-Tree:
◦ It is a new indexing method build on R* trees.
◦ Uses spatial partitions and sparse temporal indices.
◦ First the input query is filtered spatially than produce
candidate cells, on these cells spatial time index is built and
outputs the data pages with trajectory ids.

Advantages:
◦ It provides the efficient index structure scheme.

Problems:
◦ In the algorithm, there is a limitation that in the refinement
step there is a overhead in checking the temporal condition
met by all the line segments from that data page.

TS2-Tree:

Advantages:

Problems:
◦ It is a novel indexing method for time specific queries called
time specific similarity tree.
◦ It is similar to the R-tree. Each leaf node in a tree stores a
trajectory symbolic representation and also a pointer to the
raw trajectory where the actual trajectory is stored.
◦ The proposed structure is dynamic, that is the insert and
delete operations are intermixed.
◦ It provides the efficient organization for time specific queries
on trajectory.
◦ Spatial threshold is the main thing to consider if it increases
the query evaluation is expensive.




Different types of metrics used to analyze the
indexes.
Given knowledge about the types of queries used.
It given me idea about how the trajectories will be
and how it is stored and retrieved.
Main thing, it is used in my research for
simulating the abnormal trajectories into normal
data.





D. Pfoser, C. S. Jensen, and Y. Theodoridis, "Novel
Approaches to the Indexing of Moving Object Trajectories,"
in Proc. 26th VLDB conf., 2000, pp. 395-406.
Petko Bakalov, Eamonn J. Keogh, Vassilis J. Tsotras: TS2tree - an efficient similarity based organization for
trajectory data. GIS 2007: 58
Chakka, V. P.; Everspaugh, A. & Patel, J. M.
Indexing Large Trajectory Data Sets With SETI
CIDR, 2003.
M. Hadjieleftheriou, G. Kollios, V. J. Tsotras, and D.
Gunopulos. Efficient Indexing of Spatiotemporal Objects.
In
Proc. of the Intl. Conf. on Extending Database Technology,
EDBT, pages 251–268, Czech Republic, Mar. 2002.
Thank You….