Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 57 Issue 1, November 2009

Space-time tradeoffs for approximate nearest neighbor searching
Sunil Arya, Theocharis Malamatos, David M. Mount
Article No.: 1
DOI: 10.1145/1613676.1613677

Nearest neighbor searching is the problem of preprocessing a set of n point points in d-dimensional space so that, given any query point q, it is possible to report the closest point to q rapidly. In approximate nearest...

On the union of fat tetrahedra in three dimensions
Esther Ezra, Micha Sharir
Article No.: 2
DOI: 10.1145/1613676.1613678

We show that the combinatorial complexity of the union of n “fat” tetrahedra in 3-space (i.e., tetrahedra all of whose solid angles are at least some fixed constant) of arbitrary sizes, is O(n2+ϵ),...

Efficient and secure authenticated key exchange using weak passwords
Jonathan Katz, Rafail Ostrovsky, Moti Yung
Article No.: 3
DOI: 10.1145/1613676.1613679

Mutual authentication and authenticated key exchange are fundamental techniques for enabling secure communication over public, insecure networks. It is well known how to design secure protocols for achieving these goals when parties share...

Compressing and indexing labeled trees, with applications
Paolo Ferragina, Fabrizio Luccio, Giovanni Manzini, S. Muthukrishnan
Article No.: 4
DOI: 10.1145/1613676.1613680

Consider an ordered, static tree T where each node has a label from alphabet Σ. Tree T may be of arbitrary degree and shape. Our goal is designing a compressed storage scheme of T that supports basic navigational...