Fast small-space algorithms for approximate histogram maintenance (2009)
Anna C. Gilbert, Yannis Kotidis
Avector A of lengthN is de ned implicitly, via a stream of updates of the form \add 5 to A3. " We give asketching algorithm, that constructs a small sketch from the stream of updates, and a...
Fast Algorithm for Sparse Signal Approximation using Multiple Additive Dictionaries (2009)
Maleh, Ray, Yoon, Daehyun, Gilbert, Anna C.
There are several models for sparse approximation: one where a signal is a sparse linear combination of vectors over a redundant dictionary and a second model in which a collection of signals is a...
Fast Algorithm for Sparse Signal Approximation using Multiple Additive Dictionaries (2009)
Maleh, Ray, Yoon, Daehyun, Gilbert, Anna C.
There are several models for sparse approximation: one where a signal is a sparse linear combination of vectors over a redundant dictionary and a second model in which a collection of signals is a...
ABSTRACT Compressing Network Graphs (2008)
Graphs form the foundation of many real-world datasets ranging from Internet connectivity to social networks. Yet despite this underlying structure, the size of these datasets presents a nearly...
Fast small-space algorithms for approximate histogram maintenance (2008)
Anna C. Gilbert, Yannis Kotidis
Avector A of lengthN is de ned implicitly, via a stream of updates of the form \add 5 to A3. " We give asketching algorithm, that constructs a small sketch from the stream of updates, and a...
Anja Feldmann, Anna C. Gilbert, Polly Huang, Walter Willinger
Using the ns-2-simulator to experiment with different aspects of user- or session-behaviors and network configurations and focusing on the qualitative aspects of a wavelet-based scaling analysis, we...
Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit (2007)
Tropp, Joel A., Gilbert, Anna C.
This paper demonstrates theoretically and empirically that a greedy algorithm called Orthogonal Matching Pursuit (OMP) can reliably recover a signal with $m$ nonzero entries in dimension $d$ given $...
is a linear combination of dictionary (2007)
Anna C. Gilbert, S. Muthukrishnan, Martin J. Strauss, Input A R
One of the central problems of modern mathematical approximation theory is to approximate functions, or signals, concisely, with elements from a large candidate set called a dictionary. Formally, we...
Anna C. Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss
A vector A of length N is defined implicitly, via a stream of updates of the form "add 5 to A 3. " We give a sketching algorithm, that constructs a small sketch from the stream of...
TCP/IP traffic dynamics and network performance: (2007)
Lesson In Workload, Youngmi Joo, Vinay Ribeiro Y, Anja Feldmann Z, Anna C. Gilbert, Walter Willinger X
The main objective of this paper is to demonstrate in the context of a simple TCP#IP-based network that depending on the underlying assumptions about the inherent nature of the dynamics of network...
Sparse Approximation Via Iterative Thresholding (2006)
Herrity, Kyle K., Gilbert, Anna C., Tropp, Joel A.
The well-known shrinkage technique is still relevant for contemporary signal processing problems over redundant dictionaries. We present theoretical and empirical analyses for two iterative...
Sparse Approximation Via Iterative Thresholding (2006)
Herrity, Kyle K., Gilbert, Anna C., Tropp, Joel A.
The well-known shrinkage technique is still relevant for contemporary signal processing problems over redundant dictionaries. We present theoretical and empirical analyses for two iterative...
List decoding of noisy Reed-Muller-like codes (2006)
Calderbank, A. R., Gilbert, Anna C., Strauss, Martin J.
First- and second-order Reed-Muller (RM(1) and RM(2), respectively) codes are two fundamental error-correcting codes which arise in communication as well as in probabilistically-checkable proofs and...
Algorithms for simultaneous sparse approximation (2006)
Joel A. Tropp, Anna C. Gilbert, J. Strauss, J. A. Tropp, A. C. Gilbert, ...
Abstract. A simultaneous sparse approximation problem requests a good approximation of several input signals at once using different linear combinations of the same elementary signals. At the same...
List decoding of noisy Reed-Muller-like codes (2006)
A. Robert Calderbank, Anna C. Gilbert, Martin J. Strauss
Coding theory has played a central role in the development of computer science. One critical point of interaction is decoding error-correcting codes. First- and second-order Reed-Muller (RM(1) and...
Better Alternatives to OSPF Routing (2005)
Strauss, Martin J., Gilbert, Anna C., Fong, Jessica H., Kannan, Sampath
The current standard for intra-domain network routing, Open ShortestPath First (OSPF), suffers from a number ofproblems-the tunable parameters (the weights) are hard tooptimize, the chosen paths are...
Domain-driven data synopses for dynamic quantiles (2005)
Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss
Abstract—In this paper, we present new algorithms for dynamically computing quantiles of a relation subject to insert as well as delete operations. At the core of our algorithms lies a small-space...
Compressing network graphs (2004)
Anna C. Gilbert, Kirill Levchenko
Graphs form the foundation of many real-world datasets ranging from Internet connectivity to social networks. Yet despite this underlying structure, the size of these datasets presents a nearly...
One-Pass Wavelet Decompositions of Data Streams (2003)
Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss
We present techniques for computing small space representations of massive data streams. These are inspired by traditional wavelet-based approximations that consist of specific linear projections of...
How to summarize the universe: Dynamic maintenance of quantiles (2002)
Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss
Order statistics, i.e., quantiles, are frequently used in databases both at the database server as well as the application level. For example, they are useful in selectivity estimation during query...
Fast, Small-Space Algorithms for Approximate Histogram (2002)
Maintenance Extend Ed, Anna C. Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, S. Muthukrishnan, ...
Anna C. Gilbert AT&T Labs---Research agilbert@research.att.com Yannis Kotidis AT&T Labs---Research kotidis@research.att.com Sudipto Guha CIS,University of Pennsylvania sudipto@cis.upenn.edu...
How to Summarize the Universe: Dynamic Maintenance of Quantiles (2002)
Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss
Order statistics, i.e., quantiles, are frequently used in databases both at the database server as well as the application level. For example, they are useful in selectivity estimation during query...
How to summarize the universe: Dynamic maintenance of quantiles (2002)
Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss
Abstract Order statistics, i.e., quantiles, are frequently used in databases both at the database server as well as the application level. For example, they are useful in selectivity estimation...
Optimal and approximate computation of summary statistics for range aggregates (2001)
Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss
Fast estimates for aggregate queries are useful in database query optimization, approximate query answering and online query processing. Hence, there has been a lot of focus on “selectivity...
Surfing wavelets on streams: One-pass summaries for approximate aggregate queries (2001)
Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss
Abstract We present techniques for computing small spacerepresentations of massive data streams. These are inspired by traditional wavelet-based approx-imations that consist of specific linear...
Optimal and approximate computation of summary statistics for range aggregates (2001)
Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss
Fast estimates for aggregate queries are useful in database query optimization, approximate query answering and online query processing. Hence, there has been a lot of focus on "selectivity...
Surfing wavelets on streams: One-pass summaries for approximate aggregate queries (2001)
Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss
We present techniques for computing small space representations of massive data streams. These are inspired by traditional wavelet-based approximations that consist of specific linear projections of...
Surfing wavelets on streams: One-pass summaries for approximate aggregate queries (2001)
Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss
We present techniques for computing small space representations of massive data streams. These are inspired by traditional wavelet-based approximations that consist of specific linear projections of...
Surfing wavelets on streams: One-pass summaries for approximate aggregate queries (2001)
Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss
We present techniques for computing small space representations of massive data streams. These are inspired by traditional wavelet-based approximations that consist of specific linear projections of...
Surfing wavelets on streams: One-pass summaries for approximate aggregate queries (2001)
Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss
We present techniques for computing small space representations of massive data streams. These are inspired by traditional wavelet-based approximations that consist of specific linear projections of...
Congestion control and periodic behavior (2001)
Anna C. Gilbert, Youngmi Joo, Nick Mckeown
Abstract-- Feedback based congestion control — used by TCP and other transport protocols — causes the transmission rate of a long-lived flow to oscillate. This paper is about the tendency of...
Surfing wavelets on streams: One-pass summaries for approximate aggregate queries (2001)
Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss
We present techniques for computing small space representations of massive data streams. These are inspired by traditional wavelet-based approximations that consist of specific linear projections of...
Dynamics of IP traffic: A study of the role of variability and the impact of control (1999)
Anja Feldmann, Anna C. Gilbert, Polly Huang, Walter Willinger
Using the ns-2-simulator to experiment with different aspects of user- or session-behaviors and network configurations and focusing on the qualitative aspects of a wavelet-based scaling analysis, we...
Dynamics of IP traffic: A study of the role of variability and the impact of control (1999)
Anja Feldmann, Anna C. Gilbert, Polly Huang, Walter Willinger
Using the ns-2-simulator to experiment with different aspects of user- or session-behaviors and network configurations and focusing on the qualitative aspects of a wavelet-based scaling analysis, we...
On the impact of variability on the buffer dynamics in IP networks (1999)
Youngmi Joo, Vinay Ribeiro, Anja Feldmann, Anna C. Gilbert, Walter Willinger
The main objective of this paper is to demonstrate in the context of a simple TCP/IPbased network that depending on the underlying assumptions about the inherent nature of the variability of network...
On the impact of variability on the buffer dynamics in IP networks (1999)
Youngmi Joo, Vinay Ribeiro, Anja Feldmann, Anna C. Gilbert, Walter Willinger
The main objective of this paper is to demonstrate in the context of a simple TCP/IPbased network that depending on the underlying assumptions about the inherent nature of the variability of network...
Multiresolution Homogenization Schemes for Differential Equations and Applications (1997)
Multiresolution Homogenization, Anna C. Gilbert
The multiresolution analysis (MRA) strategy for homogenization consists of two algorithms; a procedure for extracting the effective equation for the average or for the coarse scale behavior of the...