Loading...
Please wait, while we are loading the content...
Similar Documents
Fast parallel algorithms that compute transitive closure of a fuzzy relation
| Content Provider | NASA Technical Reports Server (NTRS) |
|---|---|
| Author | Kreinovich, Vladik YA |
| Copyright Year | 1993 |
| Description | The notion of a transitive closure of a fuzzy relation is very useful for clustering in pattern recognition, for fuzzy databases, etc. The original algorithm proposed by L. Zadeh (1971) requires the computation time O(n(sup 4)), where n is the number of elements in the relation. In 1974, J. C. Dunn proposed a O(n(sup 2)) algorithm. Since we must compute n(n-1)/2 different values s(a, b) (a not equal to b) that represent the fuzzy relation, and we need at least one computational step to compute each of these values, we cannot compute all of them in less than O(n(sup 2)) steps. So, Dunn's algorithm is in this sense optimal. For small n, it is ok. However, for big n (e.g., for big databases), it is still a lot, so it would be desirable to decrease the computation time (this problem was formulated by J. Bezdek). Since this decrease cannot be done on a sequential computer, the only way to do it is to use a computer with several processors working in parallel. We show that on a parallel computer, transitive closure can be computed in time O((log(sub 2)(n))2). |
| File Size | 576292 |
| Page Count | 9 |
| File Format | |
| Alternate Webpage(s) | http://archive.org/details/NASA_NTRS_Archive_19930016001 |
| Archival Resource Key | ark:/13960/t72v7g139 |
| Language | English |
| Publisher Date | 1993-01-01 |
| Access Restriction | Open |
| Subject Keyword | Cybernetics Computation Parallel Computers Closure Law Pattern Recognition Parallel Processing Computers Data Bases Fuzzy Systems Ntrs Nasa Technical Reports Server (ntrs) Nasa Technical Reports Server Aerodynamics Aircraft Aerospace Engineering Aerospace Aeronautic Space Science |
| Content Type | Text |
| Resource Type | Technical Report |
