Transcript Moving Objects Databases

Moving Objects Databases
Nilanshu Dharma
Shalva Singh
Agenda

Introduce the topic of Moving Objects (MOs).

Discuss challenges regarding the storage of MOs.

Discussion of various storage & retrieval strategies

Perform a comparative analysis on all the 3 strategies and suggest a
solution.

Conclusion
Introduction

Global Positioning System (GPS) makes use of a network of satellites
provide
 aid to navigation,
 land surveying, and
 scientific studies of various kinds by determining receiver’s location,
directions, and speed.

These functionalities are used by Location Based Services (LBS) for
tourists, mobile commerce, digital battlefield and emergency responses

It involves tracking of the transient location of a mobile caller or a vehicle,
also termed as Moving Objects (MOs).
Introduction

Since the data of millions of MOs changes incessantly, it has become
inevitable to store and manage the voluminous and by devising scalable
data management system.

The DBMS for MOs would deal with data mining, location propagation,
privacy, and synchronization, efficiently.

This paper analyses 3 different strategies to store and retrieve data. We
support one of the strategies as the solution for a better database approach.
Challenges with DBMS of MOs

Modeling of location information, uncertainty management, indexing &
scalability, data mining, location dissemination, privacy of data and
location fusion & synchronization.

Distributing, replication, and caching of database for efficient execution.

The issues to be addressed also involve- how to search database and how
frequently the database needs to be updated.
Strategies for Database Management in
MOs
Moving Object Management System Based on a
File

This system stores both the current location and the past location of the
moving object to store and search data efficiently, as location of MOs
change intermittently.

MOMS’ architecture consists 3 major components,

Namely Query Processor Component,
 Location Storage Component, and
 Index Component.
 An additional module, Gateway
Past & Current Location Index
Architecture of File-based Location Storage
System
The Design of File-based System

Location Query Component carries out query depending upon MO’s model
and its operator.

Index Component comprises two indexes simultaneously
 Current Location Index Component (CLIC), that takes only current
locations into consideration and
 Past Location Index Component (PLIC) which processes time interval
and trajectories queries.

Location Storage Component is used to store MOs and search the ones that
associate with query results of location.

CLIC adopts the approach of spatial based indexing on current location
information and object based indexing on MO Identification. On the other
hand, PLIC manages spatiotemporal index about the past location
information.
One Update for all Moving Objects at a
Timestamp

It is an updating technique applied for indexing methods developed from
R-Tree. This updates the indexes at one time and has considerably
improved the quality of queries.

R-tree is a height balanced external memory data structure. It is an efficient
method for indexing, but requires deletion of obsolete state and then insert
new state in top-down manner. The features of this approach are as follows:



Support for both deletion and update queries.
Updates process for all new states at one timestamp, which means it
tries to access a disk block at most once in a process.
It does not deteriorate the quality of the tree while providing improved
performance.
Contd.


It is not dependent on a specific type of new data distribution.
Capacity of main memory used in algorithm is not large and can be
easily estimated.
Deletion & Update Query Processing

The deletion takes place from the leaf level, i.e. deletes all the
obsolete states at leafs using a parent of pointer.

This also saves memory as instead of loading the entire tree, only
the pointer is needed.

For the insertion process the rule is, if leaf node is underflow the
process will not reinsert its entries immediately instead it would
move them into a stack in main memory for being inserted together
with insertion process. If internal is underflow normal insertion
process is used.
Use of information table and parent_of pointer

The experiments aim to compare update and insert query performance
compared to other R-Tree update methods.

The algorithm proposed outperforms its competitors in two sets of
experiments conducted. One was update queries randomly generated for set
of 10,000 cars for timestamps 1 to 4 at rates 1% and 5%. Other experiment
was on different data sizes, 5k, 10k, 20k and 30k cars. Updates were taken
at 1% and 5% rates and the algorithm proved to give most stable results for
all loads
Comparative Analysis

Both the strategies mentioned in the paper are unique methods.

Method using R-Tree is better approach.

It gives a detailed organized algorithm to store and retrieve indexes.
 The experiment results are quite convincing to convey the claim.
 The R-Tree model is scalable and consistent in performance.
 Also it is less cumbersome in terms of resource use as compared to file based
location storage.
Hybrid Model

A novel approach where a model can be designed that incorporates features
based on heuristics.

A problem exists with moving objects. If no update is received the position
of the object cannot be declared.

We propose a model which would use the past information from a moving
object to predict its current location. Incorporating such “intelligence”
would help further reduce the use of database resources and improve
efficiency of the entire system. This model would be implemented on the
one update at a timestamp concept.
Conclusion

We insinuate that one update at a timestamp is a better database approach
than index file method.

We also propose that it would be beneficial if this concept is used under a
model which also uses heuristics to determine the position of an object
even if no update is provided. This model would work best for objects
whose path is predetermined.
Questions?