Indexing for Moving Objects in Multi-Floor Indoor Spaces That Supports Complex Semantic Queries

Hui Lin, Ling Peng, Si Chen, Tianyue Liu, Tianhe ChiISPRS Int. J. Geo Inf 2016 · DOI

TL;DR

This paper introduces MACSI, a novel indexing strategy for indoor moving objects that uniquely combines spatial and semantic information across multiple floors. By addressing limitations of existing methods, MACSI enables more efficient and accurate complex semantic queries in indoor environments, crucial for emerging indoor applications.

What Problem Does This Paper Address?

Humans spend a significant amount of time indoors, leading to a growing need for effective indoor navigation, tracking, and emergency response systems. While outdoor moving object indexing is mature, indoor environments present unique challenges: GPS is unreliable, and indoor spaces are constrained by walls and complex layouts. Existing indoor indexing methods often focus on single floors and primarily spatial queries, neglecting the rich semantic information and multi-floor connectivity that are vital for many real-world applications. This gap limits the ability to perform complex queries like "find all VIP customers in the shopping mall who are currently near the food court and have a birthday today."

Methods

The core contribution is the Multi-floor Adjacency Cell and Semantic-based Index (MACSI). MACSI integrates two key components:

  • MAC-tree (Spatial Index): This extends existing single-floor adjacency cell indices to multi-floor spaces.
  • Open Cell Processing: Hallways and lobbies are subdivided using "space syntax" (specifically axis analysis) to better reflect actual travel distances.
  • 3D Connected Cell Processing: Stairs and elevators are handled by incorporating "caloric cost" to model the energy expenditure of movement between floors, creating an asymmetric adjacency matrix. This is a significant improvement over treating them as simple connections.
  • MGSI (Semantic Index): This component handles semantic queries.
  • Multi-Granularity Semantic Hierarchy Tree (MGSH-tree): This tree organizes semantic keywords hierarchically, allowing for both coarse-grained (e.g., "shopping") and fine-grained (e.g., "Nike") semantic queries.
  • Semantic Inverted Indexing: This is used to efficiently link semantic keywords to indoor cells and objects, improving query performance and semantic expansion capabilities.
  • Semantic Trajectory Modeling: A novel approach to model trajectories that captures multi-granularity semantic information, going beyond simple location sequences.

Datasets

The paper utilizes two types of datasets for evaluation:

  • Simulated Data: Generated based on the floor plan of a 22-floor building in Tianjin, China. Moving object trajectories were simulated on this plan.
  • Real Data: Collected from a shopping center in Beijing, China. This environment provided a real-world testbed with 60 moving objects and their trajectories. Semantic information for stores and brands was manually established and extracted from Wikipedia.

Key Insights and Ideas

  • Caloric Cost for Vertical Movement: Modeling the energy cost of using stairs and elevators, rather than just distance, provides a more realistic representation of travel time and user preference in multi-floor spaces.
  • Space Syntax for Hallways: Subdividing large open spaces like hallways using techniques like axis analysis is crucial for accurately representing adjacency and travel paths, which simple wall-based subdivisions miss.
  • Multi-Granularity Semantics: The MGSH-tree is key to handling diverse user needs, from broad categories like "shopping" to specific brands like "Nike," enabling more nuanced and relevant queries.
  • Inverted Indexing for Semantics: This technique significantly boosts the efficiency of semantic queries and allows for dynamic semantic expansion (e.g., adding new products or brands) without rebuilding the entire index.
  • MACSI's Superiority in Complex Queries: The combination of spatial and semantic indexing, particularly the multi-granularity approach, allows MACSI to outperform existing methods in complex semantic trajectory queries, which are difficult for simpler indices.

Key Results

  • Query Efficiency: MACSI consistently outperforms ITD-tree and SI in fine-grained semantic cell and object queries, especially as the number of cells and objects increases. For example, in fine-grained semantic cell queries, MACSI's execution time remains stable while ITD-tree and SI degrade significantly.
  • Semantic Trajectory Queries: MACSI shows significantly better performance than SI for complex semantic trajectory queries, especially as the scale of cells and objects increases.
  • Update Efficiency: MACSI demonstrates superior semantic cell keyword update efficiency compared to SI and ITD-tree, particularly as the number of cells increases.
  • Real-World Reliability: In a real-world scenario, MACSI provided more reliable nearest neighbor search results for lavatories compared to ITD-tree and SI, which struggled with multi-floor context. MACSI's ranking of destinations more closely matched actual arrival times.
  • Memory Cost: While MACSI uses more memory than ITD-tree and SI due to its comprehensive indexing approach (combining spatial, semantic, and auxiliary tables), its memory cost remains manageable and suitable for large-scale applications.

Limitations and Future Work

  • Memory Consumption: The paper acknowledges that MACSI's integrated approach leads to higher memory costs compared to simpler indices like ITD-tree and SI.
  • Initialization and Insertion Time: The initialization and node insertion processes for MACSI are noted as being relatively complex and time-consuming, making it more suitable for applications that are query-sensitive rather than initialization-sensitive.
  • Dynamic Adjacency Matrices: Future work could explore dynamic adjacency matrices to adapt to structural changes in buildings.
  • Integrated Indoor/Outdoor Indexing: Seamlessly connecting indoor and outdoor spaces for unified indexing is a promising future direction.
  • Broader Evaluation Metrics: Future research could incorporate user satisfaction, actual arrival time, and other indicators, drawing inspiration from big data application evaluation methods.

Summary updated

BibTeX
@article{lin2016indexing,
  author = {Hui Lin and Ling Peng and Si Chen and Tianyue Liu and Tianhe Chi},
  title = {{Indexing for Moving Objects in Multi-Floor Indoor Spaces That Supports Complex Semantic Queries}},
  journal = {ISPRS Int. J. Geo Inf.},
  year = {2016},
  doi = {10.3390/ijgi5100176},
}

Loading related content...

Figure