EvoMiner: frequent subtree mining in phylogenetic databases

The problem of mining collections of trees to identify common patterns, called frequent subtrees (FSTs), arises often when trying to interpret the results of phylogenetic analysis. FST mining generalizes the well-known maximum agreement subtree problem. Here we present EvoMiner, a new algorithm for mining frequent subtrees in collections of phylogenetic trees. EvoMiner is an Apriori-like levelwise method, which uses a novel phylogeny-specific constant-time candidate generation scheme, an efficient fingerprinting-based technique for downward closure, and a lowest-common-ancestor-based support counting step that requires neither costly subtree operations nor database traversal. Our algorithm achieves speedups of up to 100 times or more over Phylominer, the current state-of-the-art algorithm for mining phylogenetic trees. EvoMiner can also work in depth-first enumeration mode to use less memory at the expense of speed. We demonstrate the utility of FST mining as a way to extract meaningful phylogenetic information from collections of trees when compared to maximum agreement subtrees and majority-rule trees—two commonly used approaches in phylogenetic analysis for extracting consensus information from a collection of trees over a common leaf set.     

Dense subgraph maintenance under streaming edge weight updates for real-time story identification

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.     

Stratified random sampling from streaming and stored data

Distributed and Parallel Databases - Stratified random sampling (SRS) is a widely used sampling technique for approximate query processing. We consider SRS on continuously arriving data streams and...     

Sketching asynchronous data streams over sliding windows

We study the problem of maintaining a sketch of recent elements of a data stream. Motivated by applications involving network data, we consider streams that are asynchronous, in which the observed order of data is not the same as the time order in which the data was generated. The notion of recent elements of a stream is modeled by the sliding timestamp window, which is the set of elements with timestamps that are close to the current time. We design algorithms for maintaining sketches of all elements within the sliding timestamp window that can give provably accurate estimates of two basic aggregates, the sum and the median, of a stream of numbers. The space taken by the sketches, the time needed for querying the sketch, and the time for inserting new elements into the sketch are all polylogarithmic with respect to the maximum window size. Our sketches can be easily combined in a lossless and compact way, making them useful for distributed computations over data streams. Previous works on sketching recent elements of a data stream have all considered the more restrictive scenario of synchronous streams, where the observed order of data is the same as the time order in which the data was generated. Our notion of recency of elements is more general than that studied in previous work, and thus our sketches are more robust to network delays and asynchrony. The work of the authors was supported in part through NSF grants CNS 0520102 and CNS 0520009. A preliminary version of this paper appeared in Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC) 2006, pages 82–91. Work done while the third author was at Rensselaer Polytechnic Institute. Authors are listed in reverse alphabetical order.     

Identifying frequent items in a network using gossip

We present algorithms for identifying frequently occurring items in a large distributed data set. Our algorithms use gossip as the underlying communication mechanism, and do not rely on any central control, nor on an underlying network structure, such as a spanning tree. Instead, nodes repeatedly select a random partner and exchange data with that partner. If this process continues for a (short) period of time, the desired results are computed, with probabilistic guarantees on the accuracy. Our algorithm for identifying frequent items is built by layering a novel small space “sketch” of data over a gossip-based data dissemination mechanism. We prove that the algorithm identifies the frequent items with high probability, and provides bounds on the time till convergence. To our knowledge, this is the first work on identifying frequent items using gossip.     

Self-stabilizing smoothing and balancing networks

A smoothing network is a distributed data structure that accepts tokens on input wires and routes them to output wires. It ensures that however imbalanced the traffic on input wires, the numbers of tokens emitted on output wires are approximately balanced. Prior work on smoothing networks always assumed that such networks were properly initialized. In a real distributed system, however, network switches may be rebooted or replaced dynamically, and it may not be practical to determine the correct initial state for the new switch. Prior analyses do not work under these new assumptions. This paper makes the following contributions. First, we show that some well-known 1-smoothing networks, known as counting networks, when started in an arbitrary initial state (perhaps chosen by an adversary), remain remarkably smooth, degrading from 1-smooth to (log n)-smooth, where n is the number of input/output wires. For the networks that we consider, we show that the above (log n) bound for the smoothness is tight. Our second contribution is to show how any balancing network can be made self-stabilizing with the addition of local stabilization actions and state, which restore the network back to a “legal state” even if it starts out in an illegal state. A preliminary version of this work appeared in the Proceedings of The 23rd International Conference on Distributed Computing Systems, Providence, Rhode Island, USA.     

Sparse Covers for Planar Graphs and Graphs that Exclude a Fixed Minor

We consider the construction of sparse covers for planar graphs and other graphs that exclude a fixed minor. We present an algorithm that gives a cover for the γ-neighborhood of each node. For planar graphs, the cover has radius less than 16γ and degree no more than 18. For every n node graph that excludes a minor of a fixed size, we present an algorithm that yields a cover with radius no more than 4γ and degree O(logn). This is a significant improvement over previous results for planar graphs and for graphs excluding a fixed minor; in order to obtain clusters with radius O(γ), it was required to have the degree polynomial in n. Our algorithms are based on a recursive application of a basic routine called shortest-path clustering, which seems to be a novel approach to the construction of sparse covers. Since sparse covers have many applications in distributed computing, including compact routing, distributed directories, synchronizers, and Universal TSP, our improved cover construction results in improved algorithms for all these problems, for the class of graphs that exclude a fixed minor.