Tighter Estimation using Bottom-k Sketches (2009)
Summaries of massive data sets support approximate query processing over the original data. A basic aggregate over a set of records is the weight of subpopulations specified as a predicate over...
Envy-Free Makespan Approximation (2009)
Cohen, Edith, Feldman, Michal, Fiat, Amos, Kaplan, Haim, Olonetsky, Svetlana
We study envy-free mechanisms for scheduling tasks on unrelated machines (agents) that approximately minimize the makespan. For indivisible tasks, we put forward an envy-free poly-time mechanism that...
Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments (2009)
Cohen, Edith, Kaplan, Haim, Sen, Subhabrata
Many data sources are naturally modeled by multiple weight assignments over a set of keys: snapshots of an evolving database at multiple points in time, measurements collected over multiple time...
ABSTRACT Tighter Estimation using Bottom k Sketches (2009)
Summaries of massive data sets support approximate query processing over the original data. A basic aggregate over a set of records is the weight of subpopulations specified as a predicate over...
Leveraging Discarded Samples for Tighter Estimation of Multiple-Set Aggregates (2009)
Many datasets such as market basket data, text or hypertext documents, and sensor observations recorded in different locations or time periods, are modeled as a collection of sets over a ground set...
ABSTRACT Processing Top-k Queries from Samples (2009)
queries are desired aggregation operations on data sets. Examples of queries on network data include the top 100 source AS’s, Top-¢ top 100 ports, or top Domain names over IP packets or over IP...
ABSTRACT Sketching Unaggregated Data Streams for Subpopulation-Size Queries (2009)
IP packet streams consist of multiple interleaving IP flows. Statistical summaries of these streams, collected for different measurement periods, are used for characterization of traffic, billing,...
ABSTRACT Summarizing Data using Bottom-k Sketches (2008)
sketch is a summary of a set of items with nonnegative weights that supports approximate query processing. A sketch is obtained by associating with each item in a ground set an independent random...
General General Terms Algorithms (2008)
Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke
A recent seminal result of Räcke is that for any network there is an oblivious routing algorithm with a polylog competitive ratio with respect to congestion. Unfortunately, Räcke’s construction...
1 Introduction The Internet provides a platform for decentralized applications where content or services are requested, stored, and provided by very large number of loosely coupled hosts. In these...
Abstract A new general theory about restoration of network paths is first introduced. The theory pertains to restoration of shortest paths in a network following failure, e.g., we prove that a...
General General Terms Algorithms (2008)
Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke
A recent seminal result of Räcke is that for any network there is an oblivious routing algorithm with a polylog competitive ratio with respect to congestion. Unfortunately, Räcke’s construction...
ABSTRACT Spatially-Decaying Aggregation Over a Network: Model and Algorithms (2008)
Data items are often associated with a location in which they are present or collected, and their relevance or in uence decays with their distance. Aggregate values over such data thus depend on the...
ABSTRACT Sketching Unaggregated Data Streams for Subpopulation-Size Queries (2008)
IP packet streams consist of multiple interleaving IP flows. Statistical summaries of these streams, collected for different measurement periods, are used for characterization of traffic, billing,...
Variance optimal sampling based estimation of subset sums (2008)
Cohen, Edith, Duffield, Nick, Kaplan, Haim, Lund, Carsten, Thorup, Mikkel
From a high volume stream of weighted items, we want to maintain a generic sample of a certain limited size $k$ that we can later use to estimate the total weight of arbitrary subsets. This is the...
Sketch-Based Estimation of Subpopulation-Weight (2008)
Summaries of massive data sets support approximate query processing over the original data. A basic aggregate over a set of records is the weight of subpopulations specified as a predicate over...
tralizedarchitecturesseemtosupportatmostone:pre partial-matchqueries,butsincesearchisunrelatedtothe vailingprotocols(suchasGnutellaandFastTrack)support...
ABSTRACT Summarizing Data using Bottom-k Sketches (2008)
A Bottom-k sketch is a summary of a set of items with nonnegative weights that supports approximate query processing. A sketch is obtained by associating with each item in a ground set an independent...
Processing Top-k Queries from Samples (2008)
Edith Cohen, Nadav Grossaug, Haim Kaplan
Top-k queries are desired aggregation operations on data sets. Examples of queries on network data include finding the top 100 source Autonomous Systems (AS), top 100 ports, or top domain names over...
1 Restoration by Path Concatenation: Fast Recovery of MPLS Paths (2007)
Anat Bremler-barr, Yehuda Afek, Haim Kaplan, Edith Cohen, Michael Merritt
A new general theory about restoration of network paths is first introduced. The theory pertains to restoration of shortest paths in a network following failure, e.g., we prove that a shortest path...
Multi-Rate Detection For The Is-95 Cdma Forward Traffic Channels (2007)
The IS-95 Direct Sequence Code Division Multiple Access (DS-CDMA) system has become a U.S. digital cellular standard. In the forward traffic channels (from the base station to the mobiles), the...
Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick
Reachability and distance queries in graphs are fundamental to numerous applications, ranging from geographic navigation systems to Internet routing. Some of these applications involve huge graphs...
1 Prefetching the Means for Document Transfer: A New Approach for Reducing Web Latency (2007)
User-perceived latency is recognized as the central performance problem in the Web. We systematically measure factors contributing to this latency, across several locations. Our study reveals that...
Connection caching: Model and algorithms (2007)
Edith Cohen, Haim Kaplan, Uri Zwick
We introduce a theoretical model for connection caching. In our model each host maintains (caches) a limited number of open connections to other hosts. A request may utilize an open connection in...
Abstract Reachability and distance queries via 2-hop labels (2007)
Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick
Reachability and distance queries in graphs are fundamental to numerous applications, ranging from geographic navigation systems to Internet routing. Some of these applications involve huge graphs...
The success of a P2P file-sharing network highly depends on the scalability and versatility of its search mechanism. Two particularly desirable search features are scope (ability to find infrequent...
Edith Cohen, Mayur Datar, Shinji Fujiwara, Aristides Gionis, Piotr Indyk, Rajeev Motwani, ...
Association-rule mining has heretofore relied on the condition of high support to do its work efficiently. In particular, the well-known a-priori algorithm is only effective when the only rules of...
Edith Cohen, Eran Halperin, Haim Kaplan
Performance aspects of distributed caches using
1 Refreshment Policies for Web Content Caches (2007)
Web content caches are often placed between end-users and origin servers as a mean to reduce server load, network usage, and ultimately, user-perceived latency. Cached objects typically have...
Edith Cohen, Haim Kaplan, Uri Zwick
Abstract. We present a competitive analysis of the LRFU paging algorithm, a hybrid of the LRU (Least Recently Used) and LFU (Least Frequently Used) paging algorithms. We show that the competitive...
Algorithms and estimators for accurate summarization of Internet traffic (2007)
Statistical summaries of traffic in IP networks are at the heart of network operation and are used to recover information on arbitrary subpopulations of flows. It is therefore of great importance to...
Algorithms and estimators for accurate summarization of Internet traffic (2007)
Statistical summaries of traffic in IP networks are at the heart of network operation and are used to recover information on arbitrary subpopulations of flows. It is therefore of great importance to...
Algorithms and estimators for accurate summarization of Internet traffic (2007)
Statistical summaries of traffic in IP networks are at the heart of network operation and are used to recover information on arbitrary subpopulations of flows. It is therefore of great importance to...
Bottom-k sketches: Better and more efficient estimation of aggregates (2007)
A Bottom- sketch is a summary of a set of items with nonnegative weights. Each such summary allows us to compute approximate aggregates over the set of items. Bottom-sketches are obtained by...
A short walk in the Blogistan (2006)
The increasingly prominent new subset of Web pages, called ‘blogs ’ differs from traditional Web pages both in characteristics and potential to applications. We explore three aspects of the...
Optimal oblivious routing in polynomial time (2003)
Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke
A recent seminal result of Räcke is that for any undirected network there is an oblivious routing algorithm with a polylogarithmic competitive ratio with respect to congestion. Unfortunately,...
Maintaining time-decaying stream aggregates (2003)
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...
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...
Efficient Sequences of Trials (2003)
Edith Cohen, Amos Fiat, Haim Kaplan, Evelle J. Younger, La Times
We introduce a problem called sequential trial optimization, a generalization of the well studied set cover problem with a new objective function. We give a simple algorithm that achieves a constant...
Optimal Oblivious Routing in Polynomial Time (2003)
Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke
A recent seminal result of Räcke is that for any network there is an oblivious routing algorithm with a polylog competitive ratio with respect to congestion. Unfortunately, Räcke's...
Reachability and Distance Queries via 2-hop Labels (2002)
Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick
1 Reachability and distance queries in graphs are fundamental to numerous applications, ranging from geographic navigation systems to Internet routing. Some of these applications involve huge graphs...
Search and replication in unstructured peer-to-peer networks (2002)
Qin Lv, Pei Cao, Edith Cohen, Kai Li, Scott Shenker
Abstract Decentralized and unstructured peer-to-peer networks such as Gnutella are attractive for certain applicationsbecause they require no centralized directories and no precise control over...
Replication Strategies in Unstructured Peer-to-Peer Networks (2002)
The Peer-to-Peer (P2P) architectures that are most prevalent in today’s Internet are decentralized and unstructured. Search is blind in that it is independent of the query and is thus not more...
Predicting and bypassing end-to-end Internet service degradations (2002)
Anat Bremler-barr, Edith Cohen, Haim Kaplan, Yishay Mansour
We study the patterns and predictability of Internet End-to-End service degradations, where a degradation is a significant deviation of the round trip time between a client and a server. We use...
Labeling Dynamic XML Trees (2002)
Edith Cohen Att, Edith Cohen, Haim Kaplan, Tova Milo
We present algorithms to label the nodes of an XML tree which is subject to insertions and deletions of nodes. The labeling is done such that (1) we label each node immediately when it is inserted...
Balanced-replication algorithms for distribution trees (2002)
Abstract In many Internet applications, requests for a certain object are routed bottom-up over a tree where the root of the tree is the node containing the object. When an object becomes popular,...
Search and replication in unstructured peer-to-peer networks (2002)
Qin Lv, Pei Cao, Edith Cohen, Kai Li, Scott Shenker
Decentralized and unstructured peer-to-peer networks such as Gnutella are attractive for certain applications because they require no centralized directories and no precise control over network...
Aging through cascaded caches: Performance issues in the distribution of web content (2001)
The Web is a distributed system, where data is stored and disseminated from both origin servers and caches. Origin servers provide the most up-to-date copy whereas caches store and serve copies that...
Refreshment policies for web content caches (2001)
Web content caches are often placed between end-users and origin servers as a mean to reduce server load, network usage, and ultimately, user-perceived latency. Cached objects typically have...
Competitive analysis of the LRFU paging algorithm (2001)
Edith Cohen, Haim Kaplan, Uri Zwick
We present a competitive analysis of the LRFU paging algorithm, a hybrid of the LRU (Least Recently Used) and LFU (Least Frequently Used) paging algorithms. We show that the competitive ratio of LRFU...
Restoration by Path Concatenation: Fast Recovery of MPLS Paths (2001)
Yehuda Afek, Anat Bremler-barr, Haim Kaplan, Edith Cohen, Michael Merritt
A new general theory about restoration of network paths is rst introduced. The theory pertains to restoration of shortest paths in a network following failure, e.g., we prove that a shortest path in...
Aging through cascaded caches: Performance issues in the distribution of web content (2001)
The Web is a distributed system, where data is stored and disseminated from both origin servers and caches. Origin servers provide the most up-to-date copy whereas caches store and serve copies that...
Restoration by Path Concatenation: Fast Recovery of MPLS Paths (2001)
Anat Bremler-barr, Yehuda Afek, Haim Kaplan, Edith Cohen, Michael Merritt
A new general theory about restoration of network paths is rst introduced. The theory pertains to restoration of shortest paths in a network following failure, e.g., we prove that a shortest path in...
Proactive caching of DNS records: Addressing a performance bottleneck (2001)
The resolution of a host name to an IP-address is a necessary predecessor to connection establishment and HTTP exchanges. Nonetheless, DNS resolutions often involve multiple remote name-servers and...
The age penalty and its effect on cache performance (2001)
Web content caching is recognized as an effective mechanism to decrease server load, network traffic, and user-perceived latency. An HTTP compliant cache associates with each cached object an...
Competitive analysis of the LRFU paging algorithm (2001)
Edith Cohen Haim, Edith Cohen, Haim Kaplan, Uri Zwick
We present a competitive analysis of the LRFU paging algorithm, a hybrid of the LRU (Least Recently Used) and LFU (Least Frequently Used) paging algorithms. We show that the competitive ratio of LRFU...
Search and Replication in Unstructured Peer-to-Peer Networks (2001)
Qin Lv, Pei Cao, Edith Cohen, Kai Li, Scott Shenker
Decentralized and unstructured peer-to-peer networks such as Gnutella are attractive for certain applications because they require no centralized directories and no precise control over network...
Restoration by Path Concatenation: Fast Recovery of MPLS Paths (2001)
Yehuda Afek, Anat Bremler-barr, Haim Kaplan, Edith Cohen, Michael Merritt
A new general theory about restoration of network paths is first introduced. The theory pertains to restoration of shortest paths in a network following failure, e.g., we prove that a shortest path...
Connection Caching under (2000)
Various Models Of, Edith Cohen, Haim Kaplan, Uri Zwick
Motivated by Web applications, we recently introduced the following theoretical model for connection-caching: Each host on a network can maintain (cache) a limited number of connections to other...
Prefetching the Means for Document Transfer: A New Approach for Reducing Web Latency (2000)
User-perceived latency is recognized as the central performance problem in the Web. We systematically measure factors contributing to this latency, across several locations. Our study reveals that...
Prefetching the Means for Document Transfer: A New Approach for Reducing Web Latency (2000)
User-perceived latency is recognized as the central performance problem in the Web. We systematically measure factors contributing to this latency, across several locations. Our study reveals that...
All-Pairs Small-Stretch Paths (2000)
length is at most t times the distance between u and v in the graph. We consider the problem of finding small-stretch paths between all pairs of vertices in the graph G.
Finding Interesting Associations without Support Pruning (2000)
Edith Cohen, Mayur Datar, Shinji Fujiwara, Aristides Gionis, Piotr Indyk, Rajeev Motwani, ...
Association-rule mining has heretofore relied on the conditionof high support to do its work efficiently. In particular, the well-known a-priori algorithm is only effective when the only rules of...
Finding interesting associations without support pruning (2000)
Edith Cohen, Mayur Datar, Shinji Fujiwara, Aristides Gionis, Piotr Indyk, Rajeev Motwani, ...
Abstract Association-rule mining has heretofore relied on the condition of high support to do its work efficiently. In particular, the well-known a-priori algorithm is only effective when the only...
Caching documents with variable sizes and fetching costs: an LP based approach (1999)
We give an integer programming formulation of the paging problem with varying sizes and fetching costs. We use this formulation to provide an alternative proof that a variant of the algorithm...
Exploiting regularities in Web traffic patterns for cache replacement (1999)
Caching web pages at proxies and in web servers' memories can greatly enhance performance. Proxy caching is known to reduce network load and both proxy and server caching can significantly...
Policies for managing TCP connections under persistent HTTP (1999)
Edith Cohen, Haim Kaplan, Jeffrey D. Oldham
Hyper Text Transfer Protocol (HTTP) traffic dominates Internet traffic. The exchange of HTTP messages is implemented using the connection-oriented TCP. HTTP/1.0 establishes a new TCP connection for...
Exploiting regularities in Web traffic patterns for cache replacement (1999)
Abstract Caching web pages at proxies and in web servers ' memories can greatly enhance performance. Proxy caching is known to reduce network load and both proxy and server caching can...
Exploiting regularities in Web traffic patterns for cache replacement (1999)
Caching web pages at proxies and in web servers ' memories can greatly enhance performance. Proxy caching is known to reduce network load and both proxy and server caching can significantly...
Edith Cohen, Haim Kaplan, Uri Zwick
Communication between clients and servers in the Web is performed using TCP (Transmission Control Protocol). TCP first opens a connection between the two nodes and then sends data packets via this...
Caching Documents with Variable Sizes and Fetching Costs: An LP-Based Approach (1999)
We give an integer programming formulation of the paging problem with varying sizes and fetching costs. We use this formulation to provide an alternative proof that a variant of the algorithm...
Finding Interesting Associations without Support Pruning (1999)
Edith Cohen, Mayur Datar, Shinji Fujiwara, Aristides Gionis, Piotr Indyk, Jeffrey D. Ullman, ...
Association-rule mining has heretofore relied on the condition of high support to do its work efficiently. In particular, the well-known a-priori algorithm is only effective when the only rules of...
Edith Cohen Haim, Edith Cohen, Haim Kaplan, Uri Zwick
Communication between clients and servers in the Web is performed using TCP (Transmission Control Protocol) . TCP first opens a connection between the two nodes and then sends data packets via this...
Managing TCP Connections under Persistent HTTP (1999)
Edith Cohen, Haim Kaplan, Jeffrey D. Oldham
Hyper Text Transfer Protocol (HTTP) traffic dominates Internet traffic. The exchange of HTTP messages is implemented using the connection-oriented TCP.
Combinatorial Algorithms for Optimization Problems. (1998)
Linear programming is a very general and widely used framework. In this thesis we consider several combinatorial optimization problems that can be viewed as classes of linear programming problems...
Evaluating server-assisted cache replacement in the Web (1998)
Edith Cohen, Er Krishnamurthy, Jennifer Rexford
To reduce user-perceived latency in retrieving documents on the world wide web, a commonly used technique is caching both at the client's browser and more gainfully (due to sharing) at a proxy....
Improving End-to-End Performance of the Web Using Server Volumes and Proxy Filters (1998)
Edith Cohen, Er Krishnamurthy, Jennifer Rexford
The rapid growth of the World Wide Web has caused serious performance degradation on the Internet. This paper offers an end-to-end approach to improving Web performance by collectively examining the...
Improving End-to-End Performance of the Web Using Server Volumes and Proxy Filters (1998)
Edith Cohen, Balachander Krishnamurthy, From Edith Cohen, Jennifer Rexford
This paper offers an end-to-end framework by collectively examining the Web components -- clients, proxies, servers, and the network. Our goal is to reduce user-perceived latency and the number of...
Efficient Algorithms for Predicting Requests to Web Servers (1998)
Edith Cohen, Er Krishnamurthy, Jennifer Rexford
Internet traffic has grown significantly with the popularity of the Web. Consequently user perceived latency in retrieving web pages has increased. Caching and prefetching at the client side, aided...
Evaluating Server-Assisted Cache Replacement in the Web (1998)
Edith Cohen, Balachander Krishnamurthy, Er Krishnamurthy, Jennifer Rexford
. To reduce user-perceived latency in retrieving documents on the world wide web, a commonly used technique is caching both at the client's browser and more gainfully (due to sharing) at a...
Efficient Algorithms for Predicting Requests to Web Servers (1998)
Edith Cohen, Balachander Krishnamurthy, From Edith Cohen, Jennifer Rexford
this paper The entries needed for our study were the IP address of the client (proxy), the accessed resource, and the time of the access. We converted the first two into hashed integers, the ASCII...
Efficient Algorithms for Predicting Requests to Web Servers (1998)
Edith Cohen, Balachander Krishnamurthy, Er Krishnamurthy, Jennifer Rexford
Due to the dramatic increase in the popularity of the World Wide Web, where clients and proxies access resources on servers, Internet traffic has grown significantly. Correspondingly, user perceived...
All-Pairs Small-Stretch Paths (1997)
Let G = (V; E) be a weighted undirected graph. A path between u; v 2 V is said to be of stretch t if its length is at most t times the distance between u and v in the graph. We consider the problem...
Approximating Matrix Multiplication for Pattern Recognition Tasks (1997)
Many pattern recognition tasks, including estimation, classification, and the finding of similar objects, make use of linear models. The fundamental operation in such tasks is the computation of the...
Improvise: Interactive Multimedia Process Visualization Environment (1995)
Naser S. Barghouti, Eleftherios Koutsofios, Edith Cohen
. Improvise is a multimedia system for modeling, visualizing and documenting software and business processes. It runs under Microsoft Windows and on most flavors of the UNIX operating system....
When Piecewise Determinism Is (1995)
Almost Edith, Edith Cohen, Yi-min Wang, Gaurav Suri
Most existing log-based recovery techniques assume perfect piecewise determinism. In practice, however, the behavior of certain events is determined by the execution environment, and is not...
When Piecewise Determinism Is (1995)
Almost Edith, Edith Cohen, Yi-min Wang, Gaurav Suri
Most existing log-based recovery techniques assume perfect piecewise determinism. In practice, however, the behavior of certain events is determined by the execution environment, and is not...
Maximizing Concave Functions in Fixed Dimension (1993)
In [3, 5, 2] the authors introduced a technique which enabled them to solve the parametric minimum cycle problem with a fixed number of parameters in strongly polynomial time. In the current paper 1...
Maximizing Concave Functions in Fixed Dimension (1993)
In [3, 5, 2] the authors introduced a technique which enabled them to solve the parametric minimum cycle problem with a fixed number of parameters in strongly polynomial time. In the currentpaper we...
Combinatorial algorithms for optimization problems [microform] / (1991)
Linear programming is a very general and widely used framework. In this thesis we consider several combinatorial optimization problems that can be viewed as classes of linear programming problems...
Finding Interesting Associations without Support Pruning
Edith Cohen, Mayur Datar, Shinji Fujiwara, Aristides Gionis, Piotr Indyk, Rajeev Motwani, ...
Association-rule mining has heretofore relied on the condition of high support to do its work efficiently. In particular, the well-known a-priori algorithm is only effective when the only rules of...