System Overview and Data Structure

Suppose that $P$ is a set of $2$ -dimensional moving data points. Each data point $p\in P$ is represented by $(p.x, p.y)$ . The data points change their location in an unpredictable fashion and frequently. At each timestamp, the data point $p$ which moves from $p_{pre}$ to $p_{cur}$ , issues a location update as $\langle p.id, p_{pre},p_{cur}\rangle$ . Updates of query points are recorded similarly.

Figure  illustrates our continuous $k$ NN query monitoring system. There are four components in the system, query table, $k$ NN computation module, monitoring computation module, and CircularTrip module. Once a new continuous $k$ NN query arrives, it is first registered in the query table. Then, $k$ NN computation module retrieves the initial $k$ NN results. When either data points or query points move, monitoring computation module receives the location updates and reports the new $k$ NN results to the corresponding queries. CircularTrip module is invoked by both the $k$ NN computation module and monitoring computation module, which guarantees the minimum number of cells are accessed during all the computation. By accessing or visiting a cell, we mean that all the objects lying inside it are retrieved and their distances from $q$ are calculated. We use another term encountering a cell by which we mean to calculate the $mindist$ of that cell from $q$ . Clearly, the cost of encountering a cell is negligible as compared to accessing a cell.

Figure: System Overview and Data Structure

Each cell $c$ contains an object list $P_c$ that contains all the objects lying in $c$ . Influence list $Q_c$ of a cell $c$ contains every query $q$ such that $mindist(c,q)\leq q.dist_k$ . Intuitively, influence list of cell $c$ records all the queries $q$ affected by this cell $c$ . Both the object lists and influence lists are implemented as hash tables so that insertion, deletion or retrieval of any element takes constant time.

As shown in Algorithm , our CircularTrip-based continuous $k$ NN algorithm consists of two phases. In phase 1, the initial results of each new continuous $k$ NN query are computed. Then, the results are incrementally updated by continuous monitoring module at each time stamp upon the moves of query points and data points. Both phases take advantages of CircularTrip algorithm. Phase 1 and phase 2 are presented in Section  and Section , respectively.