Databases Reference
In-Depth Information
3.3 GN Complexity Estimation
An estimate of the computational complexity of the recognition procedure of
a GN implementation follows. A Big-O analysis of the bias array update phase
of the GN procedure was performed. Because the core recognition function in
the GN procedure is the bias array update of each GN, a limited analysis is
justified. The pseudocode for the bias array update procedure for each neuron
is as follows:
Algorithm 1
Bias Array Update Procedure for a GN
1:
input.l ← leftGN
2:
input.r ← rightGN
3:
for all
σ
l,r
∈ σ
do
4:
if
input
l,r
≡ σ
l,r
then
5:
return
σ
l,r
6:
exit FOR
7:
else
8:
if
σ
l,r
is last entry
then
9:
σ
l,r
+ 1 = input
l,r
10:
else
11:
continue
12:
end if
13:
end if
14:
end for
Consider the bias array update as a function f (σ) = T
f(σ)
(N). Algorithm 1
clearly demonstrates that the function implements a linear search mechanism
for each input pattern, and thus its complexity is O (N). We can deduce
that T
f(σ)
(N) = O (N). By implementing a simple linear search technique to
identify recall or introduce new patterns into the network, the Big-O analysis
proves that GN offers a low complexity recognition process.
A storage capacity analysis provides another complexity estimate for the
GN implementation. This analysis estimates the maximum size of the bias
array for each input pattern stored in the GN network. For a two-dimensional
GN structure, the maximum number of bias entries is determined by the
number of possible combinations of (left, right) entries σ
ent
, obtained from
adjacent neurons. The number of possible combinations is directly related to
the number of rows (or pattern elements) in the composition. In addition, the
maximum bias array size for each neuron depends on its position. For a given
number of rows, n
row
, there are two possible values for the maximum bias
array size, σ
max
of a neuron:
