In recent decades, cloud computing as a service has emerged as a major computing paradigm. These services (e.g., Amazon EC2, Google Compute Engine, Azure Virtual Machines) all offer variations of the following basic model for how storage works: a compute instance can choose between placing data on something that resembles a local disk (e.g., Amazon EBS, Google Block Store, Azure Managed Disks) versus what we will refer to as a global disk (e.g., Amazon S3, Google GCS, Azure Blob Storage). The disks are distinguished by two features:

Abstract We define simple variants of zip trees, called zip-zip trees , which provide several advantages over zip trees, including overcoming a bias that favors smaller keys over larger ones. We analyze zip-zip trees theoretically and empirically, showing, e.g., that the expected depth of a node in an n -node zip-zip tree is at most $$1.3863\log n-1+o(1)$$ , which matches the expected depth of treaps and binary search trees built by uniformly random insertions. Unlike these other data structures, however, zip-zip trees achieve their bounds using only $$O(\log \log n)$$ bits of metadata per node, w.h.p., as compared to the $$\Theta (\log n)$$ bits per node required by treaps. In addition, we describe a “just-in-time” zip-zip tree variant, which needs just an expected O (1) number of bits of metadata per node. Moreover, we can define zip-zip trees to be strongly history independent, whereas treaps are generally only weakly history independent. We also introduce biased zip-zip trees , which have an explicit bias based on key weights, so the expected depth of a key, k , with weight, $$w_k$$ , is $$O(\log (W/w_k))$$ , where W is the weight of all keys in the weighted zip-zip tree. Finally, we show that one can easily make zip-zip trees partially persistent with only O ( n ) space overhead w.h.p.

We introduce a quantum algorithm design paradigm called combine and conquer, which is a quantum version of the "marriage-before-conquest" technique of Kirkpatrick and Seidel. In a quantum combine-and-conquer algorithm, one performs the essential computation of the combine step of a quantum divide-and-conquer algorithm prior to the conquer step while avoiding recursion. This model is better suited for the quantum setting, due to its non-recursive nature. We show the utility of this approach by providing quantum algorithms for 2D maxima set and convex hull problems for sorted point sets running in Õ(√{nh}) time, w.h.p., where h is the size of the output.

In this paper we present an algorithmic framework for solving a class of combinatorial optimization problems on graphs with bounded pathwidth. The problems are NP-hard in general, but solvable in linear time on this type of graphs. The problems are relevant for assessing network reliability and improving the network's performance and fault tolerance. The main technique considered in this paper is dynamic programming.

A witness drawing of a graph is a visualization that clearly shows a given property of a graph. We study and implement various drawing paradigms for witness drawings to clearly show that graphs have bounded pathwidth or treewidth. Our approach draws the tree decomposition or path decomposition as a tree of bags, with induced subgraphs shown in each bag, and with "tracks" for each graph vertex connecting its copies in multiple bags. Within bags, we optimize the vertex layout to avoid crossings of edges and tracks. We implement a visualization prototype for crossing minimization using dynamic programming for graphs of small width and heuristic approaches for graphs of larger width. We introduce a taxonomy of drawing styles, which render the subgraph for each bag as an arc diagram with one or two pages or as a circular layout with straight-line edges, and we render tracks either with straight lines or with orbital-radial paths.

Spatial graphs, where nodes carry geographic location information, are vital for modeling complex relationships in domains such as location-based social networks, transportation systems, and knowledge graphs. However, it is challenging to visualize large spatial graphs while simultaneously showing edge connections and vertex spatial fidelity, especially when the location of each vertex is imprecise. We present a distributed geospatial force-directed framework that visualizes spatial graphs where location can be represented as a point, multi-point, linestring, or polygon. It integrates three models for anchoring forces: centroidal, inside-out, and closest-point. The algorithm is formulated as relational operations and runs end-to-end on Apache Spark/SparkSQL, achieving near-linear scaling. Experiments on train networks, author-publication graphs, and location-based social networks show clearer layouts that balance edge lengths and spatial fidelity while reducing crossings.

Balanced search trees are widely used in computer science to efficiently maintain dynamic ordered data. To support efficient set operations (e.g., union, intersection, difference) using trees, the join-based framework is widely studied. This framework has received particular attention in the parallel setting, and has been shown to be effective in enabling simple and theoretically efficient set operations on trees. Despite the widespread adoption of parallel join-based trees, a major drawback of previous work on such data structures is the inefficiency of their input/output (I/O) access patterns. Some recent work (e.g., C-trees and PaC-trees) focused on more I/O-friendly implementations of these algorithms. Surprisingly, however, there have been no results on bounding the I/O-costs for these algorithms. It remains open whether these algorithms can provide tight, provable guarantees in I/O-costs on trees. This paper studies efficient parallel algorithms for set operations based on search tree algorithms using a join-based framework, with a special focus on achieving I/O efficiency in these algorithms. To better capture the I/O-efficiency in these algorithms in parallel, we introduce a new computational model, the Fork-Join I/O Model, to measure the I/O costs in fork-join parallelism. This model measures the total block transfers (I/O work) and their critical path (I/O span). Under this model, we propose our new solution based on B-trees. Our parallel algorithm computes the union, intersection, and difference of two B-trees with O(m log_B(n/m)) I/O work and O(log_B m ⋅ log₂ log_B n + log_B n) I/O span, where n and m ≤ n are the sizes of the two trees, and B is the block size.

We introduce a quantum dynamic programming framework that allows us to directly extend to the quantum realm a large body of classical dynamic programming algorithms. The corresponding quantum dynamic programming algorithms retain the same space complexity as their classical counterpart, while achieving a computational speedup. For a combinatorial (search or optimization) problem P and an instance I of P, such a speedup can be expressed in terms of the average degree δ of the dependency digraph GP(I) of I, determined by a recursive formulation of P. The nodes of this graph are the subproblems of P induced by I and its arcs are directed from each subproblem to those on whose solution it relies. In particular, our framework allows us to solve the considered problems in Õ(|V (GP(I))|√δ) time. As an example, we obtain a quantum version of the Bellman-Ford algorithm for computing shortest paths from a single source vertex to all the other vertices in a weighted n-vertex digraph with m edges that runs in Õ(n√nm) time, which improves the best known classical upper bound when m ∈ Ω(n1.4).

Much prior work has been done on designing computational geometry algorithms that handle input degeneracies, data imprecision, and arithmetic round-off errors. We take a new approach, inspired by the noisy sorting literature, and study computational geometry algorithms subject to noisy Boolean primitive operations in which, e.g., the comparison "is point q above line 𝓁?" returns the wrong answer with some fixed probability. We propose a novel technique called path-guided pushdown random walks that generalizes the results of noisy sorting. We apply this technique to solve point-location, plane-sweep, convex hulls in 2D and 3D, and Delaunay triangulations for noisy primitives in optimal time with high probability.

In this paper, we derive parameterized Chernoff bounds and show their applications for simplifying the analysis of some well-known probabilistic algorithms and data structures. The parameterized Chernoff bounds we provide give probability bounds that are powers of two, with a clean formulation of the relation between the constant in the exponent and the relative distance from the mean. In addition, we provide new simplified analyses with these bounds for hash tables, randomized routing, and a simplified, non-recursive adaptation of the Floyd-Rivest selection algorithm.

Force-directed algorithms are among the most flexible methods for calculating layouts of simple undirected graphs. Also known as spring embedders, such algorithms calculate the layout of a graph using only information contained within the structure of the graph itself, rather than relying on domain-specific knowledge. Graphs drawn with these algorithms tend to be aesthetically pleasing, exhibit symmetries, and tend to produce crossing-free layouts for planar graphs. In this survey we consider several classical algorithms, starting from Tutte's 1963 barycentric method, and including recent scalable multiscale methods for large and dynamic graphs.

A data structure is history independent if its internal representation reveals nothing about the history of operations beyond what can be determined from the current contents of the data structure. History independence is typically viewed as a security or privacy guarantee, with the intent being to minimize risks incurred by a security breach or audit. Despite widespread advances in history independence, there is an important data-structural primitive that previous work has been unable to replace with an equivalent history-independent alternative---dynamic partitioning. In dynamic partitioning, we are given a dynamic set S of ordered elements and a size-parameter B, and the objective is to maintain a partition of S into ordered groups, each of size Θ(B). Dynamic partitioning is important throughout computer science, with applications to B-tree rebalancing, write-optimized dictionaries, log-structured merge trees, other external-memory indexes, geometric and spatial data structures, cache-oblivious data structures, and order-maintenance data structures. The lack of a history-independent dynamic-partitioning primitive has meant that designers of history-independent data structures have had to resort to complex alternatives. In this paper, we achieve history-independent dynamic partitioning. Our algorithm runs asymptotically optimally against an oblivious adversary, processing each insert/delete with O(1) operations in expectation and O(B log N/loglog N) with high probability in set size N.

We present comparison-based parallel algorithms for sorting n comparable items subject to comparison errors. We consider errors to occur according to a well-studied framework, where the comparison of two elements returns the wrong answer with a fixed probability. In the persistent model, the result of the comparison of two given elements, x and y, always has the same result, and is independent of all other pairs of elements. In the non-persistent model, the result of the comparison of each pair of elements, x and y, is independent of all prior comparisons, including for x and y. It is not possible to always correctly sort a given input set in the persistent model, so we study algorithms that achieve a small maximum dislocation and small total dislocation of the elements in the output permutation. In this paper, we provide parallel algorithms for sorting with comparison errors in the persistent and non-persistent models. Our algorithms are asymptotically optimal in terms of their span, work, and, in the case of persistent errors, maximum and total dislocation. The main results are algorithms for the binary-forking parallel model with atomics, but we also provide algorithms for the CREW PRAM model. Our algorithms include a number of novel techniques and analysis tools, including a PRAM-to-binary-forking-model simulation result, and are the first optimal parallel algorithms for the persistent model and the non-persistent model in the binary-forking parallel model with atomics. In particular, our algorithms have O(log n) span, O(n log n) work, and, in the case of the persistent model, O(log n) maximum dislocation and O(n) total dislocation, with high probability. We achieve similar results for the CREW PRAM model, which are the first optimal methods for the persistent model and the first optimal results for the non-persistent model with reasonable constant factors in the performance bounds.

We provide and study several algorithms for sorting an array of n comparable distinct elements subject to probabilistic comparison errors. In this model, the comparison of two elements returns the wrong answer according to a fixed probability, p_e < 1/2, and otherwise returns the correct answer. The dislocation of an element is the distance between its position in a given (current or output) array and its position in a sorted array. There are various algorithms that can be utilized for sorting or near-sorting elements subject to probabilistic comparison errors, but these algorithms are not data oblivious because they all make heavy use of noisy binary searching. In this paper, we provide new methods for sorting with comparison errors that are data oblivious while avoiding the use of noisy binary search methods. In addition, we experimentally compare our algorithms and other sorting algorithms.

In this paper, we derive simplified Chernoff bounds with powers-of-two probabilities, and we show their uses in analyzing probabilistic algorithms.

This paper addresses volume leakage (i.e., leakage of the number of records in the answer set) when processing keyword queries in encrypted key-value (KV) datasets. Volume leakage, coupled with prior knowledge about data distribution and/or previously executed queries, can reveal both ciphertexts and current user queries. We develop a solution to prevent volume leakage, entitled Veil, that partitions the dataset by randomly mapping keys to a set of equi-sized buckets. Veil provides a tunable mechanism for data owners to explore a trade-off between storage and communication overheads. To make buckets indistinguishable to the adversary, Veil uses a novel padding strategy that allow buckets to overlap, reducing the need to add fake records. Both theoretical and experimental results show Veil to significantly outperform existing state-of-the-art.

Motivated by the importance of floating-point computations, we study the problem of securely and accurately summing many floating-point numbers. Prior work has focused on security absent accuracy or accuracy absent security, whereas our approach achieves both of them. Specifically, we show how to implement floating-point superaccumulators using secure multi-party computation techniques, so that a number of participants holding secret shares of floating-point numbers can accurately compute their sum while keeping the individual values private.

Dating back to two famous experiments by the social-psychologist, Stanley Milgram, in the 1960s, the small-world phenomenon is the idea that all people are connected through a short chain of acquaintances that can be used to route messages. Many subsequent papers have attempted to model this phenomenon, with most concentrating on the "short chain" of acquantances rather than their ability to efficiently route messages. For example, a well-known preferential attachment model by Barabási and Albert provides a mathematical explanation of how a social network can have small diameter---hence, short chains between participants--- but this model doesn't explain how they can route messages. A notable exception is a well-known model by Jon Kleinberg, which shows that it is possible for participants in a n × n grid to route a message in O(log2 n) hops by augmenting the grid with a small number of long-range random links and using a simple greedy routing strategy. Although Kleinberg's model is intriguing, it does not take into account the road network of the United States used in the original Milgram experiments and its O(log2 n) number of hops for messages is actually quite far from the average of six hops for successful messages observed by Milgram in his experiments, which gave rise to the "six-degrees-of-separation" expression. In this paper, we study the small-world navigability of the U.S. road network, with the goal of providing a model that explains how messages in the original small-world experiments could be routed along short paths using U.S. roads. To this end, we introduce the Neighborhood Preferential Attachment model, which combines elements from Kleinberg's model and the Barabási-Albert model, such that long-range links are chosen according to both the degrees and (road-network) distances of vertices in the network. We empirically evaluate all three models by running a decentralized routing algorithm, where each vertex only has knowledge of its own neighbors, and find that our model outperforms both of these models in terms of the average hop length. Moreover, our experiments indicate that similar to the Barabási-Albert model, networks generated by our model are scale-free, which could be a more realistic representation of acquaintanceship links in the original small-world experiment.

Complex networks are at the core of an intense research activity. However, in most cases, intricate and costly measurement procedures are needed to explore their structure. In some cases, these measurements rely on link queries: given two nodes, it is possible to test the existence of a link between them. These tests may be costly, and thus minimizing their number while maximizing the number of discovered links is a key issue. This paper studies this problem: we observe that properties classically observed on real-world complex networks give hints for their efficient measurement; we derive simple principles and several measurement strategies based on this, and experimentally evaluate their efficiency on real-world cases. In order to do so, we introduce methods to evaluate the efficiency of strategies. We also explore the bias that different measurement strategies may induce.

The completeness of road network data is significant in the quality of various routing services and applications. We introduce an efficient randomized algorithm for exact learning of road networks using simple distance queries, which can find missing roads and improve the quality of routing services. The efficiency of our algorithm depends on a cluster degree parameter, d_max, which is an upper bound on the degrees of vertex clusters defined during our algorithm. Unfortunately, we leave open the problem of theoretically bounding d_max, although we conjecture that d_max is small for road networks and other similar types of graphs. We support this conjecture by experimentally evaluating our algorithm on road network data for the U.S. and 5 European countries of various sizes. This analysis provides experimental evidence that our algorithm issues a quasilinear number of queries in expectation for road networks and similar graphs.

We prove an Ω (log n log log n) lower bound for the span of implementing the n input, log n-depth FFT circuit (also known as butterfly network) in the nonatomic binary fork-join model. In this model, memory-access synchronizations occur only through fork operations, which spawn two child threads, and join operations, which resume a parent thread when its child threads terminate. Our bound is asymptotically tight for the nonatomic binary fork-join model, which has been of interest of late, due to its conceptual elegance and ability to capture asynchrony. Our bound implies super-logarithmic lower bound in the nonatomic binary fork-join model for implementing the butterfly merging networks used, e.g., in Batcher's bitonic and odd-even mergesort networks. This lower bound also implies an asymptotic separation result for the atomic and nonatomic versions of the fork-join model, since, as we point out, FFT circuits can be implemented in the atomic binary fork-join model with span equal to their circuit depth.

Motivated from parallel network mapping, we provide efficient query complexity and round complexity bounds for graph reconstruction using distance queries, including a bound that improves a previous sequential complexity bound. Our methods use a high-probability parametric parallelization of a graph clustering technique of Thorup and Zwick, which may be of independent interest.

Abstract For a clustered graph, i.e, a graph whose vertex set is recursively partitioned into clusters, the C-Planarity Testing problem asks whether it is possible to find a planar embedding of the graph and a representation of each cluster as a region homeomorphic to a closed disk such that (1) the subgraph induced by each cluster is drawn in the interior of the corresponding disk, (2) each edge intersects any disk at most once, and (3) the nesting between clusters is reflected by the representation, i.e., child clusters are properly contained in their parent cluster. The computational complexity of this problem, whose study has been central to the theory of graph visualization since its introduction in 1995 [Feng, Cohen, and Eades, Planarity for clustered graphs, ESA’95], has only been recently settled [Fulek and Tóth, Atomic Embeddability, Clustered Planarity, and Thickenability, to appear at SODA’20]. Before such a breakthrough, the complexity question was still unsolved even when the graph has a prescribed planar embedding, i.e, for embedded clustered graphs. We show that the C-Planarity Testing problem admits a single-exponential single-parameter FPT (resp., XP) algorithm for embedded flat (resp., non-flat) clustered graphs, when parameterized by the carving-width of the dual graph of the input. These are the first FPT and XP algorithms for this long-standing open problem with respect to a single notable graph-width parameter. Moreover, the polynomial dependency of our FPT algorithm is smaller than the one of the algorithm by Fulek and Tóth. In particular, our algorithm runs in quadratic time for flat instances of bounded treewidth and bounded face size. To further strengthen the relevance of this result, we show that an algorithm with running time O(r(n)) for flat instances whose underlying graph has pathwidth 1 would result in an algorithm with running time O(r(n)) for flat instances and with running time $$O(r(n^2) + n^2)$$ O ( r ( n 2 ) + n 2 ) for general, possibly non-flat, instances.

In this paper, we study the parallel query complexity of reconstructing biological and digital phylogenetic trees from simple queries involving their nodes. This is motivated from computational biology, data protection, and computer security settings, which can be abstracted in terms of two parties, a responder, Alice, who must correctly answer queries of a given type regarding a degree-d tree, T, and a querier, Bob, who issues batches of queries, with each query in a batch being independent of the others, so as to eventually infer the structure of T. We show that a querier can efficiently reconstruct an n-node degree-d tree, T, with a logarithmic number of rounds and quasilinear number of queries, with high probability, for various types of queries, including relative-distance queries and path queries. Our results are all asymptotically optimal and improve the asymptotic (sequential) query complexity for one of the problems we study. Moreover, through an experimental analysis using both real-world and synthetic data, we provide empirical evidence that our algorithms provide significant parallel speedups while also improving the total query complexities for the problems we study.

We study the parallel query complexity of reconstructing binary trees from simple queries involving their nodes. We show that a querier can efficiently reconstruct a binary tree with a logarithmic number of rounds and quasilinear number of queries, with high probability, for various types of queries.

Given a planar digraph G and a positive even integer k, an embedding of G in the plane is k-modal, if every vertex of G is incident to at most k pairs of consecutive edges with opposite orientations, i.e., the incoming and the outgoing edges at each vertex are grouped by the embedding into at most k sets of consecutive edges with the same orientation. In this paper, we study the k-Modality problem, which asks for the existence of a k-modal embedding of a planar digraph. This combinatorial problem is at the very core of a variety of constrained embedding questions for planar digraphs and flat clustered networks. First, since the 2-Modality problem can be easily solved in linear time, we consider the general k-Modality problem for any value of k>2 and show that the problem is NP-complete for planar digraphs of maximum degree Delta <= k+3. We relate its computational complexity to that of two notions of planarity for flat clustered networks: Planar Intersection-Link and Planar NodeTrix representations. This allows us to answer in the strongest possible way an open question by Di Giacomo [https://doi.org/10.1007/978-3-319-73915-1_37], concerning the complexity of constructing planar NodeTrix representations of flat clustered networks with small clusters, and to address a research question by Angelini et al. [https://doi.org/10.7155/jgaa.00437], concerning intersection-link representations based on geometric objects that determine complex arrangements. On the positive side, we provide a simple FPT algorithm for partial 2-trees of arbitrary degree, whose running time is exponential in k and linear in the input size. Second, motivated by the recently-introduced planar L-drawings of planar digraphs [https://doi.org/10.1007/978-3-319-73915-1_36], which require the computation of a 4-modal embedding, we focus our attention on k=4. On the algorithmic side, we show a complexity dichotomy for the 4-Modality problem with respect to Delta, by providing a linear-time algorithm for planar digraphs with Delta <= 6. This algorithmic result is based on decomposing the input digraph into its blocks via BC-trees and each of these blocks into its triconnected components via SPQR-trees. In particular, we are able to show that the constraints imposed on the embedding by the rigid triconnected components can be tackled by means of a small set of reduction rules and discover that the algorithmic core of the problem lies in special instances of NAESAT, which we prove to be always NAE-satisfiable - a result of independent interest that improves on Porschen et al. [https://doi.org/10.1007/978-3-540-24605-3_14]. Finally, on the combinatorial side, we consider outerplanar digraphs and show that any such a digraph always admits a k-modal embedding with k=4 and that this value of k is best possible for the digraphs in this family.

We consider the NP-complete problem of tracking paths in a graph, first introduced by Banik et. al. [3]. Given an undirected graph with a source $s$ and a destination $t$, find the smallest subset of vertices whose intersection with any $s-t$ path results in a unique sequence. In this paper, we show that this problem remains NP-complete when the graph is planar and we give a 4-approximation algorithm in this setting. We also show, via Courcelle's theorem, that it can be solved in linear time for graphs of bounded-clique width, when its clique decomposition is given in advance.

We show new applications of the nearest-neighbor chain algorithm, a technique that originated in agglomerative hierarchical clustering. We apply it to a diverse class of geometric problems: we construct the greedy multi-fragment tour for Euclidean TSP in $O(n\log n)$ time in any fixed dimension and for Steiner TSP in planar graphs in $O(n\sqrt{n}\log n)$ time; we compute motorcycle graphs (which are a central part in straight skeleton algorithms) in $O(n^{4/3+\varepsilon})$ time for any $\varepsilon>0$; we introduce a narcissistic variant of the $k$-attribute stable matching model, and solve it in $O(n^{2-4/(k(1+\varepsilon)+2)})$ time; we give a linear-time $2$-approximation for a 1D geometric set cover problem with applications to radio station placement.

For a clustered graph, i.e, a graph whose vertex set is recursively partitioned into clusters, the C-Planarity Testing problem asks whether it is possible to find a planar embedding of the graph and a representation of each cluster as a region homeomorphic to a closed disk such that 1. the subgraph induced by each cluster is drawn in the interior of the corresponding disk, 2. each edge intersects any disk at most once, and 3. the nesting between clusters is reflected by the representation, i.e., child clusters are properly contained in their parent cluster. The computational complexity of this problem, whose study has been central to the theory of graph visualization since its introduction in 1995 [Feng, Cohen, and Eades, Planarity for clustered graphs, ESA'95], has only been recently settled [Fulek and Tóth, Atomic Embeddability, Clustered Planarity, and Thickenability, to appear at SODA'20]. Before such a breakthrough, the complexity question was still unsolved even when the graph has a prescribed planar embedding, i.e, for embedded clustered graphs. We show that the C-Planarity Testing problem admits a single-exponential single-parameter FPT algorithm for embedded clustered graphs, when parameterized by the carving-width of the dual graph of the input. This is the first FPT algorithm for this long-standing open problem with respect to a single notable graph-width parameter. Moreover, in the general case, the polynomial dependency of our FPT algorithm is smaller than the one of the algorithm by Fulek and Tóth. To further strengthen the relevance of this result, we show that the C-Planarity Testing problem retains its computational complexity when parameterized by several other graph-width parameters, which may potentially lead to faster algorithms.

We empirically study sorting in the evolving data model. In this model, a sorting algorithm maintains an approximation to the sorted order of a list of data items while simultaneously, with each comparison made by the algorithm, an adversary randomly swaps the order of adjacent items in the true sorted order. Previous work studies only two versions of quicksort, and has a gap between the lower bound of Ω(n) and the best upper bound of O(n log log n). The experiments we perform in this paper provide empirical evidence that some quadratic-time algorithms such as insertion sort and bubble sort are asymptotically optimal for any constant rate of random swaps. In fact, these algorithms perform as well as or better than algorithms such as quicksort that are more efficient in the traditional algorithm analysis model.

We study oblivious random access machine (ORAM) simulation, in cloud computing environments where a thin client outsources her data to a server using O(1)-sized messages.

We give optimal sorting algorithms in the evolving data framework, where an algorithm's input data is changing while the algorithm is executing. In this framework, instead of producing a final output, an algorithm attempts to maintain an output close to the correct output for the current state of the data, repeatedly updating its best estimate of a correct output over time. We show that a simple repeated insertion-sort algorithm can maintain an O(n) Kendall tau distance, with high probability, between a maintained list and an underlying total order of n items in an evolving data model where each comparison is followed by a swap between a random consecutive pair of items in the underlying total order. This result is asymptotically optimal, since there is an Omega(n) lower bound for Kendall tau distance for this problem. Our result closes the gap between this lower bound and the previous best algorithm for this problem, which maintains a Kendall tau distance of O(n log log n) with high probability. It also confirms previous experimental results that suggested that insertion sort tends to perform better than quicksort in practice.

We introduce and study the online house numbering problem, where houses are added arbitrarily along a road and must be assigned labels to maintain their ordering along the road. The online house numbering problem is related to classic online list labeling problems, except that the optimization goal here is to minimize the maximum number of times that any house is relabeled. We provide several algorithms that achieve interesting tradeoffs between upper bounds on the number of maximum relabels per element and the number of bits used by labels.

The classic notion of history-independence guarantees that if a data structure is ever observed, only its current contents are revealed, not the history of operations that built it. This powerful concept has applications, for example, to e-voting and data retention compliance, where data structure histories should be private. The concept of weak history-independence (WHI) assumes only a single observation will ever occur, while strong history-independence (SHI) allows for multiple observations at arbitrary times. WHI constructions tend to be fast, but provide no repeatability, while SHI constructions provide unlimited repeatability, but tend to be slow. We introduce auditable data structures, where an auditor can observe data structures at arbitrary times (as in SHI), but we relax the unrealistic restriction that data structures cannot react to observations, since in most applications of history-independence, data owners know when observations have occurred. We consider two audit scenarios-secure topology, where an auditor can observe the contents and pointers of a data structure, and secure implementation, where an auditor can observe the memory layout of a data structure. We present a generic template for auditable data structures and, as a foundation for any auditable data structure, an Auditable Memory Manager (AMM), which is an efficient memory manager that translates any auditable data structure with a secure topology into one with a secure implementation. We give a prototype implementation that provides empirical evidence that the worst-case time running times of our AMM are 45 to 8,300 faster than those of a well-known SHI memory manager. Thus, auditable data structures provide a practical way of achieving time efficiency, as in WHI, while allowing for multiple audits, as in SHI.

We introduce a novel method for defining geographic districts in road networks using stable matching. In this approach, each geographic district is defined in terms of a center, which identifies a location of interest, such as a post office or polling place, and all other network vertices must be labeled with the center to which they are associated. We focus on defining geographic districts that are equitable, in that every district has the same number of vertices and the assignment is stable in terms of geographic distance. That is, there is no unassigned vertex-center pair such that both would prefer each other over their current assignments. We solve this problem using a version of the classic stable matching problem, called symmetric stable matching, in which the preferences of the elements in both sets obey a certain symmetry. We show that, for a planar graph or road network with n nodes and k centers, the problem can be solved in O(n √ n log n) time, which improves upon the O(nk) runtime of using the classic Gale--Shapley stable matching algorithm when k is large. Finally, we provide experimental results on road networks for these algorithms and a heuristic algorithm that performs better than the Gale--Shapley algorithm for any range of values of k.

We show how to answer spatial multiple-set intersection queries in O(n(log w)/w + kt) expected time, where n is the total size of the t ≤ wc sets involved in the query, w is the number of bits in a memory word, k is the output size, and c ≥ 1 is any fixed constant.

We introduce new dynamic set intersection data structures, which we call 2-3 cuckoo filters and hash tables. These structures differ from the standard cuckoo hash tables and cuckoo filters in that they choose two out of three locations to store each item, instead of one out of two, ensuring that any item in an intersection of two structures will have at least one common location in both structures. We demonstrate the utility of these structures by using them in improved algorithms for listing triangles and answering set intersection queries in internal or external memory. For a graph G of n vertices and m edges, our internal-memory triangle listing algorithm runs in O(m⌈(α(G)log w)/w⌉ + k) expected time, where α(G) is the arboricity of G, w is the number of bits in a machine word, and k is the number of output triangles. Our external-memory algorithm uses O(sort(n,α(G))+ sort(m⌈(α(G)log w)/w⌉) + sort(k)) expected number of I/Os.

We use multi-level parallelism and a new type of data structures, known as 2-3 cuckoo filters, to answer set intersection queries faster than previous methods, with applications to improved sparse Boolean matrix multiplication.

We study various versions of the problem of scheduling platoons of autonomous vehicles through an unregulated intersection, where an algorithm must schedule which platoons should wait so that others can go through, so as to minimize the maximum delay for any vehicle. We provide polynomial-time algorithms for constructing such schedules for a k-way merge intersection, for constant k, and for a crossing intersection involving two-way traffic. We also show that the more general problem of scheduling autonomous platoons through an intersection that includes both a k-way merge, for non-constant k, and a crossing of two-way traffic is NP-complete.

We provide an efficient algorithm for determining how a road network has evolved over time, given two snapshot instances from different dates. To allow for such determinations across different databases and even against hand-drawn maps, we take a strictly topological approach in this paper, so that we compare road networks based strictly on graph-theoretic properties. Given two road networks of same region from two different dates, our approach allows one to match road network portions that remain intact and also point out added or removed portions. We analyze our algorithm both theoretically, showing that it runs in polynomial time for non-degenerate road networks even though a related problem is NP-complete, and experimentally, using dated road networks from the TIGER/Line archive of the U.S. Census Bureau.

We study parallel comparison-based algorithms for finding all equivalence classes of a set of $n$ elements, where sorting according to some total order is not possible. Such scenarios arise, for example, in applications, such as in distributed computer security, where each of n agents are working to identify the private group to which they belong, with the only operation available to them being a zero-knowledge pairwise-comparison (which is sometimes called a "secret handshake") that reveals only whether two agents are in the same group or in different groups. We provide new parallel algorithms for this problem, as well as new lower bounds and distribution-based analysis.

The problem of exactly summing n floating-point numbers is a fundamental problem that has many applications in large-scale simulations and computational geometry. Unfortunately, due to the round-off error in standard floating-point operations, this problem becomes very challenging. Moreover, all existing solutions rely on sequential algorithms which cannot scale to the huge datasets that need to be processed. In this paper, we provide several efficient parallel algorithms for summing n floating point numbers, so as to produce a faithfully rounded floating-point representation of the sum. We present algorithms in PRAM, external-memory, and MapReduce models, and we also provide an experimental analysis of our MapReduce algorithms, due to their simplicity and practical efficiency.

We describe a security visualization tool for finding algorithmic complexity attacks in Java bytecode. Our tool, which we call J-Viz, visualizes connected directed graphs derived from Java bytecode according to a canonical node ordering, which we call the sibling-first recursive (SFR) numbering. The particular graphs we consider are derived from applying Shiver's k-CFA framework to Java bytecode, and our visualizer includes helpful links between the nodes of an input graph and the Java bytecode that produced it, as well as a decompiled version of that Java bytecode. We show through experiments involving test cases provided by DARPA that the canonical drawing paradigm used in J-Viz is effective for identifying potential security vulnerabilities for algorithmic complexity attacks.

The problem of finding an electric vehicle route that optimizes both driving time and energy consumption can be modeled as a bicriterion path problem. Unfortunately, the problem of finding optimal bicriterion paths is NP-complete. This paper studies such problems restricted to two-phase paths, which correspond to a common way people drive electric vehicles, where a driver uses one driving style (say, minimizing driving time) at the beginning of a route and another driving style (say, minimizing energy consumption) at the end. We provide efficient polynomial-time algorithms for finding optimal two-phase paths in bicriterion networks, and we empirically verify the effectiveness of these algorithms for finding good electric vehicle driving routes in the road networks of various U.S. states. In addition, we show how to incorporate charging stations into these algorithms.

We describe Zig-zag Sort---a deterministic data-oblivious sorting algorithm running in O(n log n) time that is arguably simpler than previously known algorithms with similar properties, which are based on the AKS sorting network. Because it is data-oblivious and deterministic, Zig-zag Sort can be implemented as a simple O(n log n)-size sorting network, thereby providing a solution to an open problem posed by Incerpi and Sedgewick in 1985. In addition, Zig-zag Sort is a variant of Shellsort, and is, in fact, the first deterministic Shellsort variant running in O(n log n) time. The existence of such an algorithm was posed as an open problem by Plaxton et al. in 1992 and also by Sedgewick in 1996. More relevant for today is the fact that the existence of a simple data-oblivious deterministic sorting algorithm running in O(n log n) time simplifies the "inner-loop" computation in several proposed oblivious-RAM simulation methods (which utilize AKS sorting networks), and this, in turn, implies simplified mechanisms for privacy-preserving data outsourcing in several cloud computing applications.

Betweenness centrality is one of the most well-known measures of the importance of nodes in a social-network graph. In this paper we describe the first known external-memory and cache-oblivious algorithms for computing betweenness centrality. We present four different external-memory algorithms exhibiting various tradeoffs with respect to performance. Two of the algorithms are cache-oblivious. We describe general algorithms for networks with weighted and unweighted edges and a specialized algorithm for networks with small diameters, as is common in social networks exhibiting the “small worlds” phenomenon.

In this paper, we study sparsity-exploiting Mastermind algorithms for attacking the privacy of an entire database of character strings or vectors, such as DNA strings, movie ratings, or social network friendship data. Based on reductions to nonadaptive group testing, our methods are able to take advantage of minimal amounts of privacy leakage, such as contained in a single bit that indicates if two people in a medical database have any common genetic mutations, or if two people have any common friends in an online social network. We analyze our Mastermind attack algorithms using theoretical characterizations that provide sublinear bounds on the number of queries needed to clone the database, as well as experimental tests on genomic information, collaborative filtering data, and online social networks. By taking advantage of the generally sparse nature of these real-world databases and modulating a parameter that controls query sparsity, we demonstrate that relatively few nonadaptive queries are needed to recover a large majority of each database.

We study oblivious storage (OS), a natural way to model privacy-preserving data outsourcing where a client, Alice, stores sensitive data at an honest-but-curious server, Bob. We show that Alice can hide both the content of her data and the pattern in which she accesses her data, with high probability, using a method that achieves O(1) amortized rounds of communication between her and Bob for each data access. We assume that Alice and Bob exchange small messages, of size O(N1/c), for some constant c>=2, in a single round, where N is the size of the data set that Alice is storing with Bob. We also assume that Alice has a private memory of size 2N1/c. These assumptions model real-world cloud storage scenarios, where trade-offs occur between latency, bandwidth, and the size of the client's private memory.

Motivated by cloud computing applications, we study the problem of providing privacy-preserving access to an outsourced honest-but-curious data repository for a group of trusted users. We show how to achieve efficient privacy-preserving data access using a combination of probabilistic encryption, which directly hides data values, and stateless oblivious RAM simulation, which hides the pattern of data accesses. We give a method with O(log n) amortized access overhead for simulating a RAM algorithm that has a memory of size n, using a scheme that is data-oblivious with very high probability. We assume that the simulation has access to a private workspace of size O(nv), for any given fixed constant v > 0, but does not maintain state in between data access requests. Our simulation makes use of pseudorandom hash functions and is based on a novel hierarchy of cuckoo hash tables that all share a common stash. The method outperforms all previous techniques for stateless clients in terms of access overhead. We also provide experimental results from a prototype implementation of our scheme, showing its practicality. In addition, we show that one can eliminate the dependence on pseudorandom hash functions in our simulation while having the overhead rise to be O(log2 n).

We consider the problem of verifying the correctness and completeness of the result of a keyword search. We introduce the concept of an authenticated web crawler and present its design and prototype implementation. An authenticated web crawler is a trusted program that computes a specially-crafted signature over the web contents it visits. This signature enables (i) the verification of common Internet queries on web pages, such as conjunctive keyword searches---this guarantees that the output of a conjunctive keyword search is correct and complete ; (ii) the verification of the content returned by such Internet queries---this guarantees that web data is authentic and has not been maliciously altered since the computation of the signature by the crawler. In our solution, the search engine returns a cryptographic proof of the query result. Both the proof size and the verification time are proportional only to the sizes of the query description and the query result, but do not depend on the number or sizes of the web pages over which the search is performed. As we experimentally demonstrate, the prototype implementation of our system provides a low communication overhead between the search engine and the user, and fast verification of the returned results by the user.

We study the degree to which a character stringQleaks details about itself any time it engages in comparison protocols with a strings provided by a querier, Bob, even if those protocols are cryptographically guaranteed to produce no additional information other than the scores that assess the degree to whichQmatches strings offered by Bob. We show that such scenarios allow Bob to play variants of the game of Mastermind withQso as to learn the complete identity ofQ. We show that there are a number of efficient implementations for Bob to employ in these Mastermind attacks, depending on knowledge he has about the structure ofQ, which show how quickly he can determineQ. Indeed, we show that Bob can discoverQusing a number of rounds of test comparisons that is much smaller than the length ofQ, under reasonable assumptions regarding the types of scores that are returned by the cryptographic protocols and whether he can use knowledge about the distribution thatQcomes from. We also provide the results of a case study we performed on a database of mitochondrial DNA, showing the vulnerability of existing real-world DNA data to the Mastermind attack.

In this paper, we study methods for improving the utility and privacy of reputation scores for online auctions, such as used in eBay, so as to reduce the effectiveness of feedback extortion. The main idea behind our techniques is to escrow reputations scores until appropriate external events occur. Depending on the degree of utility and privacy needed, these external techniques could depend on the number and type of reputation scores collected. Moreover, if additional privacy protection is needed, then random sampling can be used with respect reputation scores in such a way that reputation aggregates remain useful, but individual reputation scores are probabilistically hidden from users. Finally, we show that if privacy is also desired with respect to the the reputation aggregator, then we can use zero-knowledge proofs for reputation comparisons.

We study the MapReduce framework from an algorithmic standpoint, providing a generalization of the previous algorithmic models for MapReduce. We present optimal solutions for the fundamental problems of all-prefix-sums, sorting and multi-searching. Additionally, we design optimal simulations of the the well-established PRAM and BSP models in MapReduce, immediately resulting in optimal solutions to the problems of computing fixed-dimensional linear programming and 2-D and 3-D convex hulls. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

We describe a synopsis structure, the Difference Digest, that allows two nodes to compute the elements belonging to the set difference in a single round with communication overhead proportional to the size of the difference times the logarithm of the keyspace. While set reconciliation can be done efficiently using logs, logs require overhead for every update and scale poorly when multiple users are to be reconciled. By contrast, our abstraction assumes no prior context and is useful in networking and distributed systems applications such as trading blocks in a peer-to-peer network, and synchronizing link-state databases after a partition.

We present data-oblivious algorithms in the external-memory model for compaction, selection, and sorting. Motivation for such problems comes from clients who use outsourced data storage services and wish to mask their data access patterns. We show that compaction and selection can be done data-obliviously using O(N/B) I/Os, and sorting can be done, with a high probability of success, using O(N/B) logM/B(N/B)) I/Os.

Many data structures support dictionaries, also known as maps or associative arrays, which store and manage a set of key-value pairs. A multimap is generalization that allows multiple values to be associated with the same key. We study how multimaps can be implemented efficiently online in external memory frameworks, with constant expected I/O. The key technique used to achieve our results is a combination of cuckoo hashing using buckets that hold multiple items with a multiqueue implementation to cope with varying numbers of values per key.

In this article, we describe a randomized Shellsort algorithm. This algorithm is a simple, randomized, data-oblivious version of the Shellsort algorithm that always runs in O ( n log n ) time and succeeds in sorting any given input permutation with very high probability. Taken together, these properties imply applications in the design of new efficient privacy-preserving computations based on the secure multiparty computation (SMC) paradigm. In addition, by a trivial conversion of this Monte Carlo algorithm to its Las Vegas equivalent, one gets the first version of Shellsort with a running time that is provably O ( n log n ) with very high probability.

We describe a method for performing greedy geometric routing for any n-vertex simple connected graph G in the hyperbolic plane, so that a message M between any pair of vertices may be routed by having each vertex that receives M pass it to a neighbor that is closer to M's destination. Our algorithm produces succinct embeddings, where vertex positions are represented using O(\log n) bits and distance comparisons may be performed efficiently using these representations. These properties are useful, for example, for routing in sensor networks, where storage and bandwidth are limited.

In this paper, we study the straggler identification problem, in which an algorithm must determine the identities of the remaining members of a set after it has had a large number of insertion and deletion operations performed on it, and now has relatively few remaining members. The goal is to do this in o(n) space, where n is the total number of identities. Straggler identification has applications, for example, in determining the unacknowledged packets in a high-bandwidth multicast data stream. We provide a deterministic solution to the straggler identification problem that uses only O(d log n) bits, based on a novel application of Newton's identities for symmetric polynomials. This solution can identify any subset of d stragglers from a set of n O(log n)-bit identifiers, assuming that there are no false deletions of identities not already in the set. Indeed, we give a lower bound argument that shows that any small-space deterministic solution to the straggler identification problem cannot be guaranteed to handle false deletions. Nevertheless, we provide a simple randomized solution, using O(d log n log (1/∈)) bits that can maintain a multiset and solve the straggler identification problem, tolerating false deletions, where ∈ > 0 is a user-defined parameter bounding the probability of an incorrect response. This randomized solution is based on a new type of Bloom filter, which we call the invertible Bloom filter.

In this paper, we introduce a framework for secure two-party (S2P) computations, which we call bureaucratic computing, and we demonstrate its efficiency by designing practical S2P computations for sorting, selection, and random permutation. In a nutshell, the main idea behind bureaucratic computing is to design data-oblivious algorithms that push all knowledge and influence of input values down to small black-box circuits, which are simulated using Yao's garbled paradigm. The practical benefit of this approach is that it maintains the zero-knowledge features of secure two-party computations while avoiding the significant computational overheads that come from trying to apply Yao's garbled paradigm to anything other than simple two-input functions.

We give efficient data-oblivious algorithms for several fundamental geometric problems that are relevant to geographic information systems, including planar convex hulls and all-nearest neighbors. Our methods are "data-oblivious" in that they don't perform any data-dependent operations, with the exception of operations performed inside low-level blackbox circuits having a constant number of inputs and outputs. Thus, an adversary who observes the control flow of one of our algorithms, but who cannot see the inputs and outputs to the blackbox circuits, cannot learn anything about the input or output. This behavior makes our methods applicable to secure multiparty computation (SMC) protocols for geographic data used in location-based services. In SMC protocols, multiple parties wish to perform a computation on their combined data without revealing individual data to the other parties. For instance, our methods can be used to solve a problem posed by Du and Atallah, where Alice has a set, A, of m private points in the plane, Bob has another set, B, of n private points in the plane, and Alice and Bob want to jointly compute the convex hull of A ∪ B without disclosing any more information than what can be derived from the answer. In particular, neither Alice nor Bob want to reveal any of their respective points that are in the interior of the convex hull of A ∪ B.

In this paper, we study parallel I/O efficient graph algorithms in the Parallel External Memory (PEM) model, one o f the private-cache chip multiprocessor (CMP) models. We study the fundamental problem of list ranking which leads to efficient solutions to problems on trees, such as computing lowest common ancestors, tree contraction and expression tree evaluation. We also study the problems of computing the connected and biconnected components of a graph, minimum spanning tree of a connected graph and ear decomposition of a biconnected graph. All our solutions on a P-processor PEM model provide an optimal speedup of ¿(P) in parallel I/O complexity and parallel computation time, compared to the single-processor external memory counterparts.

In this paper, we describe a randomized Shellsort algorithm. This algorithm is a simple, randomized, data-oblivious version of the Shellsort algorithm that always runs in O(n log n) time and succeeds in sorting any given input permutation with very high probability. Taken together, these properties imply applications in the design of new efficient privacy-preserving computations based on the secure multi-party computation (SMC) paradigm. In addition, by a trivial conversion of this Monte Carlo algorithm to its Las Vegas equivalent, one gets the first version of Shellsort with a running time that is provably O(n log n) with very high probability.

We provide linear-time algorithms for geometric graphs with sublinearly many edge crossings. That is, we provide algorithms running in $O(n)$ time on connected geometric graphs having n vertices and k pairwise crossings, where k is smaller than n by an iterated logarithmic factor. Specific problems that we study include Voronoi diagrams and single-source shortest paths. Our algorithms all run in linear time in the standard comparison-based computational model; hence, we make no assumptions about the distribution or bit complexities of edge weights, nor do we utilize unusual bit-level operations on memory words. Instead, our algorithms are based on a planarization method that “zeros in” on edge crossings, together with methods for applying planar separator decompositions to geometric graphs with sublinearly many crossings. Incidentally, our planarization algorithm also solves an open computational geometry problem of Chazelle for triangulating a self-intersecting polygonal chain having n segments and k crossings in linear time, for the case when k is sublinear in n by an iterated logarithmic factor.

A geometric graph is a graph embedded in the plane with vertices at points and edges drawn as curves (which are usually straight line segments) between those points. The average transversal complexity of a geometric graph is the number of edges of that graph that are crossed by random line or line segment.

We provide linear-time algorithms for geometric graphs with sublinearly many crossings. That is, we provide algorithms running in O(n) time on connected geometric graphs having n vertices and k crossings, where k is smaller than n by an iterated logarithmic factor. Specific problems we study include Voronoi diagrams and single-source shortest paths. Our algorithms all run in linear time in the standard comparison-based computational model; hence, we make no assumptions about the distribution or bit complexities of edge weights, nor do we utilize unusual bit-level operations on memory words. Instead, our algorithms are based on a planarization method that “zeroes in” on edge crossings, together with methods for extending planar separator decompositions to geometric graphs with sublinearly many crossings. Incidentally, our planarization algorithm also solves an open computational geometry problem of Chazelle for triangulating a self-intersecting polygonal chain having n segments and k crossings in linear time, for the case when k is sublinear in n by an iterated logarithmic factor.

In this paper, we study the degree to which a genomic string, Q, leaks details about itself any time it engages in comparison protocols with a genomic querier, Bob, even if those protocols are cryptographically guaranteed to produce no additional information other than the scores that assess the degree to which Q matches strings offered by Bob. We show that such scenarios allow Bob to play variants of the game of mastermind with Q so as to learn the complete identity of Q. We show that there are a number of efficient implementations for Bob to employ in these mastermind attacks, depending on knowledge he has about the structure of Q, which show how quickly he can determine Q. Indeed, we show that Bob can discover Q using a number of rounds of test comparisons that is much smaller than the length of Q, under various assumptions regarding the types of scores that are returned by the cryptographic protocols and whether he can use knowledge about the distribution that Q comes from, e.g., using public knowledge about the properties of human DNA. We also provide the results of an experimental study we performed on a database of mitochondrial DNA, showing the vulnerability of existing real-world DNA data to the mastermind attack.

We provide an efficient algorithm for two-site Voronoi diagrams in geographic networks. A two-site Voronoi diagram labels each vertex in a geographic network with their two nearest neighbors, which is useful in many contexts.

This paper studies real-world road networks from an algorithmic perspective, focusing on empirical studies that yield useful properties of road networks that can be exploited in the design of fast algorithms that deal with geographic data. Unlike previous approaches, our study is not based on the assumption that road networks are planar graphs. Indeed, based on the a number of experiments we have performed on the road networks of the 50 United States and District of Columbia, we provide strong empirical evidence that road networks are quite non-planar. Our approach therefore instead is directed at finding algorithmically-motivated properties of road networks as non-planar geometric graphs, focusing on alternative properties of road networks that can still lead to efficient algorithms for such problems as shortest paths and Voronoi diagrams. In particular, we study road networks as multiscale-dispersed graphs, which is a concept we formalize in terms of disk neighborhood systems. This approach allows us to develop fast algorithms for road networks without making any additional assumptions about the distribution of edge weights. In fact, our algorithms can allow for non-metric weights.

We study approximate topological matching of quadrilateral meshes, that is, the problem of finding as large a set as possible of matching portions of two quadrilateral meshes. This study is motivated by applications in graphics that involve shape modeling whose results need to be merged in order to produce a final unified representation of an object. We show that the problem of producing a maximum approximate topological match of two quad meshes in NP-hard. Given this result, which makes an exact solution extremely unlikely, we show that the natural greedy algorithm derived from polynomial-time graph isomorphism can produce poor results, even when it is possible to find matches with only a few non-matching quads. Nevertheless, we provide a "lazy-greedy" algorithm that is guaranteed to find good matches when mis-matching portions of mesh are localized. Finally, we provide empirical evidence that this approach produces good matches between similar quad meshes.

In this paper, we study parallel algorithms for private-cache chip multiprocessors (CMPs), focusing on methods for foundational problems that are scalable with the number of cores. By focusing on private-cache CMPs, we show that we can design efficient algorithms that need no additional assumptions about the way cores are interconnected, for we assume that all inter-processor communication occurs through the memory hierarchy. We study several fundamental problems, including prefix sums, selection, and sorting, which often form the building blocks of other parallel algorithms. Indeed, we present two sorting algorithms, a distribution sort and a mergesort. Our algorithms are asymptotically optimal in terms of parallel cache accesses and space complexity under reasonable assumptions about the relationships between the number of processors, the size of memory, and the size of cache blocks. In addition, we study sorting lower bounds in a computational model, which we call the parallel external-memory (PEM) model, that formalizes the essential properties of our algorithms for private-cache CMPs.

Abstract We describe algorithms for canonically partitioning semi‐regular quadrilateral meshes into structured submeshes, using an adaptation of the geometric motorcycle graph of Eppstein and Erickson to quad meshes. Our partitions may be used to efficiently find isomorphisms between quad meshes. In addition, they may be used as a highly compressed representation of the original mesh. These partitions can be constructed in sublinear time from a list of the extraordinary vertices in a mesh. We also study the problem of further reducing the number of submeshes in our partitions—we prove that optimizing this number is NP‐hard, but it can be efficiently approximated.

We propose a notarized federated identity management model that supports efficient user authentication when providers are unknown to each other. Our model introduces a notary service, owned by a trusted third-party, to dynamically notarize assertions generated by identity providers. An additional f eature of our model is the avoidance of direct communications between identity providers and service providers, which provides improved privacy protection for users. We present an efficient implementation of our notarized federated identity management model based on the Secure Transaction Management System (STMS). We also give a practical solution for mitigating aspects of the identity theft problem and discuss its use in our notarized federated identity management model. The unique feature of our cryptographic solution is that it enables one to proactively prevent the leaking of secret identity information.

We consider the problem of placing a small number of angle guards inside a simple polygon P so asto provide efficient proofs that any given point is inside P. Each angle guard views an infinite wedge of the plane, and a point can prove membership in P if it is inside the wedges for a set of guards whose common intersection contains no points outside the polygon. This model leads to a broad class of new art gallery type problems, which we call "sculpture garden" problems and for which we provide upper and lower bounds. In particular, we show there is a polygon P such that a "natural" angle-guard vertex placement cannot fully distinguish between pointson the inside and outside of P (even if we place a guard at every vertex of P), which implies that Steiner-point guards are sometimes necessary. More generally, we show that, for any polygon P, there is a set of n+2(h-1) angle guards that solve the sculpture garden problem for P, where h is the number of holes in P (so a simple polygon can be defined with n-2 guards). In addition, we show that, for any orthogonal polygon P, the sculpture garden problem can besolved using n/2 angle guards. We also give an example of a class of simple (non-general-position) polygons that have sculpture garden solutions using O(√n) guards, and we show this bound is optimal to within a constant factor. Finally, while optimizing the number of guards solving a sculpture garden problem for a particular P is of unknown complexity, we show how to find in polynomial time a guard placement whose size is within a factor of 2 of the optimal number for any particular polygon.

We study practically efficient methods for performing combinatorial group testing. We present efficient nonadaptive and two‐stage combinatorial group testing algorithms, which identify the at most d items out of a given set of n items that are defective, using fewer tests for all practical set sizes. For example, our two‐stage algorithm matches the information‐theoretic lower bound for the number of tests in a combinatorial group testing regimen.

We present memory-efficient deterministic algorithms for constructing ϵ-nets and ϵ-approximations of streams of geometric data. Unlike probabilistic approaches, these deterministic samples provide guaranteed bounds on their approximation factors. We show how our deterministic samples can be used to answer approximate online iceberg geometric queries on data streams. We use these techniques to approximate several robust statistics of geometric data streams, including Tukey depth, simplicial depth, regression depth, the Thiel-Sen estimator, and the least median of squares. Our algorithms use only a polylogarithmic amount of memory, provided the desired approximation factors are at least inverse-polylogarithmic. We also include a lower bound for noniceberg geometric queries.

Secure pairing of electronic devices that lack any previous association is a challenging problem which has been considered in many contexts and in various flavors. In this paper, we investigate the use of audio for human-assisted authentication of previously un-associated devices. We develop and evaluate a system we call Loud-and-Clear (L&C) which places very little demand on the human user. L&C involves the use of a text-to-speech (TTS) engine for vocalizing a robust-sounding and syntactically-correct (English-like) sentence derived from the hash of a device’s public key. By coupling vocalization on one device with the display of the same information on another device, we demonstrate that L&C is suitable for secure device pairing (e.g., key exchange) and similar tasks. We also describe several common use cases, provide some performance data for our prototype implementation and discuss the security properties of L&C.

With the proliferation of wireless communication technologies and mobile computing devices, research interest has grown for location-aware systems and services. We propose LAAC, a novel location-aware access control protocol based on a coarsely defined location area that is enclosed by overlapping areas of multiple access points. Accordingly, a location key for location claim is derived from the overlapping access points' beacon information. In addition, the fact that a mobile device derives the location key enables us to track the location of the mobile device. LAAC does not require additional hardwares such as GPS or ultrasonic devices in order to localize the mobile devices. We enumerate possible attacks to the system and analyze their countermeasures. The computational and communicational costs and the memory requirement are evaluated, and the simulation results are presented

We study parallel algorithms for identifying the dead sensors in a mobile ad hoc wireless network and for resolving broadcast conflicts on a multiple access channel (MAC). Our approach involves the development and application of new group-testing algorithms, where we are asked to identify all the defective items in a set of items when we can test arbitrary subsets of items. In the standard group-testing problem, the result of a test is binary--the tested subset either contains defective items or not. In the versions we study in this paper, the result of each test is non-binary. For example, it may indicate whether the number of defective items contained in the tested subset is zero, one, or at least two (i.e., the results are 0, 1, or 2+). We give adaptive algorithms that are provably more efficient than previous group testing algorithms (even for generalized response models). We also show how our algorithms can be implemented in parallel, because they possess a property we call conciseness, which allows them to be used to solve dead sensor diagnosis and conflict resolution on a MAC. Dead sensor diagnosis poses an interesting challenge compared to MAC resolution, because dead sensors are not locally detectable, nor are they themselves active participants. Even so, we present algorithms that can be applied in both contexts that are more efficient than previous methods. We also give lower bounds for generalized group testing.

Many database applications that need to disseminate dynamic information from a server to various clients can suffer from heavy communication costs. Data caching at a client can help mitigate these costs, particularly when individual PUSH-PULL decisions are made for the different semantic regions in the data space. The server is responsible for notifying the client about updates in the PUSH regions. The client needs to contact the server for queries that ask for data in the PULL regions. We call the idea of partitioning the data space into PUSH-PULL regions to minimize communication cost data gerrymandering. In this paper, we present solutions to technical challenges in adopting this simple but powerful idea. We give a provably optimal-cost dynamic programming algorithm for gerrymandering on a single query attribute. We propose a family of efficient heuristics for gerrymandering on multiple query attributes. We handle the dynamic case in which the workloads of queries and updates evolve over time. We validate our methods through extensive experiments on real and synthetic data sets

We present a new multi-dimensional data structure, which we call the skip quadtree (for point data in R2) or the skip octree (for point data in Rd, with constant d > 2). Our data structure combines the best features of two well-known data structures, in that it has the well-defined "box"-shaped regions of region quadtrees and the logarithmic-height search and update hierarchical structure of skip lists. Indeed, the bottom level of our structure is exactly a region quadtree (or octree for higher dimensional data). We describe efficient algorithms for inserting and deleting points in a skip quadtree, as well as fast methods for performing point location, approximate range, and approximate nearest neighbor queries.

We present a framework for designing efficient distributed data structures for multi-dimensional data. Our structures, which we call skip-webs, extend and improve previous randomized distributed data structures, including skipnets and skip graphs. Our framework applies to a general class of data querying scenarios, which include linear (one-dimensional) data, such as sorted sets, as well as multi-dimensional data, such as d-dimensional octrees and digital tries of character strings defined over a fixed alphabet.We show how to perform a query over such a set of n items spread among n hosts using O(log n/log log n) messages for one-dimensional data, or O(log n) messages for fixed-dimensional data, while using only O(log n) space per host. We also show how to make such structures dynamic so as to allow for insertions and deletions in O(log n) messages for quadtrees, octrees, and digital tries, and O(log n/log log n) messages for one-dimensional data. Finally, we show how to apply a blocking strategy to skip-webs to further improve message complexity for one-dimensional data when hosts can store more data.

We present two new approaches to improving the integrity of network broadcasts and multicasts with low storage and computation overhead. The first approach is a leapfrog linking protocol for securing the integrity of packets as they traverse a network during a broadcast, such as in the setup phase for link-state routing. This technique allows each router to gain confidence about the integrity of a packet before passing it on to the next router; hence, allows many integrity violations to be stopped immediately in their tracks. The second approach is a novel key predistribution scheme that we use in conjunction with a small number of hashed message authentication codes (HMAC), which allows end-to-end integrity checking as well as improved hop-by-hop integrity checking. Our schemes are suited to environments, such as in ad hoc and overlay networks, where routers can share only a small number of symmetric keys. Moreover, our protocols do not use encryption (which, of course, can be added as an optional security enhancement). Instead, security is based strictly on the use of one-way hash functions; hence, our algorithms are considerably faster than those based on traditional public-key signature schemes. This improvement in speed comes with only modest reductions in the security for broadcasting, as our schemes can tolerate small numbers of malicious routers, provided they do not form significant cooperating coalitions.

We present memory-efficient deterministic algorithms for constructing ∈-nets and ∈-approximations of streams of geometric data. Unlike probabilistic approaches, these deterministic samples provide guaranteed bounds on their approximation factors. We show how our deterministic samples can be used to answer approximate online iceberg geometric queries on data streams. We use these techniques to approximate several robust statistics of geometric data streams, including Tukey depth, simplicial depth, regression depth, the Thiel-Sen estimator, and the least median of squares. Our algorithms use only a polylogarithmic amount of memory, provided the desired approximation factors are inverse-polylogarithmic. We also include a lower bound for non-iceberg geometric queries.

We present a new approach to IP traceback based on the probabilistic packet marking paradigm. Our approach, which we call randomize-and-link, uses large checksum cords to "link" message fragments in a way that is highly scalable, for the checksums serve both as associative addresses and data integrity verifiers. The main advantage of these checksum cords is that they spread the addresses of possible router messages across a spectrum that is too large for the attacker to easily create messages that collide with legitimate messages. Our methods therefore scale to attack trees containing hundreds of routers and do not require that a victim know the topology of the attack tree a priori. In addition, by utilizing authenticated dictionaries in a novel way, our methods do not require routers sign any setup messages individually.

Silhouettes are perceptually and geometrically salient features of geo metric models. Hence a number of graphics and visualization applications need to find them to aid further processing. The efficient computation of silhouettes, especially in the context of perspective projection, is known to be difficult. This paper presents a novel efficient and practical algorithm to compute silhouettes from a sequence of viewpoints under perspective projection. Parallel projection is a special case of this algorithm. Our approach is based on a point-plane duality in three dimensions, which allows an efficient computation of the \emph{changes} in the silhouette of a polygonal model between consecutive frames. In addition, we present several applications of our technique to problems from computer graphics and medical visualization. We also provide experimental data that show the efficiency of our approach.

We describe an Internet-based approach for teaching important concepts in a Junior-Senior level course on the design and analysis of data structures and algorithms (traditionally called CS7 or DS&A). The main idea of this educational paradigm is twofold. First, it provides fresh motivation for fundamental algorithms and data structures that are finding new applications in the context of the Internet. Second, it provides a source for introducing new algorithms and data structures that are derived from specific Internet applications. In this paper, we suggest some key pedagogical and curriculum updates that can be made to the classic CS7/DS&A course to turn it into a course on Internet Algorithmics. We believe that such a course will stimulate new interest and excitement in material that is perceived by some students to be stale, boring, and purely theoretical. We argue that the foundational topics from CS7/DS&A should remain even when it is taught in an Internet-centric manner. This, of course, should come as no surprise to the seasoned computer scientist, who understands the value of algorithmic thinking.

We describe a randomized algorithm for computing the trapezoidal decomposition of a simple polygon.Its expected running time is linear in the size of the polygon.By a well-known and simple linear time reduction, this implies a linear time algorithm for triangulating a simple polygon.Our algorithm is considerably simpler than Chazelle's (1991) celebrated optimal deterministic algorithm and, hence, positively answers his question of whether a simpler randomized algorithm for the problem exists.The new algorithm can be viewed as a combination of Chazelle's algorithm and of non-optimal randomized algorithms due to Clarkson et al. (1991) andto Seidel (1991), with the essential innovation that sampling is performed on subchains of the initial polygonal chain, rather than on its edges.It is also essential, as in Chazelle's algorithm, to include a bottom-up preprocessing phase previous to the top-down construction phase.

We describe a Web-based interactive system, called PILOT, for testing computer science concepts.The strengths of PILOT are its universal access and platform independence, its use as an algorithm visualization tool, its ability to test algorithmic concepts, its support for graph generation and layout, its automated grading mechanism, and its ability to award partial credit to proposed solutions.

In this paper we present a package for the creation of Specialized Assignments In LATEX, SAIL. We describe several features which allow an instructor to create sufficiently different instances of the “same” problem so as to encourage student cooperation without fear of plagiarism. The SAIL package also provides support for grading aids and grading automation. In addition, we describe an on-line system for archiving homework problems in a database that can be easily searched and to which new parametrized problems can be easily added. Together, the SAIL package and the searchable database of problems offer a powerful tool for generating, archiving, and retrieving homework assignments (as well as tests and quizzes).

No abstract available.

We present two tools to support the teaching of data structures and algorithms: Visualizers, which provide interactive visualizations of user-written data structures, and Testers, which check the functionality of user-written data structures. We outline a prototype implementation of visualizers and testers for data structures written in Java, and report on classroom use of testers and visualizers in an introductory Data Structures and Algorithms (CS2) course.

We describe an approach for incorporating randomization in the teaching of data structures and algorithms. The proofs we include are quite simple and can easily be made a part of a Freshman-Sophomore Introduction to Data Structures (CS2) course and a Junior-Senior level course on the design and analysis of data structures and algorithms (CS7/DS&A). The main idea of this approach is to show that using randomization in data structures and algorithms is safe and can be used to significantly simplify efficient solutions to various computational problems. We illustrate this approach by giving examples of the use of randomization in some traditional topics from CS2 and DS&A.

We present techniques for matching point-sets in two and three dimensions under rigid-body transformations. We prove bounds on the worst-case performance of these algorithms to be within a small constant factor of optimal and conduct experiments to show that the average performance of these matching algorithms is often better than that predicted by the worst-case bounds.

We study the problem of sorting n numbers on a p-processor bulk-synchronous parallel (BSP) computer, which is a parallel multicomputer that allows for general processor-to-processor communication rounds provided each processor sends and receives at most h items in any round. We provide parallel sorting methods that use internal computation time that is $O({n\log n \over p})$ and a number of communication rounds that is $O({\log n \over \log (h+1)})$ for $h=\Theta(n/p)$. The internal computation bound is optimal for any comparison-based sorting algorithm. Moreover, the number of communication rounds is bounded by a constant for the (practical) situations when $p\le n^{1-{1/c}}$ for a constant $c\ge 1$. In fact, we show that our bound on the number of communication rounds is asymptotically optimal for the full range of values for p, for we show that just computing the "or"of n bits distributed evenly to the first O(n/h) of an arbitrary number of processors in a BSP computer requires $\Omega(\log n/\log (h+1))$ communication rounds.

We present efficient algorithms for solving polygonal-path approximation problems in three and higher dimensions.Given an n-vertex polygonal curve P in EL', d 2 3, we approximate P by another polygonal curve P' of m 5 n vertices in IR! such that the vertex sequence of P' is an ordered subsequence of the vertices of P. The goal is to either minimize the size m of P' for a given error tolerance E (called the min-# problem), or to minimize the deviation error E between P and P' for a given size m of P' (called the min-.sproblem).Our techniques enable us to develop efficient nearquadratic-time algorithms in 3-D and sub-cubictime algorithms in 4-D for solving the mm-# and mine problems.We discuss extensions of our solutions to d-dimensional space, where d > 4.

In this paper we present an approach for teaching the Freshman-Sophomore introduction to data structures course (CS2) in a way that provides an introduction to object-oriented software engineering patterns in addition to the theory of data structures. We survey in this paper several design patterns and describe how they can be naturally integrated in the CS2 curriculum.

We describe an approach for visually teaching important proofs in the Junior-Senior level course on the design and analysis of data structures and algorithms (CS7/DS&A). The main idea of this educational paradigm is to justify important claims about data structures and algorithms by using pictures that visualize proofs so clearly that the pictures can qualify as proofs themselves. The advantage of using this approach for DS&A is that it augments or even replaces inductive arguments that many students find difficult. Moreover, this paradigm communicates important algorithmic facts in a compelling way for students who are more visually-oriented. We illustrate this technique by giving examples of visual proofs of several key concepts in DS&A.

An offset-polygon annulus region is defined in terms of a polygon P and a distance δ > 0 (offset of P). In this paper we solve several containment problems for polygon annulus regions with respect to an input point set. Optimization criteria include both maximizing the number of points contained in a fixed size annulus and minimizing the size of the annulus needed to contain all points. We address the following variants of the problem: placement of an annulus of a convex polygon as well as of a simple polygon; placement by translation only, or by translation and rotation; off-line and on-line versions of the corresponding decision problems; and decision as well as optimization versions of the problems. We present efficient algorithms in each case.

This paper describes new methods for maintaining a point-location data structure for a dynamically changing monotone subdivision $\cal S$. The main approach is based on the maintenance of two interlaced spanning trees, one for $\cal S$ and one for the graph-theoretic planar dual of $\cal S$. Queries are answered by using a centroid decomposition of the dual tree to drive searches in the primal tree. These trees are maintained via the link-cut trees structure of Sleator and Tarjan [J. Comput. System Sci., 26 (1983), pp. 362--381], leading to a scheme that achieves vertex insertion/deletion in O(log n) time, insertion/deletion of k-edge monotone chains in O(log n + k) time, and answers queries in O(log 2 n ) time, with O(n) space, where n is the current size of subdivision $\cal S$. The techniques described also allow for the dual operations expand and contract to be implemented in O(log n) time, leading to an improved method for spatial point location in a 3-dimensional convex subdivision. In addition, the interlaced-tree approach is applied to on-line point location (where one builds $\cal S$ incrementally), improving the query bound to $O(\log n\log\log n)$ time and the update bounds to O(1)amortized time in this case. This appears to be the first on-line method to achieve a polylogarithmic query time and constant update time.

No abstract available.

In this paper we present GeomNet, a system for performing dktributed geometric computing over the Internet.We also provide seved examples of actual geometric algorithms that our system already supports.Application domains for GeomNet include collaborative research and dist ante education.

We study the problem of robustly rounding a set S of n line segments in R2 using the snap rounding paradigm.In this paradigm each pixel containing an endpoint or intersection point is called "hot," and all segments intersecting a hot pixel are re-routed to pass through its center.We show that a snap-rounded approximation to the arrangement defined by S can be built in an output-sensitive fashion, and that this can be done without first determining all the intersecting pairs of segments in S. Specifically, we give a deterministic plan~sweep algorithm running in time O(n bgn -F &H Ihl10g ~), where ~is the set of hot pixela and \hl is the number of segments intersecting a hot pixel h E H. We alsogive a simple randomized incremental construction whose expected running time matches that of our deterministic algorithm.The complexity of these algorithms is optimal up to polylogarithmic factors.

Given two planar sets A and B, we examine the problem of determining the smallest ϵ such that there is a Euclidean motion (rotation and translation) of A that brings each member of A within distance ϵ of some member of B. We establish upper bounds on the combinatorial complexity of this subproblem in model-based computer vision, when the sets A and B contain points, line segments, or (filled-in) polygons. We also show how to use our methods to substantially improve on existing algorithms for finding the minimum Hausdorff distance under Euclidean motion.

We show that several well-known optimization problems involving 3-dimensional convex polyhedra and decision trees are NP-hard or NP-complete. One of the techniques we employ is a linear-time method for realizing a planar 3-connected triangulation as a convex polyhedron, which may be of independent interest.

We present a number of efficient parallel algorithms for constructing 2-dimensional convex hulls on a randomized CRCW PRAM. Specifically, we show how to build the convex hull of n presorted points in the plane in O(1) time using O(n log n) work, with n-exponential probability, or, alternately, in O(log∗ n) time using O(n) work, with n-exponential probability. We also show how to find the convex hull of n unsorted planar points in O(log n) time using O(n log h) work, with n-exponential probability, where h is the number of edges in the convex hull (h is O(n), but can be as small as O(1)). Our algorithm for unsorted inputs depends on the use of new in-place procedures, that is, procedures that are defined on a subset of elements in the input and that work without reordering the input. In order to achieve our n-exponential confidence bounds we use a new parallel technique called failure sweeping.

In this paper, we investigate the area and volume requirement of convex drawings of planar graphs in two and three dimensions, under various resolution rules. Let G be a triconnected planar graph with n vertices. We provide O(n)-time algorithms for constructing the following types of drawings of G: ffl a 2D convex grid drawing of G with (3n) \\Theta (3n=2) area under the edge resolution rule (in the L 1 metric). ffl a 2D strictly convex grid drawing of G with O(n 3 ) \\Theta O(n 3 ) area under the edge resolution rule (in the L 1 metric). ffl a 2D strictly convex drawing of G with O(1) \\Theta O(n) area under the vertex-resolution rule, and with vertex coordinates represented by O(n log n)-bit rational numbers; ffl a 3D convex drawing of G with O(1)\\ThetaO(1)\\ThetaO(n) volume under the vertex-resolution rule, and with vertex coordinates represented by O(n log n)-bit rational numbers. We also show the following lower bounds on the area/volume of 2D/3D convex drawings under the edg...

We study the problem of sorting n numbers on a p-processor bulk-synchronous parallel (BSP) computer, which is a parallel multicomputer that allows for general processor-to-processor communication rounds provided each processor sends and receives at most h items in any round.We provide parallel sorting methods that use internal computation time that is O(*) and a number of communication rounds that is 0( ~$$~1) ) for h = @(n/p).The internal computation bound is optimal for any comparison-based sorting algorithm.Moreover, the number of communication rounds is bounded by a constant for the (practical) situations when p < nl-l/c for a constant c > 1.In fact, we show that our bound on the number of communication rounds is asymptotically optimal for the full range of values for p, for we show that just computing the "or" of n bits distributed evenly to the first O(n/h) of an arbitrary number of processors in a BSP computer requires fl(log n/ log(h + 1)) communication rounds.

We present optimal algorithms for sorting on parallel CREW and EREW versions of the pointer machine model. Intuitively, one can view our methods as being based on a parallel mergesort using linked lists rather than arrays (the usual parallel data structure). We also show how to exploit the “locality” of our approach to solve the set expression evaluation problem, a problem with applications to database querying and logic-programming in O (log n ) time using O ( n ) processors. Interestingly, this is an asymptotic improvement over what seems possible using previous techniques.

For a set S of n line segments in the plane, we give the first work-optimal deterministic parallel algorithm for con-structing their arrangement. It runs in O(log2 n) time using O(n logn + k) work in the EREW PRAM model, where k is the number of intersecting line segment pairs, and pro-vides a fairly simple divide-and-conquer alternative to the optimal sequential “plane-sweep ” algorithm of Chazelle and Edelsbrunner. Moreover, our method can be used to out-put all k intersecting pairs while using only O(n) working space, which solves an open problem posed by Chazelle and Edelsbrunner. We also describe a sequential algorithm for computing a single face in an arrangement of n line seg-ments that runs in O(n2(n) logn) time, which improves on a previous O(n log2 n) time algorithm. For collections of simplices in IRd, we give methods for constructing a set ofm = O(nd1 logc n+k) cells of constant descriptive complexity that covers their arrangement, where c> 1 is a constant and k is the number of faces in the arrangement. The construction is performed sequentially in O(m) time, or in O(logn) time using O(m) work in the EREW PRAM model. The covering can be augmented to answer point location queries in O(logn) time. In addition to supplying the first parallel methods for these problems, we improve on the previous best sequential methods by reducing the query times (from O(log2 n) in IR3 and O(log3 n) in IRd, d> 3), and also the size and construction cost of the covering (from O(nd1+ + k)). 1

We show how to construct an O(√n)-separator decomposition of a planar graph G in O(n) time. Such a decomposition defines a binary tree, where each node corresponds to a subgraph of G and stores an O(√n)-separator of that subgraph. We also show how to construct an O(nϵ)-way decomposition tree in parallel in O(log n) time so that each node corresponds to a subgraph of G and stores an O(n12+ϵ)-separator of that subgraph. We demonstrate the utility of such a separator decomposition by showing how it can be used in the design of a parallel algorithm for triangulating a simple polygon deterministically in O(log n) time using O(n/log n) processors on a CRCW PRAM.

We present a method for maintaining biased search trees so as to support fast finger updates (i.e., updates in which one is given a pointer to the part of the tree being changed). We illustrate the power of such biased finger trees by showing how they can be used to derive an optimal O(nlogn) algorithm for the 3-dimensional layers-of-maxima problem and also obtain an improved method for dynamic point location.

We give a deterministic polynomial time method for finding a set cover in a set system (X,ℜ) of VC-dimension d such that the size of our cover is at most a factor of O(dlog(dc)) from the optimal size, c. For constant VC-dimension set systems, which are common in computational geometry, our method gives an O(logc) approximation factor. This improves the previous Θ(log |X|) bound of the greedy method and beats recent complexity-theoretic lower bounds for set covers (which don't make any assumptions about VC-dimension). We give several applications of our method to computational geometry, and we show that in some cases, such as those that arise in 3-d polytope approximation and 2-d disc covering, we can quickly find O(c)-sized covers.

We give an O(nlogn)-time method for finding a best k-link piecewise-linear function approximating an n-point planar data set using the well-known uniform metric to measure the error, ε≥0, of the approximation. Our method is based upon new characterizations of such functions, which we exploit to design an efficient algorithm using a plane sweep in “ε space” followed by several applications of the parametric searching technique. The previous best running time for this problem was O(n2).

We present practical methods for approximate geometric pattern matching in d-dimensions along with experimental data regarding the quality of matches and running times of these methods versus those of a branch-and-bound search. Our methods are faster than previous methods but still produce good matches.

We give fast randomized and deterministic parallel methods for constructing convex hulls in R/sup d/, for any fixed d. Our methods are for the weakest shared-memory model, the EREW PRAM, and have optimal work bounds (with high probability for the randomized methods). In particular, we show that the convex hull of n points in R/sup d/ can be constructed in O(log n) time using O(n log n+n/sup [d/2]/) work, with high probability. We also show that it can be constructed deterministically in O(log/sup 2/ n) time using O(n log n) work for d=3 and in O(log n) time using O(n/sup [d/2]/ log/sup c([d/2]-[d/2]/) n) work for d/spl ges/4, where c>0 is a constant which is optimal for even d/spl ges/4. We also show how to make our 3-dimensional methods output-sensitive with only a small increase in running time. These methods can be applied to other problems as well.>

Given an off-line sequence S of n set-manipulation operations, we investigate the parallel complexity of evaluating S (i.e., finding the response to every operation in S and returning the resulting set). We show that the problem of evaluating S is in NC for various combinations of common set-manipulation operations. Once we establish membership in NC (or, if membership in NC is obvious), we develop techniques for improving the time and/or processor complexity.

Rooted trees are usually drawn planar and upward, i.e., without crossings and with parents placed above their children. In this paper we investigate the area requirement of planar upward drawings of trees, and present optimal algorithms for constructing such drawings.

We present a simple approach for constructing geometric partitions in a way that is easy to apply to new problems. We avoid the use of VC-dimension arguments, and, instead, base our arguments on a notion we call the scaffold dimension, which subsumes the VC-dimension and is simpler to apply. We show how to easily construct (1/r)-nets and (1/r)-approximations for range spaces with bounded scaffold dimension, which immediately implies simple algorithms for constructing (1/r)-cuttings (by straight-forward recursive subdivision methods). More significant than simply being a conceptual simplification of previous approaches, however, is that our methods lead to asymptotically faster and more-efficient EREW PRAM parallel algorithms for a number of computational geometry problems, including the development of the first optimal-work NC algorithm for the well-known 3-dimensional convex hull problem, which solves an open problem of Amato and Preparata. Interestingly, our approach also yields a faster sequential algorithm for the distance selection problem, by the parametric searching paradigm, which solves an open problem posed by Agarwal, Aronov, Sharir, and Suri, and reiterated by Dickerson and Drysdale.

Article Free Access Share on Dynamic ray shooting and shortest paths via balanced geodesic triangulations Authors: Michael T. Goodrich Johns Hopkins Univ., Baltimore, MD Johns Hopkins Univ., Baltimore, MDView Profile , Roberto Tamassia Brown Univ., Providence, RI Brown Univ., Providence, RIView Profile Authors Info & Claims SCG '93: Proceedings of the ninth annual symposium on Computational geometryJuly 1993 Pages 318–327https://doi.org/10.1145/160985.161157Published:01 July 1993Publication History 14citation372DownloadsMetricsTotal Citations14Total Downloads372Last 12 Months5Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In this paper we give new techniques for designing efficient algorithms for computational geometry problems that are too large to be solved in internal memory. We use these techniques to develop optimal and practical algorithms for a number of important large-scale problems. We discuss our algorithms primarily in the context of single processor/single disk machines, a domain in which they are not only the first known optimal results but also of tremendous practical value. Our methods also produce the first known optimal algorithms for a wide range of two-level and hierarchical multilevel memory models, including parallel models. The algorithms are optimal both in terms of I/O cost and internal computation.>

In this paper, we consider the problem of using disk blocks efficiently in searching graphs that are too large to fit in internal memory. Our model allows a vertex to be represented any number of times on the disk in order to take advantage of redundancy. We give matching upper and lower bounds for complete d-ary trees and d-dimensional grid graphs, as well as for classes of general graphs that intuitively speaking have a close to uniform number of neighbors around each vertex. We also show that for the special case of grid graphs blocked with isothetic hypercubes, there is a provably better speed-up if even a small amount of redundancy is permitted.

We show how to construct a O(fi)-separator decomposition of a planar graph in O(n) time, and how to triangulate a simple polygon deterministically in parallel in O(log n) time using O(n/ log n) processors on a CRCW PRAM.Both of these results are based on exploiting more of the "tree structure" of these problems.

this paper we give an algorithm for the hidden-line elimination problem that is optimal in the worst case, and also takes advantage of problem instances that are "simpler" than in the worst case. Intuitively, our approach is to exploit the polygonal 2

A framework is presented for designing parallel algorithms that may ignore processor allocation. A number of fast approximation algorithms are developed, and it is shown how to use these algorithms to simulate any algorithm that fits this framework in a work-preserving fashion on a randomized CRCW PRAM. Several applications of the approach to parallel computational geometry are given.>

We present a number of efficient parallel algorithms for constructing 2-and 3-dimensional convex hulls on a randomized CRCW PRAM.

of ResultsWe give two optimal parallel algorithms for constructing the arrangement of n lines in the plane.The first method is quite simple and runs in O(log2 n) time using O(n2 ) work, and the second method, which is more sophisticated, runs in O(log n) time using O(n2) work.This second result solves a well-known open problem in parallel computational geometry, and involves the use of a new algorithmic technique, the construction of ~-pseudo-nets, which may be of interest in its own right.Our results immediately imply that one can optimally construct the arrangement of n hyperplanes in 31d in O(log n) time using O(nd) work, for fixed d.Our algorithms are for the CREW PRAM.binatorial structure describing the cells of !Rd determined by the hyperplanes, as well as the adjacency information for these cells [13, 21, 32, 33] (see Figure 1 for a 2-dimensional example).Indeed, in his highly-regarded book on algorithms in combinatorial geometry, Edels-

ResultsWe give new methods for maintaining a pointlocation data structure for a dynamically-changing monotone subdivision S. Our approa,ch is based on a new, optimal static point-location structure, where one represents $ via two int erlaced spanning trees, one for S and one for the graph-theoretic dual of S. Queries are answered by using a centroid decomposition of the dual tree to drive searches in the primal tree.We maintain these trees via the link-cut trees structure of Sleator and Tarjan, leading to a scheme that achieves vertex

An efficient parallel algorithm is given for constructing the arrangement of n line segments in the plane, i.e., the planar graph determined by the segment endpoints and intersections. This algorithm is efficient relative to three efficiency measures—it is an NC algorithm, it has a small time-processor product, and it is output-size sensitive. In particular, it runs in $O(\log n)$ time using $O(n\log n + k)$ processors, where k is the size of the output (which is $\Omega (n^2 )$ in the worst case). The algorithm does not receive the value of k as input, it determines it on-line. A method or solving an important special case of the segment arrangement problem is also shown, namely, when each input segment is parallel to one of the coordinate axes (i.e., iso-oriented). The algorithm for this problem runs in $O(\log n)$ time using an optimal $O(n + k / \log n)$ processors. The model of computation is the CREW PRAM model, where processor allocation must be explicit and global.

In this paper we give efficient parallel algorithms for solving a number of visibility and shortest path problems for simple polygons. Our algorithms all run in Ο(log n) time and are based on the use of a new data structure for implicitly representing all shortest paths in a simple polygon P, which we call the stratified decomposition tree. We use this approach to derive efficient parallel methods for computing the visibility of P from an edge, constructing the visibility graph of the vertices of P (using an output-sensitive number of processors), constructing the shortest path tree from a vertex of P, and determining all-farthest neighbors for the vertices in P. The computational model we use is the CREW PRAM.

Article P-complete geometric problems Share on Authors: M. Atallah Dept. of Computer Sciences, Purdue Univ., W. Lafayette, IN Dept. of Computer Sciences, Purdue Univ., W. Lafayette, INView Profile , P. Callahan Dept. of Computer Science, The Johns Hopkins Univ., Baltimore, MD Dept. of Computer Science, The Johns Hopkins Univ., Baltimore, MDView Profile , M. Goodrich Dept. of Computer Science, The Johns Hopkins Univ., Baltimore, MD Dept. of Computer Science, The Johns Hopkins Univ., Baltimore, MDView Profile Authors Info & Claims SPAA '90: Proceedings of the second annual ACM symposium on Parallel algorithms and architecturesMay 1990 Pages 317–326https://doi.org/10.1145/97444.97699Online:01 May 1990Publication History 3citation312DownloadsMetricsTotal Citations3Total Downloads312Last 12 Months4Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Article Generalized sweep methods for parallel computational geometry Share on Authors: M. Goodrich Dept. of Computer Science, The Johns Hopkins Univ., Baltimore, MD Dept. of Computer Science, The Johns Hopkins Univ., Baltimore, MDView Profile , M. Ghouse Dept. of Computer Science, The Johns Hopkins Univ., Baltimore, MD Dept. of Computer Science, The Johns Hopkins Univ., Baltimore, MDView Profile , J. Bright Dept. of Computer Science, The Johns Hopkins Univ., Baltimore, MD Dept. of Computer Science, The Johns Hopkins Univ., Baltimore, MDView Profile Authors Info & Claims SPAA '90: Proceedings of the second annual ACM symposium on Parallel algorithms and architecturesMay 1990 Pages 280–289https://doi.org/10.1145/97444.97695Online:01 May 1990Publication History 8citation405DownloadsMetricsTotal Citations8Total Downloads405Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We present an algorithm that, given a set of n parallel line segments in the plane, finds a convex polygon whose boundary intersects each segment at least once or that determines that none exists. Our algorithm runs in O(nlogn) steps and linear space, which is optimal. Our solution involves a reduction to a bipartite stabbing problem, using a “point-sweeping” or “chain-unwrapping” technique. We use geometric duality to solve bipartite stabbing. We also indicate how to extend our algorithm to find the convex polygon with minimum area or perimeter that intersects each segment.

We show how to extend any tree-structured dictionary machine so that it can perform order statistics robustly. In particular, we consider how to allow for redundant insertions, deletions, and updates, as well as operations based on the ranks of data items, such as Extract (j), which simultaneously selects and deletes the jth smallest data item. All these operations can be performed without ever interrupting the pipelining of responses coming from the machine, and the resulting machine has the same interval time and latency time performance as the original design, to within constant factors.

Optimal algorithms for sorting on parallel CREW (concurrent read, exclusive write) and EREW (exclusive read, exclusive write) versions of the pointer machine model are presented. Intuitively, these methods can be viewed as being based on the use of linked lists rather than arrays (the usual parallel data structure). It is shown how to exploit the 'locality' of the approach to solve a problem with applications to database querying and logic programming (set-expression evaluation) in O(log n) time using O(n) processors.>

Article Free Access Share on Intersecting line segments in parallel with an output-sensitive number of processors Author: M. T. Goodrich Department of Computer Science, The Johns Hopkins University, Baltimore, MD Department of Computer Science, The Johns Hopkins University, Baltimore, MDView Profile Authors Info & Claims SPAA '89: Proceedings of the first annual ACM symposium on Parallel algorithms and architecturesMarch 1989 Pages 127–137https://doi.org/10.1145/72935.72950Published:01 March 1989Publication History 19citation329DownloadsMetricsTotal Citations19Total Downloads329Last 12 Months16Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Techniques for parallel divide-and-conquer are presented, resulting in improved parallel algorithms for a number of problems. The problems for which improved algorithms are given include segment intersection detection, trapezoidal decomposition, and planar point location. Efficient parallel algorithms are algo given for fractional cascading, three-dimensional maxima, two-set dominance counting, and visibility from a point. All of the algorithms presented run in $O(\log n)$ time with either a linear or a sublinear number of processors in the CREW PRAM model.

In this paper we give parallel algorithms for a number of problems defined on polygons and point sets. All of our algorithms have optimal T(n) * P(n) products, where T(n) is the time complexity and P(n) is the number of processors used, and are for the EREW PRAM or CREW PRAM models. In addition, our algorithms provide parallel analogues to well known phenomena from sequential computational geometry, such as the fact that problems for polygons can oftentimes be solved more efficiently that point-set problems, and that one can solve nearest-neighbor problems without explicitly constructing a Voronoi diagram.

We present techniques for parallel divide-and-conquer, resulting in improved parallel algorithms for a number of problems. The problems for which we give improved algorithms include intersection detection, trapezoidal decomposition (hence, polygon triangulation), and planar point location (hence, Voronoi diagram construction). We also give efficient parallel algorithms for fractional cascading, 3-dimensional maxima, 2-set dominance counting, and visibility from a point. All of our algorithms run in O(log n) time with either a linear or sub-linear number of processors in the CREW PRAM model.

We present techniques which result in improved parallel algorithms for a number of problems whose efficient sequential algorithms use the plane-sweeping paradigm. The problems for which we give improved algorithms include intersection detection, trapezoidal decomposition, triangulation, and planar point location. Our technique can be used to improve on the previous time bound while keeping the space and processor bounds the same, or improve on the previous space bound while keeping the time and processor bounds the same. We also give efficient parallel algorithms for visibility from a point, 3-dimensional maxima, multiple range-counting, and rectilinear segment intersection counting. We never use the AKS sorting network in any of our algorithms.