UC Riverside

The continuous growth of the internet and the popularity of social networks have created a huge amount of social media data. This includes social networks like users' friendships, as well as users' contributed content such as tags, blogs, posts, tweets, and etc. In addition, other collaborating applications also generate large data, such as the versioned textual documents created in a collaborative authoring environment like Wikipedia. In a dynamic world, the social media data is continuously evolving with time. In December 2004, Facebook had about 1 million users; but by October 2012, Facebook has over 1 billion active users. The dynamically changing and rapidly growing data bring us critical challenges: how to store, how to query, and how to use it in different application domains. This dissertation examines four related problems. First, we consider the large historical evolving graphs created from a social network, and examined various temporal shortest-path queries (e.g., find the shortest-path between two nodes as of certain time in the past). For this environment we proposed an efficient storage model, and fast query processing algorithms that take advantage of appropriate speed-up indexing techniques. For second problem examined, deals with social tagging websites, where users post and share items like bookmarks, videos, photos etc., along with comments and tags. Within this environment, we presented a study of top-k search that utilizes the temporal information as well as a user's participation in multiple social networks; our results show an improved search performance. Third, we examined the problem of temporal top-k keyword search in versioned textual collections; we compared different approaches and proposed novel methods that utilize multi-version access methods to improve the search. Finally, we considered applications that support multi-version schema evolutions; we explored scenarios for branching and merging, and proposed efficient indexing structures along with query processing optimizations.