Daniel H. Greene

FOCS Conference 1994 Conference Paper

Multi-Index Hashing for Information Retrieval

• Daniel H. Greene
• Michal Parnas
• F. Frances Yao

We describe a technique for building hash indices for a large dictionary of strings. This technique permits robust retrieval of strings from the dictionary even when the query pattern has a significant number of errors. This technique is closely related to the classical Turan problem for hypergraphs. We propose a general method of multi-index construction by generalizing certain Turan hypergraphs. We also develop an accompanying theory for analyzing such hashing schemes. The resulting algorithms have been implemented and can be applied to a wide variety of recognition and retrieval problems. >

STOC Conference 1993 Conference Paper

On-line algorithms for cache sharing

• Marshall W. Bern
• Daniel H. Greene
• Arvind Raghunathan

STOC Conference 1990 Conference Paper

Online Algorithms for Locating Checkpoints

• Marshall W. Bern
• Daniel H. Greene
• Arvind Raghunathan
• Madhu Sudan 0001

STOC Conference 1988 Conference Paper

Optimal Algorithms for Approximate Clustering

• Tomás Feder
• Daniel H. Greene

In a clustering problem, the aim is to partition a given set of n points in d -dimensional space into k groups, called clusters, so that points within each cluster are near each other. Two objective functions frequently used to measure the performance of a clustering algorithm are, for any L 4 metric, (a) the maximum distance between pairs of points in the same cluster, and (b) the maximum distance between points in each cluster and a chosen cluster center; we refer to either measure as the cluster size. We show that one cannot approximate the optimal cluster size for a fixed number of clusters within a factor close to 2 in polynomial time, for two or more dimensions, unless P=NP. We also present an algorithm that achieves this factor of 2 in time Ο ( n log k ), and show that this running time is optimal in the algebraic decision tree model. For a fixed cluster size, on the other hand, we give a polynomial time approximation scheme that estimates the optimal number of clusters under the second measure of cluster size within factors arbitrarily close to 1. Our approach is extended to provide approximation algorithms for the restricted centers, suppliers, and weighted suppliers problems that run in optimal Ο ( n log k ) time and achieve optimal or nearly optimal approximation bounds.

FOCS Conference 1986 Conference Paper

Finite-Resolution Computational Geometry

• Daniel H. Greene
• F. Frances Yao

Geometric algorithms are usually designed with continuous parameters in mind. When the underlying geometric space is intrinsically discrete, as is the case for computer graphics problems, such algorithms are apt to give invalid solutions if properties of a finite-resolution space are not taken into account. In this paper we discuss an approach for transforming geometric concepts and algorithms from the continuous domain to the discrete domain. As an example we consider the discrete version of the problem of finding all intersections of a collection of line segments. We formulate criteria for a satisfactory solution to this problem, and design an interface between the continuous domain and the discrete domain which supports certain invariants. This interface enables us to obtain a satisfactory solution by using plane-sweep and a variant of the continued fraction algorithm.