Line Transversals of Convex Polyhedra in $\reals^3$ (2008)
Kaplan, Haim, Rubin, Natan, Sharir, Micha
We establish a bound of $O(n^2k^{1+\eps})$, for any $\eps>0$, on the combinatorial complexity of the set $\T$ of line transversals of a collection $\P$ of $k$ convex polyhedra in $\reals^3$ with a...
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...
Data Structures for Mergeable Trees (2007)
Georgiadis, Loukas, Kaplan, Haim, Shafrir, Nira, Tarjan, Robert E., Werneck, Renato F.
Motivated by an application in computational topology, we consider a novel variant of the problem of efficiently maintaining dynamic rooted trees. This variant requires merging two paths in a single...
Learning with Attribute Costs (2005)
Kaplan, Haim, Kushilevitz, Eyal, Mansour, Yishay
We study an extension of the ``standard'' learning models to settings where observing the value of an attribute has an associated cost (which might be different for different attributes). Our model...
Addendum to "Scalable Secure Storage when Half the System is (2004)
Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien Stern
Introduction. We consider the following problem. A file of size s bits is to be stored on n disks. Our failure model assumes that a potentially malicious adversary may choose after the file is stored...
Persistent data structures Haim Kaplan (2004)
this paper is as follows. Section 1.2 describes few algorithms that use persistent data structures to achieve their best time or space bounds. Section 1.3 surveys the general methods to make data...
Optimal Oblivious Routing in Polynomial Time (2003)
Yossi Azar, Edith Cohen, Haim Kaplan
A recent seminal result of Racke is that for any network there is an oblivious routing algorithm with a polylog competitive ratio with respect to congestion. Unfortunately, Racke's construction is...
Associative Search in Peer to Peer Networks: Harnessing Latent Semantics (2003)
Edith Cohen, Amos Fiat, Haim Kaplan
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...
Associative Search in Peer to Peer Networks: Harnessing Latent Semantics (2002)
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...
Efficient Data Structures and a New Randomized Approach for Sorting Signed Permutations (2002)
The problem of sorting signed permutations by reversals (SBR) is a fundamental problem in computational molecular biology. The goal is, given two genomes (represented as permutations of the gene...
Ecient Sequences of Trials (2002)
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...
A Case for Associative Peer to Peer Overlays (2002)
Edith Cohen, Amos Fiat, Haim Kaplan
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...
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...
Linear-Time Pointer-Machine Algorithms for Path-Evaluation Problems on Trees and Graphs (2002)
Buchsbaum, Adam L., Georgiadis, Loukas, Kaplan, Haim, Rogers, Anne, Tarjan, Robert E., Westbrook, Jeffery R.
We present algorithms that run in linear time on pointer machines for a collection of problems, each of which either directly or indirectly requires the evaluation of a function defined on paths in a...
Nearest Common Ancestors : (2002)
Stephen Alstrup, Cyril Gavoille, Haim Kaplan, Theis Rauhe
Several papers describe linear time algorithms to preprocess a tree, such that one can answer subsequent nearest common ancestor queries in constant time. Here, we survey these algorithms and related...
On-line Complexity of Monotone Set Systems (Extended Abstract) (2002)
On-line analysis models a player A (randomized or deterministic) who makes immediate responses to incoming elements of an input sequence s = a 1 : : : a r . In this paper a 1 ; : : : ; a r are...
Restoration by Path Concatenation: Fast Recovery of MPLS Paths (2002)
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...
Just the Fax-Differentiating Voice and Fax Phone Lines Using Call Billing Data (2002)
Haim Kaplan, Martin Strauss, Mario Szegedy
We survey an experiment in distinguishing voice and fax customers in a long distance telephony network based on the customers' calling patterns. We highlight three elements of algorithmic interest....
Nearest Common Ancestors: A survey and a new distributed algorithm (2002)
Stephen Alstrup, Cyril Gavoille, Haim Kaplan, Theis Rauhe
Several papers describe linear time algorithms to preprocess a tree, such that one can answer subsequent nearest common ancestor queries in constant time. Here, we survey these algorithms and related...
Union-Find With Deletions (2002)
Haim Kaplan, Nira Shafrir, Robert E. Tarjan
In the classical union-find problem we maintain a partition of a universe of n elements into disjoint sets subject to the operations union and find. The operation union(A; B;C) replaces sets A and B...
A Comparison of Labeling Schemes for Ancestor Queries (2002)
Haim Kaplan, Tova Milo, Ronen Shabo
Motivated by a recent application in XML search engines we study the problem of labeling the nodes of a tree (XML file) such that given the labels of two nodes one can determine whether one node is...
Short and Simple Labels for Small Distances and Other Functions (2002)
We present a labeling scheme for rooted trees which allows to compute, from the label of v alone, unique identi ers for the ancestors of v that are at distance at most d from v. For any constant d...
Reachability and Distance Queries Via 2-Hop Labels (2002)
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...
Meldable Heaps and Boolean Union-Find (Extended Abstract) (2002)
Haim Kaplan, Nira Shafrir, Robert E. Tarjan
In the classical meldable heap data type we maintain an item-disjoint collection of heaps under the operations find-min, insert, delete, decrease-key, and meld. In the usual definition decrease-key...
Caching Documents with Variable Sizes and Fetching Costs: An LP-Based Approach (2002)
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...
Haim Kaplan, Ron Shamir, E. Tarjan
We study the parameterizedcomplexity of three NP-hard graph completionproblems. The MINIMUM FILL-IN problem is to decide if a graph can be triangulated by adding at most k edges. We develop O(c m)...
Prefetching the Means for Document Transfer: (2002)
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...
Simple Confluently Persistent Catenable Lists (2002)
Haim Kaplan, Chris Okasaki, E. Tarjan
We consider the problem of maintaining persistent lists subject to concatenation and to insertions and deletions at both ends. Updates to a persistent data structure are nondestructive - each...
Refreshment Policies for Web Content Caches (2002)
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...
Scalable Secure Storage when Half the System is Faulty (2002)
Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien Stern
In this paper, we provide a method to safely store a document in perhaps the most challenging settings, a highly decentralized replicated storage system where up to half of the storage servers may...
Exploiting Regularities in Web Traffic Patterns for Cache Replacement (2002)
Caching web pages at proxies and in web servers' memories can greatly enhance performance. Proxy caching is known...
Competitive analysis of the LRFU paging algorithm (2002)
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...
A New, Simpler Linear-Time Dominators Algorithm (2002)
Adam L. Buchsbaum, Haim Kaplan, Anne Rogers, Jeffery R. Westbrook
this article is organized as follows. Section 2 outlines Lengauer and Tarjan's approach. Section 3 gives a broad overview of our algorithm and dierentiates it from previous work. Section 4 presents...
Adam L. Buchsbaum, Haim Kaplan, Anne Rogers, Jeffery R. Westbrook
We present two new data structure tools---disjoint set union with bottom-up linking, and pointer-based radix sort---and combine them with bottom-level microtrees to devise the first linear-time...
Connection Caching: Model and Algorithms (2002)
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...
A Faster And Simpler Algorithm For Sorting Signed Permutations By Reversals (2002)
Haim Kaplan, Ron Shamir, E. Tarjan
We give a quadratic-time algorithm for nding the minimum number of reversals needed to sort a signed permutation. Our algorithm is faster than the previous algorithm of Hannenhalli and Pevzner and...
Purely Functional, Real-Time Deques with Catenation (2002)
We describe an efficient, purely functional implementation of deques with catenation. In addition to being an intriguing problem in its own right, finding a purely functional implementation of...
Aging Through Cascaded Caches: Performance Issues in the Distribution of Web Content (2002)
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...
Bounded Degree Interval Sandwich Problems (2002)
The problems of Interval Sandwich (IS) and Intervalizing Colored Graphs (ICG) have received a lot of attention recently, due to their applicability to DNA physical mapping problems with ambiguous...
Purely Functional Representations of Catenable Sorted Lists. (2002)
The power of purely functional programming in the construction of data structures has received much attention, not only because functional languages have many desirable properties, but because...
Sanjeev Arora, Alan Frieze, Haim Kaplan
We present a randomized procedure for rounding fractional perfect matchings to (integral) matchings. If the original fractional matching satis es any linear inequality, then with high probability,...
Managing TCP Connections under Persistent HTTP (2002)
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.
On the Complexity of DNA Physical Mapping (2002)
Martin Charles Golumbic, Ramat Gan Israel, Haim Kaplan, Ron Shamir
The Physical Mapping Problem is to reconstruct the relative position of fragments (clones) of DNA along the genome from information on their pairwise overlaps. We show that two simplified versions of...
Four Strikes Against Physical Mapping of DNA (2002)
Paul W. Goldberg, Martin C. Golumbic, Haim Kaplan, Ron Shamir
Physical Mapping is a central problem in molecular biology and the human genome project. The problem is to reconstruct the relative position of fragments of DNA along the genome from information on...
Graph Sandwich Problems (2002)
Martin Charles Golumbic, Haim Kaplan, Ron Shamir
The graph sandwich problem for property Pi is defined as follows: Given two graphs G ) such that E ` E , is there a graph G = (V; E) such that E which satisfies property Pi? Such problems generalize...
The Domatic Number Problem on Some Perfect Graph Families (2002)
An extremely simple, linear time algorithm is given for constructing a domatic partition in totally balanced hypergraphs. This simplifies and generalizes previous algorithms for interval and strongly...
Pathwidth, Bandwidth and Completion Problems to Proper Interval Graphs with Small Cliques (2002)
We study two related problems motivated by molecular biology: ffl Given a graph G and a constant k, does there exist a supergraph G of G which is a unit interval graph and has clique size at most k?...
Sanjeev Arora, Alan Frieze, Haim Kaplan
We present approximation schemes for "dense" instances of many well-known NP-hard problems, including 0-1 quadratic-assignment, (an optimization formulation of) graphisomorphism,...
Scalable Secure Storage when Half the System is Faulty (2002)
Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien Stern
In this paper, we provide a method to safely store a document in perhaps the most challenging settings, a highly decentralized replicated storage system where up to half of the storage servers may...
A Comparison of Labeling Schemes for Ancestor Queries (2002)
Haim Kaplan, Tova Milo, Ronen Shabo
XML documents are often viewed as trees (basically the parse tree of the document), and queries over such documents typically test for ancestor relationships among tree nodes. Search engines process...
Short and Simple Labels for Small Distances and Other Functions (2002)
We present a labeling scheme for rooted trees which allows to compute, from the label of v alone, unique identi ers for the ancestors of v that are at distance at most d from v. For any constant d...
Labeling Dynamic XML Trees (2002)
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...
Reachability and Distance Queries Via 2-Hop Labels (2001)
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...
Making Data Structures Confluently Persistent (2001)
We address a longstanding open problem of [10, 9], and present a general transformation that transforms any pointer based data structure to be confluently persistent. Such transformations for fully...
Reachability and Distance Queries Via 2-Hop Labels (2001)
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...
Performance aspects of distributed caches using TTL-based consistency (2001)
Edith Cohen, Eran Halperin, Haim Kaplan
Web objects are stored and can be requested from numerous servers, including authoritative "origin" servers and caches. Objects can be modified only by their origin servers and weak consistency with...
Competitive Analysis of the LRFU Paging (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...
Identifying Nearest Common Ancestors in a Distributed Environment (2001)
Stephen Alstrup, Cyril Gavoille, Haim Kaplan, Theis Rauhe
We give a simple algorithm that labels the nodes of a rooted tree such that from the labels of two nodes alone one can compute in constant time the label of their nearest common ancestor. The labels...
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...
Scalable Secure Storage when Half the System is Faulty (2001)
Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien Stern
In this paper, we provide a method to safely store a document in perhaps the most challenging settings, a highly decentralized replicated storage system where up to half of the storage servers may...
Scalable Secure Storage when Half the System is Faulty (2001)
Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi
In this paper, we provide a method to safely store a document in perhaps the most challenging settings, a highly decentralized replicated storage system where up to half of the storage servers may...
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...
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...
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...
Proactive Caching of DNS Records: Addressing a Performance Bottleneck (2000)
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...
Connection Caching under (2000)
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...
Restoration by Path Concatenation: Fast Recovery of MPLS Paths (2000)
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...
Scalable Secure Storage when Half the System is Faulty (2000)
Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi
. In this paper, we provide a method to safely store a document in perhaps the most challenging settings, a highly decentralized replicated storage system where up to half of the storage servers may...
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...
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 decrease...
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...
Prefetching the Means for Document Transfer: A New Approach for Reducing Web Latency (1999)
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...
A New, Simpler Linear-Time Dominators Algorithm (1999)
Adam L. Buchsbaum, Haim Kaplan, Anne Rogers, Jeffery R. Westbrook
We present a new linear-time algorithm to find the immediate dominators of all vertices in a flowgraph. Our algorithm is simpler than previous linear-time algorithms: we combine the use of microtrees...
Just the Fax-Differentiating Voice and Fax Phone Lines Using Call Billing Data (1999)
Haim Kaplan, Martin Strauss, Mario Szegedy
this paper we are particularly concerned with classifying lines as either voice or fax, we point out that the techniques we use may apply in other classification problems as well. The ability to...
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.
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...
Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals (1998)
Haim Kaplan, Ron Shamir, Robert E. Tarjan
We give a quadratic algorithm for finding the minimum number of reversals needed to sort a signed permutation. Our algorithm is faster than the previous algorithm of Hannenhalli and Pevzner and its...
Bounded Degree Interval Sandwich Problems (1998)
The problems of Interval Sandwich (IS) and Intervalizing Colored Graphs (ICG) have received a lot of attention recently, due to their applicability to DNA physical mapping problems with ambiguous...