C-tree: efficient cell-based indexing of indoor mobile objects

With the increasing popularity of indoor positioning system technologies, many applications have become available that allow moving objects to be monitored and queried on the basis of their indoor locations. At the center of these applications is a data structure that is used for indexing the moving objects. For most of the current applications, the indexing is based on certain modifications of methods from the established research area of indexing objects moving in outdoor spaces. But the approach to indexing objects moving in indoor spaces should be more radically different. The nature of indoor spaces, which essentially consist of cells and connections between cells, and the concept of cell-based adjacency, as opposed to metric-based adjacency, require a significantly different focus and approach. In this paper, we present a cell-based index structure, which is called the C-tree (‘C’ for ‘cell’), for efficiently grouping and managing updates of moving objects in indoor spaces. The C-tree can efficiently serve indoor spatial queries, topological queries, adjacency queries and density-based queries. In addition, as shown in the paper, the density of indoor cells can play an important role in the performance of the index data structure. Taking cell density into account, we extend the application of the C-tree to construct what is called a density-based index tree, which substantially improves the performance of the index structure when the indoor space contains high density cells.