Bursty and hierarchical structure in streams

TLDR

Text data mining seeks to extract structure from continuous document streams, such as e‑mail and news, where topics burst, grow, and fade, and similar patterns appear over longer timescales in research literature. This study aims to formalize burst modeling so that bursts can be robustly and efficiently detected and used to structure and analyze stream content. The method models streams with an infinite‑state automaton in which bursts correspond to state transitions, analogous to queueing‑theory models of bursty traffic. The algorithms are highly efficient, producing a nested representation that imposes a hierarchical structure on the stream, and experiments with e‑mail and research archives show that these structures meaningfully reflect the underlying content.

Abstract

A fundamental problem in text data mining is to extract meaningful structure from document streams that arrive continuously over time. E-mail and news articles are two natural examples of such streams, each characterized by topics that appear, grow in intensity for a period of time, and then fade away. The published literature in a particular research field can be seen to exhibit similar phenomena over a much longer time scale. Underlying much of the text mining work in this area is the following intuitive premise --- that the appearance of a topic in a document stream is signaled by a "burst of activity," with certain features rising sharply in frequency as the topic emerges.The goal of the present work is to develop a formal approach for modeling such "bursts," in such a way that they can be robustly and efficiently identified, and can provide an organizational framework for analyzing the underlying content. The approach is based on modeling the stream using an infinite-state automaton, in which bursts appear naturally as state transitions; in some ways, it can be viewed as drawing an analogy with models from queueing theory for bursty network traffic. The resulting algorithms are highly efficient, and yield a nested representation of the set of bursts that imposes a hierarchical structure on the overall stream. Experiments with e-mail and research paper archives suggest that the resulting structures have a natural meaning in terms of the content that gave rise to them.