STREAM ORDER AND ORDER STATISTICS: QUANTILE ESTIMATION IN RANDOM-ORDER STREAMS ∗ (2009)
Abstract. When trying to process a data-stream in small space, how important is the order in which the data arrives? Are there problems that are unsolvable when the ordering is worst-case, that can...
Finding Metric Structure in Information Theoretic Clustering (2009)
Kamalika Chaudhuri, Andrew Mcgregor
We study the problem of clustering discrete probability distributions with respect to the Kullback-Leibler (KL) divergence. This problem arises naturally in many applications. Our goal is to pick k...
Presentation detailing past, present and future work by JISC funded projects related to repository use and development.
Institutional Repositories in the UK: The JISC Approach (2009)
Neil Jacobs, Amber Thomas, Andrew McGregor
Library Trends - Volume 57, Number 2, Fall 2008
Island hopping and path colouring, with applications to WDM network design (2009)
Two benefits of optical communication are (a) the possibility of using a single fiber optic cable to carry multiple signals simultaneously if each signal uses light of a distinct wavelength, and (b)...
Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams (2009)
Guha, Sudipto, Mcgregor, Andrew
When trying to process a data stream in small space, how important is the order in which the data arrive? Are there problems that are unsolvable when the ordering is worst case, but that can be...
Declaring Independence via the Sketching of Sketches (2008)
We consider the problem of identifying correlations in data streams. Surprisingly, our work seems to be the first to consider this natural problem. In the centralized model, we consider a stream of...
Graph Distances in the Data-Stream Model (2008)
Feigenbaum, Joan, Kannan, Sampth, Mcgregor, Andrew, Suri, Siddarth, Zhang, Jian
We explore problems related to computing graph distances in the data-stream model. The goal is to design algorithms that can process the edges of a graph in an arbitrary order given only a limited...
Amit Chakrabarti, Graham Cormode, Andrew Mcgregor
We describe a simple algorithm for approximating the empirical entropy of a stream of m values in a single pass, using O(ε −2 log(δ −1) log m) words of space. Our algorithm is based upon a...
Better Bounds for Frequency Moments in Random-Order Streams (2008)
Andoni, Alexandr, McGregor, Andrew, Onak, Krzysztof, Panigrahy, Rina
Estimating frequency moments of data streams is a very well studied problem and tight bounds are known on the amount of space that is necessary and sufficient when the stream is adversarially...
Abstract Reconstructing Strings from Random Traces (2008)
Sampath Kannan, Sanjeev Khanna, Andrew Mcgregor
We are given a collection of m random subsequences (traces) of a string t of length n where each trace is obtained by deleting each bit in the string with probability q. Our goal is to exactly...
Prof Eva Tardos, Vlady Ravelomanana, Herve Daudé, Ivan Rapaport, Karol Suchan, Ioan Todinca, ...
15:00-15:20 Computing the growth of the number of overlap-free words with spectra
Island hopping and path colouring, with applications to WDM network design (2008)
Wavelength division multiplexed (WDM) optical communication offers the advantages of increased capacity and decreased latency for signals (traffic) carried across such networks. The devices used for...
SYNONYMS Graph Streams; Semi-Streaming Model Graph Mining on Streams (2008)
Consider a data stream A = 〈a1, a2,..., am 〉 where each data item ak ∈ [n] × [n]. Such a stream naturally defines an undirected, unweighted graph G = (V, E) where V = {v1,..., vn} and, E =...
LIST DECODING OF CONCATENATED CODES: IMPROVED PERFORMANCE ESTIMATES (2008)
Alexander Barg, Andrew Mcgregor
Abstract. An improved bound is proved on the list-decoding radius of a concatenated code relying upon a combination of (soft-decision) algebraic list decoding and generalized minimum distance (GMD)...
Checking and Spot-Checking the Correctness of Priority Queues (2008)
Matthew Chu, Sampath Kannan, Andrew Mcgregor
Abstract. We revisit the problem of memory checking considered by Blum et al. [3]. In this model, a checker monitors the behavior of a data structure residing in unreliable memory given an arbitrary...
Amit Chakrabarti, Graham Cormode, Andrew Mcgregor
We describe a simple algorithm for approximating the empirical entropy of a stream of m values in a single pass, using O(ε −2 log(δ −1) log m) words of space. Our algorithm is based upon a...
A Bond Graphs approach to Physical Modelling of Musical Instruments (2008)
Andrew Mcgregor, Eduardo Mir, A Peter Gawthrop
In this paper we introduce the use of bond graphs for the implementation of classic physical models of musical instruments. Bond graphs are a diagram-based technique for representing physical...
Tight Lower Bounds for Multi-Pass Stream Computation via Pass Elimination (2008)
There is a natural relationship between lower bounds in the multi-pass stream model and lower bounds in multiround communication. However, this connection is less understood than the connection...
Joan Feigenbaum, Joan Feigenbaum, Siddharth Suri, Siddharth Suri, Sampath Kannan, Sampath Kannan, ...
We investigate the importance of space when solving problems based on graph distance in the streaming model. In this model, the input graph is presented as a stream of edges in an arbitrary order....
Student Competition: Integrating Archival Data with mapping (2007)
Andrew McGregor Undergraduate, Department of Social Sciences (History) Baker University
Integrating Archival Data with mapping (2007)
* KU Department of Geography * State of Kansas Data Access and Support Center (DASC) * KU Libraries GIS and Scholar Services * KU Transportation Research Institute * KU Institute for Policy & Social...
Sorting and Selection with Random Costs (2007)
Angelov, Stanislav, Kunal, Keshav, McGregor, Andrew
There is a growing body of work on sorting and selection in models other than the unit-cost comparison model. This work is the first treatment of a natural stochastic variant of the problem where the...
Lower Bounds for Quantile Estimation in Random-Order and Multi-Pass Streaming (2007)
Guha, Sudipto, McGregor, Andrew
We present lower bounds on the space required to estimate the quantiles of a stream of numerical values. Quantile estimation is perhaps the most studied problem in the data stream model and it is...
On the Hardness of Approximating Stopping and Trapping Sets in LDPC Codes (2007)
McGregor, Andrew, Milenkovic, Olgica
We prove that approximating the size of stopping and trapping sets in Tanner graphs of linear block codes, and more restrictively, the class of low-density parity-check (LDPC) codes, is NP-hard. The...
Processing data streams (2007)
Data streams are ubiquitous. Examples include the network traffic flowing past a router, data generated by an SQL query, readings taken in a sensor network, and files read from an external memory...
Lower bounds for quantile estimation in random-order and multi-pass streaming (2007)
Abstract. We present lower bounds on the space required to estimate the quantiles of a stream of numerical values. Quantile estimation is perhaps the most studied problem in the data stream model and...
Graduate Group Chairperson (2007)
Andrew Mcgregor, Sampath Kannan, Rajeev Alur, Andrew Mcgregor
I am fortunate to have learnt a lot from some great people during my time in graduate school. First and foremost, I would like to thank Sampath Kannan for being a fantastic advisor. Talking with...
On the hardness of approximating stopping and trapping sets in LDPC codes (2007)
Abstract — We prove that approximating the size of the smallest trapping set in Tanner graphs of linear block codes, and more restrictively, LDPC codes, is NP-hard. The proof techniques rely on...
Sketching information divergences (2007)
Sudipto Guha, Piotr Indyk, Andrew Mcgregor
When comparing discrete probability distributions, natural measures of similarity are not ℓp distances but rather are information divergences such as Kullback-Leibler and Hellinger. This paper...
Sketching information divergences (2007)
Sudipto Guha, Piotr Indyk, Andrew Mcgregor
Abstract. When comparing discrete probability distributions, natural measures of similarity are not ℓp distances but rather are informationdivergences such as Kullback-Leibler and Hellinger. This...
Sketching information divergences (2007)
Sudipto Guha, Piotr Indyk, Andrew Mcgregor
When comparing discrete probability distributions, natural measures of similarity are not ℓp distances but rather are information-divergences such as Kullback-Leibler and Hellinger. This paper...
Estimating Aggregate Properties on Probabilistic Streams (2006)
McGregor, Andrew, Muthukrishnan, S.
The probabilistic-stream model was introduced by Jayram et al. \cite{JKV07}. It is a generalization of the data stream model that is suited to handling ``probabilistic'' data where each item of the...
Streaming and sublinear approximation of entropy and information distances (2006)
Sudipto Guha, Andrew Mcgregor, Suresh Venkatasubramanian
In most algorithmic applications which compare two distributions, information theoretic distances are more natural than standard ℓp norms. In this paper we design streaming and sublinear time...
Stream-Order and Order-Statistics (2006)
When processing a data-stream in small space, how important is the order in which the data arrives? Are there problems that are unsolvable when the ordering is worst-case, that can typically be...
Streaming and sublinear approximation of entropy and information distances (2006)
Sudipto Guha, Andrew Mcgregor, Suresh Venkatasubramanian
In most algorithmic applications which compare two distributions, information theoretic distances are more natural than standard ℓp norms. In this paper we design streaming and sublinear time...
On Graph Problems in a Semi-Streaming Model (2005)
Feigenbaum, Joan, Kannan, Sampath, McGregor, Andrew, Suri, Siddharth, Zhang, Jian
We formalize a potentially rich new streaming model, the semi-streaming model, that we believe is necessary for the fruitful study of efficient algorithms for solving problems on massive graphs whose...
Streaming and Sublinear Approximation of Entropy and Information Distances (2005)
Guha, Sudipto, McGregor, Andrew, Venkatasubramanian, Suresh
In many problems in data mining and machine learning, data items that need to be clustered or classified are not points in a high-dimensional space, but are distributions (points on a high...
Graph distances in the streaming model: the value of space (2005)
Joan Feigenbaum, Sampath Kannan, Andrew Mcgregor, Siddharth Suri, Jian Zhang
We investigate the importance of space when solving problems based on graph distance in the streaming model. In this model, the input graph is presented as a stream of edges in an arbitrary order....
Distance distribution of binary codes and the error probability of decoding (2004)
Barg, Alexander, McGregor, Andrew
We address the problem of bounding below the probability of error under maximum likelihood decoding of a binary code with a known distance distribution used on a binary symmetric channel. An improved...
Reconstructing strings from random traces (2004)
Batu, Tugkan, Kannan, Sampath, Khanna, Sanjeev, McGregor, Andrew
Reconstructing Strings from Random Traces (2004)
Batu, Tugkan, Kannan, Sampath, Khanna, Sanjeev, McGregor, Andrew
We are given a collection of m random subsequences (traces) of a string t of length n where each trace is obtained by deleting each bit in the string with probability q. Our goal is to exactly...
Finding Matchings in the Streaming Model (2004)
This report presents algorithms for finding large matchings in the streaming model. In this model, applicable when dealing with massive graphs, edges are streamed-in in some arbitrary order rather...
On graph problems in a semi-streaming model (2004)
Joan Feigenbaum, Sampath Kannan, Andrew Mcgregor, Jian Zhang
Abstract. We formalize a potentially rich new streaming model, the semi-streaming model, that we believe is necessary for the fruitful study of efficient algorithms for solving problems on massive...
On graph problems in a semi-streaming model (2004)
Joan Feigenbaum, Sampath Kannan, Andrew Mcgregor, Jian Zhang
Abstract. We formalize a potentially rich new streaming model, the semi-streaming model, that we believe is necessary for the fruitful study of ecient algorithms for solving problems on massive...
Warm fuzzy feelings : discursive explorations into Australian environmental imaginations (2000)
McGregor, Andrew (Andrew Robin)
Bibliography: leaves 274-296.
Patient Warming Device for Casualty Care (1998)
Hansen, Gary, Albrecht, Mark, Barrows, Ryan, McGregor, Andrew, Sparrow, Ephraim
We have shown that convective air warming device (e.g., "Bair Hugger') is feasible for cold weather conditions and aeromedical evacuation. The goal of the project was to develop such a device that...
Spatial scan statistics: Approximations and performance study (1991)
Deepak Agarwal, Suresh Venkatasubramanian, Andrew Mcgregor, Jeff M. Phillips, Zhengyuan Zhu
Spatial scan statistics are used to determine hotspots in spatial data, and are widely used in epidemiology and biosurveillance. In recent years, there has been much effort invested in designing...
Photocopy of typescript. Bibliography: p. 60-62.
Capital rent extraction and the survival of the producer cooperative. (1974)
Thesis (M.S.)--Cornell University, June 1974.
Joan Feigenbaum, Sampath Kannan, Andrew Mcgregor, Siddharth Suri, Jian Zhang
Abstract. We explore problems related to computing graph distances in the data-stream model. The goal is to design algorithms that can process the edges of a graph in an arbitrary order given only a...