Campus Units

Computer Science, Electrical and Computer Engineering

Document Type

Article

Publication Version

Accepted Manuscript

Publication Date

4-2014

Journal or Book Title

The VLDB Journal

Volume

23

Issue

2

First Page

175

Last Page

199

DOI

10.1007/s00778-013-0340-z

Abstract

Recent years have witnessed an unprecedented proliferation of social media. People around the globe author, everyday, millions of blog posts, social network status updates, etc. This rich stream of information can be used to identify, on an ongoing basis, emerging stories, and events that capture popular attention. Stories can be identified via groups of tightly coupled real-world entities, namely the people, locations, products, etc, that are involved in the story. The sheer scale and rapid evolution of the data involved necessitate highly efficient techniques for identifying important stories at every point of time. The main challenge in real-time story identification is the maintenance of dense subgraphs (corresponding to groups of tightly coupled entities) under streaming edge weight updates (resulting from a stream of user-generated content). This is the first work to study the efficient maintenance of dense subgraphs under such streaming edge weight updates. For a wide range of definitions of density, we derive theoretical results regarding the magnitude of change that a single edge weight update can cause. Based on these, we propose a novel algorithm, DynDens, which outperforms adaptations of existing techniques to this setting and yields meaningful, intuitive results. Our approach is validated by a thorough experimental evaluation on large-scale real and synthetic datasets.

Comments

This is a manuscript of an article published as Angel, Albert, Nick Koudas, Nikos Sarkas, Divesh Srivastava, Michael Svendsen, and Srikanta Tirthapura. "Dense subgraph maintenance under streaming edge weight updates for real-time story identification." The VLDB Journal 23, no. 2 (2014): 175-199. The final publication is available at Springer via DOI: 10.1007/s00778-013-0340-z. Posted with permission.

Copyright Owner

Springer Berlin Heidelberg

Language

en

File Format

application/pdf

Published Version

Share

COinS