CN104573082B - Space small documents distributed data storage method and system based on access log information - Google Patents

Abstract

The present invention provides a small space file data distributed storage method and system based on access log information, including dividing the small space file data set into frequently accessed subsets and non-frequently accessed subsets, and extracting frequently accessed small space file data subsets Access sequence, calculate the correlation degree of each frequently accessed small space file data in sections, and form an association matrix with the correlation degree values of each frequently accessed small space file data; after the size conversion of each element value in the association matrix Use the RCM sorting algorithm to rearrange the output, use the local approximation search method to find the best combination for the rearranged correlation matrix, use the best combination to store the data of frequently accessed small files in a distributed manner, and use the best combination to store the data of frequently accessed small files File data is stored separately according to the adjacent relationship of spatial position. The invention improves the parallel access performance of small space file data.

Description

Method and system for distributed storage of small spatial file data based on access log information

technical field

The invention belongs to the technical field of distributed storage of small spatial file data, and in particular relates to a new method and system for distributed storage of small spatial file data based on access log information.

Background technique

The storage and fast access of massive spatial information has always been an important problem that the spatial information service system tries to solve. Commonly used spatial information service systems such as the NASA Earth Observation System collect up to 2TB of data per day. The reasonable distribution and storage of these data is to obtain parallelism. Fast access becomes the key, and one of the important solutions is to improve data access efficiency by distributing data storage to achieve parallel access to data.

At present, typical distributed file storage systems mainly include GFS (Google file system), HDFS (Hadoop distributed file system) and Luster. However, the improvement in storage performance of these systems is mainly reflected in the storage and processing of large files. Such as GFS, its storage strategy is mainly to divide large files into fixed-length blocks (such as 64MB), and then store all blocks in different memories to improve the parallel access rate of data (references Ghemawat S, Gobioff H, Shun-Tak L. The Google file system. In: Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles (SOSP'03). Bolton Landing, New York: IEEE, 2003.1–15). Another typical storage technology, such as RAID (Redundant Array of Independent Disks), also divides each large data file into several data blocks and stores them on different disks to improve parallel access to the file.

Although the above distributed storage methods are effective for large file data, for small file data, the method of block storage is not adaptable because it cannot continue to be divided into blocks. The current general method is simply to store a single file on a single storage server. , so it is difficult to achieve parallel access to multiple small file data, and the I/O efficiency is not high.

Studies have shown that there are a large number of small file data in most systems at present. For example, 99% of the 13 million files of the National Energy Research Scientific Computing Center in the United States are smaller than 64M, and 44% of the files are smaller than 64K (reference Carns P, Lang S, Ross R, et al.. Small-file access in parallel file systems [C]. Parallel & Distributed Processing, 2009. IPDPS 2009. IEEE International Symposium On. IEEE, 2009: 1-11).

In fact, spatial information service systems based on the pyramid model, such as Google Earth, World Wind, etc., also store spatial data in the form of small files. World Wind divides the earth into tile data with different resolutions according to the pyramid model. Each tile data is saved as a file. The size of each tile data is fixed at 512×512 pixels, and the size of each tile file does not exceed 1MB ( References Boschetti L, Roy D P, Justice C O.Using NASA'sWorld Wind virtual globe for interactive internet visualization of the global MODIS burned area product.Int J Remote Sens,2008,29(11):3067–3072); GoogleEarth also uses The multi-resolution model stores spatial data, and the size of each data file does not exceed 64MB (reference Sample J T, Loup E. Tile-base geospatial information system: principles and practices. New York: Springer, 2010.23–200).

In short, the current distributed storage method for large file data is difficult to apply to the storage of small file data, and the optimization for small file data focuses on data access optimization (non-storage optimization, access optimization is client-oriented, and storage optimization is service-oriented) end), such as reducing the execution time of data-intensive applications (references J. Kim, A. Chandra, and J. B. Weissma. Using Data Accessibility for Resource Selection in Large-Scale Distributed Systems. IEEE Trans. Parallel Distributed Systems, vol. 20, no.6, pp.788-801, June 2009), or reduce the overhead of small file index information (references A.L.Chervenak, R.Schuler, M.Ripeanu, M.A.Amer, S.Bharathi, I.Foster, A Iamnitchi, and C. Kesselman. The Globus Replica Location Service: Design and Experience. IEEETrans. Parallel Distributed Systems, vol.20, no.9, pp.1260-1272, Sept.2009) etc. But in a distributed system, the performance of access latency is not only related to the access method, but also related to the data distribution storage mode. Therefore, the optimization problem of small file data has not been fundamentally resolved.

Contents of the invention

In view of the above problems, the present invention provides a method and system for distributed storage of small space file data based on access log information, which uses the access log information of small space file data to analyze the relationship between each small space file data, and based on this Distributed storage of small file data in order to improve the parallel access rate of small file data.

A method and system for distributed storage of small space file data based on access log information according to the present invention, the technical solution adopted is:

A distributed storage method for small space file data based on access log information, for any type of small space file data, the execution includes the following steps:

Step 1, divide the data set of small spatial files into frequently accessed subsets and non-frequently accessed subsets according to different access frequencies; including the following sub-steps,

Step 1.1, obtain the data access heat of small files in each space, the implementation is as follows,

Let the small space file data set be F={f ₁ , f ₂ ,...,f _N }, including the small space file data f ₁ , f ₂ ,...,f _N , where N is the number of small space file data The total number, the i-th space small file data is marked as f _i , i=1,2,...,N;

Set the access log information to record that the space small file data is accessed in sequence The access log sequence of small file data is A=(a ₁ ,a ₂ ,…,a _M ) is the data access sequence vector of small spatial files, a _t ∈[1,N], access sequence number t=1,2,…,M, where M is the The total number of access times of all space small file data;

Count the number of times λ _i of each small file data f _i in the access log sequence R, and take λ _i as the access heat of the small file data f _i in this space;

Step 1.2, extract frequently accessed small space file data according to the access heat of small space file data, the implementation is as follows,

Input the preset discriminant parameter λ,

If the access heat of small spatial file data f _i in the small spatial file data set F is λ _i > λ, then the small spatial file data f _i is frequently accessed small spatial file data, otherwise f _i belongs to infrequently accessed small spatial file data ;

Step 1.3, according to the frequently accessed small space file data obtained in step 1.2, constitutes a subset of the small space file data set, which is implemented as follows,

Suppose the subset of all frequently accessed small file data is Among them, N ₁ is the total number of frequently accessed small space file data, and the i ₁ and j _1th frequently accessed small space file data are respectively marked as with i ₁ ,j ₁ ∈[1,N ₁ ];

Step 2, extract the access sequence of frequently accessed small space file data subsets from the access log information, including forming the access sequence in chronological order Access sequence vectors for frequently accessed space small file data, Access sequence number t ₁ =(1 ₁ ,2 ₁ ,...,M ₁ ), where M ₁ is the total number of visits to all frequently accessed space small file data in F ₁ ;

Step 3: Use the access sequences of frequently accessed small space file data subsets to calculate the correlation degree of each frequently accessed small space file data, and form an association with the correlation degree values of each frequently accessed small space file data matrix; includes the following sub-steps,

Step 3.1, according to the number m of storage servers and the length N1 of data subsets of frequently accessed space small files, calculate the segment length _{n =} N1/m of frequent access sequences;

Step 3.2, segment the frequent access sequence according to the segment length of the access sequence, the implementation is as follows,

According to the access sequence, the frequently accessed space small file data access sequence vector A ₁ is divided into several sub-vectors in groups of n elements, expressed as A ₁ =(S ₁ ,S ₂ ,…,S _l ), where the sub-vector S _k ＝(a _k1 ,a _k2 ,…,a _kn ), a _kj ∈[1,N ₁ ], 1≤k≤l, 1≤j≤n; record all sub-vector sets in A ₁ as S, S ={S _k :k∈[1,l]};

Step 3.3, calculate the correlation degree value between frequently accessed small space file data, the implementation is as follows,

define function

in is the set of all elements in S _k ; the function Represents small file data in space that is frequently accessed within an access cycle of length n with Is it relevant;

Define the function R _S (i ₁ , j ₁ ),

where R _S (i ₁ , j ₁ ) represents the pair of S with the total correlation degree;

Step 3.4, form the correlation matrix R _S with the correlation degree values between frequently accessed small space file data,

Step 4, after performing size conversion on the value of each element in the correlation matrix, use the RCM sorting algorithm to rearrange and output;

Step 5, using the local approximation search method for the rearranged correlation matrix to find m best combinations in turn and then output them, the method is as follows,

Step 6, use the optimal combination obtained in step 5 to store the frequently accessed small space file data in a distributed manner, and store the infrequently accessed small space file data separately according to the adjacent relationship of spatial positions.

Moreover, step 4 includes the following sub-steps,

Step 4.1, obtaining the maximum value of elements in the incidence matrix, including traversing all element values of the incidence matrix, and obtaining the maximum value R _max ;

Step 4.2, perform size conversion on the element values of the incidence matrix, including traversing all element values of the incidence matrix, and performing the operation R _S (i ₁ ,j ₁ )=R _max -R _S (i ₁ ,j ₁ );

Step 4.3, using the standard RCM sorting algorithm to rearrange the incidence matrix.

Moreover, step 5 includes the following sub-steps,

Step 5.1, initialize the current number of iterations d=1;

Step 5.2, using the local approximation search method to find an optimal combination, including finding an n×n block in the current matrix, so that the value of the corresponding matrix element in the n×n block in the matrix is the largest, and the corresponding n files constitute An optimal combination; when step 5.2 is executed for the first time, the current matrix is the rearranged correlation matrix obtained in step 4; when step 5.2 is subsequently executed, the current matrix is the matrix obtained in the previous iteration;

Step 5.3, after executing step 5.2 in this iteration to search for an optimal combination consisting of n files, delete the elements of the correlation matrix corresponding to n files in the correlation matrix to obtain (N ₁ -dn)×(N ₁ - dn) matrix;

Step 5.4, judge whether d=m-1, otherwise set d=d+1, take the matrix of (N ₁ -dn)×(N ₁ -dn) obtained by performing step 5.3 in this iteration as the current matrix, and return to step 5.2 Carry out the next iteration and continue to search for the next closest combination, if it is, stop the search, and get m best combinations in total.

The present invention also correspondingly provides a small space file data distribution storage system based on access log information, including the following units,

The small spatial file data set preprocessing unit (100) is used to divide the small spatial file data set of any small spatial file data type into a frequently accessed subset and a non-frequently accessed subset according to different access frequencies; including the following Module, small space file data access frequency statistics module (101), used to obtain the data access heat of each space small file, the realization is as follows,

Let the small space file data set be F={f ₁ , f ₂ ,...,f _N }, including the small space file data f ₁ , f ₂ ,...,f _N , where N is the number of small space file data The total number, the i-th space small file data is marked as f _i , i=1,2,...,N;

Set the access log information to record that the space small file data is accessed in sequence The access log sequence of small file data is A=(a ₁ ,a ₂ ,…,a _M ) is the data access sequence vector of small spatial files, a _t ∈[1,N], access sequence number t=1,2,…,M, where M is the The total number of access times of all space small file data;

Count the number of times λ _i of each small file data f _i in the access log sequence R, and take λ _i as the access heat of the small file data f _i in this space;

Frequently accessed small space file data set extraction module (102), used for extracting frequently accessed small space file data according to the access heat of small space file data, realized as follows,

Input the preset discriminant parameter λ,

If the access heat of small spatial file data f _i in the small spatial file data set F is λ _i > λ, then the small spatial file data f _i is frequently accessed small spatial file data, otherwise f _i belongs to infrequently accessed small spatial file data ;

Frequently accessed space small file subset construction module (103), used for forming a subset of space small file data set according to frequently accessed space small file data obtained by frequently accessed space small file data set extraction module (102), as follows,

Suppose the subset of all frequently accessed small file data is Among them, N ₁ is the total number of frequently accessed small space file data, and the i ₁ and j _1th frequently accessed small space file data are respectively marked as with i ₁ ,j ₁ ∈[1,N ₁ ];

Small space file data access vector acquisition unit (200), used to extract the access sequence of frequently accessed small space file data subsets from the access log information, including forming the access sequence in chronological order Access sequence vectors for frequently accessed space small file data, Access sequence number t ₁ =(1 ₁ ,2 ₁ ,...,M ₁ ), where M ₁ is the total number of visits to all frequently accessed space small file data in F ₁ ;

Spatial small file data access association matrix calculation unit (300), used for utilizing the access sequence segmentation of frequently accessed small spatial file data subsets to calculate the correlation degree of each frequently accessed small spatial file data, and each frequently accessed space The correlation degree values between the small file data form a correlation matrix; including the following modules, the frequent access sequence segmentation length calculation module (301), used for calculating according to the storage server quantity _m , the frequent access space small file data subset length N1 Frequent access sequence segment length n=N ₁ /m;

The parameter m of the number of storage servers is input from the outside.

The frequent access sequence segmentation module (302), is used for segmenting the frequent access sequence according to the access sequence segmentation length, as follows,

According to the access sequence, the frequently accessed space small file data access sequence vector A ₁ is divided into several sub-vectors in groups of n elements, expressed as A ₁ =(S ₁ ,S ₂ ,…,S _l ), where the sub-vector S _k ＝(a _k1 ,a _k2 ,…,a _kn ), a _kj ∈[1,N ₁ ], 1≤k≤l, 1≤j≤n; record all sub-vector sets in A ₁ as S, S ={S _k :k∈[1,l]};

Small space file data association degree calculation module (303), used for calculating the association degree value between frequently accessed small space file data, is realized as follows,

define function

in is the set of all elements in S _k ; the function Represents small file data in space that is frequently accessed within an access cycle of length n with Is it relevant;

Define the function R _S (i ₁ , j ₁ ),

where R _S (i ₁ , j ₁ ) represents the pair of S with the total correlation degree;

Spatial small file data association matrix generating module (304), for forming the association matrix R _S with the correlation degree values between frequently accessed small spatial file data,

An association matrix conversion and rearrangement unit (400), which is used to convert the value of each element in the association matrix and output it after rearranging using the RCM sorting algorithm;

Incidence matrix best combination search unit (500), used for utilizing local approximation search method to find the best combination for rearranged incidence matrix;

The small space file data distribution storage unit (600) is used to use the optimal combination obtained by the correlation matrix optimal combination search unit (500) to distribute and store the frequently accessed small space file data, and to store the infrequently accessed small space file data Stored separately according to the adjacent relationship of spatial position.

And, the correlation matrix conversion and rearrangement unit (400) includes the following modules,

The maximum element value acquisition module (401) of the correlation matrix is used to obtain the maximum value of the elements in the correlation matrix, including traversing all element values of the correlation matrix, and obtaining the maximum value _Rmax ;

Incidence matrix element value size conversion module (402), used for performing size conversion on the incidence matrix element value, including traversing all element values of the incidence matrix, and performing the operation R _S (i ₁ , j ₁ )=R _max -R _S (i ₁ ,j ₁ );

A correlation matrix rearrangement module (403), configured to use a standard RCM sorting algorithm to rearrange the correlation matrix.

And, the correlation matrix optimal combination search unit (500) comprises the following modules,

The initialization module is used to initialize the current number of iterations d=1;

The optimal combination search module is used to find an optimal combination by using the local approximation search method, including finding an n×n block in the current matrix, so that the value of the corresponding matrix element in the n×n block in the matrix is the largest, corresponding The n files constitute an optimal combination; when the optimal combination search module works for the first time, the current matrix is the correlation matrix after the rearrangement of the resulting rearrangement of the correlation matrix conversion rearrangement unit (400); , the current matrix is the matrix obtained from the previous iteration;

The matrix update module is used to delete the elements of the correlation matrix corresponding to n files in the correlation matrix after the optimal combination search module performs this iterative work search to obtain an optimal combination consisting of n files, and obtains (N ₁ - dn)×(N ₁ -dn) matrix;

Judgment output module, used to judge whether d=m-1, otherwise let d=d+1, take the matrix of (N ₁ -dn)×(N ₁ -dn) obtained by the matrix update module this iteration work as the current matrix , command the best combination search module to carry out the next iteration and continue to search for the next closest combination, otherwise stop searching, and get m best combinations in total.

The beneficial effect of the present invention is that: due to the huge amount of small space file data, but the aggregation of user access behaviors, most of the requests are concentrated in a small part of small space file data, so the present invention classifies the access popularity of small space file data Finally, use the access log information to calculate the degree of correlation between frequently accessed small space files, and use the local approximation search method to find the best distribution and storage combination scheme after forming the correlation matrix. The data is distributed and stored in different schemes, and under the limited consumption of computing resources, the optimal distributed storage of massive space and small file data is realized, so as to improve its parallel access performance and the service capability of the spatial information system. Therefore, the present invention can reduce the concurrency rate of small file data access inside the server, thereby finally obtaining a high parallel access rate of small file data between servers, improving the service performance of small file data, and reducing the amount of calculation data, and the efficiency is relatively high. High, with good engineering practice, it can be applied to the field of distributed storage technology for small spatial file data in a large-scale distributed environment.

Description of drawings

Fig. 1 is a schematic diagram of the system structure in the embodiment of the present invention.

Fig. 2 is a schematic structural diagram of the preprocessing unit 100 of the small spatial file data set in the embodiment of the present invention.

FIG. 3 is a schematic structural diagram of a small spatial file data access correlation matrix calculation unit 300 in an embodiment of the present invention.

FIG. 4 is a schematic structural diagram of an association matrix transformation and rearrangement unit 400 in an embodiment of the present invention.

Fig. 5 is a flow chart of the method in the embodiment of the present invention.

detailed description

In a distributed environment, access to small spatial file data is difficult to achieve parallel access through distributed storage of data in blocks. Therefore, it is necessary to analyze the relationship between the data of each small spatial file in order to realize the access to small spatial file data. When accessing, store the requested data of small spatial files in different storage servers as much as possible, so as to achieve parallel acquisition of data of small spatial files as much as possible, thereby improving the performance of the spatial information service system.

Due to the huge amount of small space file data, the storage combination optimization of large-scale small space file data has high computational complexity, and the search time is high. Therefore, it is necessary to classify the popularity of small space file data, and use different method to obtain the optimal storage combination scheme.

The following provides detailed suggestion descriptions for the specific implementation of the technical solution of the present invention.

The small spatial file data of the present invention includes spatial data type and spatial coordinate position, and the data of each small spatial file is small, so it is not suitable to divide it into multiple parts and store them on different servers to improve the efficiency of parallel access. The access log information is recorded by the corresponding spatial information service system in chronological order, and the log information of each client application accessing the small spatial file data includes the data type and coordinates of the small spatial file accessed. The access log information is recorded by the spatial information service system during operation, and the forms include but are not limited to files and databases.

The small spatial file data includes different types, including but not limited to SRTM30 (the 30m of global Shuttle Radar Topography Mission terrain data files), SRTM90.

The method and system for distributed storage of small space file data based on interrogation log information processes each type of small space file data separately, and the method and system process the data of different types of small space files in the same way.

As shown in Figure 5, the technical solution adopted by the method of the present invention is: a method and system for distributed storage of small space file data based on access log information, and for any type of small space file data, the execution includes the following steps:

(1) Data subset extraction of frequently accessed small files in space: divide the data set of small files in space into frequent access subsets and infrequent access subsets according to different access frequencies; including the following sub-steps,

① Obtain the data access popularity of small files in each space.

Let the small space file data set be F={f ₁ , f ₂ ,...,f _N }, including the small space file data f ₁ , f ₂ ,...,f _N , where N is the number of small space file data The total number, the i-th space small file data is marked as f _i , i=1,2,...,N.

Set the access log information to record that the space small file data is accessed in sequence The access log sequence of small file data is Correspondingly, A=(a ₁ ,a ₂ ,…,a _M ) is the data access sequence vector of small spatial files, at _t ∈ [1,N] (access sequence number t=1,2,…,M), where M It is the total number of visits to all small file data in F.

Count the number of occurrences λ _i of each f _i (f _i ∈ F) in the access log sequence R, then λ _i is the access heat of the small file data f _i in this space.

② Extract frequently accessed small space file data according to the data access heat of small space files.

Input the preset discriminant parameter λ for frequently accessed small file data,

If the access heat of small spatial file data f _i in the small spatial file data set F is λ _i > λ, then the small spatial file data f _i is frequently accessed small spatial file data; otherwise, f _i belongs to the infrequently accessed small spatial file data.

③According to ②, the frequently accessed small space file data constitutes a subset of the small space file data set F

If the subset of all frequently accessed small file data is Among them, N ₁ is the total number of frequently accessed small space file data, and the i ₁ and j _1th frequently accessed small space file data are respectively marked as with i ₁ ,j ₁ ∈[1,N ₁ ].

Similarly, the infrequently accessed small file data set can be set as Among them, N ₂ is the total number of infrequently accessed small file data. where N ₁ +N ₂ =N.

(2) Access sequence extraction of frequently accessed small file data subsets: extract the access sequence of frequently accessed small file data subsets from the access log information;

Access log information records the coordinates of spatial data, and different coordinates represent different data. Therefore, the coordinate information of the accessed small spatial file data can be extracted from the access log information in order of access time. During specific implementation, the specific information extraction method may be determined according to the recording format of the access log information. The coordinate information is the spatial longitude and latitude coordinates of the small spatial file data.

Extract the access sequence subset according to the frequently accessed space small file data subset, the implementation is as follows,

In the access log information, the small space file data in the access time sequence is selected, and the frequently accessed small space file data is taken to form the access sequence of the frequently accessed small space file data subset Corresponding name Access sequence vectors for frequently accessed space small file data, (Access sequence number t ₁ =(1 ₁ ,2 ₁ ,...,M ₁ )), where M ₁ is the total number of accesses to all frequently accessed space small file data in F ₁ .

(3) Correlation degree calculation and correlation matrix acquisition: use the access sequences of frequently accessed small spatial file data subsets to calculate the correlation degree of each frequently accessed small spatial file data, and compare the frequently accessed small spatial file data with each other The association degree values between form an association matrix; including the following sub-steps,

① Calculate the frequent access sequence segment length n according to the number of storage servers and the data subset length N _of frequent access space small files.

The number m of storage servers can be input from outside, for example, from a system configuration file.

The frequent access sequence segment length n is calculated by the formula n=N ₁ /m.

②Segment the frequent access sequence according to the segment length of the access sequence.

According to the access sequence of frequently accessed small file data, the frequently accessed small file data access sequence vector A ₁ is divided into several sub-vectors in groups of n elements, expressed as: A ₁ =(S ₁ ,S ₂ ,…, S _l ), where sub-vector S _k = (a _k1 ,a _k2 ,…,a _kn ), a _kj ∈ [1,N ₁ ], 1≤k≤l, 1≤j≤n is the length in A ₁ is a subvector of n. Record all access vector sets with length n in A ₁ as S, that is, the set of all sub-vectors in A ₁ S={S _k :k∈[1,l]}.

③Calculate the value of the correlation degree between frequently accessed small space file data

Firstly, calculate the interrelationship degree of small spatial file data in each segment. Define the function:

in is the set of all elements in S _k . The significance of the function is that the frequently accessed small file data in the access period of length n with Is it related.

Based on this, define the function:

Then R _S (i ₁ , j ₁ ) represents the pair of S with total correlation.

④ Compose the correlation matrix between the correlation degree values of frequently accessed small spatial file data.

The following correlation matrix R _S can be obtained by expressing the correlation degrees among all N ₁ frequently accessed small spatial file data in a matrix.

(4) Correlation matrix conversion and rearrangement output: use the RCM sorting algorithm to rearrange the output after the size conversion of each element value in the correlation matrix; include the following sub-steps,

① Obtain the maximum value of the element in the incidence matrix.

Traverse all element values of the incidence matrix, and obtain the maximum value R _max .

②Convert the size of the element values of the incidence matrix.

Traverse all element values of the incidence matrix, and execute the operation R _S (i ₁ , j ₁ )=R _max -R _S (i ₁ , j ₁ ), to convert the size of the element values of the incidence matrix.

③ Use the standard RCM sorting algorithm to rearrange the correlation matrix.

The standard RCM sorting algorithm is used to rearrange the incidence matrix, and the goal is to concentrate the non-zero elements in the incidence matrix near the diagonal. Denote the rearranged new matrix as P. The standard RCM sorting algorithm is a prior art. For specific implementation, please refer to Gibbs N E, Poole W G, Stockmeyer P K. An algorithm for reducing the bandwidth and profile of a sparse matrix. SIAM Journal on Numerical Analysis, 1976, 13 (2): 236-250.

(5) Optimal storage distribution combination search output.

Use the local approximation search method to find the best combination for the rearranged association matrix obtained in (4) in order to obtain the highest parallel access rate of the small file data in the subset space. The local approximation search method is an existing technology. For specific implementation, reference can be made to XIA Kai, Wen-zhan. Adaptive Genetic Algorithm Based on Local Search Mechanism Quickly Solving TSP. Journal of Zhejiang Institute of Science and Technology, 2014, 31(3).

According to the rearranged correlation matrix obtained in (4), the local approximation search method is used iteratively. Each time the local approximation search is performed, an optimal combination containing n files can be obtained, and finally m combinations can be obtained for subsequent storage in m stored on the server. Each combination consists of n files, and the correlation value between n files corresponds to an n×n block in the matrix; the specific implementation is as follows:

①Initialize the current number of iterations d=1;

② Use the local approximation search method to find an optimal combination, including finding an n×n block in the current matrix, so that the value of the corresponding matrix element in the n×n block in the matrix is the largest, and the corresponding n files constitute an optimal combination. good combination;

When ② is executed for the first time, the current matrix is the rearranged correlation matrix obtained in (4), and the size of the matrix is N ₁ ×N ₁ ; when ② is executed subsequently, the current matrix is obtained from the previous iteration (N ₁ -(d -1)n)×(N ₁ -(d-1)n) matrix;

③ After performing ② search in this iteration to obtain an optimal combination consisting of n files, delete the elements of the correlation matrix corresponding to n files in the correlation matrix to obtain (N ₁ -dn)×(N ₁ -dn) Matrix, reducing the size of the correlation matrix to continue searching can save search time;

④ judge whether d=m-1, otherwise let d=d+1, execute ③ the matrix (N ₁ -dn)×(N ₁ -dn) obtained by this iteration (after d=d+1, that is (N ₁ -(d-1)n)×(N ₁ -(d-1)n)) as the current matrix, return to ② for the next iteration and continue to search for the next closest combination, if yes, stop the search, the current matrix is n×n, the last best combination consisting of n files can be directly obtained, together with the best combination obtained by sequentially searching m-1 times, a total of m best combinations can be obtained.

(6) Distributed storage of small space file data: Use the best combination finally obtained in (5) to store frequently accessed small space file data in a distributed manner, and to separate infrequently accessed small space file data according to their spatial position adjacency storage.

The embodiment distributes and stores the frequently accessed small space file data according to the obtained optimal combination to obtain the highest parallel access rate of the small space file data.

The space-small file data of the optimal distribution storage combination obtained through step (5) has the characteristics of low correlation between each other (that is, the corresponding element value in the rearranged correlation matrix after matrix element value conversion is large), Then all the small-space file data in an optimal combination can be stored in one server, so as to obtain low concurrent access requirements among each other (that is, realize a high parallel access rate among different servers).

According to the coordinate information of the small spatial file data, the embodiment separately stores the infrequently accessed small spatial file data according to their spatial location correlation.

For F ₂ in step (1), according to the principle that if the locations are adjacent, then they are stored in different servers, and the data of small files that are infrequently accessed are stored in the server.

According to the characteristics of spatial data access, spatial data access has the continuity of spatial access path. Therefore, adjacent spatial data has a high probability of being accessed at the same time. Therefore, storing in different servers can reduce concurrency and improve parallelism.

During specific implementation, the discriminant parameters of frequently accessed small file data in space, the parameters of the correlation matrix RCM sorting algorithm, and the number of storage servers can be input externally or preset by those skilled in the art.

Referring to FIG. 1 , the present invention also provides a corresponding access log information-based small space file data distribution storage system, including the following units,

The small spatial file data set preprocessing unit (100) is used to divide the small spatial file data set of any small spatial file data type into a frequently accessed subset and a non-frequently accessed subset according to the access frequency; see Fig. 2. Including the following modules, the small space file data access frequency statistics module (101), used to obtain the data access heat of each small space file, the implementation is as follows,

Let the small space file data set be F={f ₁ , f ₂ ,...,f _N }, including the small space file data f ₁ , f ₂ ,...,f _N , where N is the number of small space file data The total number, the i-th space small file data is marked as f _i , i=1,2,...,N;

Set the access log information to record that the space small file data is accessed in sequence The access log sequence of small file data is A=(a ₁ ,a ₂ ,…,a _M ) is the data access sequence vector of small spatial files, a _t ∈[1,N], access sequence number t=1,2,…,M, where M is the The total number of access times of all space small file data;

Count the number of times λ _i of each small file data f _i in the access log sequence R, and take λ _i as the access heat of the small file data f _i in this space;

Frequently accessed small space file data set extraction module (102), used for extracting frequently accessed small space file data according to the access heat of small space file data, realized as follows,

Input the preset discriminant parameter λ,

If the access heat of small spatial file data f _i in the small spatial file data set F is λ _i > λ, then the small spatial file data f _i is frequently accessed small spatial file data, otherwise f _i belongs to infrequently accessed small spatial file data ;

Frequently accessed space small file subset construction module (103), used for forming a subset of space small file data set according to frequently accessed space small file data obtained by frequently accessed space small file data set extraction module (102), as follows,

Suppose the subset of all frequently accessed small file data is Among them, N ₁ is the total number of frequently accessed small space file data, and the i ₁ and j _1th frequently accessed small space file data are respectively marked as with i ₁ ,j ₁ ∈[1,N ₁ ];

Small space file data access vector acquisition unit (200), used to extract the access sequence of frequently accessed small space file data subsets from the access log information, including forming the access sequence in chronological order Access sequence vectors for frequently accessed space small file data, Access sequence number t ₁ =(1 ₁ ,2 ₁ ,...,M ₁ ), where M ₁ is the total number of visits to all frequently accessed space small file data in F ₁ ;

Spatial small file data access association matrix calculation unit (300), used for utilizing the access sequence segmentation of frequently accessed small spatial file data subsets to calculate the correlation degree of each frequently accessed small spatial file data, and each frequently accessed space The correlation degree values between the small file data form a correlation matrix; referring to Fig. 3, including the following modules, the frequent access sequence segmentation length calculation module (301), used for the small file data subset according to the number m of storage servers and frequent access space Length N ₁ calculates frequent access sequence segment length n=N ₁ /m;

The frequent access sequence segmentation module (302), is used for segmenting the frequent access sequence according to the access sequence segmentation length, as follows,

According to the access sequence, the frequently accessed space small file data access sequence vector A ₁ is divided into several sub-vectors in groups of n elements, expressed as A ₁ =(S ₁ ,S ₂ ,…,S _l ), where the sub-vector S _k ＝(a _k1 ,a _k2 ,…,a _kn ), a _kj ∈[1,N ₁ ], 1≤k≤l, 1≤j≤n; record all sub-vector sets in A ₁ as S, S ={S _k :k∈[1,l]};

Small space file data association degree calculation module (303), used for calculating the association degree value between frequently accessed small space file data, is realized as follows,

define function

in is the set of all elements in S _k ; the function Represents small file data in space that is frequently accessed within an access cycle of length n with Is it relevant;

Define the function R _S (i ₁ , j ₁ ),

where R _S (i ₁ , j ₁ ) represents the pair of S with the total correlation degree;

Spatial small file data association matrix generating module (304), for forming the association matrix R _S with the correlation degree values between frequently accessed small spatial file data,

An association matrix conversion and rearrangement unit (400), which is used to convert the value of each element in the association matrix and output it after rearranging using the RCM sorting algorithm;

Incidence matrix best combination search unit (500), used for utilizing local approximation search method to find the best combination for rearranged incidence matrix;

The small space file data distribution storage unit (600) is used to use the optimal combination obtained by the correlation matrix optimal combination search unit (500) to distribute and store the frequently accessed small space file data, and to store the infrequently accessed small space file data Stored separately according to the adjacent relationship of spatial position.

Referring to Fig. 4, the association matrix conversion and rearrangement unit (400) further includes the following modules,

The maximum element value acquisition module (401) of the correlation matrix is used to obtain the maximum value of the elements in the correlation matrix, including traversing all element values of the correlation matrix, and obtaining the maximum value _Rmax ;

Incidence matrix element value size conversion module (402), used for performing size conversion on the incidence matrix element value, including traversing all element values of the incidence matrix, and performing the operation R _S (i ₁ , j ₁ )=R _max -R _S (i ₁ ,j ₁ );

A correlation matrix rearrangement module (403), configured to use a standard RCM sorting algorithm to rearrange the correlation matrix.

The optimal combination search unit (500) of the correlation matrix comprises the following modules,

The initialization module is used to initialize the current number of iterations d=1;

The optimal combination search module is used to find an optimal combination by using the local approximation search method, including finding an n×n block in the current matrix, so that the value of the corresponding matrix element in the n×n block in the matrix is the largest, corresponding The n files constitute an optimal combination; when the optimal combination search module works for the first time, the current matrix is the correlation matrix after the rearrangement of the resulting rearrangement of the correlation matrix conversion rearrangement unit (400); , the current matrix is the matrix obtained from the previous iteration;

The matrix update module is used to delete the elements of the correlation matrix corresponding to n files in the correlation matrix after the optimal combination search module performs this iterative work search to obtain an optimal combination consisting of n files, and obtains (N ₁ - dn)×(N ₁ -dn) matrix;

Judgment output module, used to judge whether d=m-1, otherwise let d=d+1, take the matrix of (N ₁ -dn)×(N ₁ -dn) obtained by the matrix update module this iteration work as the current matrix , command the best combination search module to carry out the next iteration and continue to search for the next closest combination, otherwise stop searching, and get m best combinations in total.

The specific implementation of each module may be consistent with the specific steps of the method, which will not be described in detail in the present invention.

The specific embodiments described herein are merely illustrative of the spirit of the invention. Those skilled in the art to which the present invention belongs can make various modifications or supplements to the described specific embodiments or adopt similar methods to replace them, but they will not deviate from the spirit of the present invention or go beyond the definition of the appended claims range.

Claims (4)

1. A small space file data distribution storage method based on access log information, characterized in that: for any small space file data type, the execution includes the following steps: Step 1, divide the data set of small spatial files into frequently accessed subsets and non-frequently accessed subsets according to different access frequencies; including the following sub-steps, Step 1.1, obtain the data access heat of small files in each space, the implementation is as follows, Let the small space file data set be F={f ₁ , f ₂ ,...,f _N }, including the small space file data f ₁ , f ₂ ,...,f _N , where N is the number of small space file data The total number, the i-th space small file data is marked as f _i , i=1,2,...,N; Set the access log information to record that the space small file data is accessed in sequence The access log sequence of small file data is A=(a ₁ ,a ₂ ,…,a _M ) is the data access sequence vector of small spatial files, a _t ∈[1,N], access sequence number t=1,2,…,M, where M is the The total number of access times of all space small file data; Count the number of times λ _i of each small file data f _i in the access log sequence R, and take λ _i as the access heat of the small file data f _i in this space; Step 1.2, extract frequently accessed small space file data according to the access heat of small space file data, the implementation is as follows, Input the preset discriminant parameter λ, If the access heat of small spatial file data f _i in the small spatial file data set F is λ _i > λ, then the small spatial file data f _i is frequently accessed small spatial file data, otherwise f _i belongs to infrequently accessed small spatial file data ; Step 1.3, according to the frequently accessed small space file data obtained in step 1.2, constitutes a subset of the small space file data set, which is implemented as follows, Suppose the subset of all frequently accessed small file data is Among them, N ₁ is the total number of frequently accessed small space file data, and the i ₁ and j _1th frequently accessed small space file data are respectively marked as with i ₁ ,j ₁ ∈[1,N ₁ ]; Step 2, extract the access sequence of frequently accessed small space file data subsets from the access log information, including forming the access sequence in chronological order Access sequence vectors for frequently accessed space small file data, Access sequence number t ₁ =(1 ₁ ,2 ₁ ,...,M ₁ ), where M ₁ is the total number of visits to all frequently accessed space small file data in F ₁ ; Step 3: Use the access sequences of frequently accessed small space file data subsets to calculate the correlation degree of each frequently accessed small space file data, and form an association with the correlation degree values of each frequently accessed small space file data matrix; includes the following sub-steps, Step 3.1, according to the number m of storage servers and the length N1 of data subsets of frequently accessed space small files, calculate the segment length _{n =} N1/m of frequent access sequences; Step 3.2, segment the frequent access sequence according to the segment length of the access sequence, the implementation is as follows, According to the access sequence, the frequently accessed space small file data access sequence vector A ₁ is divided into several sub-vectors in groups of n elements, expressed as A ₁ =(S ₁ ,S ₂ ,…,S _l ), where the sub-vector S _k ＝(a _k1 ,a _k2 ,…,a _kn ), a _kj ∈[1,N ₁ ], 1≤k≤l, 1≤j≤n; record all sub-vector sets in A ₁ as S, S ={S _k :k∈[1,l]}; Step 3.3, calculate the correlation degree value between frequently accessed small space file data, the implementation is as follows, define function in is the set of all elements in S _k ; the function Represents small file data in space that is frequently accessed within an access cycle of length n with Is it relevant; Define the function R _S (i ₁ , j ₁ ), <mfenced open = "" close = ""><mtable><mtr><mtd><mrow><msub><mi>R</mi><mi>S</mi></msub><mrow><mo>(</mo><msub><mi>i</mi><mn>1</mn></msub><mo>,</mo><msub><mi>j</mi><mn>1</mn></msub><mo>)</mo></mrow><mo>=</mo><munderover><mo>&amp;Sigma;</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>l</mi></munderover><msub><mi>R</mi><msub><mi>S</mi><mi>k</mi></msub></msub><mrow><mo>(</mo><msub><mi>i</mi><mn>1</mn></msub><mo>,</mo><msub><mi>j</mi><mn>1</mn></msub><mo>)</mo></mrow></mrow></mtd><mtd><mrow><mn>1</mn><mo>&amp;le;</mo><msub><mi>i</mi><mn>1</mn></msub><mo>&amp;le;</mo><msub><mi>N</mi><mn>1</mn></msub><mo>,</mo><mn>1</mn><mo>&amp;le;</mo><msub><mi>j</mi><mn>1</mn></msub><mo>&amp;le;</mo><msub><mi>N</mi><mn>1</mn></msub></mrow></mtd></mtr></mtable></mfenced> where R _S (i ₁ , j ₁ ) represents the pair of S with the total correlation degree; Step 3.4, form the correlation matrix R _S with the correlation degree values between frequently accessed small space file data, <mfenced open = "" close = ""><mtable><mtr><mtd><mrow><msub><mi>R</mi><mi>S</mi></msub><mo>=</mo><msub><mrow><mo>(</mo><msub><mi>R</mi><mi>S</mi></msub><mo>(</mo><mrow><msub><mi>i</mi><mn>1</mn></msub><mo>,</mo><msub><mi>j</mi><mn>1</mn></msub></mrow><mo>)</mo><mo>)</mo></mrow><mrow><msub><mi>N</mi><mn>1</mn></msub><mo>&amp;times;</mo><msub><mi>N</mi><mn>1</mn></msub></mrow></msub></mn>mrow></mtd><mtd><mrow><mn>1</mn><mo>&amp;le;</mo><msub><mi>i</mi><mn>1</mn></msub><mo>&amp;le;</mo><msub><mi>N</mi><mn>1</mn></msub><mo>,</mo><mn>1</mn><mo>&amp;le;</mo><msub><mi>j</mi><mn>1</mn></msub><mo>&amp;le;</mo><msub><mi>N</mi><mn>1</mn></msub></mrow></mtd></mtr></mtable></mfenced> Step 4, after performing size conversion on the value of each element in the correlation matrix, use the RCM sorting algorithm to rearrange and output; Step 5, using the local approximation search method to find the best combination for the rearranged correlation matrix; Step 5 includes the following sub-steps, Step 5.1, initialize the current number of iterations d=1; Step 5.2, using the local approximation search method to find an optimal combination, including finding an n×n block in the current matrix, so that the value of the corresponding matrix element in the n×n block in the matrix is the largest, and the corresponding n files constitute An optimal combination; when step 5.2 is executed for the first time, the current matrix is the rearranged correlation matrix obtained in step 4; when step 5.2 is subsequently executed, the current matrix is the matrix obtained in the previous iteration; Step 5.3, after executing step 5.2 in this iteration to search for an optimal combination consisting of n files, delete the elements of the correlation matrix corresponding to n files in the correlation matrix to obtain (N ₁ -dn)×(N ₁ - dn) matrix; Step 5.4, judge whether d=m-1, otherwise set d=d+1, take the matrix of (N ₁ -dn)×(N ₁ -dn) obtained by performing step 5.3 in this iteration as the current matrix, and return to step 5.2 Carry out the next iteration and continue to search for the next best combination, if yes, stop the search, and get m best combinations in total; Step 6, use the optimal combination obtained in step 5 to store the frequently accessed small space file data in a distributed manner, and store the infrequently accessed small space file data separately according to the adjacent relationship of spatial positions. 2. according to claim 1, based on the access log information, the space small file data distribution storage method is characterized in that: step 4 comprises the following sub-steps, Step 4.1, obtaining the maximum value of elements in the incidence matrix, including traversing all element values of the incidence matrix, and obtaining the maximum value R _max ; Step 4.2, perform size conversion on the element values of the incidence matrix, including traversing all element values of the incidence matrix, and performing the operation R _S (i ₁ ,j ₁ )=R _max -R _S (i ₁ ,j ₁ ); Step 4.3, using the standard RCM sorting algorithm to rearrange the incidence matrix. 3. A small space file data distribution storage system based on access log information, characterized in that: comprising the following units, The small spatial file data set preprocessing unit (100) is used to divide the small spatial file data set of any small spatial file data type into a frequently accessed subset and a non-frequently accessed subset according to different access frequencies; including the following module, Small space file data access frequency statistical module (101), used to obtain the data access heat of each space small file, the realization is as follows, Let the small space file data set be F={f ₁ , f ₂ ,...,f _N }, including the small space file data f ₁ , f ₂ ,...,f _N , where N is the number of small space file data The total number, the i-th space small file data is marked as f _i , i=1,2,...,N; Set the access log information to record that the space small file data is accessed in sequence The access log sequence of small file data is A=(a ₁ ,a ₂ ,…,a _M ) is the data access sequence vector of small spatial files, a _t ∈[1,N], access sequence number t=1,2,…,M, where M is the The total number of access times of all space small file data; Count the number of times λ _i of each small file data f _i in the access log sequence R, and take λ _i as the access heat of the small file data f _i in this space; Frequently accessed small space file data set extraction module (102), used for extracting frequently accessed small space file data according to the access heat of small space file data, realized as follows, Input the preset discriminant parameter λ, If the access heat of small spatial file data f _i in the small spatial file data set F is λ _i > λ, then the small spatial file data f _i is frequently accessed small spatial file data, otherwise f _i belongs to infrequently accessed small spatial file data ; Frequently accessed space small file subset construction module (103), used for forming a subset of space small file data set according to frequently accessed space small file data obtained by frequently accessed space small file data set extraction module (102), as follows, Suppose the subset of all frequently accessed small file data is Among them, N ₁ is the total number of frequently accessed small space file data, and the i ₁ and j _1th frequently accessed small space file data are respectively marked as with i ₁ ,j ₁ ∈[1,N ₁ ]; Small space file data access vector acquisition unit (200), used to extract the access sequence of frequently accessed small space file data subsets from the access log information, including forming the access sequence in chronological order Access sequence vectors for frequently accessed space small file data, Access sequence number t ₁ =(1 ₁ ,2 ₁ ,...,M ₁ ), where M ₁ is the total number of visits to all frequently accessed space small file data in F ₁ ; Spatial small file data access association matrix calculation unit (300), used for utilizing the access sequence segmentation of frequently accessed small spatial file data subsets to calculate the correlation degree of each frequently accessed small spatial file data, and each frequently accessed space A correlation matrix is composed of correlation degree values between small file data; it includes the following modules, Frequent access sequence segment length calculation module (301), used for calculating frequent access sequence segment length n=N ₁ /m according to storage server quantity m, frequent access space small file data subset length N ₁ ; The frequent access sequence segmentation module (302), is used for segmenting the frequent access sequence according to the access sequence segmentation length, as follows, According to the access sequence, the frequently accessed space small file data access sequence vector A ₁ is divided into several sub-vectors in groups of n elements, expressed as A ₁ =(S ₁ ,S ₂ ,…,S _l ), where the sub-vector S _k ＝(a _k1 ,a _k2 ,…,a _kn ), a _kj ∈[1,N ₁ ], 1≤k≤l, 1≤j≤n; record all sub-vector sets in A ₁ as S, S ={S _k :k∈[1,l]}; Small space file data association degree calculation module (303), used for calculating the association degree value between frequently accessed small space file data, is realized as follows, define function in is the set of all elements in S _k ; the function Represents small file data in space that is frequently accessed within an access cycle of length n with Is it relevant; Define the function R _S (i ₁ , j ₁ ), <mfenced open = "" close = ""><mtable><mtr><mtd><mrow><msub><mi>R</mi><mi>S</mi></msub><mrow><mo>(</mo><msub><mi>i</mi><mn>1</mn></msub><mo>,</mo><msub><mi>j</mi><mn>1</mn></msub><mo>)</mo></mrow><mo>=</mo><munderover><mo>&amp;Sigma;</mo><mrow><mi>k</mi><mo>=</mo><mn>1</mn></mrow><mi>l</mi></munderover><msub><mi>R</mi><msub><mi>S</mi><mi>k</mi></msub></msub><mrow><mo>(</mo><msub><mi>i</mi><mn>1</mn></msub><mo>,</mo><msub><mi>j</mi><mn>1</mn></msub><mo>)</mo></mrow></mrow></mtd><mtd><mrow><mn>1</mn><mo>&amp;le;</mo><msub><mi>i</mi><mn>1</mn></msub><mo>&amp;le;</mo><msub><mi>N</mi><mn>1</mn></msub><mo>,</mo><mn>1</mn><mo>&amp;le;</mo><msub><mi>j</mi><mn>1</mn></msub><mo>&amp;le;</mo><msub><mi>N</mi><mn>1</mn></msub></mrow></mtd></mtr></mtable></mfenced> where R _S (i ₁ ,j ₁ ) represents the S pair with the total correlation degree; Spatial small file data association matrix generating module (304), for forming the association matrix R _S with the correlation degree values between frequently accessed small spatial file data, <mfenced open = "" close = ""><mtable><mtr><mtd><mrow><msub><mi>R</mi><mi>S</mi></msub><mo>=</mo><msub><mrow><mo>(</mo><msub><mi>R</mi><mi>S</mi></msub><mo>(</mo><mrow><msub><mi>i</mi><mn>1</mn></msub><mo>,</mo><msub><mi>j</mi><mn>1</mn></msub></mrow><mo>)</mo><mo>)</mo></mrow><mrow><msub><mi>N</mi><mn>1</mn></msub><mo>&amp;times;</mo><msub><mi>N</mi><mn>1</mn></msub></mrow></msub></mn>mrow></mtd><mtd><mrow><mn>1</mn><mo>&amp;le;</mo><msub><mi>i</mi><mn>1</mn></msub><mo>&amp;le;</mo><msub><mi>N</mi><mn>1</mn></msub><mo>,</mo><mn>1</mn><mo>&amp;le;</mo><msub><mi>j</mi><mn>1</mn></msub><mo>&amp;le;</mo><msub><mi>N</mi><mn>1</mn></msub></mrow></mtd></mtr></mtable></mfenced> An association matrix conversion and rearrangement unit (400), which is used to convert the value of each element in the association matrix and output it after rearranging using the RCM sorting algorithm; Incidence matrix best combination search unit (500), used for utilizing local approximation search method to find the best combination for rearranged incidence matrix; The optimal combination search unit (500) of the correlation matrix comprises the following modules, The initialization module is used to initialize the current number of iterations d=1; The optimal combination search module is used to find an optimal combination by using the local approximation search method, including finding an n×n block in the current matrix, so that the value of the corresponding matrix element in the n×n block in the matrix is the largest, corresponding The n files constitute an optimal combination; when the optimal combination search module works for the first time, the current matrix is the correlation matrix after the rearrangement of the resulting rearrangement of the correlation matrix conversion rearrangement unit (400); , the current matrix is the matrix obtained from the previous iteration; The matrix update module is used to delete the elements of the correlation matrix corresponding to n files in the correlation matrix after the optimal combination search module performs this iterative work search to obtain an optimal combination consisting of n files, and obtains (N ₁ - dn) × (N ₁ -dn) matrix; Judgment output module, used to judge whether d=m-1, otherwise let d=d+1, take the matrix of (N ₁ -dn)×(N ₁ -dn) obtained by the matrix update module this iteration work as the current matrix , command the best combination search module to carry out the next iteration and continue to search for the next best combination, if so, stop the search, and obtain m best combinations in total; The small space file data distribution storage unit (600) is used to use the optimal combination obtained by the correlation matrix optimal combination search unit (500) to distribute and store the frequently accessed small space file data, and to store the infrequently accessed small space file data Stored separately according to the adjacent relationship of spatial position. 4. according to the described storage system of spatial small file data distribution based on access log information of claim 3, it is characterized in that: association matrix conversion rearrangement unit (400) comprises following module, The maximum element value acquisition module (401) of the correlation matrix is used to obtain the maximum value of the elements in the correlation matrix, including traversing all element values of the correlation matrix, and obtaining the maximum value _Rmax ; Incidence matrix element value size conversion module (402), used for performing size conversion on the incidence matrix element value, including traversing all element values of the incidence matrix, and performing the operation R _S (i ₁ , j ₁ )=R _max -R _S (i ₁ ,j ₁ ); A correlation matrix rearrangement module (403), configured to use a standard RCM sorting algorithm to rearrange the correlation matrix.