Abstract Networks of strong ties (2008)
Xiaolin Shi, Lada A. Adamic, Martin J. Strauss
Social networks transmitting covert or sensitive information cannot use all ties for this purpose. Rather, they can only use a subset of ties that are strong enough to be “trusted”. This paper...
Histogramming Data Streams with Fast Per-Item Processing (2008)
Abstract. Avector A of length N can be approximately represented by a histogram H, by writing [0;N) as the non-overlapping union of B intervals Ij, assigning a value bj to Ij, and approximating Ai by...
Joan Feigenbaum, Martin J. Strauss, Rebecca N. Wright
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct...
A Tutorial on Fast Fourier Sampling [How to apply it to problems] (2008)
Gilnert, Anna C., Strauss, Martin J., Tropp, Joel A.
This article describes a computational method, called the Fourier sampling algorithm, that exploits this insight [10]. The algorithm takes a small number of (correlated) random samples from a signal...
William A. Aiello, Aviel D. Rubin, Martin J. Strauss
smartcards to secure a personalized gambling device
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...
Private multiparty sampling and approximation of vector combinations (2007)
Yuval Ishai, Tal Malkin, Martin J. Strauss, Rebecca N. Wright
Abstract. We consider the problem of private efficient data mining of vertically-partitioned databases. Each of several parties holds a column of a data matrix (a vector) and the parties want to...
Private Approximate Heavy Hitters (2006)
Strauss, Martin J., Zheng, Xuan
We consider the problem of private computation of approximate Heavy Hitters. Alice and Bob each hold a vector and, in the vector sum, they want to find the B largest values along with their indices....
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...
Networks of strong ties (2006)
Shi, Xiaolin, Adamic, Lada A., Strauss, Martin J.
Social networks transmitting covert or sensitive information cannot use all ties for this purpose. Rather, they can only use a subset of ties that are strong enough to be ``trusted''. In this paper...
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...
Maintaining time-decaying stream aggregates (2003)
Edith Cohen, Martin J. Strauss
Abstract We formalize the problem of maintaining time-decaying aggregates and statistics of a data stream:the relative contribution of each data item to the aggregate is scaled down by a factor that...
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...
An Approximate L¹-Difference Algorithm for Massive Data Streams (2002)
Joan Feigenbaum, Sampath Kannan, Martin J. Strauss, Mahesh Viswanathan
Massive data sets are increasingly important in a wide range of applications, includingobservational sciences, product marketing, and the monitoring and operations of large systems. In network...
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 Maintenance (Extended Abstract) (2002)
Anna Gilbert, Yannis Kotidis, Sudipto Guha, S. Muthukrishnan, Piotr Indyk, Martin J. Strauss
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...
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...
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...
An approximate L 1 -dierence algorithm for massive data streams (1999)
Joan Feigenbaum, Sampath Kannan, Martin J. Strauss, Mahesh Viswanathan
Massive data sets are increasingly important in a wide range of applications, including observational sciences, product marketing, and monitoring and operations of large systems. In network...
Using smartcards to secure a personalized gambling device (1999)
William A. Aiello, Aviel D. Rubin, Martin J. Strauss
We introduce a technique for using an untrusted device, such as a hand-held personal digital assistant or a laptop to perform real financial transactions without a network. We utilize the...
Using Smartcards to Secure a Personalized Gambling Device (1999)
William A. Aiello, Aviel D. Rubin, Martin J. Strauss
We introduce a technique for using an untrusted device, such as a hand-held personal digital assistant or a laptop to perform real financial transactions without a network. We utilize the...