Maximizing Influence Query Over Indoor Trajectories
- 9 December 2024
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 37 (3) , 1294-1310
Abstract
Maximizing Influence (Max-Inf) query is a fundamental operation in spatial data management. This query returns an optimal site from a candidate set to maximize its influence . Existing work commonly focuses on outdoor spaces. In practice, however, people spend up to 87% of their daily life inside indoor spaces. The outdoor techniques fall short in indoor spaces due to the complicated topology of indoor spaces. In this paper, we formulate two indoor Max-Inf queries: Top-$k$ Probabilistic Influence Query (T $k$ PI) and Collective-$k$ Probabilistic Influence Query (C $k$ PI) taking probability and mobility factors into consideration. We propose a novel spatial index, IT-tree, which utilizes the properties of indoor venues to facilitate the indoor distance computation, and then applies a trie to further organize the trajectories with similar check-in partitions together, based on their sketch information. This structure is simple but highly effective in pruning the trajectory search space. To process T $k$ PI efficiently, we devise subtree pruning and progressive pruning techniques to delicately filter out unnecessary trajectories based on probability bounds and the monotonicity of influence probability. For C $k$ PI queries, which is a submodular NP-hard problem, three approximation algorithms are provided with different strategies of computing marginal influence value during the search. Through extensive experiments on several real indoor venues, we demonstrate the efficiency and effectiveness of our proposed algorithms.
Keywords
Funding Information
- National Natural Science Foundation of China (U22A2025, 72371084, 62102119, U21A20513)
- Taishan Scholars Program of Shandong Province (tsqn202211091)
This publication has 51 references indexed in Scilit:
- Influence Computation for Indoor Spatial Objects2022
- C-tree: efficient cell-based indexing of indoor mobile objectsJournal of Ambient Intelligence and Humanized Computing, 2019
- Collective-k Optimal Location Selection2017
- Detecting Hotspots from Trajectory Data in Indoor Spaces2015
- On efficient k-optimal-location-selection query processing in metric spacesInformation Sciences, 2015
- A connectivity index for moving objects in an indoor cellular spacePersonal and Ubiquitous Computing, 2013
- Indexing in-network trajectory flowsThe VLDB Journal, 2011
- Indexing the Trajectories of Moving Objects in Symbolic Indoor Space2009
- The Optimal-Location Query2005
- Activity patterns of Californians: Use of and proximity to indoor pollutant sourcesAtmospheric Environment. Part A. General Topics, 1992