CN103235974B - A kind of method improving massive spatial data treatment effeciency - Google Patents

Abstract

A method for improving the processing efficiency of massive spatial data, comprising the following steps: public operator extraction, public operator parallel strategy design, public operator parallel implementation, public operator call, public operator combination, and other steps. The present invention extracts the basic and common parts in spatial data processing as common operators, and parallelizes them based on MPI. In terms of data scale, it can process massive spatial data with millions of samples and hundreds of attributes. However, the existing spatial data The processing method is incomprehensible, but it can be processed efficiently and correctly. Task submission and parameter setting use web pages for interaction. All calculations are concentrated on the server side for efficient execution and completion. The client side has less pressure and is easy to operate. <pb pnum="1"/>

Description

A Method of Improving the Processing Efficiency of Massive Spatial Data

technical field

The invention relates to a method for improving the processing efficiency of massive spatial data based on public operators and high-performance computing. By providing a parallel computing framework for spatial data processing that can run stably and efficiently on a server, the processing efficiency of spatial data is improved, and at the same time Study how to apply spatial data processing methods to multiple fields.

Background technique

With the rapid development of aerospace remote sensing technology, sensor technology and the Internet, the speed and scale of obtaining spatiotemporal data continue to grow (from GB to PB), and at the same time, the number of data instances, attributes, and classifications has surged, and high-dimensional Large data sets followed. Due to the complexity of spatial data processing algorithms and the complexity of spatial information, spatial data processing of large data sets will take a lot of time. At the same time, in many fields such as public health and health, disaster early warning, and population spatialization, many non-professionals need to use complex models in spatial data processing. Existing models basically cannot be customized according to needs, resulting in the inability to be widely promoted.

In terms of spatial data processing operations, well-known foreign GIS basic software platforms such as Arc/Info and MGE have complete and efficient tool libraries. However, the combination and collaborative work between each tool can only be carried out at a coarser level, and the individual use and combination of the fine-grained algorithm level within the tool cannot be realized. For this reason, the basic part and the common part in spatial statistics can be extracted as a common operator. The use of public operators can solve the problems of repeated writing of spatial data processing codes, difficulties in the interaction of various algorithms, and customization of spatial data processing models according to applications.

The advancement of modern science and technology has greatly promoted the development of computing science. The new generation of computers is much superior to the early computers in terms of computing power and computing speed. In practice, due to the limitation of the extreme speed of physical components and technical level, a single processor is far from meeting the demand for computing resources of challenging large-scale computing tasks in many modern fields, so in addition to enhancing the processor itself In addition to computing power, parallel processing is an effective means to improve computing power.

While multi-core processors are in full swing, the software industry is far from ready for it. How to develop various spatial data processing applications conveniently and quickly on the emerging multi-core cluster platform to provide more efficient online services; more importantly, how to isolate the lower multi-core platform for upper-level program developers, so that the developed spatial data processing It will be a serious challenge for parallel algorithms to be easily used by users.

Generally speaking, the existing spatial data operation models, algorithms, and theories and methods are not deep enough, and the research results obtained have not been realized in time for further application. The rapid development of high-performance computing environment, especially multi-core computing environment, provides a broader development space for spatial data processing. Therefore, designing a parallel computing framework for spatial data processing based on common operators will be the best solution to isolate the lower-level high-performance platform and upper-level application development, and apply it to a wider range of industries.

Contents of the invention

The technical solution of the present invention is to overcome the deficiencies of the prior art, and propose a method for improving the processing efficiency of massive spatial data, by extracting the basic and common parts in spatial data processing as common operators, and parallelizing them based on MPI, In terms of data scale, it can handle massive spatial data with millions of samples and hundreds of attributes, which cannot be calculated by existing spatial data processing software, and can be processed efficiently and correctly. Task submission and parameter setting are interactive through web pages. All calculations are concentrated on the server side for efficient execution, and the client has less pressure and is easy to operate.

The technical solution of the present invention: a method for improving the processing efficiency of massive spatial data, comprising the following steps:

(1) Common operator extraction

(1.1) The spatial data processing method is divided into four parts: preprocessing, spatial feature exploration, spatial information calculation, and result inference according to input and output, implementation ideas, and functional purposes. Each part contains multiple spatial processing models. A single model can Complete a complete spatial data processing function, such as: classification, interpolation, etc.;

(1.2) Study the space processing model contained in each part of (1.1), and split the space processing model into multiple independent modules according to the principle of functional integrity and indivisibility, and each module is used as a public operator. The processing results are used as the input data and input conditions of other public operators in the subsequent process, or directly as the final result;

(1.3) Screen the extracted public operator sets, remove duplication, and obtain the public operator sets that need to be parallelized and accelerated;

So far, the common operators in all spatial data processing methods have been extracted, and then it is necessary to parallelize the common operators to achieve acceleration.

(2) Public operator parallel strategy design

(2.1) Divide each public operator obtained in step (1.3) into more detailed calculation units, and a single calculation unit only performs the simplest complete calculation operation once to find the expectation and logarithm; the sequence string between the calculation units Row, internally implemented as parallel;

(2.2) Determine the type of computing unit one by one, and formulate a data block distribution strategy. If the computing units are all local computing Local or neighborhood computing Focal, the raster data is divided into rows, and the vector data needs to consider the spatial topological relationship. The principle of node data integrity is divided into blocks; if the global calculation Global is included, all node operations require data, so the data is not divided into blocks, but the data is sent to all nodes, and the transmission adopts a broadcast strategy. The basic unit for broadcasting is a process, and a process is a computing and communication unit, usually a core in a CPU. Each process joins the broadcaster after getting the data, and sends it to the remaining processes of this node and all processes of other nodes;

(2.3) After the data block strategy design is completed, it is necessary to design the parallel strategy of the computing unit. The calculation unit is divided into global parameter calculation and single sample value cycle calculation. First, the parallel strategy design for global parameter calculation is carried out. The parallel strategy includes regional decomposition and functional decomposition. Since the global parameter calculation can usually be expressed as a mathematical formula, the formula can be decomposed and the spatial data to be processed can be allocated to multiple processes.

(2.4) Then, the parallel strategy design of single-sample value cycle calculation is carried out. Since each calculation only depends on each sample value and global parameters, and has nothing to do with other sample calculations, a data parallel strategy can be used to evenly distribute samples to each process.

So far, the parallel strategies of all public operators have been designed, and then public operators can be implemented using specific programming languages and parallel interfaces according to the formulated parallel strategies.

(3) Parallel implementation of common operators

(3.1) According to the data block distribution strategy mentioned in step (2) and the parallel strategy of the computing unit, based on MPI (Message Passing Interface), based on the parallel library of the message passing interface, four parallel primitives are designed, including distribution Map, Reduce, broadcast, and multiplex interleaving operations are regulated, so as to realize the expansion of the MPI function library and improve the transmission efficiency of public operators under the condition of big data, especially massive spatial data;

(3.2) According to the four parallel primitives and the MPI function in the step (3.1), the high-level language C++ is used to write the code, and the common operators are processed in parallel to obtain a parallel common operator set that runs efficiently;

(3.3) Perform parallel efficiency tests on the public operators implemented in step (3.2) on single-node and multi-node clusters, count IO and communication costs, and continuously improve until the executable parallel public operators that meet the requirements are obtained.

So far, all public operators have been implemented in parallel, and each public operator will be compiled into an independent executable file that can run efficiently on high-performance computing platforms.

(4) Public operator call

(4.1) Deploy the executable file of the public operator obtained in step (3.3) to a high-performance cluster, and write a daemon process. The daemon process on the cluster is a service that starts with the system and runs in the background for parameter parsing, task execution, and result feedback.

(4.2) After the daemon process is started, the user can submit the parameters required for public operator calculation through the web page in the client browser, and the web server will write the parameters into the database;

(4.3) The daemon process reads the public operator calculation parameters from the database and interprets them to obtain a hash table containing multiple Key-Value pairs. Key represents the parameter name, and Value represents the parameter value. After the key-value pair splicing process, the instruction expression that needs to perform spatial data processing tasks is obtained;

(4.4) The task instruction obtained in (4.3) of the daemon process operation, simultaneously writes the operation output information and the log into the database, and writes the result of the calculation into the disk;

(4.5) The web server extracts the output information and logs from the disk and database, and organizes the output, logs, and calculation results into a web page for feedback to the user. After the user obtains the operation result and output information, the entire public operator calling process ends;

When performing simple spatial data processing, that is, only a single public operator is used, and the entire process has ended. At this point, users can submit public operator parameters through the web page, and obtain operation results, output information, and logs.

(5) Combination of public operators

If it is necessary to process complex spatial data or complete the spatial data processing requirements of a specific field, skip step (4) directly and perform step (5).

(5.1) Deploy the executable file of the public operator obtained in step (3) to a high-performance cluster, and write a daemon process.

(5.2) Study the logical structure of complex spatial data processing or spatial data processing in a specific field, and obtain the required public operators and the logical structural relationship between each public operator, including the execution sequence, dependency, and The relationship between the input and output of public operators;

(5.3) According to the logical structure relationship obtained in step (5.2), in the visualized complex model editor, combine common operators through directional connection lines to obtain a visualized model;

(5.4) The complex model editor converts the obtained visual model into a set of instructions with order, and submits the set of instructions to the database at the same time;

(5.5) The daemon process reads the command set from the database to interpret, determines the dependencies and then runs step by step, and writes the log to the database;

(5.6) Wait for all the instructions in step (5.5) to run sequentially, and the daemon process will write the result of the space processing to the disk, and the web server will feed it back to the user; if the operation fails, roll back according to the log, and feed back the error information For users, the method to improve the processing of massive spatial data has been constructed so far.

The region decomposition parallel strategy implementation step in the step (2.3) is: decompose the non-overlapping regions in the partial differential equations, thus transforming the discretized equations into some independent simple equation solving problems and one and each A global problem related to two simple equations; the implementation steps of the parallel strategy of functional decomposition: when solving a system of linear equations with the Newton iterative method, the two independent processes of solving function values and derivation values can be assigned to different computers.

The advantage of the present invention compared with prior art is:

(1) By using the technology proposed in the parallel strategy design and parallel implementation of the claims, the present invention can make full use of the advantages of high-performance cluster computing, greatly improve the processing efficiency of massive spatial data, and make full use of the performance advantages brought by computing hardware. The invention also solves the problems of how to divide the vector data into blocks according to the spatial relationship and communicate data between multi-node processes when the spatial data is introduced into high-performance computing.

(2) Use public operators to build a parallel computing framework for spatial data processing. The parallel granularity is small and the customization is strong. Using the complex model editor can be freely combined according to the final application, so that the model in spatial data processing can be applied to multiple industries. .

(3) As described in the public operator call in step 3 of the claim, the final result of the present invention provides free services to users through the Web, and non-professional users do not need to care about the implementation details, but only provide the necessary system input. The server is deployed on a high-performance Linux cluster, making complex spatial data processing easier to use. At the same time, it also provides professional users with more parameter control, making the calculation results more accurate.

Description of drawings

Figure 1 is the common operator framework for spatial data processing;

Fig. 2 is the realization flow chart of the method of the present invention;

Fig. 3 is the spatial variogram fitting parallel strategy design;

Figure 4 is the parallel strategy design for high-precision surface modeling;

Fig. 5 is MSN parallel strategy design;

Figure 6 shows the parallel strategy design for multi-unit sandwich sampling;

Figure 7 shows four parallel primitives;

Fig. 8 is the implementation steps and discretization process of high-performance Bayesian classifier;

Fig. 9 is the implementation steps of high-performance Bayesian classifier structure learning and parameter learning;

Figure 10 shows the parallel efficiency of high-performance Bayesian classifiers.

Detailed ways

As shown in Figures 1 and 2, the present invention mainly comprises the following steps:

public operator extraction

Spatial data processing is generally relatively simple in terms of resource organization, and is based on the calculation of a certain type of data. In terms of algorithms, when calculating based on a certain type of attribute or graph, the calculation is relatively simple; while when doing statistical inference calculations, the complexity will be higher. In short, the more sources of resources involved, the more complex the processing of spatial data is, and the process of its realization requires the comprehensive coordination of many aspects.

In the present invention, the spatial data processing method is divided into four parts: preprocessing, spatial feature exploration, spatial information calculation, and result inference according to the purpose. Each part contains a plurality of spatial processing models; Among them, the basic and common parts are used as public operators to ensure that each public operator is an independent module, and its processing results can be used as input data and conditions of other public operators, or directly as the final result; and then the obtained public operators Sets are screened to remove duplicate and non-parallelizable common operators.

Data preprocessing is to roughly process the existing spatial data, and provide the required format data for the subsequent model. Common operators for extraction and processing include distribution conversion, regularization, and discretization, etc. Spatial feature exploration is a tentative calculation of spatial distribution and correlation to obtain the overall and local clustering features of spatial data. Common operators that can be extracted include Moran’I, GetisG, and spatial scanning statistics. The purpose of spatial information calculation is to obtain the overall characteristic parameters of the area and transform the discrete sample values into a continuous area through spatial interpolation. The extracted common operators include semivariogram, block matrix transformation, matrix eigenvalue calculation, etc. The result inference is to infer the unknown sample value after training the model with known sample information, and the extracted common operators include maximum likelihood estimation, EM, naive Bayes, etc.

Public Operator Parallel Strategy Design

Divide the public operators obtained in the previous step into more detailed calculation units, and each calculation unit only performs the simplest complete calculation operation once, such as finding expectation, logarithm, etc. Computing units are sequentially serialized, and internally implemented in parallel. Determine the type of computing unit one by one, and formulate a data block distribution strategy. If the calculation units are all local calculations or neighborhood calculations Focal, the raster data is divided into rows, and the vector data needs to consider the spatial topological relationship and be divided according to the principle of data integrity of a single node; if the global calculation Global is included, all All node operations require data, so the data is not divided into blocks, but the data is sent to all nodes, and the sending adopts a broadcast strategy. After each process gets the data, it joins the broadcaster and sends it to other processes.

After the data block strategy design is completed, it is necessary to design the parallel strategy of the computing unit. The calculation unit is divided into global parameter calculation and single sample value cycle calculation. First of all, the parallel strategy design for global parameter calculation is generally to decompose the calculation formula itself and distribute the calculation content to multiple processes. Parallel strategies include regional decomposition and functional decomposition. Region decomposition parallel strategy implementation steps: decompose the non-overlapping regions in the partial differential equations, thereby transforming the discretized equations into some independent small-scale problems and a global problem associated with each small problem. Functional decomposition parallel strategy implementation steps: When using Newton iterative method to solve linear equations, the two independent processes of solving function value and derivation value can be assigned to different computers. Then, the parallel strategy design of single-sample value cycle calculation is carried out. Since each calculation only depends on each sample value and global parameters, and has nothing to do with other sample calculations, a data parallel strategy can be used to evenly distribute samples to each process.

The detailed parallel strategy design of each public operator is as follows:

(1) Data preprocessing

Regularization and distribution conversion adopt the strategy of combining data block and asynchronous parallelism, which can handle multi-variable data, and users can perform regularization and function conversion of multi-dimensional selection; the goal of discretization is to use optimized The discretization of the algorithm is convenient for achieving the best results in classification learning. The discrete parallel strategy mainly adopts synchronous parallel algorithm and pipeline technology. When calculating candidate breakpoints, according to data parallelism, each process calculates breakpoints separately, and then aggregates them to the follower process. When screening breakpoints, each process calculates the importance of breakpoints separately, and obtains the most important point of each process, performs a reduce operation to obtain the most important breakpoint, and judges whether to continue the cycle according to the consistency requirement.

(2) Spatial correlation exploration

Spatial variation function fitting, using different functions to fit, and then using R2 to select the best fitting parameters. The parallel strategy design is shown in Figure 3. Asynchronous parallelism is used on the overall level, and the variability in different directions can be calculated using the region decomposition method at the next level. A synchronous and parallel design strategy will be adopted to select the optimal model and improve the solution efficiency. The main process selects the variation function model with the largest R2 and the highest precision according to the results of n sub-processes.

(3) Spatial interpolation

(1) Kriging interpolation, due to the batch nature of interpolation, the interpolation operation of each point can be assigned to an MPI process to obtain very good parallelism and performance gain. When the computing resources are far greater than the number of interpolation points required, consider parallel optimization of the built-in The K-th nearest neighbor operation and the operation of solving linear equations. Two steps of interpolation: (a) find the N points closest to the target point; (b) calculate the result using some interpolation method. For Kriging interpolation, two steps evolve into: The nearest K-th neighbor and solving a system of linear equations.

Public operator 1: nearest neighbor algorithm, specific implementation method: (a) original algorithm: brute-force (violent method); (b) serial optimization algorithm: algorithm based on space division and index tree, typical algorithm such as ANN; (c) Parallel algorithm: divide and conquer (merge calculation results for each part of data).

Common operator 2: To solve linear equations, use a mature parallel linear algebra library, such as Linpack or Intel KernalMath Library; Run on a single machine to reduce communication costs. Region decomposition parallel strategy implementation steps: decompose the non-overlapping regions in the partial differential equations, thereby transforming the discretized equations into some independent small-scale problems and a global problem associated with each small problem. Functional decomposition parallel strategy implementation steps: When using Newton iterative method to solve linear equations, the two independent processes of solving function value and derivation value can be assigned to different computers.

(2) High-precision curved surface

High-precision surface modeling and parallel strategy design are shown in Figure 4. The fundamental problem is to solve the problem of constrained least squares. Through iteration, the numerical surface is obtained for fast and efficient temperature interpolation. The overall parallel strategy adopts a symmetrical mode, and the upper layer adopts a regional decomposition strategy. By decomposing the final problem, it is transformed into three parts: automatic fitting of spatial variation, solution of block triangular transformation equation, and solution of least squares method. The parallel strategies within the three common operators all adopt region decomposition.

(4) Area overall parameter estimation

(a) MSN is the unbiased optimal estimation of the heterogeneous surface mean, which can improve the estimation accuracy of the area mean in the study area.

The parallel strategy design is shown in Figure 5. The master-slave model is generally adopted, and the top layer adopts the parallelization strategy of region decomposition. It is mainly transformed into the parallelization of two common operators, automatic fitting of spatial variation and unbiased optimal solution of Gaussian equation, and the parallel strategy is region decomposition.

(b) Multi-unit sandwich sampling

The parallel strategy design is shown in Figure 6. Generally, the master-slave mode is adopted to transform the required problem into three basic common operators: automatic fitting of spatial variation, calculation of similarity coefficient, and unbiased optimal solution of Gaussian equation. Sub-intra-parallel strategies are all region-decomposed.

The Sandwich space sampling model will be synthesized by a hierarchical similarity calculation and a Gaussian equation for unbiased optimal estimation.

(5) Spatial classification

Spatial DAG classification inference, the model is based on Bayesian network, incorporating spatial factors. It includes three steps: learning of network structure, learning of network parameters, and network reasoning, and each step adopts different parallel strategies.

The learning of network structure generally includes two aspects: model selection and model optimization. Model selection determines the criteria for judging the pros and cons of different models, such as scoring algorithms (including K2, BIC, AIC, etc.), while model optimization is to find the optimal model Come out, such as hill climbing algorithm. The single operation time of the scoring function is not long, but it needs to be called repeatedly, so there is no need to implement parallelism inside the scoring function. Hill climbing algorithm is a meta-heuristic local search algorithm, including three local operators (add edge, delete edge, reverse edge). The specific implementation is to choose an operator that can improve the score of the Bayesian network in your given initial structure, and iterate continuously. Every time you need to find the local operator that can maximize the score of the Bayesian network, you can assign each operation to multiple threads for calculation, and then use the Reduce operation to obtain the optimal local operator. After the local operator is executed, recalculate A set of executable local operator operations, redistributing task calculations, and repeating until the network score no longer improves.

The learning of network parameters is to determine the conditional probability distribution of each node under the premise of a given topology. The parameter learning method currently used in the present invention is EM. The specific implementation is divided into two steps, E-M. The E-step mainly adopts the strategy of data parallel separation. Each calculation only depends on a single sample. After all calculations are completed, communication is required to obtain the final result. In the M step, the conditional independence of BN and the expected sufficient statistical factor of the E step are used, and the decomposability of the likelihood function under the complete data set is used to calculate each local likelihood function in parallel.

The reasoning of the network adopts the data block parallel strategy. Each reasoning operation only needs the current sample impact factor data and the Bayesian network with conditional probability to classify the decision factors. Therefore, the parallel strategy design is only for the data, and the data can be divided into blocks.

(6) Spatio-temporal pattern recognition

Spatio-temporal scanning statistics, hotspot/gathering area detection parallelization scheme:

(1) Selecting candidate aggregation areas: a. Divide all grid points into n disjoint subsets and assign them to n parallel processes; b. Calculate and obtain the set of candidate aggregation areas without repetition in the subsets; c. For every two sub-sets, repeated candidate aggregation regions are eliminated.

(2) Find the largest possible aggregation area based on the real observation data: a. Distribute the real observation case values into n parallel processes; b. Calculate the likelihood ratio for the candidate aggregation areas included in it; c. Find the The largest possible aggregation area where the likelihood ratio is maximized.

(3) Monte Carlo simulation, calculate the maximum likelihood ratio, and independently calculate in several parallel processes in parallel, and finally get N maximum likelihood ratio values, which are stored in each parallel process respectively. (4) Calculate the statistical significance p-value of the largest possible aggregation area: a. In each parallel process, perform the sorting to maximize the likelihood value; b. Merge the sorting results of the two processes until the final merge is a sorted sequence containing all N likelihood ratios.

Parallel implementation of common operators

Parallelize each public operator according to the designed parallel strategy. In the distributed network computer system, the communication between processes is realized by the method of message passing. The current popular parallel programming environments based on message passing are MPI (Message Passing Interface) and PVM (Parallel Virtual Machine). Among them, the message passing interface MPI has become the most important parallel programming environment due to its good portability, powerful functions, and high efficiency. tool.

According to the three operations mentioned in step 2, four parallel primitives (Map, Reduce, Broadcast, Multiplex) are designed based on MPI. As shown in Figure 7, specifically, by extending the functions of MPI, the transmission efficiency of large data, especially spatial data, is improved. Compared with ordinary Map-Reduce, parallel granularity is finer, multiple states (MultipleStages), and their communication mechanisms are different.

(a) The Map operation is implemented based on MPI_Scatter, MPI_Send, and MPI_Recv, and is used to distribute the original data and intermediate data to all processes in the current communication domain. Raster data corresponds to integer or floating-point type, which belongs to the default supported type of MPI, and is sent directly; vector data needs to be serialized into a binary string, and then sent as a Char type.

(b) The Reduce operation is implemented based on MPI_Reduce, and the results calculated by each process are aggregated to the root process.

(c) The Broadcast operation is implemented based on MPI_Bcast, which broadcasts the structure of a single process to all processes.

(d) Multiplex operations are implemented based on MPI_Gatherall, MPI_Bcast, MPI_Send, and MPI_Recv, and broadcast the read data or calculation results of all processes to all processes.

The following takes Moran's I as an example to illustrate the specific steps of parallel implementation of public operators.

In this paper, it is necessary to calculate the local Moran's I value for all the influencing factor variables of the sample one by one, and each calculation is divided into three stages (seeking expectation beg beg ), execute serially between the three stages, and execute in parallel within the three stages. After the sample data is divided into blocks, the first two stages only need to perform intra-block calculations and aggregate them to the main process, and then broadcast to all processes. The last stage includes not only intra-block calculations, but also inter-block calculations, summing up the intra-block and inter-block values. Inter-block operations need to send a large amount of data, and use the method of sending data between processes to avoid excessive waiting for each process.

The specific steps of Moran's I parallel computing are as follows:

(1) Process 0 reads raster image information in blocks and sends them to other processes in turn;

(2) All processes compute the received blocks and compute the sum of the observations in the blocks;

(3) Calculate the sum of all observed values and calculate the average value through Reduce, and broadcast the average value to all processes at the same time;

(4) All processes calculate data blocks in this process and

(5) Each process broadcasts the blocks it receives to other processes. After each process receives the block, it performs an intersection operation (Multiplex) with the block it received in step 1 to calculate

(6) Obtain each process through Reduce and with and, and get the final Moran's I value;

(7) Write the Moran's I value into the sample attribute.

public operator call

After each public operator is implemented in step 3, it will be compiled into a single executable file, which can be used by the daemon process (a daemon process is a service under the Linux system to schedule and execute computing tasks, and at the same time compare the calculation results with The log is written to the server database) to call with different parameters. The specific operation steps are as follows:

(a) The user submits the parameters that need to be calculated by the public operator through the web page in the client browser, and the Web server writes the parameters into the server database;

(b) The daemon process reads the parameters from the server database, splicing each part of the parameters to obtain the tasks to be executed;

(c) The daemon process submits tasks, executes instructions, and intercepts program operation output information and logs through pipeline technology, writes them into the server database, and writes the calculated results into the server disk;

(d) The web server extracts output information and logs from the server disk and database, and organizes the operation output, logs, and calculation results into web pages to feed back to users;

Professional users can also install ssh on the client, and then call it through the command line. There are more parameters to choose from when the command line is invoked. The following is the invocation command for data preprocessing and spatial DAG classification inference, that is, the detailed parameter description.

(1) Data preprocessing

mpirun-np 2GeoPreprocessing-a 2-co 0-k 0-p gps_people_s.csv -c 0,1,2-ore_dis.csv

Parameter explanation:

-a 0 means log algorithm, 1 means normal algorithm, 2 means discretization algorithm

-p indicates the input file path

-o indicates the input file path

-c indicates the column to be calculated, starting from 0; raster data indicates the band

-co indicates whether to output the classification information after the completion of discrete words, 0 means no output, 1 means output, the default is 0

-k indicates whether to use k-mean clustering to filter breakpoints, 0 means not used, 1 means used, the default is 0

-C indicates the column where the decision attribute in the discretization algorithm is located

(2) Spatial DAG classification inference

mpirun-np 2 ParBayes–a StrLeaning_HC-p re_dis.csv-cn 2-dn 6-c 0,1,2,3,4

-a indicates the algorithm for structure learning or parameter learning

-p indicates the input file path

-c indicates the column to be calculated, starting from 0

-cn indicates the node size of a common node, that is, the value category, and the default is 2

-dn indicates the node size of the decision node, the default is 6

Combination of public operators

Each public operator is generally only responsible for the realization of specific functions and algorithms, such as discretization public operators and variation function public operators. To implement complex functions or customize some functions for specific fields, multiple public operators must be Structures are combined into complex models. Each public operator has its own algorithm parameters and interfaces. The parallel framework for spatial data processing based on public operators provides a visual complex model editor to assist users to express the logical structure of each business through a visual model, and then by The parallel framework turns this into a command run that can be executed on the server. When the parallel framework calls public operators, it can not only be parallelized internally, but also can be parallelized between public operators without dependencies, thereby improving the operating efficiency of the entire complex model.

The specific implementation steps are as follows:

(a) Study the logical structure of the business, and obtain the required public operators and the logical structural relationship between each public operator;

(b) According to the logical structure obtained in 5.1, in the visual complex model editor, combine common operators through directional connection lines to obtain a visual model;

(c) After the model editing is completed, the complex model editor converts the obtained visual model into a set of instructions with order, and submits the set of instructions to the server database at the same time;

(d) The daemon process reads the command set from the server database to interpret, determines the dependencies and then runs step by step, and writes the log into the server database;

(e) After waiting for all the instructions in 5.4 to run sequentially, the daemon process writes the space processing results to the server, and the web server feeds back to the user; if the operation fails, rollback is performed according to the log, and the error information is fed back to the user.

The specific steps that the present invention implements are illustrated below with high-performance Bayesian classifier as an example:

(1) Data description (sample data can be downloaded from http://159.226.110.219/ website)

Test case: Through the information of known samples (trajectory data), study the relationship between influencing factor variables (such as moving speed, human activity, etc.) and category variables (person's activity status), and then target unknown samples Make classification inferences.

Influencing factor variables: 17 characteristic variables including moving speed, human activity, maximum speed within 10 minutes before and after, distance difference before and after 10 minutes, and GPS measurement parameters.

Categorical variable: person's activity status, including indoors, outdoors, working outside the house, or in the car.

Data volume: 120,000 rows of vector data with known categorical variables. Use 90% of the data for learning, and infer the categorical variables of the remaining 10% of the samples, and compare with the real value to get the inference accuracy.

(2) Test environment

Using the above data, the parallel Bayesian classifier implemented in this paper is tested on the cluster environment. The cluster consists of four nodes, each node has two Intel(R) Quad Core E5520 Xeon(R) CPUs, a total of eight cores, 16G independent memory, 200G disk, and the connection bandwidth between nodes is Gigabit Ethernet.

(3) Implementation steps

As shown in Figure 8, the entire implementation process is mainly divided into data preprocessing (discretization), Bayesian network structure learning, Bayesian network parameter learning, and Bayesian network classification inference.

Discretization is to turn continuous variables into discrete (categorical), and the discretized variables have strong anti-interference. Since Bayesian network learning requires discretized data, and most of the sample attributes usually obtained are continuous (for example: human activity, various parameters of GPS, etc.), it is necessary to discretize the data first. The algorithm used in the present invention is calculated based on the breakpoint importance.

Spatial DAG classification inference mainly uses Bayesian network. As shown in Figure 9, the learning of the network structure adopts the hill-climbing algorithm to obtain a Bayesian network that is optimal locally and overall; the learning of the network parameters adopts EM (Maximum Likelihood Algorithm) to obtain The Bayesian network; network reasoning, using Naive Bayes (naive Bayesian).

The specific calling methods include the following three methods:

(1) Each public operator is regarded as an object in the model editor, and the relationship between input and output, parameters and objects can be expressed through connecting lines with directions.

(2) Log in to the website http://159.226.110.219/, after registering as a user, select Add Content->Data Preprocessing_Discretization in the navigation bar, and enter the parameters required for calculation (if the data is too large, you can upload it through ftp, and then enter Select File attach at the file). Similarly, perform other operations sequentially according to the steps in FIG. 7 to obtain the final result.

(3) Enter commands in ssh to run directly

mpirun-np 4 GeoPreprocessing-a 2-co 0-k 0-p gps_people_s.shp-c 0-17-ore_dis.csv

mpirun-np 4 ParBayes–a StrLeaning_HC -p re_dis.shp -c 0-17–o re.str

mpirun-np 4 ParBayes–a ParLeaning_EM -p re_dis.shp–s re.str -c 0-17–ore.bys

mpirun-np 4 ParBayes–a Inferring_Naive-p data_infer.shp–b re.bys -c 0-17

(4) Calculation results

Parallel efficiency is an index used to indicate the acceleration of parallel computing algorithms. The calculation formula for n-core parallel efficiency is P _n = (τ _n /τ ₁ )/n, where t _n represents the time spent by n cores to execute the algorithm, and t ₁ represents Single core execution time.

The average parallel efficiency of the Bayesian classifier is 0.84, and the parallel efficiency of each step is shown in Figure 8, which can greatly improve the efficiency of classification and inference of massive spatial data. When performing ten-fold cross-validation on the final classification results, the inference accuracy (pd value) was 0.85. The four curves ABCD in Figure 10 represent the parallel efficiency of the four common operators of discretization, hill-climbing algorithm, EM algorithm, and naive Bayesian algorithm in turn. Due to inter-process communication and non-parallelizable parts of the algorithm, the parallel efficiency will decrease as the number of processes increases. The slope of the curve, that is, the speed of decline, is determined by three factors: the number of communications, the amount of communications, and the proportion of the parallel part of the algorithm itself. Generally speaking, the parallel Bayesian classifier has high parallel efficiency, and the efficiency improvement is very obvious when performing massive spatial data classification and prediction, and it also proves that the present invention is effective for improving the processing efficiency of massive spatial data.

For discretized parallelism, the parallel efficiency can still reach 0.8 when there are 32 cores (curve A in Figure 10). Doing it locally, the communication overhead is very small.

The average parallel efficiency of Bayesian network structure learning using BIC scoring algorithm and hill-climbing optimization algorithm is 0.77 (curve B in Figure 10). As the number of iterations increases, the parallel efficiency will decrease year-on-year. The reason is that DAG will be randomly generated in each iteration. This step cannot be parallelized, and communication is required every time a local operator operation is performed to obtain the local operator with the highest score. And broadcast the score value, operation type, and participating nodes.

Bayesian network parameter learning adopts EM algorithm, and the average parallel efficiency is 0.80 (C curve in Fig. 10). The calculation of the expected sufficient statistical factors of each sample in the E step is independent of each other, which has good data parallelism. The M step can also be parallelized with a small amount of communication by decomposing the likelihood function. However, the number of processes used by the M step can only be equal to the number of variables at most, and the parallelism of the M step is not high when there are fewer variables. Since the entire calculation of M steps takes very little time, the efficiency of parallelism is relatively high.

Naive Bayesian is used for inference classification, with an average parallel efficiency of 0.82 (curve D in Figure 10). The classification of each sample is independent of each other and only depends on the known Bayesian network with conditional probability. After the data is divided into parallel blocks, no communication is required at all. Each process writes the calculation results to the disk or database respectively, so parallel Very efficient.

Parts not described in detail in the present invention belong to the well-known technology in the art.

The above are only some specific implementations of the present invention, but the protection scope of the present invention is not limited thereto. Any changes or substitutions that can be easily conceived by those skilled in the art within the technical scope disclosed in the present invention should be covered within the protection scope of the present invention.

Claims (2)

1. improve a method for massive spatial data treatment effeciency, it is characterized in that comprising the following steps:

(1) public operator extraction

(1.1) pre-service, space characteristics exploration, spatial information calculating and result is divided into infer four parts by input and output, realization approach, function and usage difference spatial data processing method, each part comprises multiple spatial manipulation model, and single model can complete a complete spatial data handling function;

(1.2) the spatial manipulation model that in (1.1), each part comprises is studied, according to functional completeness and inseparability principle, spatial manipulation model is divided into multiple standalone module, each module as a public operator, its result as other public operators in follow-up flow process input data, initial conditions or be directly net result;

(1.3) the public operator collection extracted is screened, remove and repeat, obtain needing to carry out the public operator collection that process is accelerated in parallelization;

So far by the public operator extraction in all spatial data processing methods out, then need to carry out parallelization process to public operator to realize accelerating;

(2) public operator paralleling tactic design

(2.1) each public operator obtained in step (1.3) is divided into finer computing unit, single computing unit only carries out once the operation of the simplest complete computation, namely asks expectation and logarithm; Be order serial operation between each computing unit, each computing unit inside is parallel work-flow;

(2.2) type of computing unit is judged one by one, formulate deblocking distribution policy, if computing unit is all local computing Local or neighborhood calculate Focal, raster data carries out piecemeal by row, vector data need consider spatial topotaxy, carries out piecemeal according to the principle of single node data integrity; If comprise global calculation Global, all node compute all need data, therefore piecemeal is not carried out, and data are sent all nodes, send and adopt broadcast strategy, elementary cell when broadcasting is process, a process is exactly one and calculates and communication unit, be generally a core in CPU, each process adds broadcaster after obtaining data, sends this data to the residue process of this node and all processes of other node;

(2.3), after deblocking Strategy Design completes, the paralleling tactic design carrying out computing unit is needed.Computing unit is divided into global parameter to calculate and single sample value cycle calculations.First, carry out the paralleling tactic design of global parameter calculating, paralleling tactic has Region Decomposition, Function Decomposition, because global parameter calculation expression is a mathematical formulae, decomposes this formula, distributes to multiple process by needing the spatial data carrying out processing;

(2.4) carry out the paralleling tactic design of single sample value cycle calculations, because calculating each time only relies on each sample value and global parameter, calculate irrelevant with other samples, data parallel strategy can be adopted, sample mean is dispensed to each process;

So far, the paralleling tactic of all public operators has designed, and according to the paralleling tactic formulated, adopts C++ programming language and parallel interface to realize public operator;

(3) public operator Parallel Implementation

(3.1) according to the paralleling tactic of the deblocking distribution policy mentioned in step (2) and computing unit, based on the parallel storehouse of MPI and Effect-based operation passing interface, design four kinds of parallel primitives, comprise distribution Map, stipulations Reduce, broadcast Broadcast, crossing operation Multiplex, thus realize expansion to MPI function library, improve the transfer efficiency of public operator especially massive spatial data under large data qualification;

(3.2) according to four kinds of parallel primitives in step (3.1) and MPI function, adopt higher level lanquage C++ to write code, public operator is carried out parallelization process, obtains the parallel public operator collection of Effec-tive Function;

(3.3) the public operator that step (3.2) realizes is carried out parallel efficiency test respectively in single node and multi-node cluster, statistics input and output IO, communication cost, update, until be met requirement perform parallel public operator;

So far, all public operator Parallel Implementation, each public operator can be compiled into the standalone executable file of an Effec-tive Function on high-performance calculation platform;

(4) public operator calls

(4.1) executable file of the public operator obtained in step (3.3) is deployed in High-Performance Computing Cluster, and write finger daemon, finger daemon on cluster starts with system and in the service of running background, is used for carrying out Parameter analysis of electrochemical, tasks carrying, result feedback;

(4.2), after finger daemon starts, namely user submits to public operator to calculate desired parameters, by Web server by parameter read-in database at client browser by webpage;

(4.3) finger daemon reads public operator calculating parameter and decipher obtains comprising the Hash table of multiple Key-Value key-value pair from database, Key represents parameter name, Value represents parameter value, the instruction obtaining needing to carry out spatial data handling task is expressed after all key-value pair splicings in Hash table;

(4.4) finger daemon runs the assignment instructions obtained in (4.3), will run in output information and daily record write into Databasce simultaneously, computing acquired results write disk;

(4.5) Web server extracts output information and daily record from disk and database, after tissue, operation output, daily record, result of calculation are configured to webpage and feed back to user, after user obtains operation result and output information, whole public operator invoked procedure also just terminates;

When carrying out simple spatial data handling, namely only carry out the use of single public operator, whole flow process so far terminates, and now public operator parameter can be submitted to by webpage by user, and obtains operation result, output information and daily record;

(5) public operator combination

If need the spatial data handling requirement carried out complex space data processing or complete specific area, then directly skip step (4), perform step (5);

(5.1) executable file of the public operator obtained in step (3) is deployed in High-Performance Computing Cluster, and writes finger daemon;

(5.2) logical organization of complex space data processing or the specific area spatial data handling that will carry out is studied, obtain the logical organization relation between required public operator and each public operator, comprise the relation between public operator execution precedence relationship, dependence and public operator input and output;

(5.3) according to the logical organization relation that step (5.2) obtains, in visual complex model editing machine, by the connecting line combination of public operator by band direction, Visualization Model is obtained;

(5.4) gained Visualization Model is converted to the sequential instruction set of band by complex model editing machine, is submitted in database by instruction set simultaneously;

(5.5) finger daemon carries out decipher from the set of database reading command, progressively runs after determining dependence, and by daily record write into Databasce;

(5.6), after in waiting step (5.5), all instruction sequences have been run successively, finger daemon, by spatial manipulation acquired results write disk, feeds back to user by Web server; If run unsuccessfully, carry out rollback, and error message is fed back to user according to daily record, the method so far improving massive spatial data process has built.

2. the method for raising massive spatial data treatment effeciency according to claim 1, it is characterized in that: described in described step (2.3), domain decomposition parallel policy implementation step is: decomposed in region non-overlapped in partial differential equation, thus the equation after discretize is turned to some independently simple equation solve with a global issue associated with each simple equation; Described Function Decomposition paralleling tactic implementation step: during with Newton solution by iterative method system of linear equations, by solution functional value and differentiate numerical value two independently process different computing machines can be transferred to be responsible for.