Mobile Information Management

  *PhoneDB: A Small Foot-print DBMS for Mobile Phones* 

PhoneDB is a small foot-print DBMS with 100KB size lib and 100KB RAM usage for mobile phones.

Due to the resource limitations on mobile phones, such as limited main memory (RAM), slow write, expensive block-based erase and limited erase block cycles of Flash Memory, the page-based storage and read/write buffer policies used in the traditional DBMS can not be applied to mobile phone platforms. For example, when updating one byte data frequently (e.g. in the meta-data page), the whole page will be appended to the Flash Memory block multiple times due to its out-of-place update feature and therefore it will be exhausted quickly.

We propose the log-based record storage and write buffer policy in the PhoneDB to solve the problem. In the append-only record storage, the log record (delete log record and update log record) is added to the data file and the index file is separated from data file. Both index and data have timestamps so that they can be recovered to keep the consistence. When updating data, we first write in the data file the log record, then the data record and finally update the index. We use write buffer to cache index data to defer and reduce the hot record write. Data are read directly from Flash memory. For the garbage collection, we recycle block with most lost bytes and youngest and copy valid data to new block.

PhoneDB can provide local information management on mobile client and simplify the complex development and maintenance of applications brought by diverse platforms of mobile phones.

  *Update-efficient Indexing of Moving Objects* 

Indexing locations of moving objects (e.g. mobile users and cars with GPS) is necessary to support efficient location dependent spatial queries. However, applying the traditional spatial index structure (e.g. R-tree) to index moving objects will lead to expensive indexing update cost (the splitting or merging of tree structure) due to their continuously changing locations.

By exploiting the network constrains and traffic features, we propose a new update-efficient index method for moving objects in road networks to reduce indexing updates. We use the R-tree for indexing road segments and introduce a one-dimensional dynamic data structure, called adaptive unit (AU), for indexing a group of moving objects on each segment with similar movement patterns. The R-tree remains fixed since the road network seldom changes. The AU is only updated at road intersections since it is capable of dynamically adapting itself to cover the movement of the objects it contains on the segment. Specifically, an AU captures the movement bounds of the objects based on a more accurate prediction method. It first simulates two future trajectories representing the fastest movement and slowest movement of object respectively by the Cellular Automata (CA) model and then obtains two linear trajectory bounds as the predicted functions by the linear regression of the discrete points and translating of two regression lines.

Efficient locations indexing will contribute a lot to location information management for mobile users.

  *Clustering Analysis on Moving Objects* 

Existing clustering algorithms mainly focus on a static dataset. Due to the innate feature of continuously changing positions of moving objects, clustering analysis on moving objects is a challenging issue. It is difficult because even minor location changes of moving objects could lead to significantly different clustering results.

We propose a unified framework for clustering moving cars in a road network, which can be used in the traffic jam prediction. The main idea is to divide clustering process into different granularity and maintain the micro-cluster in each road segment by predicting the movement feature of objects. We first group objects close to each other at present and near future time into initial cluster block (CB) in road segments and incrementally maintain each CB by taking into account the objects' anticipated movements. We capture the predicted update events (including split and merge events) of each CB during the continuous movement and process these events accordingly. At any time, the global clusters can be constructed from the CBs, instead of the entire set of moving objects, which makes the construction processing cost efficient.

The real time analysis of location information such as clustering analysis can be used to catch interesting pattern changes during motion process and provide better insight into essence of moving objects.