Social networks and discovery in the enterprise (SaND)
Inbal Ronen, Elad Shahar, et al.
SIGIR 2009
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.
Inbal Ronen, Elad Shahar, et al.
SIGIR 2009
G. Ramalingam
Theoretical Computer Science
Hans Becker, Frank Schmidt, et al.
Photomask and Next-Generation Lithography Mask Technology 2004
Oliver Bodemer
IBM J. Res. Dev