Influence Maximization (IM), which selects a set of k users (called seed set) from a social network to maximize the expected number of influenced users (called influence spread), is a key algorithmic problem in social influence analysis. Due to its immense application potential and enormous technical challenges, IM has been extensively studied in the past decade. In this paper, we survey and synthesize a wide spectrum of existing studies on IM from an algorithmic perspective, with a special focus on the following key aspects (1) a review of well-accepted diffusion models that capture information diffusion process and build the foundation of the IM problem, (2) a fine-grained taxonomy to classify existing IM algorithms based on their design objectives, (3) a rigorous theoretical comparison of existing IM algorithms, and (4) a comprehensive study on the applications of IM techniques in combining with novel context features of social networks such as topic, location, and time. Based on this analysis, we then outline the key challenges and research directions to expand the boundary of IM research.

Personalized PageRank (PPR) is a well-known proximity measure in graphs. To meet the need for dynamic PPR maintenance, recent works have proposed a local update scheme to support incremental computation. Nevertheless, sequential execution of the scheme is still too slow for highspeed stream processing. Therefore, we are motivated to design a parallel approach for dynamic PPR computation. First, as updates always come in batches, we devise a batch processing method to reduce synchronization cost among every single update and enable more parallelism for iterative parallel execution. Our theoretical analysis shows that the parallel approach has the same asymptotic complexity as the sequential approach. Second, we devise novel optimization techniques to effectively reduce runtime overheads for parallel processes. Experimental evaluation shows that our parallel algorithm can achieve orders of magnitude speedups on GPUs and multi-core CPUs compared with the state-of-the-art sequential algorithm.

In this paper, we study a new variant of trajectory similarity search from the context of continuous query processing. Given a moving object from s to $d$ , following a reference route $T_r$ , we monitor the trajectory similarity between the reference route and the current partial route at each timestamp for online detour detection. Since existing trajectory distance measures fail to adequately capture the deviation between a partial route and a complete route, we propose a partial trajectory similarity measure to bridge the gap. In particular, we enumerate all the possible routes extended from the partial route to reach the destination d and calculate their minimum distance to $T_r$ . We consider deviation calculation in both Euclidean space and road networks. In Euclidean space, we can directly infer the optimal future path with the minimum trajectory distance. In road networks, we propose an efficient expansion algorithm with a suite of pruning rules. Furthermore, we propose efficient incremental processing strategies to facilitate continuous query processing for moving objects. Our experiments are conducted on multiple real datasets and the experimental results verify the efficiency of our query processing algorithms.

Mobile and tablet apps, ubiquitous and pervasive computing, wearable computing and domotics for health.