Performance measurement and data base design
Alfonso P. Cardenas, Larry F. Bowman, et al.
ACM Annual Conference 1975
We present a randomized parallel algorithm for term matching. Let n be the number of nodes of the directed acyclic graphs (dags) representing the terms to be matched. Then our algorithm uses O(log2 n) parallel time and M(n) processors, where M(n) is the complexity of n×n matrix multiplication. The randomized algorithm is of the Las Vegas type, that is, the answer is always correct, although with small probability the algorithm might fail to produce an answer. The number of processors is a significant improvement over previously known bounds. Under various syntactic restrictions on the form of the input dags, only O(n2) processors are required in order to achieve deterministic O(log2n) parallel time. Furthermore, we reduce directed graph reachability to term matching using constant parallel time and O(n2) processors. This is evidence that no deterministic algorithm can significantly beat the processor bound of our randomized algorithm.
Alfonso P. Cardenas, Larry F. Bowman, et al.
ACM Annual Conference 1975
Elliot Linzer, M. Vetterli
Computing
Thomas M. Cheng
IT Professional
Limin Hu
IEEE/ACM Transactions on Networking