Top-k Socially Constrained Spatial Keyword Search in Large SIoT Networks

Social Internet of Things (SIoT) incorporates social relationship into Internet of Things, and compositive relationship between persons, devices and persons to devices is utilized for providing better services. This paper proposes a novel type of search, namely top-k social spatial keyword search (SSKS) in SIoT networks to discover relevant users or data objects according to social, spatial and textual preferences. Existing works mainly focus on two of these preferences at the same time, and efficiently processing top-k SSKS remains challenging. To this end, we propose two algorithms to evaluate top-k SSKS in SIoT networks. The first algorithm is a forward search based algorithm, which spreads the search from the vertex of the querying user. An effective pruning strategy is established by recognizing an early termination condition according to the threefold preference. The forward search based algorithm is efficient when textual objects are dense. The second algorithm is based on index searching. We present an index namely 2HL-GIL to support spatial and textual pruning while providing fast computation of social distances in the SIoT. Then an index-based search algorithm is proposed for top-k SSKS, and it is efficient especially when textual objects are sparse. Our proposed algorithms are evaluated over two real-life social networks attached with synthetic locations and textual data. Evaluation results illustrate the effectiveness and efficiency of our proposed forward search based algorithm and index-based search algorithm.