Content：
English

Chinese(TW)
Finding clusters in data streams is a popular application in data mining fields. For example, a web site may cluster customer shopping information with some criteria so that the recommendation system may suggest suitable products to each individual customer.
CDSTree(Cell Dimension Tree for Streams) proposed by Sun et al[1], is an effective data structure to finding clusters in data streams using a cell based algorithm.
The basic idea of the cellbased algorithms is to:
The input data space is spanned by two data streams corresponding to a two dimensional cell array. The cell array is a square array with the maximum array size, 10×10. Each cell may represent different number of data for each individual dimension. The objective of your program is to construct the CDSTrees according to the input parameters as well as to print out the CDSTrees by the level order.
The input data file consists of NS sets of data, where 1 ≤ NS ≤ 10. Each set of data is defined by exact 5 consecutive lines. The first line defines the number of cells, NC, for both two dimension, and 1 ≤ NC ≤ 10. The 2nd and 3rd lines give the number of data, ND, for each individual cell in the dimension A1 and the dimension A2 respectively, where 1 ≤ ND ≤ 10. The NDs are separated by a blank space according to the dimension index in ascending order. The 4th and 5th lines are data streams for dimension A1 and A2 respectively. Each data stream consists of digits, 0 or 1, with maximum data length, MAX D L, where NC ≤ MAX D L ≤ 100. The digits of the input data stream are separated by a blank space.
For example, an input file with only one set of data is illustrated in the figure 2 and the corresponding twodimensional cell array is depicted in the figure 1:
The first line defines NC=4, that means the input data space will be represent in a 4 × 4 cell array.
The second line assigns the NDs for the cell indexes 1, 2, 3, 4 of the dimension A1 to 4, 3, 1, and 2.
The third line assigns the NDs for the cell indexes 1, 2, 3, 4 of the dimension A2 to 2, 1, 2, and 5.
The 4th line defines the data stream of dimension A1: 0101111110
The 5th line defines the data stream of dimension A2: 1110010001
Your program should read in data according to the cell array information in the first three lines of each data set and generate the corresponding CDS Trees. An example of the CDSTrees is depicted in the figure 3.
A CDSTree consists of 3 kinds of nodes:
Only those coordinates of nonzero NoPs would be inserted into CDS Tree. Mid nodes and root node are constructed based on the inserted leaf nodes.
Finally your program should print out all CDSTrees using the readin order of the corresponding data sets. All printouts of the CDSTrees are separated by a line blank. For each CDSTree, your program should use the level order to print out the RootNode, all MidNodes, and all LeafNodes in sequence one node per line consecutively as the Sample Output. For each node your program should separate the indexes of the dimension or the NoP by one space blank.
Input：
Output：
Sample Input：
4 4 3 1 2 2 1 2 5 0 1 0 1 1 1 1 1 1 0 1 1 1 0 0 1 0 0 0 1
Sample Output ：
1 2 3 4 1 2 3 3 4 4 4 1 1 3 1 2 1 1 3 1 2 3 1 2 4 3 3 4 1 4 4 2
Hint
：
Author
：
C 
C++ 
JAVA 
PASCAL 

51176. rabbit125 (0ms, 782KB, 2133B) 
