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

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.