Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 48 Issue 5, September 2001

A model of multimedia information retrieval
Carlo Meghini, Fabrizio Sebastiani, Umberto Straccia
Pages: 909-970
DOI: 10.1145/502102.502103
Research on multimedia information retrieval (MIR) has recently witnessed a booming interest. A prominent feature of this research trend is its simultaneous but independent materialization within several fields of computer science. The resulting...

Static analysis in datalog extensions
Alon Y. Halevy, Inderpal Singh Mumick, Yehoshua Sagiv, Oded Shmueli
Pages: 971-1012
DOI: 10.1145/502102.502104
We consider the problems of containment, equivalence, satisfiability and query-reachability for datalog programs with negation. These problems are important for optimizing datalog programs. We show that both query-reachability and satisfiability are...

Improved implementations of binary universal operations
Hagit Attiya, Eyal Dagan
Pages: 1013-1037
DOI: 10.1145/502102.502105
We present an algorithm for implementing binary operations (of any type) from unary load-linked (LL) and store-conditional (SC) operations. The performance of the algorithm is evaluated according to its sensitivity, measuring the...

Interval arithmetic: From principles to implementation
T. Hickey, Q. Ju, M. H. Van Emden
Pages: 1038-1068
DOI: 10.1145/502102.502106
We start with a mathematical definition of a real interval as a closed, connected set of reals. Interval arithmetic operations (addition, subtraction, multiplication, and division) are likewise defined mathematically and we provide algorithms for...

A unified approach to approximating resource allocation and scheduling
Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph (Seffi) Naor, Baruch Schieber
Pages: 1069-1090
DOI: 10.1145/502102.502107
We present a general framework for solving resource allocation and scheduling problems. Given a resource of fixed size, we present algorithms that approximate the maximum throughput or the minimum loss by a constant factor. Our approximation factors...