Abstract

A directed graph is considered for organization of a knowledge base for neural, associative, model-based, and other advanced processors. Its ability to self-organize itself, delete old information, and add new information and its many interconnections make it most suitable for optical realization and use in advanced neural and adaptive optical processors. An alphanumeric image space example is used as a case study, and an optical processor architecture to achieve this with impressive performance is discussed.

© 1988 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. Technical Digest, Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1985).
  2. Technical Digest, Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987).
  3. N. Christofides, Graph Theory: An Algorithmic Approach (Academic, New York, 1975).
  4. E. Baranoski, D. Casasent, “A Directed Graph Optical Processor,” Proc. Soc. Photo-Opt. Instrum. Eng. 752, 58 (1987).
  5. P. H. Swain, H. Hauska, “The Decision Tree Classifier: Design and Potential,” IEEE Trans. Geosci. Electron. GE-15, 142 (1977).
  6. E. M. Rounds, “A Combined Nonparametric Approach to Feature Selection and Binary Decision Tree Design,” Pattern Recognition 12, 313 (1980).
    [CrossRef]
  7. I. K. Sethi, G. P. R. Sarvarayudo, “Hierarchical Classifier Design Using Mutual Information,” IEEE Trans. Pattern Anal. Machine Intell. PAMI-4, 441 (1982).
    [CrossRef]
  8. D. A. Jared, D. J. Ennis, “Learned Pattern Recognition Using Synthetic-Discriminant-Functions,” Proc. Soc. Photo-Opt. Instrum. Eng. 638, 91 (1986).
  9. H. S. Stone, P. Sipala, “The Average Complexity of Depth-First Search with Backtracking and Cutoff,” IBM J. Res. Dev. 30, 242 (1986).
    [CrossRef]
  10. S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, “Optimization by Simulated Annealing,” Science 220, 671 (1983).
    [CrossRef] [PubMed]
  11. J. M. Wozencraft, I. M. Jacobs, Principles of Communication Engineering (Wiley, New York, 1965).
  12. Special Issue on Optical Computing, Proc. IEEE 72 (July1984).
  13. J. W. Goodman, F. J. Leonberger, S-Y. Kung, R. A. Athale, “Optical Interconnections for VLSI Systems,” Proc., IEEE 72, 850 (1984).
    [CrossRef]
  14. Special Issue on Optical Interconnections, Opt. Eng. 25, No. 10 (Oct.1986).

1987 (1)

E. Baranoski, D. Casasent, “A Directed Graph Optical Processor,” Proc. Soc. Photo-Opt. Instrum. Eng. 752, 58 (1987).

1986 (3)

D. A. Jared, D. J. Ennis, “Learned Pattern Recognition Using Synthetic-Discriminant-Functions,” Proc. Soc. Photo-Opt. Instrum. Eng. 638, 91 (1986).

H. S. Stone, P. Sipala, “The Average Complexity of Depth-First Search with Backtracking and Cutoff,” IBM J. Res. Dev. 30, 242 (1986).
[CrossRef]

Special Issue on Optical Interconnections, Opt. Eng. 25, No. 10 (Oct.1986).

1984 (2)

Special Issue on Optical Computing, Proc. IEEE 72 (July1984).

J. W. Goodman, F. J. Leonberger, S-Y. Kung, R. A. Athale, “Optical Interconnections for VLSI Systems,” Proc., IEEE 72, 850 (1984).
[CrossRef]

1983 (1)

S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, “Optimization by Simulated Annealing,” Science 220, 671 (1983).
[CrossRef] [PubMed]

1982 (1)

I. K. Sethi, G. P. R. Sarvarayudo, “Hierarchical Classifier Design Using Mutual Information,” IEEE Trans. Pattern Anal. Machine Intell. PAMI-4, 441 (1982).
[CrossRef]

1980 (1)

E. M. Rounds, “A Combined Nonparametric Approach to Feature Selection and Binary Decision Tree Design,” Pattern Recognition 12, 313 (1980).
[CrossRef]

1977 (1)

P. H. Swain, H. Hauska, “The Decision Tree Classifier: Design and Potential,” IEEE Trans. Geosci. Electron. GE-15, 142 (1977).

Athale, R. A.

J. W. Goodman, F. J. Leonberger, S-Y. Kung, R. A. Athale, “Optical Interconnections for VLSI Systems,” Proc., IEEE 72, 850 (1984).
[CrossRef]

Baranoski, E.

E. Baranoski, D. Casasent, “A Directed Graph Optical Processor,” Proc. Soc. Photo-Opt. Instrum. Eng. 752, 58 (1987).

Casasent, D.

E. Baranoski, D. Casasent, “A Directed Graph Optical Processor,” Proc. Soc. Photo-Opt. Instrum. Eng. 752, 58 (1987).

Christofides, N.

N. Christofides, Graph Theory: An Algorithmic Approach (Academic, New York, 1975).

Ennis, D. J.

D. A. Jared, D. J. Ennis, “Learned Pattern Recognition Using Synthetic-Discriminant-Functions,” Proc. Soc. Photo-Opt. Instrum. Eng. 638, 91 (1986).

Gelatt, C. D.

S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, “Optimization by Simulated Annealing,” Science 220, 671 (1983).
[CrossRef] [PubMed]

Goodman, J. W.

J. W. Goodman, F. J. Leonberger, S-Y. Kung, R. A. Athale, “Optical Interconnections for VLSI Systems,” Proc., IEEE 72, 850 (1984).
[CrossRef]

Hauska, H.

P. H. Swain, H. Hauska, “The Decision Tree Classifier: Design and Potential,” IEEE Trans. Geosci. Electron. GE-15, 142 (1977).

Jacobs, I. M.

J. M. Wozencraft, I. M. Jacobs, Principles of Communication Engineering (Wiley, New York, 1965).

Jared, D. A.

D. A. Jared, D. J. Ennis, “Learned Pattern Recognition Using Synthetic-Discriminant-Functions,” Proc. Soc. Photo-Opt. Instrum. Eng. 638, 91 (1986).

Kirkpatrick, S.

S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, “Optimization by Simulated Annealing,” Science 220, 671 (1983).
[CrossRef] [PubMed]

Kung, S-Y.

J. W. Goodman, F. J. Leonberger, S-Y. Kung, R. A. Athale, “Optical Interconnections for VLSI Systems,” Proc., IEEE 72, 850 (1984).
[CrossRef]

Leonberger, F. J.

J. W. Goodman, F. J. Leonberger, S-Y. Kung, R. A. Athale, “Optical Interconnections for VLSI Systems,” Proc., IEEE 72, 850 (1984).
[CrossRef]

Rounds, E. M.

E. M. Rounds, “A Combined Nonparametric Approach to Feature Selection and Binary Decision Tree Design,” Pattern Recognition 12, 313 (1980).
[CrossRef]

Sarvarayudo, G. P. R.

I. K. Sethi, G. P. R. Sarvarayudo, “Hierarchical Classifier Design Using Mutual Information,” IEEE Trans. Pattern Anal. Machine Intell. PAMI-4, 441 (1982).
[CrossRef]

Sethi, I. K.

I. K. Sethi, G. P. R. Sarvarayudo, “Hierarchical Classifier Design Using Mutual Information,” IEEE Trans. Pattern Anal. Machine Intell. PAMI-4, 441 (1982).
[CrossRef]

Sipala, P.

H. S. Stone, P. Sipala, “The Average Complexity of Depth-First Search with Backtracking and Cutoff,” IBM J. Res. Dev. 30, 242 (1986).
[CrossRef]

Stone, H. S.

H. S. Stone, P. Sipala, “The Average Complexity of Depth-First Search with Backtracking and Cutoff,” IBM J. Res. Dev. 30, 242 (1986).
[CrossRef]

Swain, P. H.

P. H. Swain, H. Hauska, “The Decision Tree Classifier: Design and Potential,” IEEE Trans. Geosci. Electron. GE-15, 142 (1977).

Vecchi, M. P.

S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, “Optimization by Simulated Annealing,” Science 220, 671 (1983).
[CrossRef] [PubMed]

Wozencraft, J. M.

J. M. Wozencraft, I. M. Jacobs, Principles of Communication Engineering (Wiley, New York, 1965).

IBM J. Res. Dev. (1)

H. S. Stone, P. Sipala, “The Average Complexity of Depth-First Search with Backtracking and Cutoff,” IBM J. Res. Dev. 30, 242 (1986).
[CrossRef]

IEEE Trans. Geosci. Electron. (1)

P. H. Swain, H. Hauska, “The Decision Tree Classifier: Design and Potential,” IEEE Trans. Geosci. Electron. GE-15, 142 (1977).

IEEE Trans. Pattern Anal. Machine Intell. (1)

I. K. Sethi, G. P. R. Sarvarayudo, “Hierarchical Classifier Design Using Mutual Information,” IEEE Trans. Pattern Anal. Machine Intell. PAMI-4, 441 (1982).
[CrossRef]

Opt. Eng. (1)

Special Issue on Optical Interconnections, Opt. Eng. 25, No. 10 (Oct.1986).

Pattern Recognition (1)

E. M. Rounds, “A Combined Nonparametric Approach to Feature Selection and Binary Decision Tree Design,” Pattern Recognition 12, 313 (1980).
[CrossRef]

Proc. IEEE (1)

Special Issue on Optical Computing, Proc. IEEE 72 (July1984).

Proc. Soc. Photo-Opt. Instrum. Eng. (2)

E. Baranoski, D. Casasent, “A Directed Graph Optical Processor,” Proc. Soc. Photo-Opt. Instrum. Eng. 752, 58 (1987).

D. A. Jared, D. J. Ennis, “Learned Pattern Recognition Using Synthetic-Discriminant-Functions,” Proc. Soc. Photo-Opt. Instrum. Eng. 638, 91 (1986).

Proc., IEEE (1)

J. W. Goodman, F. J. Leonberger, S-Y. Kung, R. A. Athale, “Optical Interconnections for VLSI Systems,” Proc., IEEE 72, 850 (1984).
[CrossRef]

Science (1)

S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, “Optimization by Simulated Annealing,” Science 220, 671 (1983).
[CrossRef] [PubMed]

Other (4)

J. M. Wozencraft, I. M. Jacobs, Principles of Communication Engineering (Wiley, New York, 1965).

Technical Digest, Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1985).

Technical Digest, Topical Meeting on Optical Computing (Optical Society of America, Washington, DC, 1987).

N. Christofides, Graph Theory: An Algorithmic Approach (Academic, New York, 1975).

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (7)

Fig. 1
Fig. 1

Directed graph example.

Fig. 2
Fig. 2

Example of an adjacency matrix.

Fig. 3
Fig. 3

Data vectors used for the M = 4 meta-vertices in our example. They correspond to counts of the number of pixels in each quadrant of the input data image vector.

Fig. 4
Fig. 4

Directed graph for the first five characters in the alphabet.

Fig. 5
Fig. 5

Directed graph when F the sixth letter of the alphabet is added to the knowledge base.

Fig. 6
Fig. 6

Multichannel space-integrating parallel optical directed graph processor.

Fig. 7
Fig. 7

Multichannel time-integrating parallel directed graph processor.

Tables (2)

Tables Icon

Table I Directed Graph Terminology

Tables Icon

Table II Adjacency Matrix A for the N = 62 Node Alphanumeric Case Study Directed Graph

Equations (2)

Equations on this page are rendered with MathJax. Learn more.

A n + 1 = A n ( I A 1 ) ,
search time = O [ ( 1 / γ ) T log M N ] = O ( T log M γ N ) ,

Metrics