Temporal Query Processing in Social Network

Abstract

With the increasing of requirements from many aspects, various queries and analyses arise focusing on social network. Queries like finding users, friends or social activities satisfying a certain period gives temporal insights into retrieval or statistics, hence augmenting temporal query capability in such context, namely, temporal social network (TSN), is meaningful. In this paper, we mainly study three kinds of temporal queries in social network, which explore temporal attribute in user's online duration, friendship duration and participation in social activities. To address the problems, first we formally give problem descriptions, and propose 6 primitive query definitions, which are helpful for accomplishing the three queries through combining them. Next, we design a storage model to store the data of our context, and propose implementation of primitive queries based on the model. After that, we argue indexing techniques are able to accelerate the query procedure and then propose two index structures, TUR-tree, indexing temporal data of users and friendship, and TUA-tree, indexing temporal data of participations. Then we address implementation of primitive queries based on indexes, and design query algorithms to solve the three queries. We believe the algorithms could be improved and optimizations are presented. We evaluate our idea on a dataset which is synthetically generated from real dataset, and experimental results show that our indexes and query processing are effective and scalable.

http://ift.tt/2gEpqV5