With the widespread deployment of indoor positioning systems, an unprecedented scale of indoor trajectories is being produced. By considering the inherent uncertainties and the text information contained in such an indoor trajectory, a new definition named Indoor Uncertain Semantic Trajectory is defined in this paper. In this paper, we focus on a new primitive, yet quite essential query named Indoor Uncertain Semantic Trajectory Similarity Join (IUST-Join for short), which is to match all similar pairs of indoor uncertain semantic trajectories from two sets. IUST-Join targets a number of essential indoor applications. With these applications in mind, we provide a purposeful definition of an indoor uncertain semantic trajectory similarity metric named IUS. To process IUST-Join more efficiently, both an inverted index on indoor uncertain semantic trajectories named 3IST and the first acceleration strategy are proposed to form a filtering-and-verification framework, where most invalid pairs of indoor uncertain semantic trajectories are pruned at quite low computation cost. And based on this filtering-and-verification framework, we present a highly-efficient algorithm named Indoor Uncertain Semantic Trajectory Similarity Join Processing (USP for short). In addition, lots of novel and effective acceleration strategies are proposed and embedded in the USP algorithm. Thanks to these techniques, both the time complexity and the time overhead of the USP algorithm are further reduced. The results of extensive experiments demonstrate the superior performance of the proposed work.

Spatial databases store objects with their locations and certain types of attached items. A variety of modern applications have been developed by leveraging the utilization of locations and items in spatial objects, such as searching points of interest, hot topics, or users’ attitude in specified spatial regions. In many scenarios, the high and low-frequency items in a spatial region are worth noticing, considering they represent the majority’s interest or eccentric users’ opinion. However, existing works have yet to identify such items in an interactive manner, despite the significance of the endeavor in decision-making systems. This study recognizes a novel type of analytical query, called top/bottom- $k$ fraction query, to discover such items in spatial databases. To achieve fast query response, we propose a multilayered data summary that is spread out across the main memory and external memory. A memory-based estimation method for top/bottom- $k$ fraction queries is proposed. To maximize the use of the main memory space, we design a data summary tuning method to dynamically allocate memory space among different spatial partitions. The proposed approach is evaluated with real-life datasets and synthetic datasets in terms of estimation accuracy. Evaluation results demonstrate the effectiveness of the proposed data summary and corresponding estimation and tuning algorithms.