# An Experimental Analysis of Indoor Spatial Queries: Modeling, Indexing, and
Processing

Tiantian Liu† Huan Li† Hua Lu‡ Muhammad Aamir Cheema§ Lidan Shou¶
†Department of Computer Science, Aalborg University, Denmark
‡Department of People and Technology, Roskilde University, Denmark
§Faculty of Information Technology, Monash University, Australia
¶College of Computer Science, Zhejiang University, China
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
Abstract—Indoor location-based services (LBS), such as POI search and routing,
are often built on top of typical indoor spatial queries. To support such
queries and indoor LBS, multiple techniques including model/indexes and search
algorithms have been proposed. In this work, we conduct an extensive
experimental study on existing proposals for indoor spatial queries. We survey
five model/indexes, compare their algorithmic characteristics, and analyze
their space and time complexities. We also design an in-depth benchmark with
real and synthetic datasets, evaluation tasks and performance metrics. Enabled
by the benchmark, we obtain and report the performance results of all
model/indexes under investigation. By analyzing the results, we summarize the
pros and cons of all techniques and suggest the best choice for typical
scenarios.

##  1 Introduction

Thanks to the recent advances in indoor localization and high penetration of
smartphones, indoor location-based services (LBS) are becoming increasingly
popular [7, 10]. Indoor LBS applications, such as POI search [23, 19] and
routing [15, 12, 14], are often built on top of typical spatial queries like
range query, $k$ nearest neighbor query, shortest path query, and shortest
distance query. Therefore, the efficiency of processing such typical indoor
spatial queries plays a key role in the success of indoor LBS.

To facilitate spatial query processing for indoor LBS, multiple techniques
have been proposed, including models and indexes for indoor spaces and query
processing algorithms. All such proposals deal with indoor space entities such
as rooms, doors, walls, and floors. Such indoor entities form distinct indoor
topology that determines indoor distances and impacts indoor movement. As a
result, the distances in indoor spatial queries must be measured
appropriately, e.g., without involving straight line segments through walls.
Also, indoor routing in shortest path/distance queries must consider
connectivity and reachability between indoor locations.

To support distance computations with respect to indoor locations, existing
models and indexes [22, 30, 31, 26] employ different approaches to integrate
the geometry and topology information of an indoor space. All these techniques
can be used to process the aforementioned four types of indoor spatial
queries. However, a comprehensive experimental study on all these proposals is
still missing. Consequently, indoor LBS application developers inevitably
encounter difficulties in choosing the appropriate technique for a given
indoor space scenario.

To bridge this gap for LBS application development and disclose insights for
further research on indoor data management, we conduct a comprehensive
experimental study in this work. Our study focuses on five existing
model/indexes that support typical indoor spatial queries on static indoor
objects (e.g., POIs) or indoor shortest paths/distances. We compare the five
proposals theoretically and empirically. Our contributions are as follows.

  * •

We survey the five proposals by scrutinizing their structures, algorithmic
characteristics, and space and time complexities.

  * •

We design an in-depth benchmark with datasets, evaluation tasks, and
performance metrics. The datasets consist of real and synthetic data
characterized by distinctive indoor topology.

  * •

Within the same framework, we conduct extensive experiments to evaluate the
performance of the five proposals in terms of construction cost and query
efficiency.

  * •

By analyzing the results, we disclose the pros and cons of the proposals,
analyze the impact of different conditions, and recommend the best choice for
typical application scenarios.

The paper is organized as follows. Section 2 gives the preliminaries, defines
indoor spatial queries, and briefly reviews related work. Sections 3 and 4
present the indoor space model/indexes and spatial query processing,
respectively. Section 5 proposes a benchmark for the experimental evaluation.
Section 6 reports and analyzes the evaluation results. Section 7 discusses the
extensibility of all model/indexes. Section 8 concludes the paper.

##  2 Indoor Spatial Queries

Table 1 lists the frequently used notations.

Table 1: Notations Symbol | Meaning
---|---
$\mathbb{I}$ | An indoor space
$p,q\in\mathbb{I}$ | Indoor points
$o\in O$ | A static indoor object
$d\in D$ | A door
$v\in V$ | An indoor partition
$|p,q|_{I}$ |  Indoor distance from $p$ to $q$
$\phi=\langle p,d_{i},\ldots,d_{j},q\rangle$ | An indoor path
$L(\phi)$ |  Length of a path $\phi$

###  2.1 Indoor Space Concepts

Indoor space features distinct entities such as walls, doors, and rooms, which
altogether form complex indoor topology that enables and constrains movements.
Naturally, an indoor space is divided by walls and doors into indoor
partitions like rooms, hallways or staircases. Two indoor partitions can be
connected by a door or an open segment between them. Referring to the example
floorplan in Figure 1, partitions 30 and 40 (denoted as $v_{30}$ and $v_{40}$,
respectively) are connected by an open segment $d_{3}$, In this paper, we
refer to both doors and open segments as doors. We do not consider the width
of a door and represent a door by its center point. In other words, each door
can be generally regarded as an indoor point. Furthermore, a door can be
unidirectional such as a security checkpoint at the airport. The door
directionality makes the indoor distance between two points asymmetric.
Referring to Figure 1, the shortest indoor path from $p$ to $p^{\prime}$ and
that from $p^{\prime}$ to $p$ are different due to the unidirectionality of
$d_{12}$.

Topology renders the indoor distance more complex than Euclidean distance. In
Figure 1, the indoor distance $|p,o_{1}|_{I}$ from $p$ to $o_{1}$ is not
subject to the straight line segment between them; it is the total length of
the polyline $p\rightarrow d_{11}\rightarrow o_{1}$.

Figure 1: Example Floorplan

Lu et al. [22] proposes mappings to capture the relationships between indoor
partitions and doors. In particular, $\mathit{D2P}_{\sqsupset}(d_{i})$ gives
the set of partitions that one can enter through door $d_{i}$ and
$\mathit{D2P}_{\sqsubset}(d_{j})$ gives those that one can leave through door
$d_{j}$. Besides, $\mathit{D2P}(d_{i})$ gives a set of a partition pair
$(v_{j},v_{k})$ such that one can go through door $d_{i}$ from partition
$v_{j}$ to $v_{k}$. Moreover, $\mathit{P2D}_{\sqsupset}(v_{k})$ gives the set
of enterable doors through which one can enter partition $v_{k}$, and
$\mathit{P2D}_{\sqsubset}(v_{k})$ gives the set of leaveable doors through
which one can leave partition $v_{k}$. When the door directionality is not
relevant, we use
$\mathit{P2D}(v_{k})=\mathit{P2D}_{\sqsupset}(v_{k})\cup\mathit{P2D}_{\sqsubset}(v_{k})$
to denote the set of doors associated to partition $v_{k}$.

######  Example 1.

Referring to Figure 1, given the unidirectional door $d_{12}$, we have
$\mathit{D2P}_{\sqsupset}(d_{12})=\\{v_{10}\\}$,
$\mathit{D2P}_{\sqsubset}(d_{12})=\\{v_{12}\\}$, and
$\mathit{D2P}(d_{12})=\\{(v_{12},v_{10})\\}$. Moreover, we have
$\mathit{P2D}_{\sqsupset}(v_{12})=\\{d_{15}\\}$,
$\mathit{P2D}_{\sqsubset}(v_{12})=\\{d_{12}\\}$, and
$\mathit{P2D}(v_{12})=\\{d_{15},d_{12}\\}$.

###  2.2 Indoor Spatial Query Types

In our study, we focus on _static_ indoor objects such as POIs and facilities.
Our experimental study covers four fundamental indoor spatial query types as
follows.

######  Definition 1 (Range Query (RQ)).

Given an indoor point $p\in\mathbb{I}$, a set $O$ of indoor objects, and a
distance value $r$, a _range query_ $\textsf{RQ}(p,r)$ returns all indoor
objects from $O$ whose indoor distance from $p$ is within $r$. Formally,
$\textsf{RQ}(p,r)=\\{o\mid|p,o|_{I}\leq r,o\in O\\}$.

######  Definition 2 ($k$ Nearest Neighbor Query ($k$NNQ)).

Given an indoor point $p\in\mathbb{I}$, a set $O$ of indoor objects, and an
integer value $k$, a _$k$ nearest neighbor query_ $k\textsf{NNQ}(p)$ returns a
set $O^{\prime}$ of $k$ indoor objects whose indoor distances from $p$ are the
smallest, i.e., $|O^{\prime}|=k$ and $\forall o_{i}\in O^{\prime},o_{j}\in
O\setminus O^{\prime},|p,o_{i}|_{I}\leq|p,o_{j}|_{I}$.

Referring to Figure 1 where $O=\\{o_{1},\ldots,o_{4}\\}$, a query
$\textsf{RQ}(p,1.9\text{m})$ returns $\\{o_{2},o_{3}\\}$ since the distances
from $p$ to $o_{1}$ and $o_{4}$ both exceed $1.9$m.111Meter is the distance
unit in all examples in this paper. Further, a query $3\textsf{NNQ}(p)$
returns $\\{o_{2},o_{3},o_{4}\\}$, since $o_{1}$’s distance from $p$ is the
longest among all.

######  Definition 3 (Shortest Path Query (SPQ)).

Given a source point $p\in\mathbb{I}$, a target point $q\in\mathbb{I}$, a
_shortest path query_ $\textsf{SPQ}(p,q)$ returns the shortest path
$\phi=\langle p,d_{i},\ldots,d_{j},q\rangle$ from $p$ to $q$ such that 1)
$d_{i},\ldots,d_{j}$ are door sequences and each two consecutive doors are
associated to the same partition, 2) $p$ is in the partition having $d_{i}$ as
a leavable door, 3) $q$ is in the partition having $d_{j}$ as an enterable
door, and 4) $\forall\phi^{\prime}$ from $p$ to $q$, $L(\phi)\leq
L(\phi^{\prime})$.222$L(\phi)=\Sigma_{k=0}^{k=j}|d_{k},d_{k+1}|_{I}$ where
$d_{0}=p$ and $d_{j+1}=q$.

######  Definition 4 (Shortest Distance Query (SDQ)).

Given a source point $p\in\mathbb{I}$, a target point $q\in\mathbb{I}$, a
_shortest distance query_ $\textsf{SDQ}(p,q)$ returns the shortest indoor
distance from $p$ to $q$, i.e., the length of $\textsf{SPQ}(p,q)$.

As indicated by the red dashed polyline in Figure 1, a query
$\textsf{SPQ}(p,q)$ returns $\phi=\langle p,d_{1},d_{3},q\rangle$ as the
shortest path from $p$ to $q$, and the result of $\textsf{SDQ}(p,q)$ is $2.7$m
+ $3.0$m + $0.5$m = $6.2$m.

###  2.3 Related Work

Multiple studies [18, 28, 8, 16, 29] have been proposed to model indoor
spaces, focusing on symbolic modeling of topological relationships between 3D
spatial cells or space partitions. However, these works do not support indoor
distances and thus cannot process the distance-aware queries evaluated in this
study.

Other studies focus on querying indoor moving objects. In the context of RFID
indoor tracking, Yang et al. study continuous range monitoring queries [32]
and probabilistic $k$ nearest neighbor queries [33]. To improve the query
result, Yu et al. [34] propose a particle filter-based method to infer the
undetected locations indoor moving objects. Assuming a probabilistic sample
based location data format, Xie et al. [30, 31] process $k$NN query and range
query for indoor moving objects. Considering the uncertain object movements
between observed time and query time, Li et al. [19] study the search of the
current top-$k$ indoor dense regions. These works consider indoor moving
objects with uncertain positions at a particular time. In contrast, the range
and $k$NN queries evaluated in this study concern static indoor objects.

Jensen et al. [16] study historical trajectories of RFID-tracked indoor
objects. Delafontaine et al. [13] find sequential visiting patterns within
historical Bluetooth tracking data. Given a past time or a time interval, Lu
et al. define spatio-temporal joins [24] to find moving object pairs in the
same indoor partition, and top-$k$ queries [23] to find the most frequently
visited indoor POIs. Ahmed et al. [4, 5] define threshold density query to
find dense indoor semantic locations in a historical time interval. Assuming
probabilistic sample based location records, Li et al. [20] find the top-$k$
most popular indoor semantic regions with the highest object flow values.
Unlike these works, the queries studied in this paper focus on static objects
or indoor paths.

Shortest path/distance queries have been studied in indoor contexts. Goetz and
Zipf [15] study user-adaptive length-optimal indoor routing based on a
weighted routing graph. Salgado et al. [25] study indoor keyword-aware skyline
route query, considering the number of covered keywords and route distances.
Feng et al. [14] study indoor keyword-aware routing queries to find shortest
paths covering user-specified semantic keywords. Costa et al. [12] propose the
context-aware indoor-outdoor path recommendation that minimizes the outdoor
exposure and path distance. These techniques consider additional query
semantics, and thus are different from the fundamental, pure shortest
path/distance queries studied in this paper.

##  3 Model and Indexes

The aforementioned indoor spatial queries all involve indoor distances. To
facilitate such queries, indoor distances must be considered in modeling and
indexing indoor space.

###  3.1 Indoor Distance-Aware Model

Indoor distance-aware model [22] (IDModel) is a graph $G_{\text{dist}}$
$(V,E_{a},L,f_{\text{dv}},f_{\text{d2d}})$. The first three elements capture
indoor topology in an _accessibility base graph_ $G_{\text{accs}}(V,E_{a},L)$,
where $V$ is the set of vertexes each referring to an indoor partition,
$E_{a}=\\{(v_{i},v_{j},d_{k})\mid d_{k}\in
D,v_{i}\in\mathit{D2P}_{\sqsupset}(d_{k})\wedge
v_{j}\in\mathit{D2P}_{\sqsubset}(d_{k})\\}$ is a set of labeled, directed
edges, and $L$ is the set of edge labels each corresponding to a door in $D$.
The additional two are mapping functions defined as follows.

$f_{\text{dv}}(d_{i},v_{j})=\begin{cases}\max_{p\in
v_{j}}||d_{i},p||_{v_{j}},&\text{if~{}}v_{j}\in\mathit{D2P}_{\sqsupset}(d_{i});\\\
\infty,&\text{otherwise}.\end{cases}$

Here, $||p,q||_{v_{j}}$ is the indoor distance from a point $p$ to a point $q$
within the partition $v_{j}$. Note that $||p,q||_{v_{j}}$ is not necessarily a
Euclidean distance because even within the same partition there may be
obstacles in the line of sight between $p$ and $q$. Specifically, _door-to-
partition distance mapping_ $f_{\text{dv}}(d_{i},v_{j})$ returns the longest
distance one can reach within partition $v_{j}$ from door $d_{i}$, if $v_{j}$
is an enterable partition of $d_{i}$. Otherwise, it returns $\infty$.

$f_{\text{d2d}}(v_{j},d_{i},d_{j})=\begin{cases}||d_{i},d_{j}||_{v_{j}},&\text{if~{}}d_{i}\in\mathit{P2D}_{\sqsupset}(v_{j})\\\
&\text{and~{}}d_{j}\in\mathit{P2D}_{\sqsubset}(v_{j});\\\
0,&\text{if~{}}d_{i}=d_{j}\\\
&\text{and~{}}d_{i},d_{j}\in\mathit{P2D}(v_{j});\\\
\infty,&\text{otherwise}.\end{cases}$

The _door-to-door distance mapping_ $f_{\text{d2d}}(v_{j},d_{i},d_{j})$ maps a
partition $v_{j}$ and two doors $d_{i}$ and $d_{j}$ to a distance value. If
both doors are associated to $v_{j}$, it returns the distance from $d_{i}$ to
$d_{j}$ within $v_{j}$, i.e., $||d_{i},d_{j}||_{v_{j}}$. If $d_{i}$ and
$d_{j}$ are identical and associated to $v_{j}$, we stipulate
$f_{\text{d2d}}(v_{j},d_{i},d_{j})=0$. Otherwise,
$f_{\text{d2d}}(v_{j},d_{i},d_{j})$ returns $\infty$, indicating that one
cannot go from $d_{i}$ to $d_{j}$ via $v_{j}$ only.

Figure 2 illustrates the IDModel for the example shown in Figure 1. The
outdoor space is captured in a special graph vertex $v_{0}$. Two hashmaps
implement the mappings $f_{\text{dv}}(d_{i},v_{j})$ and
$f_{\text{d2d}}(v_{j},d_{i},d_{j})$. With directed edges, IDModel can support
doors’ directionality and temporal variation when needed.

Figure 2: An Example of IDModel

With the two mappings $f_{\text{dv}}(d_{i},v_{j})$ and
$f_{\text{d2d}}(v_{k},d_{i},d_{j})$, a graph traversal algorithm [22] on
IDModel is designed to compute the shortest door-to-door distance
$\text{d2d}(d_{s},d_{t})$ from a source door $d_{s}$ to a target door $d_{t}$.
The basic idea is to keep expanding to unvisited doors based on the current
shortest path until reaching the target door. Further, the shortest indoor
distance from any point $p$ to any point $q$ can be computed by finding the
minimum value of the distance summation
$||p,d_{p}||_{v_{p}}+\text{d2d}(d_{p},d_{q})+||d_{q},q||_{v_{q}}$, where
$v_{p}$ and $v_{q}$ are the partitions that host $p$ and $q$, respectively,
$d_{p}\in\mathit{P2D}_{\sqsubset}(v_{p})$, and
$d_{q}\in\mathit{P2D}_{\sqsupset}(v_{q})$.

However, IDModel does not support fast determination of the host partition of
a query/source point. It boils down to sequential scanning of all partitions
if no additional index, e.g., R-tree, is used for the partitions. Also, to
manage indoor static objects, IDModel needs additional object buckets each for
a partition.

###  3.2 Indoor Distance-Aware Index

IDModel only captures the door-to-door and door-to-partition distances within
a local partition, which entails extra search to compute the indoor distance
for two points in different partitions.

To cut such costs, indoor distance-aware index [22] (IDIndex) stores extra
information on top of IDModel, namely, precomputed global door-to-door
distances and their ordering in two matrices. The door-to-door distance matrix
$M_{\text{d2d}}$ is an $\mathsf{N}$-by-$\mathsf{N}$ matrix where
$\mathsf{N}=|D|$ is the total number of doors and
$M_{\text{d2d}}[d_{i},d_{j}]$ gives the precomputed shortest indoor distance
from $d_{i}$ to $d_{j}$. The distance index matrix $M_{\text{idx}}$ is also an
$\mathsf{N}$-by-$\mathsf{N}$ matrix such that $M_{\text{idx}}[d_{i},k]$ gives
the identifier of a door whose indoor distance from $d_{i}$ is the $k$-th
shortest among all the $N$ doors.

The IDIndex matrices for the top-left part in Figure 1 is illustrated in
Figure 3. Here, we have $M_{\text{d2d}}[d_{1},d_{15}]=4.6$m. The first row of
$M_{\text{d2d}}$ shows that $d_{15}$ has the longest indoor distance from
$d_{1}$. Accordingly, we have $M_{\text{idx}}[d_{1},6]=d_{15}$ in
$M_{\text{idx}}$.

$\begin{pmatrix}\begin{smallmatrix}&d_{1}&d_{11}&d_{12}&d_{13}&d_{14}&d_{15}\\\
d_{1}&0&1.7&2.7&3.6&2.8&4.6\\\ d_{11}&1.7&0&1.9&3.6&2.8&4.6\\\
d_{12}&2.7&1.9&0&2.6&1.8&1.6\\\ d_{13}&3.2&3.4&2&0&2&1\\\
d_{14}&2.8&2.8&1.8&1&0&2\\\ d_{15}&4.3&3.5&1.6&1&2&0\\\
\end{smallmatrix}\end{pmatrix}$

(a) Distance Matrix $M_{\text{d2d}}$

$\begin{pmatrix}\begin{smallmatrix}&1&2&3&4&5&6\\\
d_{1}&d_{1}&d_{11}&d_{12}&d_{14}&d_{13}&d_{15}\\\
d_{11}&d_{11}&d_{1}&d_{12}&d_{14}&d_{13}&d_{15}\\\
d_{12}&d_{12}&d_{15}&d_{14}&d_{11}&d_{13}&d_{1}\\\
d_{13}&d_{13}&d_{15}&d_{12}&d_{14}&d_{1}&d_{11}\\\
d_{14}&d_{14}&d_{13}&d_{12}&d_{15}&d_{1}&d_{11}\\\
d_{15}&d_{15}&d_{13}&d_{12}&d_{14}&d_{11}&d_{1}\\\
\end{smallmatrix}\end{pmatrix}$

(b) Distance Index Matrix $M_{\text{idx}}$

Figure 3: An Example of IDIndex

As the shortest indoor distances to all doors are precomputed and sorted for
each door in IDIndex, it is faster to compute the shortest indoor distance
between any two points $p$ and $q$ in the indoor space. To support the
shortest path query, in addition to the shortest distance value between any
two points, IDIndex also keeps the first-hop door of the corresponding
shortest path. In this way, the complete shortest path between two points can
be constructed by recursively concatenating the first-hop doors.

###  3.3 Composite Indoor Index

Composite indoor index [30] (CIndex) is a layered structure for indexing
indoor partitions and moving objects. It consists of three layers: geometric
layer, topological layer, and object layer. In this study, we adapt the object
layer to index static indoor objects. A partial example CIndex for Figure 1 is
given in Figure 4.

The geometric layer uses an R*-tree [9] to index all indoor partitions, with
an additional skeleton tier to maintain the distances between staircases at
different floors. To ease the geometrical computations, it decomposes each
irregular partition333A partition is irregular if it is non-convex or
imbalanced (long in one dimension but short in the other). into regular ones
using a decomposition algorithm [30]. Referring to the bottom-right of Figure
4, the hallway $v_{10}$ is divided into two regular indoor partitions
$v_{10a}$ and $v_{10b}$ by a door $d_{16}$. Afterwards, each regular partition
is represented by a _Minimum Bounding Rectangle_ (MBR). The MBRs are indexed
by the R*-tree. As shown in the top-left of Figure 4, a non-leaf node $R_{1}$
is composed of six partitions in the leaf level, i.e., $v_{10a}$, $v_{10b}$,
and $v_{11}$-$v_{14}$.

The topological layer stores the connectivity information among indoor
partitions, and it is integrated to the tree by inter-partition links. In
particular, a leaf node $v_{i}$ in the R*-tree is linked with a pointer record
$(d_{k},{\uparrow}v_{j})$ to indicate that one can move from a partition
$v_{i}$ to another partition $v_{j}$ through door $d_{k}$. As shown in the
top-right of Figure 4, the two pointer records for $v_{13}$ mean that $v_{13}$
is adjacent to $v_{10b}$ and $v_{12}$ via $d_{13}$ and $d_{15}$, respectively.

The object layer maintains a number of object buckets each for an indoor
partition at the leaf node level of the R*-tree. Each indoor object $o$ is
kept in the bucket of the partition in which $o$ is located. In addition, an
object hashtable $\text{o-table}:O\rightarrow{}^{*}V$ maps each object to its
host partition’s pointer. Unlike [30, 31], the object buckets store static
objects in this study. As shown in the bottom-left of Figure 4, the leaf node
$v_{10a}$ is linked to its object bucket with two static objects $o_{2}$ and
$o_{4}$. Also, two corresponding records are kept in the object hashtable
(o-table).

The R*-tree in CIndex organizes partitions hierarchically, and thus enables
search space pruning for distance relevant computations. As a result, CIndex
does not cache the precomputed door-to-door distances as IDIndex does.
Moreover, as the topological layer maintains the links between partitions and
doors, which form an implicit graph structure, CIndex does not need an
explicit graph model to keep connectivity information. The topological layer’s
dynamic link updating makes CIndex adaptive to possible temporal variations of
doors.

Figure 4: An Example of CIndex (Adapted from [30])

###  3.4 IP-Tree and VIP-Tree

Indoor partitioning tree [26] (IP-Tree) is a tree-based indoor partition index
with a number of matrices each materializing the door-to-door distances within
a local range. In particular, each leaf node of IP-Tree covers a number of
topologically adjacent indoor partitions. The adjacent leaf nodes are combined
to form a non-leaf node, and adjacent non-leaf nodes are combined
hierarchically until a root node is formed. Each node $N$ has a distance
matrix and a number of access doors. An access door is a border door that
connects $N$ to its external space. $\text{AD}(N)$ denotes $N$’s access door
set. The distance matrix for a leaf node stores the shortest distance (as well
as the first-hop door on the shortest path) between every door of the leaf
node to every access door of the leaf node. The distance matrix for a non-leaf
node only stores the shortest distances and first-hop door between each pair
of access doors of its child nodes. To compute the indoor distance from a
point $p$ to a point $q$, IP-Tree locates the lowest common ancestor of the
leaf nodes Leaf$(p)$ and Leaf$(q)$, finds the access doors constituting the
shortest path in that ancestor, and connects the materialized indoor distances
involving $p$, the found access doors, and $q$.

Figure 5 shows an example of IP-Tree corresponding to Figure 1.

Figure 5: An Example of IP-Tree

The topologically adjacent partitions $v_{10}$-$v_{14}$ form a leaf node
$N_{1}$. Another leaf node $N_{2}$ is composed of partitions $v_{40}$ and
$v_{50}$. As $N_{1}$ and $N_{2}$ are connected by a border door $d_{1}$,
$d_{1}$ is put into $\text{AD}(N_{1})$ and $\text{AD}(N_{2})$. For the leaf
node $N_{1}$, the distance matrix stores the distances from each of its doors
to the access door $d_{1}$ of $N_{1}$. For instance, the distance from
$N_{1}$’s only door $d_{15}$ to access door $d_{1}$ contained by $N_{1}$ is
4.3m. Moreover, as the shortest path from $d_{15}$ to $d_{1}$ is $\langle
d_{15},d_{12},d_{1}\rangle$, the first-hop door of the path is kept as
$d_{12}$ in the matrix. Differently, for the non-leaf node $N_{0}$, the
distance matrix only keeps the distances between each pair of access doors. In
the running example, each pair of access doors are directly connected.
Therefore, no first-hop door is recorded. The storage space of each distance
matrix will double when the door directionality needs to be considered. In
other words, both the distances $\text{d2d}(d_{i},d_{j})$ and
$\text{d2d}(d_{j},d_{i})$ are kept in each node.

As a variant of IP-Tree, vivid IP-Tree (VIP-Tree) [26] further accelerates the
distance computation by materializing more precomputed information.
Specifically, each leaf node $N$ additionally maintains the shortest distance
between each door contained by $N$ and each access door in $N$’s all ancestor
nodes, along with the corresponding first-hop door information.

IP-Tree and VIP-Tree materialize a small number of distances only related to
access doors that are critical in the overall topology of an indoor space.
This design eases the on-the-fly distance related computations in spatial
query processing.

##  4 Query Processing

All the aforementioned model/indexes can be used to process indoor spatial
queries. Although query processing differs for different query types, all
algorithms share a general paradigm as follows. First, an algorithm finds the
initial indoor partition for a query. The initialization decides the indoor
partition in which the query (or source) point $p$ is located for a given
$\textsf{RQ}(p,r)$ ($k\textsf{NNQ}(p)$, $\textsf{SPQ}(p,q)$, or
$\textsf{SDQ}(p,q)$). Subsequently, an algorithm expands from the initial
partition, searching adjacent partitions via doors. Finally, the expansion
stops when the search range is beyond the query range $r$ for a
$\textsf{RQ}(p,r)$, or $k$NNs have been found for a $k\textsf{NNQ}(p)$, or the
target point $q$ is met for a $\textsf{SPQ}(p,q)$ or $\textsf{SDQ}(p,q)$.
Algorithms based on different model/indexes differ in their initializations
and expansions. Below, we present a comprehensive analytical comparison of all
model/indexes.

###  4.1 Algorithmic Comparison

Table 2 summarizes the comparison.

Table 2: Feature Comparison

Models | Precomputation | Structure | Initialization | Expansion | RQ |  $k$NNQ | SPQ | SDQ
---|---|---|---|---|---|---|---|---
IDModel | No | Graph+Mappings | Sequential scan | Dijkstra | $\triangle$ | $\triangle$ | ✓ | ✓
IDIndex | Yes | Matrix | Sequential scan | Loop | ✓ | ✓ | $\triangle$ | $\triangle$
CIndex | No | Tree+Links | R*-Tree pruning | Dijkstra | ✓ | ✓ | $\triangle$ | $\triangle$
IP-Tree | Yes | Tree+Matrix | Sequential scan | LCA | ✓ | ✓ | ✓ | ✓
VIP-Tree | Yes | Tree+Matrix | Sequential scan | LCA | ✓ | ✓ | ✓ | ✓

Table 3: Complexity Analysis

| Space | RQ |  $k$NNQ | SDQ | SPQ
---|---|---|---|---|---
IDModel | $\mathcal{O}(\mathtt{V}+\mathtt{D}+2\mathtt{V}\mathtt{d}+\mathtt{V}\mathtt{d}^{2})$ | $\mathcal{O}(\mathtt{o}\mathtt{V}\log\mathtt{D})$ | $\mathcal{O}(\mathtt{o}\mathtt{V}\log\mathtt{D})$ | $\mathcal{O}(\mathtt{V}\log\mathtt{D})$ | $\mathcal{O}(\mathtt{V}\log\mathtt{D}+\mathtt{w})$
IDIndex | $\mathcal{O}(2\mathtt{D}^{2})$ | $\mathcal{O}(\mathtt{o}\mathtt{d}\log\mathtt{D})$ | $\mathcal{O}(\mathtt{o}\mathtt{d}\log\mathtt{D})$ | $\mathcal{O}(\mathtt{d}^{2})$ | $\mathcal{O}(\mathtt{d}^{2}+\mathtt{w})$
CIndex | $\mathcal{O}(\mathtt{V}+\mathtt{V}\mathtt{d}+\mathtt{O})$ | $\mathcal{O}(\mathtt{o}\mathtt{V}\log\mathtt{D})$ | $\mathcal{O}(\mathtt{o}\mathtt{V}\log\mathtt{D})$ | $\mathcal{O}(\mathtt{V}\log\mathtt{D})$ | $\mathcal{O}(\mathtt{V}\log\mathtt{D}+\mathtt{w})$
IP-Tree | $\mathcal{O}(\rho^{2}\mathtt{f}^{2}\mathtt{L}+\rho\mathtt{D})$ | $\mathcal{O}({(\rho\log_{\mathtt{f}}\mathtt{L}})^{2}(\mathtt{V}\mathtt{o}/\mathtt{L}+\rho))$ | $\mathcal{O}({(\rho\log_{\mathtt{f}}\mathtt{L}})^{2}(\mathtt{V}\mathtt{o}/\mathtt{L}+\rho))$ | $\mathcal{O}(\rho^{2}\log_{\mathtt{f}}\mathtt{L})$ | $\mathcal{O}((\rho^{2}+\mathtt{w})\log_{\mathtt{f}}\mathtt{L})$
VIP-Tree | $\mathcal{O}(\rho^{2}\mathtt{f}^{2}\mathtt{L}+\rho\mathtt{D}\log_{\mathtt{f}}\mathtt{L})$ | $\mathcal{O}(\rho^{2}\log_{\mathtt{f}}\mathtt{L}(\mathtt{V}\mathtt{o}/\mathtt{L}+\rho))$ | $\mathcal{O}(\rho^{2}\log_{\mathtt{f}}\mathtt{L}(\mathtt{V}\mathtt{o}/\mathtt{L}+\rho))$ | $\mathcal{O}(\rho^{2})$ | $\mathcal{O}(\rho^{2}+\mathtt{w})$

Distance Precomputation. IDModel and CIndex do not precompute any indoor
distances, whereas IDIndex and IP-Tree/VIP-Tree maintain some door-to-door
distances before query processing. In particular, IDIndex precomputes the
shortest indoor distances between every pair of doors, but IP-Tree/VIP-Tree
only keeps a small number of distances in each tree node.

Model/Index Structure. IDModel is a labeled graph with distance mapping
functions, whereas IDIndex materializes two matrices for global door-to-door
distances. Employing a tree-based structure, CIndex keeps topological
information incrementally by maintaining inter-partition links, whereas IP-
Tree/VIP-Tree augments each tree node with a local distance matrix. More
importantly, CIndex forms the non-leaf tree nodes according to the geometrical
proximity of partitions, whereas IP-Tree/VIP-Tree do so based on the
topological proximity of partitions.

Query Types. All model/indexes can support all the four query types. However,
IDModel [22] does not provide RQ and $k$NNQ algorithms. In this study, we
implement two algorithms as presented in Appendix. Also, there are no off-the-
shelf SPQ and SDQ algorithms for IDIndex and CIndex. Nevertheless, the global
door-to-door distances and the corresponding last-hop door information in
IDModel can be used to expand path searching in SPQ and SDQ algorithms for
IDIndex. For CIndex, the inter-partition links can be used to support path
expansion.

Initialization. To decide the initial indoor partition for a query, IDModel
and IDIndex sequentially scan all partitions. Enabled by the R*-tree indexing
partitions, CIndex can quickly find the host partition of any indoor point. In
contrast, IP-Tree and VIP-Tree are based on pure topological relationships
among partitions, and thus they also sequentially scan all partitions.

Expansion. As a graph-based model, IDModel expands to the next unvisited door
in the spirit of Dijkstra’s algorithm [17]. CIndex does so as well since the
next-hop doors are captured in the inter-partition links on the topological
layer. Instead of expanding via directly connected doors, IP-Tree/VIP-Tree
finds the lowest common ancestor (LCA) node of $p$ and $q$ and locates the
intermediate access doors on the shortest path straightforwardly. It is
noteworthy that IDIndex alone cannot support topological door expansion.
Instead, IDIndex relies on an underlying IDModel to loop through relevant
indoor partitions’ doors.

###  4.2 Complexity Analysis

Let $\mathtt{V}$, $\mathtt{D}$, $\mathtt{O}$ be the total number of indoor
partitions, doors, and indoor objects, respectively. Let $\mathtt{d}$ and
$\mathtt{o}$ be the average door number and average object number per
partition, respectively. Let $\mathtt{w}$ be the average number of door nodes
on a shortest path. For IP-Tree/VIP-Tree, we use $\mathtt{f}$ to denote the
fan-out of the tree node, $\rho$ the average access door number per node, and
$\mathtt{L}$ the total number of leaf nodes. Table 2 summarizes the space
complexity of all model/indexes and their time complexity for queries.

Space Complexity. IDModel $(V,E_{a},L,$ $f_{\text{dv}},f_{\text{d2d}})$’s
space complexity is
$\mathcal{O}(\mathtt{V}+\mathtt{V}\mathtt{d}+\mathtt{D}+\mathtt{V}\mathtt{d}+\mathtt{V}\mathtt{d}^{2})$
= $\mathcal{O}(\mathtt{V}\mathtt{d}^{2})$. IDIndex’s space complexity is
$\mathcal{O}(2\mathtt{D}^{2})$ = $\mathcal{O}(\mathtt{D}^{2})$ as it consists
of two door matrices. CIndex’s space complexity is
$\mathcal{O}(\mathtt{V}+\mathtt{V}\mathtt{d}+\mathtt{O})$ =
$\mathcal{O}(\mathtt{V}\mathtt{d}+\mathtt{O})$ where $\mathtt{V}$,
$\mathtt{V}\mathtt{d}$, and $\mathtt{O}$ correspond to partition R*-tree,
inter-partition links, and object hashtable, respectively. IP-Tree’s space
cost mainly consists of the distance matrices for leaf nodes and those for
non-leaf nodes. The former’s complexity is $\mathcal{O}(\rho\mathtt{D})$ and
the latter’s is $\mathcal{O}((\rho\mathtt{f})^{2}\mathtt{L})$ where
$\rho\mathtt{f}$ corresponds to the number of access doors from a child node
and $\mathtt{L}$ reflects the number of non-leaf nodes. In contrast, VIP-
Tree’s space cost on the distance matrices for leaf nodes is
$\mathcal{O}(\rho\mathtt{D}\log_{\mathtt{f}}\mathtt{L})$, where
$\log_{\mathtt{f}}\mathtt{L}$ corresponds to the ancestor number of each leaf
node.

Time Complexity for RQ and $k$NNQ. RQ and $k$NNQ have similar time complexity
as they both prune objects based on shortest distances. IDModel’s search
expands via qualified doors by graph traversal in
$\mathcal{O}(\mathtt{V}\log\mathtt{D})$ and iterates on the objects in each
visited partition in $\mathcal{O}(\mathtt{o})$. Also based on graph traversal,
the search on CIndex obtains a subgraph in
$\mathcal{O}(\mathtt{V}\log\mathtt{D})$ and visits all objects in each
partition of the subgraph in $\mathcal{O}(\mathtt{o})$. IDIndex’s search
expands to the nearest partitions based on the sorted result in
$M_{\text{idx}}$, and loops through each object in the expanded partition. So
its time complexity is $\mathcal{O}(\mathtt{o}\mathtt{d}\log\mathtt{D})$. The
searches via IP-Tree and VIP-Tree work similarly. They prune a tree node based
on its distance from the query point in
$\mathcal{O}(\log_{\mathtt{f}}\mathtt{L}\cdot\rho\cdot c)$, where $c$ is the
unit SDQ cost. Then, they qualify each object in the remaining nodes in
$\mathcal{O}(\log_{\mathtt{f}}\mathtt{L}\cdot\mathtt{V}/\mathtt{L}\cdot\mathtt{o}\cdot
c)$. Given the SDQ complexity
$\mathcal{O}(\rho^{2}\log_{\mathtt{f}}\mathtt{L})$ for IP-Tree and
$\mathcal{O}(\rho^{2})$ for VIP-Tree (to be detailed below), their RQ and
$k$NNQ complexities are
$\mathcal{O}({(\rho\log_{\mathtt{f}}\mathtt{L}})^{2}(\mathtt{V}\mathtt{o}/\mathtt{L}+\rho))$
and
$\mathcal{O}(\rho^{2}\log_{\mathtt{f}}\mathtt{L}(\mathtt{V}\mathtt{o}/\mathtt{L}+\rho))$,
respectively.

Time Complexity for SDQ and SPQ. For the graph traversal algorithms of IDModel
and CIndex, the SDQ complexity is $\mathcal{O}(\mathtt{V}\log\mathtt{D})$ and
SPQ complexity is $\mathcal{O}(\mathtt{V}\log\mathtt{D}+\mathtt{w})$ with
additional cost to backtrack the shortest path in $\mathtt{w}$ hops. For
IDIndex, the only cost of SDQ is to loop through two door sets corresponding
to $p$ and $q$ by a complexity of $\mathcal{O}(\mathtt{d}^{2})$. The extra
cost of SPQ to concatenate shortest path is of $\mathcal{O}(\mathtt{w})$. For
IP-Tree, SDQ needs to search the lowest common ancestor and then find a pair
of access doors from that ancestor node, resulting in a complexity of
$\mathcal{O}(\rho^{2}\log_{\mathtt{f}}\mathtt{L})$. In contrast, VIP-Tree
materializes the distances from a leaf node to each access door in the
ancestors. Its SDQ complexity is $\mathcal{O}(\rho^{2})$. The additional cost
to construct shortest path in SPQ is
$\mathcal{O}(\mathtt{w}\log_{\mathtt{f}}\mathtt{L})$ for IP-Tree and
$\mathcal{O}(\mathtt{w})$ for VIP-Tree.

##  5 Benchmark

In this section, we detail the benchmark for evaluating the indoor spatial
query techniques (model/indexes and algorithms). All code and data can be
found at https://github.com/indoorLBS/ISQEA.

###  5.1 Datasets

We use four very different indoor space datasets, each featuring a distinctive
indoor topology. The floorplans are briefly represented and illustrated in
Figure 6. The data statistics are given in Table 4.

Figure 6: Floorplan of Datasets.

Synthetic Building (SYN) is a $n$-floor building. Its each floor is from a
real-world floorplan [1] of 1368m $\times$ 1368m with 141 partitions and 216
doors. Its each two adjacent floors are connected by four 20m long stairways.
By default, we set $n=5$ and get the default dataset SYN5. To study the effect
of topological changes, from SYN5 we derived SYN5- with fewer doors and SYN5+
with more doors. Note that varying the door number will significantly change
the connectivity and accessibility of the partitions, leading to a major
topological change. We also form SYN50 in which the hallways are not
decomposed444We precompute the door-to-door distance matrix for each hallway
when it is not decomposed. The hallways are of irregular and concave shapes,
and thus the door-to-door distance in a hallway can not use the Euclidean
distance..

Menzies Building (MZB) [2] is a landmark building at Clayton campus of Monash
University. Each floor takes approximately 125m $\times$ 35m and connects to
adjacent floors by two or four stairways each being 5m long. In total, there
are 1344 partitions (including 34 staircases and 85 hallways) and 1375 doors.
By changing the hallway decomposition, we form MZB0 in which the hallways are
not decomposed and MZBΔ in which the hallways are decomposed into more
partitions than default.

Hangzhou Shopping Mall (HSM) is a 7-floor mall in Hangzhou, China, occupying
2700m $\times$ 2000m. Ten stairways connect each two adjacent floors. Each
floor contains 150 partitions and 299 doors on average. In total, there are
1050 partitions (including 70 staircases and 133 hallways) and 2093 doors.

Copenhagen Airport (CPH) refers to the ground floor of Copenhagen Airport [3],
taking around 2000m $\times$ 600m with 147 partitions (including 25 hallways)
and 211 doors.

Overall Analysis of Different Datasets. The statistics of the datasets are
given in Table 4. We use $\\#dv$ to denote the number of doors in a partition,
and conduct quartile statistics [6] on $\\#dv$. In Table 4,
$\mathsf{Q1}(\\#dv)$, $\mathsf{Q2}(\\#dv)$, and $\mathsf{Q3}(\\#dv)$ denote
the first, second, third quartiles of $\\#dv$, respectively, and $\max(\\#dv)$
denotes the maximum value of $\\#dv$. In addition, we also plot the
distributions of $\\#dv$ over all partitions in each dataset in Figure 7.

Table 4: Statistics of Datasets

Datasets | SYN | MZB | HZM | CPH |  SYN5- |  SYN5+ |  SYN50 |  MZB0 |  MZBΔ
---|---|---|---|---|---|---|---|---|---
Scale of Space | Floors | $n$ | 17 | 7 | 1 | 5 | 5 | 5 | 17 | 17
Doors |  216$n$ | 1375 | 2093 | 211 | 840 | 1280 | 880 | 1308 | 1480
Partitions |  141$n$ | 1344 | 1050 | 147 | 705 | 705 | 505 | 1276 | 1449
Hallways |  41$n$ | 85 | 483 | 72 | 205 | 205 | 5 | 17 | 190
Crucial Partitions |  8$n$ | 52 | 133 | 20 | 20 | 40 | 5 | 19 | 157
Length(m) | 1368 | 125 | 2700 | 2000 | 1368 | 1368 | 1368 | 125 | 125
| Width(m) | 1368 | 35 | 2000 | 600 | 1368 | 1368 | 1368 | 35 | 35
Door per Partition | $\mathsf{Q1}(\\#dv)$ | 2 | 1 | 2 | 1 | 1 | 2 | 1 | 1 | 1
$\mathsf{Q2}(\\#dv)$ | 2 | 1 | 4 | 2 | 1 | 3 | 2 | 1 | 1
$\mathsf{Q3}(\\#dv)$ | 4 | 1 | 5 | 4 | 3 | 4 | 3 | 1 | 1
$\max(\\#dv)$ | 10 | 56 | 17 | 12 | 10 | 10 | 132 | 82 | 47

Figure 7: Distribution of $\\#dv$ (number of doors in a partition) on (a)
SYN5, (b) MZB, (c) HSM, and (d) CPH. Table 5: Evaluation Settings (Default
Parameters in Bold)

Symbol & Meaning | Task | Metrics | Queries | Dataset | Parameter Setting
---|---|---|---|---|---
$n$ | floor number | A | a1, a2 | - | SYN | 3, 5, 7, 9
B1 |  b1, b2, b3 (only for SPDQ) |  RQ, $k$NNQ, SPDQ
$|O|$ | object number | B2 | b1, b2 |  RQ, $k$NNQ | all |  500, 1000, 1500, 2000, 2500
$r$ |  range value | B3 | b1, b2 | RQ | SYN5, HZM, CPH |  200, 400, 600, 800, 1000
MZB |  20, 40, 60, 80, 100
$k$ | - | B4 | b1, b2 |  $k$NNQ | all |  1, 5, 10, 50, 100
s2t |  source-target distance | B5 | b1, b2, b3 | SPDQ | SYN5, HZM, CPH |  1100, 1300, 1500, 1700, 1900
MZB |  30, 60, 90, 120, 150
- | topological change | B6 |  b1, b2, b3 (only for SPDQ) |  RQ, $k$NNQ, SPDQ | SYN |  SYN5-, SYN5, SYN5+
- | decomposition method | B7 | b1, b2, b3 (only for SPDQ) | RQ, $k$NNQ, SPDQ | SYN |  SYN50, SYN5
MZB |  MZB0, MZB, MZBΔ

Based on the space scale information and door distribution information from
Table 4 and Figure 7, we summarize the characteristics of each dataset as
follows.

  * •

SYN: The overall space is square and regular. The number of doors and
partitions in each floor is medium (216 doors and 141 partitions per floor).
The door density within each partition is small (with $\mathsf{Q2}$ equals
only 2).

  * •

MZB: The overall space is long and narrow with large scale crucial partitions.
The number of doors and partitions in each floor is relatively small (80.4
doors and 76.8 partitions on average), whereas the overall size of doors and
partitions is large due to the floor number. The planning of doors is rather
skewed in that most partitions have only 1 or 2 doors while there are some
crucial partitions that accommodate 56 doors (as shown in Figure 7(b)).

  * •

HSM: The overall space is long and relatively narrow. The number of doors and
partitions in each floor is medium and the overall size of doors and
partitions is large. The planning of doors is regular and door density in each
partition is medium ($\mathsf{Q2}$ and $\mathsf{Q3}$ are equal to 4 and 5,
respectively).

  * •

CPH: The space is long, narrow yet open, resulting in a small number of doors
and partitions. The door distribution is regular and door density in each
partition is small ($\mathsf{Q2}$ equals 2).

###  5.2 Object/Query Workload Generation

For each dataset, we randomly generated a set $O$ of valid points as static
objects, each object in $O$ falling in an indoor partition. To test the effect
of different object numbers, we vary $|O|$ as 500, 1000, 1500, 2000 and 2500.

The augment generation for each query type is detailed below.

$\textsf{RQ}(p,r)$. We vary the range value $r$ according to the predefined
values in Table 5 (default values in bold). For each $r$, we generate ten RQ
instances with a random $p$ in the indoor space.

$k\textsf{NNQ}(p)$. Similar to RQ generation, we generate ten random
$k\textsf{NNQ}$ instances for each $k$ value given in Table 5.

As SPQ and SDQ can be integrated into one search procedure, we use
$\textsf{SPDQ}(p,q)$ to denote the integrated query that returns the shortest
path from $p$ to $q$ along with the corresponding shortest distance value. In
the following sections, we evaluate search performance of SPDQ only.

$\textsf{SPDQ}(p,q)$. We use a parameter s2t to control the shortest distance
from the source $p$ and target $q$. Its parameter values are listed in Table
5. For each s2t, we generate ten different $(p,q)$ pairs to form SPDQ
instances as follows. First, we randomly select an indoor point $p$ and find a
door $d$ whose indoor distance from $p$ approximates s2t. Next, we expand from
$d$ to find a random point $q$ whose indoor distance from $p$ approximates
s2t.

###  5.3 Model/Index Settings

IDModel. For each partition instance $v_{i}$, we implemented the door-to-door
distance mapping $f_{\text{d2d}}(v_{i},\cdot,\cdot)$ as a 2D array, and door-
to-partition distance mapping $f_{\text{dv}}(\cdot,v_{i})$ as an 1D array.
Besides, the partition mappings $\mathit{P2D}_{\sqsupset}(v_{i})$ and
$\mathit{P2D}_{\sqsubset}(v_{i})$ (cf. Section 2.1) were implemented as lists
and attached to their corresponding instance $v_{i}$. Further, the door
mappings $\mathit{D2P}(d_{i})$, $\mathit{D2P}_{\sqsupset}(d_{i})$, and
$\mathit{D2P}_{\sqsubset}(d_{i})$ were implemented as lists associated with
the door instance $d_{i}$.

IDIndex. The distance matrix and distance index matrix were implemented as 2D
arrays.

CIndex. Since the partitions in the datasets rarely intersect, we used an
R-tree instead of R*-tree to index partitions while preserving roughly the
same spatial search performance. We set the tree fan-out to 20 as suggested in
a previous work [30]. Each partition’s inter-partition links were maintained
in an inner list.

IP-Tree and VIP-Tree. We set the minimum children degree to 2 when
constructing non-leaf tree nodes, as suggested in [26]. As each leaf node
maintains the shortest distance for each pair of doors in it, the computation
will be complicated if a leaf node contains too many “crucial partitions” that
each has many doors. Following work [26], we designate that each leaf node can
only contain one crucial partition and regard a partition as crucial partition
if its door number exceeds a threshold $\gamma$. We tuned optimal $\gamma$ for
different datasets, namely 6, 4, 7, and 5 for SYN, MZB, HZM, and CPH,
respectively.

###  5.4 Performance Evaluation Procedure

Concerning model construction and query processing, the following tasks are
implemented to evaluate each model/index. For each task, a parameter is varied
with others fixed to default. Table 5 lists all the evaluation settings.

  * A

Model Construction. We evaluate the space and time efficiency of a model/index
using two metrics: (a1) model size and (a2) construction time. In this task,
we use synthetic datasets, varying the number of floors.

  * B

Query Processing. We evaluate the search efficiency of a given query type. The
metrics are (b1) running time, (b2) memory use, and (b3) number of visited
doors (NVD) for SPDQ.

    * B1

Effect of Floor Number $n$. Using SYN with floor number $n$ varied from 3 to
9, we test the search efficiency for each indoor spatial query algorithm.

    * B2

Effect of Object Number $|O|$. To test RQ and $k$NNQ, we vary $|O|$ from 500
to 2500 in all datasets.

    * B3

Effect of Range Distance $r$. We vary and test the augment $r$ of RQ. In
particular, we vary $r$ from 200m to 1000m in SYN5, HZM and CPH, and from 20m
to 100m in MZB.

    * B4

Effect of $k$. We vary and test $k$NNQ’s augment $k$ from 1 to 100 in all
datasets.

    * B5

Effect of Source-Target Distance s2t. To test SPDQ, we vary s2t from 1100m to
1900m in SYN5, HZM, and CPH, and from 30m to 150m in MZB.

    * B6

Effect of Topological Change. We vary indoor topology by changing the door
number from 840 to 1280 in SYN5 and obtain SYN5- and SYN5+.

    * B7

Effect of Hallway’s Decomposition Method. We use SYN5 and MZB with the derived
datasets, SYN50, MZB0 and MZBΔ.

##  6 Results Analysis

This section reports and analyzes the experimental results. All experiments
are implemented in Java and run on a MAC with a 2.30GHz Intel i5 CPU and 16 GB
memory.

###  6.1 Model/Index Construction

We vary the floor number $n$ on SYN and obtain four variants SYN3, SYN5, SYN7,
and SYN9. We construct the five model/indexes (cf. Section 3) and report their
size and construction time in Figures 9 and 9. The cost of maintaining static
objects is excluded as it is the same for all model/indexes.

  * •

According to the results on SYN3 to SYN9 in Figure 9, each model/index’s size
increases steadily with a larger floor number. When there are more doors and
partitions, more storage space is needed to handle the indoor space.

  * •

Among all, IDModel construction requires the least costs on storage (Figure 9)
and time (Figure 9). This is because IDModel is extended based on a simple
graph model and maintains only a small amount of geometric information
locally. For large-scale and complex-topology spaces (e.g., SYN9, MZB, and
HZM), IDModel has clearer advantages over the tree-based indexes (i.e., IP-
Tree and VIP-Tree).

  * •

As expected, IDIndex always takes much time and storage to construct due to
its global door-to-door distance precomputation. When there are many doors, it
is difficult to fit the corresponding matrices in memory. In comparison, IP-
Tree and VIP-Tree precompute less information and therefore their consumptions
on time and storage are medium.

  * •

In addition to maintaining the topology, CIndex needs to construct a partition
R-tree. Therefore, it incurs extra time and space overheads compared to
IDModel.

Figure 8: Model Size

Figure 9: Construction Time

###  6.2 Query Processing

All results are averaged over 10 queries (cf. Section 5.2).

B1 Effect of Floor Number $n$ (using SYN)

RQ and $k$NNQ: The query time and memory use for RQ are reported in Figures 13
and 13, respectively, and those for $k$NNQ are reported in Figures 13 and 13,
respectively.

  * •

For both query types, IDIndex always runs fastest as shown in Figures 13 and
13, unaffected by the varying floor number $n$. The price behind this is to
maintain the memory-resident distance matrices, which increases rapidly with
$n$. Referring to Figures 13 and 13, when $n$ grows to 9, IDIndex requires up
to 1600MB of memory on both queries.

  * •

On each SYN dataset, IP-Tree and VIP-Tree need more time to complete the two
queries. Through analysis, we found that the two indexes need to prune tree
nodes when searching for qualified objects. In the absence of global door-to-
door distances, they need a lot of on-the-fly calculations to get the shortest
distance from a query point to a tree node. Being consistent with the
complexity analysis in Table 3, VIP-Tree outperforms IP-Tree for both queries.
However, due to the good scalability of the tree structure, both indexes’
running time is relatively stable as shown in Figures 13 and 13.

  * •

IDModel and CIndex perform similarly, and their execution time increases with
a larger $n$ (Figures 13 and 13). When $n$ increases, IDModel has a slight
advantage as CIndex costs more time in space pruning. In terms of memory
overhead, the two indexes are almost the same.

Figure 10: RQ Time
vs. $n$

Figure 11: RQ Memory
vs. $n$

Figure 12: $k$NNQ Time
vs. $n$

Figure 13: $k$NNQ Memory vs. $n$

SPDQ: The running time, memory use, and number of visited doors (NVD) are
reported in Figures 16, 16, and 16, respectively.

  * •

IDIndex’s running time and NVD are insensitive to the increasing floor number
$n$. However, its memory use grows moderately as $n$ increases. In the case of
SPQ and SDQ, we recommend using IDIndex when the door size is relatively
small.

  * •

In contrast to IDIndex, the memory of IDModel and CIndex is relatively stable
(Figure 16), and their query performance deteriorates as the space scale
increases (Figure 16).

  * •

IP-Tree and VIP-Tree achieve clearly good performance on SPDQ, in both running
time and memory use. Unlike IDIndex that precomputes global door-to-door
distances or IDModel and CIndex that compute distances on the fly, IP-Tree and
VIP-Tree cache relevant distance information only for those access doors on
shortest paths. Thus, without degrading query performance, they only incur
slightly more memory overhead than IDModel and CIndex (Figures 16 and 16).

Figure 14: SPDQ Time vs. $n$

Figure 15: SPDQ Memory vs. $n$

Figure 16: NVD in SPDQ vs. $n$

B2 Effect of Object Number $|O|$

RQ: With different sizes of $O$, the running time and memory use are reported
in Figures 17 and 18, respectively.

  * •

Algorithms based on different model/indexes are almost insensitive to $|O|$ in
running time, implying that each is able to prune irrelevant objects
effectively and stop searching early. A larger $|O|$ results in higher object
density in an indoor space. This tends to increase the query processing time
in general, as the query algorithms need to process larger object buckets.
However, this impact is negligible according to the results in Figure 17. This
implies that all model/indexes are good at pruning indoor partitions and thus
object buckets when processing RQ.

  * •

Referring to Figure 17, IDIndex runs faster than others by several orders of
magnitude in all datasets, thanks to its precomputed global door-to-door
distances. However, it also requires memory an order of magnitude higher to
store the distance matrix (Figure 18). A special case occurs on CPH (Figure
18(d)) that IP-Tree and VIP-Tree consume more memory than others. First, the
door number of CPH is quite small such that the matrices of IDIndex are not
large. Second, as there are fewer access doors, IP-Tree/VIP-Tree involves
heavy on-the-fly computations on distances between doors and non-leaf nodes
and thus needs more memory for the intermediate results.

  * •

On each dataset, IDModel and CIndex incur almost the same execution time (see
Figure 17), as they both use graph traversal to search for objects. Under
complex indoor topology, CIndex using R-tree does not have much advantage in
spatial pruning.

  * •

IP-Tree and VIP-Tree perform differently on different datasets. They
outperform IDModel and CIndex on MZB but are worse on the others (see Figure
17). Recall that MZB features some crucial partitions having up to 56 doors.
In such a case, the efficiency of graph traversal is much lower than searching
on the tree structure. On the contrary, when the number of candidate doors for
the next hop is relatively small, the graph-based search algorithms are
advantaged in range queries. Therefore, we recommend using IP-Tree/VIP-Tree to
perform RQ in spaces with very large main corridors.

  * •

Referring to Figure 17, VIP-Tree is generally faster than IP-Tree because of
more cached distances. IP-Tree needs to compute more intermediate results on
the fly. However, memory use is close between the two (see Figure 18).

Figure 17: RQ Time vs. $|O|$

Figure 18: RQ Memory vs. $|O|$

$k$NNQ: Figures 19 and 20 report $|O|$’s impact on the time and memory costs,
respectively. In general, each model/index’s performance on $k$NNQ exhibits
similar trend as that on RQ.

  * •

Referring to Figure 19, the time cost of each algorithm on each dataset
remains stable, showing that large object workloads (and high object density)
have little effect on all models.

  * •

On datasets with relatively large numbers of doors and partitions (i.e., SYN5,
MZB, and HSM), IDIndex runs faster by orders of magnitude. However, its memory
use is clearly larger.

  * •

On one-floor CPH with small numbers of doors and partitions, IP-Tree and VIP-
Tree incur more running time as well as higher memory use (Figures 19(d) and
20(d)). However, they run faster on MZB (Figure 19(b)) in which many access
doors exist due to many crucial partitions (see Table 4).

  * •

IDModel and CIndex perform comparably as shown in Figures 19 and 20. Without a
specially designed partition R-tree, IDModel achieves quite good object
pruning due to the efficient distance mapping maintained in its edges and
vertexes.

Figure 19: $k$NNQ Time vs. $|O|$

Figure 20: $k$NNQ Memory vs. $|O|$

B3 Effect of Range Distance $r$

RQ: The time and memory costs with respect to varied $r$ are reported in
Figures 21 and 22, respectively.

  * •

On SYN5, MZB, and HSM with complex indoor topology, IDIndex’s running time
reported in Figure 21 increases slowly with a growing $r$. In contrast, on the
simple-topology CPH, the advantage of IDIndex over others is not marked.

  * •

IDModel and CIndex perform well on all datasets, except on MZB (Figure 21(b))
that has a large number of crucial partitions. This again reflects the
disadvantages of the graph-based traversal algorithms when dealing with this
particular topology type. Nevertheless, through efficient node search and on-
the-fly distance computation, these two model/indexes always have the smallest
memory overhead.

  * •

When increasing $r$, the running time of IP-Tree and VIP-Tree in Figure 21
increase steadily on all datasets. A larger $r$ needs to consider a tree node
farther from the node where the query point is located, and thus introduces
more computations on the distance from a door to some non-leaf nodes. As the
distance to the access door of each ancestor node is materialized at the leaf
node, VIP-Tree runs faster than IP-Tree.

Figure 21: RQ Time vs. $r$

Figure 22: RQ Memory vs. $r$

B4 Effect of $k$

$k$NNQ: The time and memory costs with respect to different $k$ values are
reported in Figures 23 and 24, respectively.

  * •

Similar to increasing $r$ value in RQ, increasing $k$ leads to more search
time by each model/index according to the results reported in Figure 23. Among
them, IDIndex’s running time increases slowest. In addition, IP-Tree/VIP-Tree
show exponential growth on SYN, HSM, and CPH. This is because the two indexes
need to access the topologically far-away partitions and compute the distances
to them on the fly when $k$ is large.

  * •

Considering both time and memory costs, IDModel and CIndex achieve a good
balance when searching for nearest neighbor objects (see Figures 23 and 24).

Figure 23: $k$NNQ Time vs. $k$

Figure 24: $k$NNQ Memory vs. $k$

Figure 25: SPDQ Time vs. s2t

Figure 26: SPDQ Memory vs. s2t

Figure 27: NVD in SPDQ vs. s2t

B5 Effect of Source-Target Distance s2t

SPDQ: The time cost, memory use, and NVD for different s2t values are reported
in Figures 25, 26, and 27, respectively.

  * •

IDIndex runs the fastest and is not affected by s2t as reported in Figure 25.
As only a small number of doors are required to process after the source point
and before the target point, its NVD is always small (Figure 27).
Nevertheless, its global distance matrix takes up a lot of memory (Figure 26).

  * •

IDModel and CIndex use the same graph search process. Note that because the
Euclidean distance is no larger than the indoor distance, using R-tree to
prune space by Euclidean distance does not really reduce the number of doors
to visit. Therefore, the two models’ NVDs in Figure 27 are almost the same.
Also, as s2t increases, the candidate space becomes larger and the running
time of the two becomes longer (see Figure 25).

  * •

On MZB and HSM (Figure 25(b) and (c)), VIP-Tree achieves query performance
comparable to IDIndex that precomputes door-to-door distances. Both MZB and
HSM are large-scale and have over 1000 doors. In the routing process based on
VIP-Tree, the precomputed distances in non-leaf nodes greatly accelerate the
expansion to the target point. Therefore, VIP-Tree is particularly suitable
for the shortest path search in indoor spaces with complex structures.

Figure 28: RQ Time vs.
Topology

Figure 29: RQ Memory
vs. Topology

Figure 30: $k$NNQ Time
vs. Topology

Figure 31: $k$NNQ Memory vs. Topology

Figure 32: SPDQ Time
vs. Topology

Figure 33: SPDQ Memory
vs. Topology

Figure 34: NVD in SPDQ
vs. Topology

Figure 35: RQ Time
vs. Decomposition

Figure 36: RQ Memory
vs. Decomposition

Figure 37: $k$NNQ Time
vs. Decomposition

Figure 38: $k$NNQ Memory
vs. Decomposition

Figure 39: SPDQ Time
vs. Decomposition

Figure 40: SPDQ Memory vs. Decomposition

Figure 41: NVD in SPDQ
vs. Decomposition

B6 Effect of Topological Change

RQ and $k$NNQ: The time cost and memory use with respect to different topology
characteristics are reported in Figures 31, 31, 31, and 31, respectively.

  * •

Regarding the time cost, IDIndex runs fastest, but it needs large memory to
store the door-to-door distance matrix. With increasing number of doors, its
time cost and memory use increase steadily.

  * •

IDModel and CIndex use the smallest memory when processing RQ and $k$NNQ.
Regarding the time cost, they perform medium. When the topology becomes more
complex, the memory use keeps stable and the time cost increases slightly.

  * •

IP-Tree and VIP-Tree cost more time to process RQ and $k$NNQ. Moreover, when
the topology becomes more complex, the time cost rises rapidly. E.g., RQ’s
time cost using IP-Tree grows nearly 20 times from SYN5- to SYN5+ (see Figure
31).

SPDQ: The time cost, memory use and NVD with respect to different topology
characteristics are reported in Figures 34, 34, and 34, respectively.

  * •

Like in the other cases, IDIndex performs best in terms of the time cost but
costs most memory compared with others. When the topology becomes complex,
IDIndex’s time cost increases relatively slightly, while the memory use grows
fast.

  * •

Considering time cost and memory use, IP-Tree and VIP-Tree perform best with
relatively less time cost and smaller memory use. Regarding the time cost,
VIP-Tree is always better than IP-Tree because of the extra precomputation,
but it needs more memory. With the doors increasing, the time cost and memory
use rise slightly.

  * •

IDModel and CIndex performs worst in both time and memory costs because they
have to visit many doors in search.

B7 Effect of Decomposition Methods for Hallways

RQ, $k$NNQ and SPDQ: Regarding RQ and $k$NNQ, the time cost and memory use of
different decomposition methods are reported in Figures 38, 38, 38, and 38.
For SPDQ, the time cost, memory use and NVD with respect to different
decomposition methods are reported in Figures 41, 41, and 41.

  * •

IDIndex runs fastest when processing RQ and $k$NNQ but uses most memory. When
hallways are decomposed into more partitions, IDIndex’s time cost keeps nearly
stable but its memory cost increases. This is because there are more doors
connecting increased numbers of partitions, which leads to more door-to-door
pairs stored in the distance matrix.

  * •

IDModel and CIndex use the least memory but runs slowest. With more
partitions, both time cost and memory use decrease because hallways are
decomposed into more partitions each having less doors to process.

  * •

IP-Tree and VIP-Tree perform best considering both time cost and memory use.
However, when hallways are decomposed into more partitions, the two methods
need more time and memory to process RQ and $k$NNQ. Regarding the performance
in RQ, IP-Tree and VIP-Tree cost more time than IDModel. There are more nodes
in IP-Tree and VIP-Tree when hallways are decomposed into more partitions,
which entails more on-the-fly computations to prune tree nodes when processing
RQ and $k$NNQ. Moreover, the time cost of IP-Tree and VIP-Tree rises faster
when processing RQ and $k$NNQ than processing SPDQ. That is because there is
some extra cost to prune nodes when processing RQ and $k$NNQ. As the nodes
increase, this extra cost increases fast.

Summary of Findings

  * •

IDModel requires minimum time and space costs in construction. Moreover, it
works well for RQ and $k$NNQ due to its good balance in execution time and
memory use. However, it is inferior to IP-Tree and VIP-Tree for SPQ and SDQ.
The more partitions the hallways are decomposed into, the better IDModel
performs, while IP-Tree and VIP-Tree the worse.

  * •

IDIndex runs fastest for all types of indoor spatial queries. However, it
requires significantly large time to construct offline and high memory
consumptions during query processing. In general, it is suitable for indoor
spaces with relatively small numbers of doors.

  * •

CIndex is intended for handling indoor moving objects and therefore it
performs only comparably to IDModel when processing the four queries on static
space and objects.

  * •

IP-Tree and VIP-Tree are optimized for SPQ/SDQ tasks. In particular, their
advantages stand out when the indoor space accommodates a certain number of
crucial partitions that are connected by so-called access doors. VIP-Tree
gains better search efficiency than IP-Tree at the cost of extra storage
overhead for precomputed local distances. Their construction costs are in the
middle among all five proposals under investigation.

In summary, IDIndex is preferred for small-scale spaces. VIP-Tree is
recommended if routing is the task or the space accommodates crucial
partitions. For other scenarios, IDModel is recommended due to its low
construction cost and good balance in terms of storage and query time costs.

##  7 Extensibility Analysis

Table 6 summarizes the extensibility of all model/indexes.

Table 6: Extensibility Analysis | IDModel | IDIndex | CIndex | IP/VIP-Tree
---|---|---|---|---
| Temporal Variation
---
✓ | X | ✓ | X
| Moving Objects
---
✓ | ✓ | ✓ | ✓
| Uncertain Locations
---
X | X | ✓ | X
Keywords | ✓ | ✓ | ✓ | ✓

Temporal Variation. Indoor topology may feature temporal variations, e.g.,
doors may have open and close hours. To support indoor spatial queries in such
cases, temporal variation information like open and close time for doors can
be maintained as a table attached to the accessibility base graph of IDModel
or the topological layer of CIndex [21]. However, frequent temporal variations
are very hard to handle for IDIndex and IP-Tree/VIP-Tree because they need to
precompute door-to-door distances globally or locally.

Moving Objects. All model/indexes can index moving objects by maintaining
dynamic object buckets attached to indoor partitions in the way similar to how
we handle the static objects. Nevertheless, the buckets need to be updated
appropriately for indoor moving objects.

Uncetain Locations. In some settings, indoor points or objects are represented
as uncertain regions. To process indoor spatial queries over uncertain
locations, a model/index should support geometric operations on partitions. As
a result, only CIndex with partition R*-tree excels at handling uncertain
locations [30, 31].

Keywords. A spatial keyword query [11] returns objects or paths that are
spatially and textually relevant to user-specified location(s) and keyword(s).
Such queries can be supported if we extend the model/indexes by additionally
maintaining mappings between partitions/objects and keywords. Specially,
top-$k$ keyword-aware shortest path queries have been supported based on
IDModel [14], and boolean $k$NN spatial keyword queries have been supported
based on VIP-Tree [27].

##  8 Conclusion and Future Work

This work reports on an extensive experimental evaluation of five indoor space
model/indexes that support four typical indoor spatial queries, namely range
query (RQ), $k$ nearest neighbor query ($k$NNQ), shortest path query (SPQ),
and shortest distance query (SDQ). Our evaluation concerns the costs in
model/index construction and query processing using a model/index. By
analyzing the results, we summarize the pros and cons of all techniques and
suggest the best choice for typical scenarios.

For future work, an interesting direction is to consider more semantic
information in the model/indexes. It is also interesting to adapt the existing
model/indexes to handle indoor moving objects and support more query types on
moving objects.

## References

  * [1] https://deviantart.com/mjponso/art/Floor-Plan-for-a-Shopping-Mall-86396406.  Accessed May 28, 2020.
  * [2] https://www.monash.edu/virtual-tours/menzies-building.  Accessed May 28, 2020.
  * [3] https://www.cph.dk/en/practical.  Accessed May 28, 2020.
  * [4] Tanvir Ahmed, Torben Bach Pedersen, and Hua Lu.  Finding dense locations in indoor tracking data.  In MDM, volume 1, pages 189–194, 2014.
  * [5] Tanvir Ahmed, Torben Bach Pedersen, and Hua Lu.  Finding dense locations in symbolic indoor tracking data: modeling, indexing, and processing.  GeoInformatica, 21(1):119–150, 2017.
  * [6] Douglas G Altman and J Martin Bland.  Statistics notes: quartiles, quintiles, centiles, and other quantiles.  BMJ, 309(6960):996–996, 1994.
  * [7] Anahid Basiri, Elena Simona Lohan, Terry Moore, Adam Winstanley, Pekka Peltola, Chris Hill, Pouria Amirian, and Pedro Figueiredo e Silva.  Indoor location based services challenges, requirements and usability of current solutions.  Computer Science Review, 24:1–12, 2017.
  * [8] Thomas Becker, Claus Nagel, and Thomas H Kolbe.  A multilayered space-event model for navigation in indoor spaces.  In 3D geo-information sciences, pages 61–77. Springer, 2009.
  * [9] Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger.  The r*-tree: an efficient and robust access method for points and rectangles.  pages 322–331, 1990.
  * [10] Muhammad Aamir Cheema.  Indoor location-based services: challenges and opportunities.  SIGSPATIAL Special, 10(2):10–17, 2018.
  * [11] Lisi Chen, Gao Cong, Christian S Jensen, and Dingming Wu.  Spatial keyword query processing: an experimental evaluation.  Proceedings of the VLDB Endowment, 6(3):217–228, 2013.
  * [12] Constantinos Costa, Xiaoyu Ge, and Panos Chrysanthis.  Caprio: Context-aware path recommendation exploiting indoor and outdoor information.  In MDM, pages 431–436, 2019.
  * [13] Matthias Delafontaine, Mathias Versichele, Tijs Neutens, and Nico Van de Weghe.  Analysing spatiotemporal sequences in bluetooth tracking data.  Applied Geography, 34:659–668, 2012.
  * [14] Zijin Feng, Tiantian Liu, Huan Li, Hua Lu, Lidan Shou, and Jianliang Xu.  Indoor top-k keyword-aware routing query.  In ICDE, pages 1213–1224, 2020.
  * [15] Marcus Goetz and Alexander Zipf.  Formal definition of a user-adaptive and length-optimal routing graph for complex indoor environments.  Geo-Spatial Information Science, 14(2):119–128, 2011.
  * [16] Christian S Jensen, Hua Lu, and Bin Yang.  Indexing the trajectories of moving objects in symbolic indoor space.  In SSTD, pages 208–227, 2009.
  * [17] Donald B Johnson.  A note on dijkstra’s shortest path algorithm.  Journal of the ACM, 20(3):385–388, 1973.
  * [18] Jiyeong Lee.  A spatial access-oriented implementation of a 3-d gis topological data model for urban entities.  GeoInformatica, 8(3):237–264, 2004.
  * [19] Huan Li, Hua Lu, Lidan Shou, Gang Chen, and Ke Chen.  In search of indoor dense regions: An approach using indoor positioning data.  IEEE Transactions on Knowledge and Data Engineering, 30(8):1481–1495, 2018.
  * [20] Huan Li, Hua Lu, Lidan Shou, Gang Chen, and Ke Chen.  Finding most popular indoor semantic locations using uncertain mobility data.  IEEE Transactions on Knowledge and Data Engineering, 31(11):2108–2123, 2019.
  * [21] Tiantian Liu, Zijin Feng, Huan Li, Hua Lu, Muhammad Aamir Cheema, Hong Cheng, and Jianliang Xu.  Shortest path queries for indoor venues with temporal variations.  In ICDE, pages 2014–2017, 2020.
  * [22] Hua Lu, Xin Cao, and Christian S Jensen.  A foundation for efficient indoor distance-aware query processing.  In ICDE, pages 438–449, 2012.
  * [23] Hua Lu, Chenjuan Guo, Bin Yang, and Christian S Jensen.  Finding frequently visited indoor POIs using symbolic indoor tracking data.  In EDBT, pages 449–460, 2016.
  * [24] Hua Lu, Bin Yang, and Christian S Jensen.  Spatio-temporal joins on symbolic indoor tracking data.  In ICDE, pages 816–827, 2011.
  * [25] Chaluka Salgado.  Keyword-aware skyline routes search in indoor venues.  In SIGSPATIAL Workshop on Indoor Spatial Awareness, pages 25–31, 2018.
  * [26] Zhou Shao, Muhammad Aamir Cheema, David Taniar, and Hua Lu.  Vip-tree: an effective index for indoor spatial queries.  Proceedings of the VLDB Endowment, 10(4):325–336, 2016.
  * [27] Zhou Shao, Muhammad Aamir Cheema, David Taniar, Hua Lu, and Shiyu Yang.  Efficiently processing spatial and keyword queries in indoor venues.  IEEE Transactions on Knowledge and Data Engineering, 2020.
  * [28] Emily Whiting, Jonathan Battat, and Seth Teller.  Topology of urban environments.  In CAADFutures, pages 114–128. 2007.
  * [29] Michael Worboys.  Modeling indoor space.  In SIGSPATIAL Workshop on Indoor Spatial Awareness, pages 1–6, 2011\.
  * [30] Xike Xie, Hua Lu, and Torben Bach Pedersen.  Efficient distance-aware query evaluation on indoor moving objects.  In ICDE, pages 434–445, 2013.
  * [31] Xike Xie, Hua Lu, and Torben Bach Pedersen.  Distance-aware join for indoor moving objects.  IEEE Transactions on Knowledge and Data Engineering, 27(2):428–442, 2014.
  * [32] Bin Yang, Hua Lu, and Christian S Jensen.  Scalable continuous range monitoring of moving objects in symbolic indoor space.  In CIKM, pages 671–680, 2009.
  * [33] Bin Yang, Hua Lu, and Christian S Jensen.  Probabilistic threshold k nearest neighbor queries over moving objects in symbolic indoor space.  In EDBT, pages 335–346, 2010.
  * [34] Jiao Yu, Wei-Shinn Ku, Min-Te Sun, and Hua Lu.  An RFID and particle filter-based indoor spatial query evaluation system.  In EDBT, pages 263–274, 2013.

##  Appendix A APPENDIX

RQ based on IDModel is formalized in Algorithm 1, generally based on
Dijkstra’s algorithm. The function rangeSearch $(B,p,r)$ searches an object
bucket $B$ for those objects each having its distance from $p$ not larger than
$r$ [22]. Instead of keeping the last-hop door, we maintain last-hop partition
for each door in an array $\mathit{prev}[]$, as we assume that a door always
connects two partitions.

Algorithm 1 RQ_IDModel(Point $p$, distance $r$)

1:$v\leftarrow\textit{getHostPartition}(p)$;
$B_{v}\leftarrow\textit{getObjectBucket}(v)$

2:$O^{*}\leftarrow\textit{rangeSearch}(B_{v},p,r)$

3:initialize distance array $\mathit{dist}[]$ for all doors

4:initialize last-hop partition array $\mathit{prev}[]$ for all doors

5:for each door $d\in\mathit{P2D}_{\sqsubset}(v)$ do

6: $\mathit{dist}[d]\leftarrow||p,d||_{v}$

7:initialize a min-heap $H$

8:for each door $d_{i}\in D$ do

9: if $d_{i}\notin\mathit{P2D}_{\sqsubset}(v)$ then
$\mathit{dist}[d_{i}]\leftarrow\infty$; $\mathit{prev}[d_{i}]\leftarrow v$

10: enheap($H$, $\left\langle d_{i},\mathit{dist}[d_{i}]\right\rangle$);
$\mathit{prev}[d_{i}]\leftarrow$ null

11:while $H$ is not empty do

12: $\left\langle d_{i},\mathit{dist}[d_{i}]\right\rangle\leftarrow$
deheap($H$)

13: if $\mathit{dist}[d_{i}]>r$ then return $O^{*}$

14: for each partition $v_{i}\in\mathit{D2P}_{\sqsupset}(d_{j})$ $\wedge$
$v_{i}\neq\mathit{prev}[d_{i}]$ do

15: $r\leftarrow r-\mathit{dist}[d_{i}]$;
$B_{i}\leftarrow\textit{getObjectBucket}(v_{i})$

16: $O_{i}\leftarrow\textit{rangeSearch}(B_{i},d_{i},r)$; add $O_{i}$ to
$O^{*}$

17: mark $d_{i}$ and $v_{i}$ as visited

18: for each unvisited door $d_{j}\in\mathit{P2D}_{\sqsubset}(v_{i})$ do

19: $v^{\prime}_{i}\leftarrow\mathit{D2P}_{\sqsupset}(d_{j})\backslash v_{i}$;
$\mathit{dist}_{j}\leftarrow\mathit{dist}[d_{i}]+f_{\text{d2d}}(v_{i},d_{i},d_{j})$

20: if $\mathit{dist}_{j}<\mathit{dist}[d_{j}]$ then

21: $\mathit{dist}[d_{j}]\leftarrow\mathit{dist}_{j}$; enheap($H$,
$\left\langle d_{j},\mathit{dist}[d_{j}]\right\rangle$);
$\mathit{prev}[d_{j}]\leftarrow v_{i}$

22:return $O^{*}$

Algorithm 2 processes $k$NNQ based on IDModel. A function
$\textit{knnSearch}(O,B,p,k,\textit{kBound})$ is designed to update the
top-$k$ result set $O^{*}$ with objects from a bucket $B$. kBound is used to
prune unpromising objects and is updated after a calling of knnSearch.

Algorithm 2 $k$NNQ_IDModel(Point $p$, integer $k$)

1:$v\leftarrow\textit{getHostPartition}(p)$;
$B_{v}\leftarrow\textit{getObjectBucket}(v)$;
$\textit{kBound}\leftarrow\infty$

2:$O^{*}\leftarrow\varnothing$;
$\textit{knnSearch}(O^{*},B_{v},p,k,\textit{kBound})$

3:initialize distance array $\mathit{dist}[]$ for all doors

4:initialize last-hop partition array $\mathit{prev}[]$ for all doors

5:for each door $d\in D$ do

6: $\mathit{dist}[d]\leftarrow||p,d||_{v}$

7:initialize a min-heap $H$

8:for each door $d_{i}\in D$ do

9: if $d_{i}\notin\mathit{P2D}_{\sqsubset}(v)$ then
$\mathit{dist}[d_{i}]\leftarrow\infty$; $\mathit{prev}[d_{i}]\leftarrow v$

10: enheap($H$, $\left\langle d_{i},\mathit{dist}[d_{i}]\right\rangle$);
$\mathit{prev}[d_{i}]\leftarrow$ null

11:while $H$ is not empty do

12: $\left\langle d_{i},\mathit{dist}[d_{i}]\right\rangle\leftarrow$
deheap($H$)

13: if $\mathit{dist}[d_{i}]>\textit{kBound}$ then return $O^{*}$

14: for each partition $v_{i}\in\mathit{D2P}_{\sqsupset}(d_{j})$ $\wedge$
$v_{i}\neq\mathit{prev}[d_{i}]$ do

15: $B_{i}\leftarrow\textit{getObjectBucket}(v_{i})$;
$\textit{knnSearch}(O^{*},B_{i},d_{i},k,\textit{kBound})$

16: mark $d_{i}$ and $v_{i}$ as visited

17: for each unvisited door $d_{j}\in\mathit{P2D}_{\sqsubset}(v_{i})$ do

18: $v^{\prime}_{i}\leftarrow\mathit{D2P}_{\sqsupset}(d_{j})\backslash v_{i}$;
$\mathit{dist}_{j}\leftarrow\mathit{dist}[d_{i}]+f_{\text{d2d}}(v_{i},d_{i},d_{j})$

19: if $\mathit{dist}_{j}<\mathit{dist}[d_{j}]$ then

20: $\mathit{dist}[d_{j}]\leftarrow\mathit{dist}_{j}$; enheap($H$,
$\left\langle d_{j},\mathit{dist}[d_{j}]\right\rangle$);
$\mathit{prev}[d_{j}]\leftarrow v_{i}$

21:return $O^{*}$