Evaluation of Content-Matched Range Monitoring Queries over Moving Objects in Mobile Computing Environments

1. Introduction

Figure 1. An example of the safe region and resident domain.

Figure 1. An example of the safe region and resident domain.

2. Related Work

3. System Overview

Figure 2. System overview.

Figure 2. System overview.

• Moving objects: Each moving object o, which is registered at the server (with its non-spatial attribute values) and is identified by its unique identifier, is capable of sensing its current location (e.g., equipped with a GPS receiver) and has some available (memory and computational) capability $o.Cap$. We assume that each moving object o has heterogeneous capability $o.Cap$, which indicates the maximum number of (qualified) spatial query ranges it can load and process at a time, and that $o.Cap$ ≥ θ, where θ is a system parameter that indicates the minimum number of spatial query ranges o should be able to process; thus, a moving object with more powerful capability is assigned a larger resident domain together with a greater number of spatial query ranges. There are two types of location-update messages sent from moving objects to the server: $RequestDomain$ and $UpdateResult$. The former is for the purpose of receiving a new resident domain, whereas the latter is to let the server update the query result. For example, assuming the moving object $o_2$ in Figure 2 is assigned the blue-dotted rectangle as its resident domain together with spatial query range $q_3.R$, it sends the $RequestDomain$ message to the server because it exits its resident domain. On the other hand, assuming the moving object $o_1$ in Figure 2 is assigned the red-dotted rectangle as its resident domain together with spatial query ranges $q_1.R$ and $q_2.R$, it sends the $UpdateResult$ message to the server because it crosses the boundary of $q_2.R$.
• Clients: Each geographically distributed client is able to issue multiple CM range monitoring queries over the moving objects registered at the server, and continually receives the up-to-date results of these queries from the server via wireless or high-speed wired connections. Clients do not directly communicate with moving objects; instead, they use the server as an intermediary. Each query q issued by a client is identified by its unique identifier and its spatial query range is assumed to be stationary or quasi-stationary.
• Central server: The server maintains mainly two data structures: a query table (hashed on query identifiers) and the GQR-tree. The query table stores, for each query q, an identifier, a spatial query range $q.R$, a set of non-spatial values $q.V$, and the result. The following three main tasks are performed by the server.

  -

  Query registration (or de-registration): When a new query q is issued (or q is terminated) by a client, the task of query registration (or de-registration) is performed, which consists of inserting q into (or deleting q from) the query table, updating the GQR-tree, and broadcasting the message ($InsertQuery$ message or $DeleteQuery$ message) to all the moving objects to notify them of these changes.

  -

  Domain assignment: The task of domain assignment is performed in response to the $RequestDomain$ message sent by a moving object o that exits its resident domain. The server searches o’s new resident domain by traversing the GQR-tree. Then, the server assigns o’s new resident domain (together with several spatial query ranges) to o. It is important to note that the main purpose of the GQR-tree is to assign the largest possible resident domain (together with as many spatial query ranges as possible) to o.

  -

  Query result update: The task of query result update is performed mainly in response to the $UpdateResult$ message sent by a moving object o that crosses any of the boundary of its assigned spatial query ranges $q.R$. When receiving the $UpdateResult$ message from o, the server updates the result of the corresponding query q. For example, the server updates the result of $q_2$ in response to the $UpdateResult$ message sent by the moving object $o_1$ in Figure 2. As we will describe later, this task may also be performed when the server receives the $RequestDomain$ message from o.

4. Problem Definition and Motivation

Figure 3. Example of content-matched (CM) range monitoring queries.

Figure 3. Example of content-matched (CM) range monitoring queries.

Table 1. Frequently used notation.

5. The Group-Aware Query Region Tree (GQR-Tree)

5.1. Description

Similarly to the BQR-tree, we choose to extend the QR-tree to the GQR-tree because, to the best of our knowledge, the QR-tree is superior to existing index structures (e.g., the BP-tree) for evaluation of traditional spatial range monitoring queries. In addition, because the cost of implementing entirely new index structure can be more expensive than the cost of extending an already existing index structure; thus, for efficient evaluation of CM range monitoring queries, extending the QR-tree by adding new features can be an excellent alternative.

For the tight integration of the spatial and the non-spatial specifications of the queries, we group the queries based on their query bit-vectors, after which we construct the GQR-tree based on their spatial query ranges. We represent non-spatial values (or intervals) specified by the queries as query bit-vectors. The query bit-vector is generated based on a mapping function predefined for each non-spatial attribute $a_{i(1\le i\le n)}$ ∈ A. If $a_i$ is a categorical attribute with $|C_i|$ categories $c_1,$ $c_2,$ $\cdots ,$ $c_{|C_i|}$, given a non-spatial value $q.v_{i(1\le i\le n)}$ ∈ $q.V$ specified by a query q on $a_i$, its mapping function $f_{i(1\le i\le n)}$ maps $q.v_i$ into a bit-string $(b_1{b}_2\cdots b_{|C_i|})$ such that $b_{j(1\le j\le |C_i\left|\right)}$ = ‘1’ if $q.v_i=c_{j(1\le j\le |C_i\left|\right)}$, otherwise, $b_j$ = ‘0’.

On the other hand, if $a_i$ is a numerical attribute, $f_i$ divides $a_i$’s domain into $|I{V}_i|$ disjoint intervals $i{v}_1,i{v}_2,\cdots ,i{v}_{|I{V}_i|}$ of equal length. Then, given a non-spatial interval $q.v_i$, $f_i$ maps $q.v_i$ into a bit-string $(b_1{b}_2\cdots b_{|I{V}_i|})$ such that $b_{j(1\le j\le |I{V}_i\left|\right)}$ = “1” if $q.v_i$ overlaps with $i{v}_{j(1\le j\le |I{V}_i\left|\right)}$, otherwise, $b_j$ = “0”. If $q.v_i$ overlaps with more than one interval, say $\acute{|I{V}_i|}$ ($\le |I{V}_i|$) intervals, then we consider q as $\acute{|I{V}_i|}$ distinct queries.

Definition 2. Given a query q = ($q.R$, $q.V$), suppose that there is a predefined mapping function $f_{i(1\le i\le n)}$ for each non-spatial attribute $a_{i(1\le i\le n)}$ ∈ A. Then, a query bit-vector $q.bv$ generated for $q.V$ is $f_1$(q.$v_1$) + $f_2$(q.$v_2$) + ⋯ + $f_n$(q.$v_n$), where + denotes the bit-string concatenation operator. When $q.V$ does not contain the specified value (or interval) $q.v_{i(1\le i\le n)}$ on $a_i$, the bit-string for $f_i$(q.$v_i$) becomes $**\cdots *$ with its length being equal to $f_i$($a_i$), where the symbol “*” denotes a “don’t care” condition. Although a bit can represent only two states “0” and “1”, we assume that one bit represents “0”, “1”, and “*” for convenience.

In the following, using the non-spatial values (or intervals) $q_1.V\sim q_5.V$ specified on a subset of A = {$a_1$: Age, $a_2$: Dietary preference, $a_3$: Gender} in Figure 3 as an example, we show how query bit-vectors for $q_1.V\sim q_5.V$ are generated. Suppose that there are three predefined mapping functions: $f_1(x_s,x_e)=\left\{\begin{array}{c}1000\mathrm{if}[x_s,x_e)\cap [0,20)=\neg \varnothing ;\hfill \\ 0100\mathrm{if}[x_s,x_e)\cap [20,40)=\neg \varnothing ;\hfill \\ 0010\mathrm{if}[x_s,x_e)\cap [40,60)=\neg \varnothing ;\hfill \\ 0001\mathrm{otherwise},\mathrm{where}\cap \mathrm{denotes}\mathrm{intersection}.\hfill \end{array}\right.$ $f_2(x)=\left\{\begin{array}{c}10\mathrm{if}x=\mathit{Meat}\mathit{eater};\hfill \\ 01\mathrm{if}x=\mathit{Vegetarian}.\hfill \end{array}\right.$   $f_3(x)=\left\{\begin{array}{c}10\mathrm{if}x=\mathit{Male};\hfill \\ 01\mathrm{if}x=\mathit{Female}.\hfill \end{array}\right.$

Then, the query bit-vectors $q_1.bv$, $q_2.bv$, $q_3.bv$, $q_4.bv$, and $q_5.bv$ generated for $q_1.V$, $q_2.V$, $q_3.V$, $q_4.V$, and $q_5.V$ are 01000110 (0100 + 01 + 10), 00100101 (0010 + 01 + 01), $0100**10$ (0100 + $**$ + 10), $****1001$ ($****$ + 10 + 01), and 01001001 (0100 + 10 + 01), respectively.

Given a set of queries $\mathcal{Q}$ = $\{q_1,q_2,\cdots ,q_{\left|\mathcal{Q}\right|}\}$, we partition $\mathcal{Q}$ into a set of query groups $\mathcal{G}$ = $\{g_1,g_2,\cdots ,g_{\left|\mathcal{G}\right|(\le \left|\mathcal{Q}\right|)}\}$ such that each query group $g$ consists of the queries that have the same query bit-vector. Then, each query group $g$ can be identified by a unique query bit-vector, which we call group bit-vector. Let $|C_i|$ and $|I{V}_j|$ be the number of categories per each categorical attribute $a_{i(1\le i\le k)}$ and the number of intervals per each numerical attribute $a_{j(1\le j\le n-k)}$, respectively, where k ($\le n$) is the number of categorical attributes. Then, the maximum possible number of generated query groups (or the maximum possible number of generated group bit-vectors) is

$${\displaystyle \prod _{i=1}^k|C_i|·\prod _{j=1}^{n-k}\left|I{V}_j\right|}$$

(2)

Figure 4 shows an example of partitioning the queries $q_1\sim q_5$ in Figure 3 into three query groups based on their query bit-vectors $q_1.bv\sim q_5.bv$. Notice that if a query bit-vector $q.bv$ contains bit positions filled with “*”, the corresponding query q can become an element of multiple query groups because “*” is a wildcard, which matches any bit in those positions. For example, the query $q_3$ in Figure 4 can be an element of two query groups; the query group $g_1$ whose group bit-vector $g_1.bv$ is 01000110 and another query group (though not as yet generated) whose group bit-vector is 01001010.

Figure 4. An example of query grouping.

Figure 4. An example of query grouping.

The GQR-tree is a space partitioning query indexing structure, which is built by recursively splitting two-dimensional entire workspace into two subspaces. Given a set of query groups $\mathcal{G}$ = $\{g_1,g_2,\cdots ,g_{\left|\mathcal{G}\right|}\}$ on the entire workspace that corresponds to the root, if there exists a query group $g(\in \mathcal{G}$) whose cardinality (i.e., the number of queries that are the elements of $g$) is greater than the split threshold θ, the entire workspace is split into two subspaces, each of which corresponds to a child node N of the root. Without ambiguity, we use the symbol “N” to denote both a tree node and its corresponding subspace. This process recursively continues until, for each $g(\in \mathcal{G}$), the number of its elements (queries) whose spatial query ranges are covered by or partially intersect every subspace N is no more than θ. Hereafter, we denote a set of $g$’s elements whose spatial query ranges are covered by or partially intersect N as $g\_N$ ($\subseteq g$). We classify the overlap relationship between a spatial query range $q.R$ and a subspace (i.e., GQR-tree node) N into four categories according to whether the intersection and difference of $q.R$ and N are empty or non-empty.

Definition 3. Given a spatial query range $q.R$ and a subspace (a GQR-tree node) N, there can be four overlap relationships as follows.

• Cover relationship (See Figure 5a): We say that $q.R$ covers N if ($q.R\cap N=\neg \varnothing$) $\&\&$ ($q.R-N=\neg \varnothing$) $\&\&$ ($N-q.R=\varnothing$), where − denotes difference.
• Covered by relationship (See Figure 5b): We say that $q.R$ is covered by N if ($q.R\cap N=\neg \varnothing$) $\&\&$ ($q.R-N=\varnothing$) $\&\&$ ($N-q.R=\neg \varnothing$).
• Partially intersect relationship (See Figure 5c): We say that $q.R$ partially intersects N if ($q.R\cap N=\neg \varnothing$) $\&\&$ ($q.R-N=\neg \varnothing$) $\&\&$ ($N-q.R=\neg \varnothing$).
• Equal relationship (See Figure 5d): We say that $q.R$ equals N if ($q.R\cap N=\neg \varnothing$) $\&\&$ ($q.R-N=\varnothing$) $\&\&$ ($N-q.R=\varnothing$).

Figure 5. Classification of the overlap relationship. (a) $q_1.R$ and $q_2.R$ cover N; (b) $q_1.R$ and $q_2.R$ are covered by N; (c) $q_1.R$ and $q_2.R$ partially intersect N; (d) $q_1.R$ and $q_2.R$ equal N.

Figure 5. Classification of the overlap relationship. (a) $q_1.R$ and $q_2.R$ cover N; (b) $q_1.R$ and $q_2.R$ are covered by N; (c) $q_1.R$ and $q_2.R$ partially intersect N; (d) $q_1.R$ and $q_2.R$ equal N.

It should be noted that, in this paper, if a spatial query range $q.R$ meets (or touches) a subspace N, we consider that $q.R$ and N are disjoint although ($q.R\cap N=\neg \varnothing$) $\&\&$ ($q.R-N=\neg \varnothing$) $\&\&$ ($N-q.R=\neg \varnothing$). Now, we describe the structure and properties of the GQR-tree. A leaf node of the GQR-tree stores, for each query group $g$ $\in \mathcal{G}$, a tuple of the form $\langle g.bv,partial\_qid\_list\rangle$, where $g.bv$ is a group bit-vector of $g$ and $partial\_qid\_list$ is a list that contains at most θ query identifiers. A non-leaf node of the GQR-tree stores two entries of the form $\langle ptr,N\rangle$, where $ptr$ is a pointer to a child node (i.e., non-leaf or leaf node) and N is a subspace that corresponds to the child node pointed to by $ptr$.

Definition 4. Given a query group $g\in \mathcal{G}$ and a leaf node N of the GQR-tree, the list $\mathit{p}\mathit{a}\mathit{r}\mathit{t}\mathit{i}\mathit{a}\mathit{l}\_\mathit{q}\mathit{i}\mathit{d}\_\mathit{l}\mathit{i}\mathit{s}\mathit{t}$, with its size $|partial\_qid\_list|$ $\le \theta$, contains only the query identifier of each element (query) q $\in g$ whose spatial query range $q.R$ is covered by or partially intersects N (i.e., query identifier of each query q $\in g\_N$).

The GQR-tree satisfies the following properties:

• A tuple $\langle g.bv,partial\_qid\_list\rangle$ for each query group $g\in \mathcal{G}$ can be stored in a leaf node N only if there exists at least one element (query) $q\in g$ whose spatial query range $q.R$ is covered by or partially intersects N (i.e., $g\_N\ne \varnothing$).
• A tuple $\langle g.bv,partial\_qid\_list\rangle$ for each query group $g$ $\in \mathcal{G}$ can be redundantly stored in several leaf nodes if there exists an element $q\in g$ whose spatial query range $q.R$ partially intersects all of these leaf nodes.
• For each entry $\langle ptr,\acute{N}\rangle$ stored in a non-leaf node N, $\acute{N}$ represents one of the equal halves of N’s space.
• Each (non-leaf or leaf) node N stores, for each query group $g\in \mathcal{G}$, the cardinality $|g\_N|$ of $g\_N$ (i.e., the total number of $g$’s elements whose spatial query ranges are covered by or partially intersect N). In case that N is a non-leaf node, N additionally stores, for each query group $g\in \mathcal{G}$, a single bit flag $Conceptual\_Leaf$, which is set to $True$ if 0 ≤ $|g\_N|$ ≤ θ and set to $False$ otherwise.
• Each (non-leaf or leaf) node N is associated with a data structure $N.full\_qid\_table$, which is a set of tuples of the form $\langle g.bv,full\_qid\_list\rangle$, where $g.bv$ is a group bit-vector of a query group $g\in \mathcal{G}$ and $full\_qid\_list$ (See Definition 5 below) is a list that contains arbitrary number of query identifiers.
• A tuple $\langle g.bv,full\_qid\_list\rangle$ for a query group $g\in \mathcal{G}$ can be maintained in $N.full\_qid\_table$ only if there exists at least one element $q\in g$ whose spatial query range $q.R$ covers or equals N.
• Each non-leaf node N is associated with another data structure $N.partial\_qid\_table$, which is a set of tuples of the form $\langle g.bv,partial\_qid\_list\rangle$, where $g.bv$ and $partial\_qid\_list$ are defined as in the case of a leaf node.
• For each non-leaf node N, if a flag $Conceptual\_Leaf$ for a query group $g\in \mathcal{G}$ is set to $True$, N is considered as the leaf node from the viewpoint of $g$, and only if $|g\_N|$ ≥ 1, a tuple $\langle g.bv,partial\_qid\_list\rangle$ for $g$ can be maintained in $N.partial\_qid\_table$.
• For each non-leaf node N, if N is considered as the leaf node from the viewpoint of $g\in \mathcal{G}$, no information about $g$ is stored in N’s descendant nodes and their associated $partial\_qid\_table$s (if exist) and $full\_qid\_table$s.

Definition 5. Given a query group $g\in \mathcal{G}$ and a (non-leaf or leaf) node N of the GQR-tree, the list $\mathit{f}\mathit{u}\mathit{l}\mathit{l}\_\mathit{q}\mathit{i}\mathit{d}\_\mathit{l}\mathit{i}\mathit{s}\mathit{t}$ with arbitrary size contains only the query identifier of each element (query) q $\in g$ whose spatial query range $q.R$ covers or equals N.

The GQR-tree method (GQRT) has three advantages over the existing methods (e.g., MQM, QRT, and BQRT).

First, GQRT overcomes the first drawback of the existing methods (MQM, QRT, and BQRT) mentioned in Section 4. In contrast to the existing methods, in GQRT, the capability $o.Cap$ of each moving object o is measured by the number of only the spatial query ranges that are non-spatially relevant to o without any additional complex computation. Specifically, when assigning the resident domain to o, the GQR-tree enables $o.Cap$ to be measured by the number of only the queries that are the elements of the query group $g$ whose group bit-vector $g.bv$ is matched to the object bit-vector $o.bv$ of o. We say that $g.bv$ is matched to $o.bv$ or vice versa if $g.bv$ ∧ $o.bv$ = $o.bv$, where ∧ denotes bit-wise AND-ing. This helps the server assign o much larger resident domain, and thus the number of $RequestDomain$ messages sent by o can be reduced. We represent non-spatial attribute values $o.A$ of o as object bit-vector. The object bit-vector is generated based on the same mapping functions used for generating the query bit-vector.

Definition 6. Given a moving object o = ($o.loc$, $o.A$) and a set of predefined mapping functions $\{f_1,f_2,$ $\cdots ,f_n\}$ for a set of A = $\{a_1,a_2,$ $\cdots ,a_n\}$, an object bit-vector $o.bv$ generated for $o.A$ is $f_1$(o.$a_1$) + $f_2$(o.$a_2$) + ⋯ + $f_n$(o.$a_n$).

For example, the object bit-vector $o_1.bv$ generated for non-spatial attribute values $o_1.A$ = {$o_1.a_1=36,$ $o_1.a_2=Vegetarian,$ $o_1.a_3=Male$} of the object $o_1$ with its capability $o_1.Cap=2$ in Figure 3 is 01000110 (0100 + 01 + 10). Then, because the group bit-vector $g_1.bv$ of the query group $g_1$ in Figure 4 is matched to $o_1.bv$ (i.e., $g_1.bv$ ∧ $o_1.bv$ = $o_1.bv$), $o_1.Cap$ is measured by the number of only the queries that are the elements of $g_1$. Because the total number of $g_1$’s elements ($=2$) is not greater than $o_1.Cap$, $o_1$ can be assigned the entire space in Figure 3 as its resident domain.

Second, GQRT overcomes the second drawback of MQM and QRT mentioned in Section 4. In GQRT, each moving object o sends $UpdateResult$ messages to the server only when necessary because the server assigns o its resident domain together with only the qualified spatial query ranges such that the corresponding queries are the elements of the query group $g$ with its group bit-vector $g.bv$ being matched to the object bit-vector $o.bv$. Continuing the example above, $o_1$ in Figure 3 can be assigned the entire space as its resident domain together with $q_1.R$ and $q_3.R$ because the corresponding queries $q_1$ and $q_3$, respectively, are the elements of the query group $g_1$, and thus $o_1$’s movement may affect only the results of $q_1$ and $q_3$. In addition, by associating each GQR-tree node N with $full\_qid\_table$, GQRT further reduces the number of $UpdateResult$ messages sent by moving objects based on the following lemma.

Lemma 1. Given a GQR-tree node N, $N.full\_qid\_table$, and a query q that is an element of some query group $g\in \mathcal{G}$, if the query identifier of q is contained in $full\_qid\_list$ of the tuple $\langle g.bv,full\_qid\_list\rangle$, every moving object o whose object bit-vector $o.bv$ is matched to $g.bv$, and that is currently moving within N cannot cross the boundary of q’s spatial query range $q.R$.

Proof. We prove this lemma by contradiction. Given a GQR-tree node N, let us assume that there exist (i) a moving object o whose object bit-vector $o.bv$ is matched to the group bit-vector $g.bv$ of some query group $g\in \mathcal{G}$ and (ii) a query q ($\in g$) whose query identifier is contained in $full\_qid\_list$ of the tuple $\langle g.bv,full\_qid\_list\rangle$. By Definition 5, we know that the spatial query range $q.R$ of q covers or equals N. Let us further assume that we can find o, which crosses the boundary of $q.R$ but not that of N. Then, the condition $N-q.R=\neg \varnothing$ holds. This leads to a contradiction to the cover relationship or equal relationship defined in Definition 3. Hence, o cannot cross the boundary of $q.R$ as long as it is moving within N. ☐

Based on Lemma 1, when assigning N to a moving object o as its resident domain together with qualified spatial query ranges, for each spatial query range $q.R$ among them, if the query identifier of the corresponding query q is contained in $full\_qid\_list$ of the tuple $\langle g.bv,full\_qid\_list\rangle$, i.e., if $q.R$ covers or equals N, the server can exclude $q.R$; instead, when the server receives the $RequestDomain$ message from o, it has to check whether the result of q is affected by o’s movement and update the result of q (if necessary). Therefore, given a GQR-tree node N and a moving object o with its object bit-vector $o.bv$ being matched to the group bit-vector $g.bv$ of some query group $g\in \mathcal{G}$, if (i) N contains the location of o and (ii) $|g\_N|\le o.Cap$, the server can assign N to o as its resident domain together with only the spatial query ranges of the queries that are elements of $g\_N$ ($\subseteq g$), i.e., spatial query ranges that are covered by or partially intersect N, among the qualified spatial query ranges.

Assuming $\theta =1$, Figure 6 shows an example of some sub-GQR-tree rooted at the node $N_1$. In the figure, assuming the capability $o_2.Cap$ is 1 and the object bit-vector $o_2.bv$ is matched to the group bit-vector $g_1.bv$ of the query group $g_1$ (i.e., $g_1.bv$ ∧ $o_2.bv$ = $o_2.bv$), the moving object $o_2$ is assigned $N_1$ as its resident domain together with the spatial query range $q_4.R$ because $N_1$ contains the location of $o_2$ and $|g_1\_N_1|$ ($=1$) ≤ $o_2.Cap$. It should be noted that the spatial query range $q_1.R$ is not assigned to $o_2$ because the query identifier of the corresponding query $q_1$ is contained in $full\_qid\_list$ of the tuple $\langle g_1.bv,full\_qid\_list\rangle$ maintained in $N_1.full\_qid\_table$ (i.e., because $q_1.R$ covers $N_1$). When $o_2$ exits its resident domain $N_1$ as depicted in Figure 6, it sends the $RequestDomain$ message to the server. Then, the server assigns $o_2$ a new resident domain and additionally checks if $o_2$’s movement affects the result of $q_1$. Because $o_2$ does not cross the boundary of $q_1.R$, the server need not update the current result of $q_1$.

Figure 6. An example of the sub-GQR-tree.

Figure 6. An example of the sub-GQR-tree.

Third, by grouping the issued queries according to their query bit-vectors, GQRT efficiently handles the case, where a leaf node N overlaps with $\theta +1$ spatial query ranges as a result of a newly issued query q. In the existing methods (MQM, QRT, and BQRT), without any consideration of non-spatial query values (or intervals), N is recursively split until all of its descendant nodes (i.e., subspaces of N) overlap with no more than θ spatial query ranges. On the other hand, in GQRT, if q is an element of some query group $g\in \mathcal{G}$ and $|g\_N|$ $\le \theta$, no split process occurs although $\theta +1$ spatial query ranges overlap with N. In case that $|g\_N|$ $>\theta$, N is recursively split until, for each descendant node $\acute{N}$, $|g\_\acute{N}|$ $\le \theta$.

5.2. Resident Domain Search

When a new moving object o is registered at the server (or the server receives the $RequestDomain$ message from o), the search algorithm for o’s resident domain is invoked. Algorithm 1 is the pseudocode of the search algorithm on the GQR-tree. Given a GQR-tree node N (initially set to the root) and a moving object $o=(o.loc,o.A)$ with its capability $o.Cap$, the search algorithm generates an object bit-vector $o.bv$ and identifies the query group $g$ such that $g.bv$ ∧ $o.bv$ = $o.bv$. Then, the search algorithm recursively accesses the GQR-tree nodes that contain $o.loc$ until reaching the node N such that $|g\_N|\le o.Cap$. Now, N becomes o’s resident domain.

Algorithm 1 Search(N, o)

Input N: a GQR-tree node initially set to the root, o: a moving object Output R: o’s resident domain, $qid\_set$: a set of (distinct) query identifiers 1:       map $o.A$ to $o.bv$; 2:       initialize an empty set $qid\_set$; 3:       identify the query group $g$ such that $g.bv$ ∧ $o.bv$ = $o.bv$; 4:       for each entry $(ptr,\acute{N})$ stored in N do 5:         if $\acute{N}$ contains $o.loc$ then 6:           if $|g\_\acute{N}|\le o.Cap$ then 7:             set R to $\acute{N}$; 8:             set $is\_Resident\_Domain$ to $True$;   // one-bit flag 9:             $qid\_set\leftarrow qid\_set\cup$ FindQueryID $(N,o.bv,is\_Resident\_Domain)$; 10:             return R and $qid\_set$; 11:           else 12:             Search($\acute{N}$, o);

Next, the search algorithm invokes FindQueryID (See Algorithm 2), which is a depth-first search algorithm that takes N, $o.bv$, and $is\_Resident\_Domain$ (one-bit flag) as an input and retrieves all the query identifiers of the queries that are elements of $g\_N$ (⊆ $g$). Specifically, assuming N is a non-leaf node, FindQueryID identifies the query group $g$ such that $g.bv$ ∧ $o.bv$ = $o.bv$. Then, FindQueryID checks if $Conceptual\_Leaf$ stored in N for $g$ is set to $True$ (i.e., 0 ≤ $|g\_N|$ ≤ θ). If so, it visits $N.partial\_qid\_table$ and retrieves all the query identifiers contained in $partial\_qid\_list$ of the tuple $\langle g.bv,partial\_qid\_list\rangle$ (Lines 2–8).

On the other hand, if $Conceptual\_Leaf$ stored in N for $g$ is set to $False$, FindQueryID recursively accesses each N’s descendent (non-leaf or leaf) node $\acute{N}$ (Lines 9–12 or 26–28) and according to two cases, it proceeds as follows:

• Case (1): If $\acute{N}$ is a non-leaf node and $Conceptual\_Leaf$ stored in $\acute{N}$ for $g$ is set to $True$, FindQueryID visits $\acute{N}.partial\_qid\_table$ and $\acute{N}.full\_qid\_table$, after which it retrieves all the distinct query identifiers contained in $partial\_qid\_list$ of the tuple $\langle g.bv,partial\_qid\_list\rangle$ and $full\_qid\_list$ of the tuple $\langle g.bv,full\_qid\_list\rangle$ (Lines 19–25).
• Case (2): If $\acute{N}$ is a leaf node, FindQueryID retrieves all the distinct query identifiers contained in $partial\_qid\_list$ of the tuple $\langle g.bv,partial\_qid\_list\rangle$ (stored in $\acute{N}$), after which it visits $\acute{N}.full\_qid\_table$ and retrieves all the distinct query identifiers contained in $full\_qid\_list$ of the tuple $\langle g.bv,full\_qid\_list\rangle$ (Lines 29–34).

It should be noted that $\acute{N}.full\_qid\_table$ must be visited and each query identifier contained in $full\_qid\_list$ must be retrieved and checked if the corresponding query $q\in g\_N$. This is because, although the spatial query range of q covers or equals $\acute{N}$, they may be covered by or partially intersect N. In the worst case, N (o’s resident domain) may be a leaf node. In this case, FindQueryID retrieves only the query identifiers contained in $partial\_qid\_list$ of the tuple $\langle g.bv,partial\_qid\_list\rangle$ stored in N (Lines 13–16).

Algorithm 2 FindQueryID($N,o.bv,is\_Resident\_Domain$)

Input N: a GQR-tree node, $o.bv$: an object bit-vector, $is\_Resident\_Domain$: a bit flag initially set to $True$ Output $qid\_set$: a set of (distinct) query identifiers 1:       initialize an empty set $qid\_set$; 2:       if $is\_Resident\_Domain$ = $True$ then 3:         identify the query group $g$ such that $g.bv$ ∧ $o.bv$ = $o.bv$; 4:         if N is a non-leaf node then 5:             if $Conceptual\_Leaf$ stored in N for $g$ is $True$ then 6:               visit $N.partial\_qid\_table$ and get the tuple $\langle g.bv,partial\_qid\_list\rangle$; 7:               retrieve all the query identifiers contained in $partial\_qid\_list$ and insert them into $qid\_set$; 8:               return $qid\_set$; 9:             else   // $Conceptual\_Leaf$ stored in N for $g$ is $False$ 10:               set $is\_Resident\_Domain$ to $False$; 11:               for each entry $(ptr,\acute{N})$ stored in N do 12:                 FindQueryID($\acute{N},o.bv,is\_Resident\_Domain$); 13:         else   // N is a leaf node 14:           get the tuple $\langle g.bv,partial\_qid\_list\rangle$ stored in N; 15:           retrieve all the query identifiers contained in $partial\_qid\_list$ and insert them into $qid\_set$; 16:           return $qid\_set$; 17:       else   // $is\_Resident\_Domain$ = $False$ 18:        identify the query group $g$ such that $g.bv$ ∧ $o.bv$ = $o.bv$; 19:         if N is a non-leaf node then 20:          if $Conceptual\_Leaf$ stored in N for $g$ is $True$ then 21:            visit $N.partial\_qid\_table$ and get the tuple $\langle g.bv,partial\_qid\_list\rangle$; 22:            retrieve all the query identifiers contained in $partial\_qid\_list$ and insert them into $qid\_set$; 23:            visit $N.full\_qid\_table$ and get the tuple $\langle g.bv,full\_qid\_list\rangle$; 24:            retrieve all the query identifiers contained in $full\_qid\_list$ and insert them into $qid\_set$; 25:            return $qid\_set$; 26:          else   // $Conceptual\_Leaf$ stored in N for $g$ is $False$ 27:            for each entry $(ptr,\acute{N})$ stored in N do 28:              FindQueryID($\acute{N},o.bv,is\_Resident\_Domain$); 29:         else   // N is a leaf node 30:           get the tuple $\langle g.bv,partial\_qid\_list\rangle$ stored in N; 31:           retrieve all the query identifiers contained in $partial\_qid\_list$ and insert them into $qid\_set$; 32:           visit $N.full\_qid\_table$ and get the tuple $\langle g.bv,full\_qid\_list\rangle$; 33:           retrieve all the query identifiers contained in $full\_qid\_list$ and insert them into $qid\_set$; 34:           return $qid\_set$;

After Algorithm 1 terminates, the server searches all the queries (in the query table) referred to by the retrieved query identifiers, updates query results if necessary, and assigns the moving object o its resident domain N together with query identifier and spatial query range pairs. Figure 7 shows an example of the GQR-tree for the queries $q_1\sim q_5$ shown in Figure 3, assuming $\theta =1$. Let us assume that the non-spatial attribute values $o_3.A$ of the moving object $o_3$ with $o_3.Cap=1$ in Figure 7 is {$o_3.a_1=28,$ $o_3.a_2=Vegetarian,$ $o_3.a_3=Male$}. Then, the object bit-vector $o_3.bv$ of $o_3$ is 01000110 and is matched to $g_1.bv$. When $o_3$ is registered at the server, starting from the root, the search algorithm recursively traverses the GQR-tree until it reaches the node $N_2$ because $N_2$ contains the location of $o_3$ and $|g_1\_N_2|$ ($=1$) ≤ $o_3.Cap$. Then, the search algorithm invokes FindQueryID($N_2,o_3.bv,is\_Resident\_Domain$), which retrieves the query identifier of $q_3$. After the search algorithm terminates, the server assigns $N_2$ to $o_3$ as it resident domain together with a pair of query identifier and spatial query range ($q_3.id,q_3.R$).

Figure 7. An example of the Group-Aware Query Region (GQR)-tree.

Figure 7. An example of the Group-Aware Query Region (GQR)-tree.