Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 45 Issue 6, Nov. 1998

An optimal algorithm for approximate nearest neighbor searching fixed dimensions
Sunil Arya, David M. Mount, Nathan S. Netanyahu, Ruth Silverman, Angela Y. Wu
Pages: 891-923
DOI: 10.1145/293347.293348
Consider a set of S of n data points in real d-dimensional space, Rd, where distances are measured using any Minkowski metric. In nearest neighbor searching, we preprocess...

Electrostatic fields without singularities: theory, algorithms and error analysis
Marco Pellegrini
Pages: 924-964
DOI: 10.1145/293347.293349
The following problems that arise in the computation of electrostatic forces and in the Boundary Element Method are considered. Given two convex interior-disjoint polyhedra in 3-space endowed with a volume charge density which is a polynomial in...

Private information retrieval
Benny Chor, Eyal Kushilevitz, Oded Goldreich, Madhu Sudan
Pages: 965-981
DOI: 10.1145/293347.293350
Publicly accessible databases are an indispensable resource for retrieving up-to-date information. But they also pose a significant risk to the privacy of the user, since a curious database operator can follow the user's queries and infer what...

Efficient noise-tolerant learning from statistical queries
Michael Kearns
Pages: 983-1006
DOI: 10.1145/293347.293351
In this paper, we study the problem of learning in the presence of classification noise in the probabilistic learning model of Valiant and its variants. In order to identify the class of “robust” learning algorithms in the most...

Ordered chaining calculi for first-order theories of transitive relations
Leo Bachmair, Harald Ganzinger
Pages: 1007-1049
DOI: 10.1145/293347.293352
We propose inference systems for binary relations that satisfy composition laws such as transitivity. Our inference mechanisms are based on standard techniques from term rewriting and represent a refinement of chaining methods as they are used...

On parallel evaluation of game trees
Richard M. Karp, Yangun Zhang
Pages: 1050-1075
DOI: 10.1145/293347.293353
A class of parallel algorithms for evaluating game trees is presented. These algorithms parallelize a standard sequential algorithm for evaluating AND/OR trees and the &agr;-&bgr; pruning procedure for evaluating MIN/MAX trees. It is shown that,...