73 citations · 634 across the 97 of their papers we have counts for
10 papers · 1 filter
Nonadaptive Mastermind Algorithms for String and Vector Databases, with Case Studies
Arthur U. Asuncion, Michael T. Goodrich
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 rating…
Spin-the-bottle Sort and Annealing Sort: Oblivious Sorting via Round-robin Random Comparisons
Michael T. Goodrich
We study sorting algorithms based on randomized round-robin comparisons. Specifically, we study Spin-the-bottle sort, where comparisons are unrestricted, and Annealing sort, where…
Priority Range Trees
Michael T. Goodrich, Darren Strash
We describe a data structure, called a priority range tree, which accommodates fast orthogonal range reporting queries on prioritized points. Let be a set of points in the…
Privacy-Preserving Data-Oblivious Geometric Algorithms for Geographic Data
David Eppstein, Michael T. Goodrich, Roberto Tamassia
We give efficient data-oblivious algorithms for several fundamental geometric problems that are relevant to geographic information systems, including planar convex hulls and all-ne…
Extended h-Index Parameterized Data Structures for Computing Dynamic Subgraph Statistics
David Eppstein, Michael T. Goodrich, Darren Strash +1
We present techniques for maintaining subgraph frequencies in a dynamic graph, using data structures that are parameterized in terms of h, the h-index of the graph. Our methods ext…
Drawing Trees with Perfect Angular Resolution and Polynomial Area
Christian A. Duncan, David Eppstein, Michael T. Goodrich +2
We study methods for drawing trees with perfect angular resolution, i.e., with angles at each node v equal to 2π/d(v). We show: 1. Any unordered tree has a crossing-free straight-l…
Privacy-Preserving Access of Outsourced Data via Oblivious RAM Simulation
Michael T. Goodrich, Michael Mitzenmacher
Suppose a client, Alice, has outsourced her data to an external storage provider, Bob, because he has capacity for her massive data set, of size n, whereas her private storage is m…
Cloning Voronoi Diagrams via Retroactive Data Structures
Matthew T. Dickerson, David Eppstein, Michael T. Goodrich
We address the problem of replicating a Voronoi diagram of a planar point set by making proximity queries, which are of three possible (in decreasing order of informatio…
Round-Trip Voronoi Diagrams and Doubling Density in Geographic Networks
Matthew T. Dickerson, Michael T. Goodrich, Thomas D. Dickerson
The round-trip distance function on a geographic network (such as a road network, flight network, or utility distribution grid) defines the "distance" from a single vertex to a pai…
Simulating Parallel Algorithms in the MapReduce Framework with Applications to Parallel Computational Geometry
Michael T. Goodrich
In this paper, we describe efficient MapReduce simulations of parallel algorithms specified in the BSP and PRAM models. We also provide some applications of these simulation result…