22 Result(s)

Article

Stratified random sampling from streaming and stored data

Stratified random sampling (SRS) is a widely used sampling technique for approximate query processing. We consider SRS on continuously arriving data streams and statically stored data sets. We present a tight ...

Trong Duc Nguyen, Ming-Hung Shih, Divesh Srivastava… in Distributed and Parallel Databases (2021)

Article

Incremental maintenance of maximal cliques in a dynamic graph

We consider the maintenance of the set of all maximal cliques in a dynamic graph that is changing through the addition or deletion of edges. We present nearly tight bounds on the magnitude of change in the set...

Apurba Das, Michael Svendsen, Srikanta Tirthapura in The VLDB Journal (2019)

Reference Work Entry In depth

Stream Sampling

Bibudh Lahiri, Srikanta Tirthapura in Encyclopedia of Database Systems (2018)

Article

Identifying correlated heavy-hitters in a two-dimensional data stream

We consider online mining of correlated heavy-hitters (CHH) from a data stream. Given a stream of two-dimensional data, a correlated aggregate query first extracts a substream by applying a predicate along a p...

Bibudh Lahiri, Arko Provo Mukherjee… in Data Mining and Knowledge Discovery (2016)

Article

Space-Efficient Estimation of Statistics Over Sub-Sampled Streams

In many stream monitoring situations, the data arrival rate is so high that it is not even possible to observe each element of the stream. The most common solution is to sub-sample the data stream and use the ...

Andrew McGregor, A. Pavan, Srikanta Tirthapura, David P. Woodruff in Algorithmica (2016)

Living Reference Work Entry In depth

Stream Sampling

Bibudh Lahiri, Srikanta Tirthapura in Encyclopedia of Database Systems

Article

A General Method for Estimating Correlated Aggregates Over a Data Stream

On a stream \({\fancyscript{S}}\) S ...

Srikanta Tirthapura, David P. Woodruff in Algorithmica (2015)

Article

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 w...

Akshay Deepak, David Fernández-Baca… in Knowledge and Information Systems (2014)

Article

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 ...

Costas Busch, Ryan LaFortune, Srikanta Tirthapura in Algorithmica (2014)

Article

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...

Albert Angel, Nick Koudas, Nikos Sarkas, Divesh Srivastava… in The VLDB Journal (2014)

Chapter and Conference Paper

Optimal Random Sampling from Distributed Streams Revisited

We give an improved algorithm for drawing a random sample from a large data stream when the input elements are distributed across multiple sites which communicate via a central coordinator. At any point in tim...

Srikanta Tirthapura, David P. Woodruff in Distributed Computing (2011)

Reference Work Entry In depth

Stream Sampling

Bibudh Lahiri, Srikanta Tirthapura in Encyclopedia of Database Systems (2009)

Article

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 i...

Bojian Xu, Srikanta Tirthapura, Costas Busch in Distributed Computing (2008)

Chapter and Conference Paper

Computing Frequent Elements Using Gossip

We present algorithms for identifying frequently occurring elements in a large distributed data set using gossip. Our algorithms do not rely on any central control, or on an underlying network structure, such ...

Bibudh Lahiri, Srikanta Tirthapura in Structural Information and Communication Complexity (2008)

Chapter and Conference Paper

A Deterministic Algorithm for Summarizing Asynchronous Streams over a Sliding Window

We consider the problem of maintaining aggregates over recent elements of a massive data stream. Motivated by applications involving network data, we consider asynchronous data streams, where the observed order o...

Costas Busch, Srikanta Tirthapura in STACS 2007 (2007)

Article

Dynamic Analysis of the Arrow Distributed Protocol

Distributed queuing is a fundamental coordination problem that arises in a variety of applications, including distributed directories, totally ordered multicast, and distributed mutual exclusion. The arrow pro...

Maurice Herlihy, Fabian Kuhn, Srikanta Tirthapura… in Theory of Computing Systems (2006)

Article

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...

Maurice Herlihy, Srikanta Tirthapura in Distributed Computing (2006)