456
M. N. Bojnordi and P. Behnam
Corpus
TF-IDF Matrix
Clustered Data
Results
K-means
c 00 ... c 0M
c k0 ... c kM
...
...
d 00 ... d 0M
d 10 ... d 1M
d N0 ... d NM
...
...
T 00 ... T 0P
T N0 ... T NP
...
...
F 00 ... F 0M
F P0 ... F PM
...
...
Fig. 9.19 TF-IDF text mining with k-means algorithm
9.5.3 Data Clustering with Rank-Order Filters
MISC proposes to leverage rank-order filtering to enable energy-efficient data clustering within memory arrays. Rank-order filters are nonlinear digital components
widely used in signal and image processing. They are mainly used to filter out
noise from input signals. A general rank-order filter may be characterized by the
number of input signals (N) and an index (i) that determines which input signal
must appear at the output. The filter needs to send the ith largest (or smallest)
input signal to the output. A median filter may be viewed as a particular case
of the rank-order filter where i is set to N/2. The median filter may be used to
compute the cluster centroids for the k-medians algorithm. However, rank-order
median filters are memory and compute intensive operations. Numerous hardware
and software optimizations have been proposed for median filters in the literature,
which pursue two different approaches. The first approach is word-based search that
sequentially examines all of the objects to find the median. The second approach is
based on a bit-serial process to computes the majority of selected bits from all of
the objects in parallel. When applied to large-scale datasets, both approaches suffer
from excessive memory traffic and high data movement costs.
9.5.3.1 Bit-Serial Median Filter
MISC relies on the bit-serial median filter for clustering. In principle, one can find
the median of a list by sorting the data points. This technique, however, is complex
and inefficient. In 1981, Danielsson [117] proposed the first bit-serial algorithm for
median filtering that eliminates the need for sorting. Thereafter, numerous hardware
and software implementations of the bit-serial median filter have been examined that
rely on the majority function. Notice that the majority function defines a mapping
from N binary data to a single binary output. The output is 0 if N/2 or more inputs
are 0; otherwise, it is set to 1.
Figure 9.20 shows four major steps of the bit-serial algorithm to find the median
of five numbers. Initially, all numbers are represented in their binary forms (1).
Starting from the most significant bit (MSB) to the least significant bit (LSB), the
M. N. Bojnordi and P. Behnam
Corpus
TF-IDF Matrix
Clustered Data
Results
K-means
c 00 ... c 0M
c k0 ... c kM
...
...
d 00 ... d 0M
d 10 ... d 1M
d N0 ... d NM
...
...
T 00 ... T 0P
T N0 ... T NP
...
...
F 00 ... F 0M
F P0 ... F PM
...
...
Fig. 9.19 TF-IDF text mining with k-means algorithm
9.5.3 Data Clustering with Rank-Order Filters
MISC proposes to leverage rank-order filtering to enable energy-efficient data clustering within memory arrays. Rank-order filters are nonlinear digital components
widely used in signal and image processing. They are mainly used to filter out
noise from input signals. A general rank-order filter may be characterized by the
number of input signals (N) and an index (i) that determines which input signal
must appear at the output. The filter needs to send the ith largest (or smallest)
input signal to the output. A median filter may be viewed as a particular case
of the rank-order filter where i is set to N/2. The median filter may be used to
compute the cluster centroids for the k-medians algorithm. However, rank-order
median filters are memory and compute intensive operations. Numerous hardware
and software optimizations have been proposed for median filters in the literature,
which pursue two different approaches. The first approach is word-based search that
sequentially examines all of the objects to find the median. The second approach is
based on a bit-serial process to computes the majority of selected bits from all of
the objects in parallel. When applied to large-scale datasets, both approaches suffer
from excessive memory traffic and high data movement costs.
9.5.3.1 Bit-Serial Median Filter
MISC relies on the bit-serial median filter for clustering. In principle, one can find
the median of a list by sorting the data points. This technique, however, is complex
and inefficient. In 1981, Danielsson [117] proposed the first bit-serial algorithm for
median filtering that eliminates the need for sorting. Thereafter, numerous hardware
and software implementations of the bit-serial median filter have been examined that
rely on the majority function. Notice that the majority function defines a mapping
from N binary data to a single binary output. The output is 0 if N/2 or more inputs
are 0; otherwise, it is set to 1.
Figure 9.20 shows four major steps of the bit-serial algorithm to find the median
of five numbers. Initially, all numbers are represented in their binary forms (1).
Starting from the most significant bit (MSB) to the least significant bit (LSB), the