Floodlight Illumination of Infinite Wedges (2009)
Matthew Cary, Atri Rudra, Ashish Sabharwal, Erik Vee
The floodlight illumination problem asks whether there exists a one-to-one placement of n floodlights illuminating infinite wedges of angles α1,..., αn at n sites p1,..., pn in a plane such that a...
Scalable Ranked Publish/Subscribe (2009)
Ashwin Machanavajjhala, Erik Vee, Minos Garofalakis, Jayavel Shanmugasundaram
Publish/subscribe (pub/sub) systems are designed to efficiently match incoming events (e.g., stock quotes) against a set of subscriptions (e.g., trader profiles specifying quotes of interest)....
Efficient Top-K Processing Over Query-Dependent Functions (2009)
Lin Guo, Sihem Amer, Yahia Raghu, Ramakrishnan Jayavel Shanmugasundaram, Utkarsh Srivastava, Erik Vee
We study the efficient evaluation of top-k queries over data items, where the score of each item is dynamically computed by applying an item-specific function whose parameter value is specified in...
Efficient Bulk Insertion into a Distributed Ordered Table ABSTRACT (2009)
Adam Silberstein, Brian F. Cooper, Utkarsh Srivastava, Erik Vee, Ramana Yerneni, Raghu Ramakrishnan
We study the problem of bulk-inserting records into tables in a system that horizontally range-partitions data over a large cluster of shared-nothing machines. Each table partition contains a...
Floodlight Illumination of Infinite Wedges (2008)
Matthew Cary, Atri Rudra, Ashish Sabharwal, Erik Vee
The floodlight illumination problem asks whether there exists a one-to-one placement of n floodlights illuminating infinite wedges of angles α1,..., αn at n sites p1,..., pn in a plane such that a...
T. S. Jayram, Satyen Kale, Erik Vee
We study the problem of computing aggregation operators
Efficient Computation of Diverse Query Results (2008)
Erik Vee, Utkarsh Srivastava, Jayavel Shanmugasundaram, Prashant Bhat, Sihem Amer Yahia
We study the problem of efficiently computing diverse query results in online shopping applications, where users specify queries through a form interface that allows a mix of structured and...
Abstract Scalable Leader Election (2008)
Valerie King, Jared Saia, Vishal Sanwalani, Erik Vee
In the leader election problem, there are n processors of which (1 − b)n are good. The problem is to design a distributed protocol to elect a good leader from the set of all processors. In this...
Personalized Ad Delivery when Ads Fatigue: An Approximation Algorithm (2008)
Abstract. We consider a crucial aspect of displaying advertisements on the internet: the individual user. In particular, we consider ad fatigue, where a user tires of an advertisement as it is seen...
T. S. Jayram, Satyen Kale, Erik Vee
We study the problem of computing aggregation operators
Zoë Abrams, Arpita Ghosh, Erik Vee
We study keyword auctions in a setting where bidders have a vector of values for slots, and a bidder’s value for a slot is not necessarily proportional to the expected number of clicks in that...
David Liben-nowell, An Zhu, Erik Vee
We present algorithms and lower bounds for the Longest Increasing Subsequence (LIS) and Longest Common Subsequence (LCS) problems in the data-streaming model. To decide if the LIS of a given stream...
Floodlight Illumination of Infinite Wedges (2008)
Matthew Cary, Atri Rudra, Ashish Sabharwal, Erik Vee
The floodlight illumination problem asks whether there exists a one-to-one placement of n floodlights illuminating infinite wedges of angles α1,..., αn at n locations p1,..., pn in a plane such...
David Liben-nowell, Erik Vee, An Zhu
In this paper, we present algorithms and lower bounds for the Longest Increasing Subsequence (LIS) and Longest Common Subsequence (LCS) problems in the data streaming model. For the problem of...
Towards secure and scalable computation in peer-to-peer networks (2006)
Valerie King, Jared Saia, Vishal Sanwalani, Erik Vee
We consider the problems of Byzantine Agreement and Leader Election, where a constant fraction b < 1/3 of processors are controlled by a malicious adversary. The first problem requires that all...
Floodlight Illumination of Infinite Wedges (2005)
Matthew Cary, Atri Rudra, Ashish Sabharwal, Erik Vee
The floodlight illumination problem asks whether there exists a one-to-one placement of n floodlights illuminating infinite wedges of angles α1,..., αn at n sites p1,..., pn in a plane such that a...
Finding longest increasing and common subsequences in streaming data (2005)
David Liben-nowell, Erik Vee, An Zhu
In this paper, we present algorithms and lower bounds for the Longest Increasing Subsequence (LIS) and Longest Common Subsequence (LCS) problems in the data streaming model. For the problem of...
Time-space tradeoffs for nonuniform computation / (2004)
Thesis (Ph. D.)--University of Washington, 2004.
Comparing and aggregating rankings with ties (2004)
Ronald Fagin, Ravi Kumar, Mohammad Mahdian, D. Sivakumar, Erik Vee
Rank aggregation has recently been proposed as a useful abstraction that has several applications, including meta-search, synthesizing rank functions from multiple indices, similarity search, and...
Comparing partial rankings (2004)
Ronald Fagin, Ravi Kumar, Mohammad Mahdian, D. Sivakumar, Erik Vee
Abstract. We provide a comprehensive picture of how to compare partial rankings, that is, rankings that allow ties. We propose several metrics to compare partial rankings and prove that they are...
Comparing and aggregating rankings with ties (2004)
Ronald Fagin, Ravi Kumar, Mohammad Mahdian, D. Sivakumar, Erik Vee
Rank aggregation has recently been proposed as a useful abstraction that has several applications, including meta-search, synthesizing rank functions from multiple indices, similarity search, and...
Finding Longest Increasing and Common Subsequences in Streaming Data (2003)
Liben-Nowell, David, Vee, Erik, Zhu, An
In this paper, we present algorithms and lower bounds for the Longest Increasing Subsequence(LIS) and Longest Common Subsequence (LCS) problems in the data streaming model.
Finding Longest Increasing and Common Subsequences in Streaming Data (2003)
Liben-Nowell, David, Vee, Erik, Zhu, An
In this paper, we present algorithms and lower bounds for the Longest Increasing Subsequence(LIS) and Longest Common Subsequence (LCS) problems in the data streaming model.
Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems (2002)
We extend recent techniques for time-space tradeoff lower bounds using multiparty communication complexity ideas. Using these arguments, for inputs from large domains we prove larger tradeoff lower...
Super-linear time-space tradeoff lower bounds for randomized computation (2000)
Paul Beame, Michael Saks, Xiaodong Sun, Erik Vee
problems
Super-Linear Time-Space Tradeoff Lower Bounds for Randomized Computation (2000)
Paul Beame, Michael Saks, Xiaodong Sun, Erik Vee
We prove the first time-space lower bound tradeo#s for randomized computation of decision problems where computation error is allowed. Our techniques are an extension of those used by Ajtai [4, 5] in...