CN112131303A - Large-scale data lineage method based on neural network model - Google Patents

Abstract

The invention discloses a large-scale data lineage method based on a neural network model, which comprises the following steps: (1) generating a network training set; the method comprises the steps of array sequencing, dimension standard division and training subset division; sorting the data in the data set according to values in different dimensions in the data set; determining a division standard for each dimension to solve the sample exhaustion problem; dividing the training set into a number of smaller training subsets; (2) training a neural network model; a layered network structure is used for replacing the traditional neural network structure so as to solve the error problem caused by large sample data difference; the hierarchical structure specifically comprises a network selector and a subnet; (3) visual interaction and lineage; the method specifically comprises a space scatter diagram, a space-time projection view and a mode contrast view; the data set visualization interactive exploration is performed on the data set, and a visualization mode is used for facilitating exploration of data results by a user; and allows users to explore data sources in an intuitive manner.

Description

Large-scale data lineage method based on neural network model

technical field

This patent mainly relates to the field of machine learning and data visualization, and specifically relates to a method for real-time interaction of large-scale data sets and optimization of neural network models.

Background technique

In recent years, researchers have faced an exponential increase in the amount of data contained in datasets ^[4] , which undoubtedly brings trouble to interactive visual exploration and lineage. Recently proposed techniques allow analysts to interactively explore large-scale datasets in real-time ^[5] , but these techniques ignore the real data that one might care about hiding behind statistical data distributions ^[10] . We implement the inverse generation of data from the visualization, so the visual view will no longer be limited to showing statistics of the data, it can also be used as data to generate more complex visual views, or to explore the detailed distribution of data in a subset of views.

Research on data lineage has been in the database field for some time ^[7] . The traditional method captures source information by extending the basic data model ^[9] , and the disadvantage is obvious: the access source must be stored using a different model than the actual data. Proposing that products and descriptions produced by data may hide the details of where the results came from and how they were produced, Miles et al. ^[8] study and discuss how data sources can help scientists conduct experiments. Boris Glavic et al. ^[6] proposed a method of labeling result tuples for source tuples using query rewriting and demonstrated its feasibility in a database. K. Dursun et al. ^[1] propose a new intermediate reuse model that caches internal physical data structures implemented during query processing. This work accelerates the processing of analytical queries by investigating the reuse of intermediates in databases. Panda by R. Ikeda et al. ^[2] implements provenance capture, storage, operators and queries. They apply data lineage to tasks such as debugging, auditing, data integration, security, iterative analysis, and cleaning. Building on theirs, FotosPsallidas et al. ^[3] proposed Smoke, an in-memory database engine that does not need to sacrifice lineage capture overhead. Smoke pre-stores the pedigree in the form of a hash table in the form of a hash table to save the time overhead brought by pedigree query and meet the requirements of real-time visual interaction.

The above works mainly use large-scale datasets, however, these works have some shortcomings and shortcomings: first, some works create hash indexes for each input to speed up lineage queries, but at the same time, as the data size increases , the size of the hash table will also increase, which may bring problems such as memory exhaustion. Second, recent work uses a method to implement hash tables in memory in real-time to speed up queries, but even if this method optimizes the time to generate hash tables in real-time, it still brings inevitable storage overhead and additional queries time. At the same time, the above work cannot generate visualizations again using query data, it can only establish connections between multiple visualization views.

SUMMARY OF THE INVENTION

The purpose of the present invention is to solve the following problems in the prior art. 1. Use the neural network model to replace the traditional index structure, thereby reducing the time overhead and storage overhead caused by the query. 2. For a large amount of data, neural networks cannot satisfy the relationship between query and index well, so hierarchical structure is needed to solve this problem. The hierarchical structure includes a first-layer network selector, which is used to find the sub-network corresponding to the query; and a second-layer sub-network, which is used to calculate and output the query result. 3. Large-scale datasets often contain multiple dimensions, and users may not only need to constrain one dimension, so to solve the lineage query that satisfies multi-dimensional constraints at the same time, it is necessary to formulate different division criteria for different dimensions, and train the neural network separately for each dimension. network model. Therefore, the present invention proposes a framework based on neural network models for lineage exploration of large-scale datasets. First, the framework adopts an index structure based on a neural network model to satisfy real-time interactive lineage queries. Second, the framework integrates a hierarchical network model and a hash table to process error data. Finally, a visual interface that supports quick query and interaction of the data results is designed.

The purpose of this invention is to realize through the following technical solutions:

A large-scale data lineage method based on a neural network model, including the following steps:

(1) Generate a network training set; including array sorting, dimension standard division and training subset division; sort and store the data in the data set according to the values in different dimensions in the data set; determine a division standard for each dimension to solve the sample Exhaustive problem; divide the training set into several subsets as training subsets;

(2) Train the neural network model; use the layered network structure to replace the traditional neural network structure to solve the error problem caused by the large difference of sample data; the layered network structure specifically includes two parts, the network selector and the subnet, using The network selector is used as the first layer, and its role is to find the correct corresponding subnet for the query; for each subnet, use the training subset to train separately;

(3) Visual interaction and lineage; map the output of the neural network into several views, including spatial scatter plots, spatiotemporal projection views, and pattern comparison views; used for visual interactive exploration of datasets, using a visual approach It is convenient for users to explore data results; and allows users to explore data sources through lineage.

Compared with the prior art, the beneficial effects brought by the technical solution of the present invention are:

1. Visual Lineage, which is a new visualization-based query method to find data and focuses on how to find real data behind areas of visual view that people are interested in. It is understood that none of the current methods can interactively find real data in real time, especially the details in the data. This data can then be used to generate new visualizations to aid users in further analysis and research.

2. Hierarchical neural network structure. It can effectively reduce the range of values that each neural network needs to predict, and help control the number of neurons. A smaller number of neurons can make the network easy to observe and adjust, while solving the network update problem. This structure can effectively control the error. A neural network that only needs to adapt to the relationship between thousands of data samples and labels can simply control the maximum allowable error to a reasonable value.

3. An approach based on a neural network model that uses a composite structure of hash tables and hierarchical neural networks to support lineage queries on large data at interactive rates. It costs little additional storage overhead and enables fine-grained lineage queries. This structure enables real-time interactive exploration while consuming less storage overhead than all existing technologies. The structure supports updates, which solve common problems with neural network structures.

Description of drawings

Figure 1 is a general flow chart of the proposed method.

Figure 2 is a graph of network training set generation.

Figure 3 shows the structure of the neural network. In the figure: a indicates the query input by the user, b indicates that the query outputs the corresponding sub-network through the network selector, and c indicates the location of the data corresponding to the sub-network output corresponding to the query.

Detailed ways

The present invention will be further described in detail below with reference to the accompanying drawings and specific embodiments. It should be understood that the specific embodiments described herein are only used to explain the present invention, but not to limit the present invention.

The present invention proposes a framework based on a neural network model for lineage exploration of large-scale datasets. First, the framework adopts an index structure based on the neural network model. For each dimension in the dataset, all query conditions are used as samples, and the query results are used as labels to train the neural network model to satisfy real-time interactive lineage query. Secondly, the hierarchical network model and hash table, by dividing the network into two layers, the network selector and the sub-network, effectively reduce the range of values that each neural network needs to predict, and use the hash table to record data with large errors, Realize the processing of error data. Specifically, as shown in Figure 1, it mainly includes the following steps:

Step 1: Network training set generation (Figure 2). Specific operations include array sorting, dimension standard division, and training subset division. Sort the data in the dataset according to the values in the different dimensions of the dataset, and then store all these orders; determine a partitioning criterion for each dimension to solve the problem of sample exhaustion; divide the training samples into many smaller subsets to overcome the problem of Neural networks do not adapt well to small errors.

Sorting an array is a very important part of a data structure. In simple terms, sorting an array means sorting the data in the dataset based on the values in different dimensions, and then storing all those orders. Training a neural network requires some kind of functional relationship between the input and the output, and sequential ordering can establish some kind of linear relationship between the query and the output. For multiple dimensions in the dataset (longitude, latitude, hour, day), a sorted array will be stored for each dimension, sorted by the value of each data in that dimension. Like a database, each data is assigned a unique primary key, so each sorted array only needs to store the primary key, which will greatly reduce the storage space overhead. Usually, each piece of data only brings the lowest data type storage consumption, which is 4 bytes.

The generation of training samples requires generating training samples for each dimension separately. In order to make the training samples exhaustive, a division criterion needs to be determined for each dimension, that is, the samples are based on this criterion. For dimensions with a clear standard (such as days), use one day as the dividing standard; for dimensions without clear standards (such as longitude or latitude), divide them as finely as possible. Training samples are divided into inputs and outputs (labels). The input is the query condition, that is, a resolution size increases from zero until it reaches the maximum value of the dimension; the output is the query result corresponding to each input. The output is the index position of the query result in each sorted array corresponding to each input, that is, the index of the last data whose value is less than the input in the sorted array of a dimension. In this case, the input and output increase monotonically, so there may be some linear relationship between them. Since neural networks do not adapt well to small errors, this problem will be magnified as the range of training samples increases, eventually leading to unacceptable errors. So divide the training samples into many smaller subsets and use them to train different neural networks. For each subset, a normalization process is used to simplify the training of the neural network.

Step 2: Train the neural network model (Figure 3). Use a layered network structure to replace the traditional neural network structure to solve the error problem caused by the large difference in sample data; the hierarchical structure specifically includes two parts: the network selector and the subnet, and the network selector is used as the first layer. The role is to find the correct corresponding subnet for the query; for each subnet, use the training subset to train separately.

With a training sample, the traditional approach is to use it to train a neural network and then save the network. In the process of this embodiment, due to the large range of the sample range, the subtle deviation of the neural network is amplified many times, so the error is unacceptable. So it was decided to use a hierarchical structure instead of traditional neural networks. The hierarchy mainly consists of two parts: network selectors and subnets. A network selector is used as the first layer whose role is to find the correct corresponding subnet for the query. Training samples are distributed evenly according to a certain number, so when a query is entered, it can easily be calculated in one calculation to which subnet it belongs. The query is then normalized and fed into the subnet, which then outputs the index of the data corresponding to the query in a sorted array. It should be noted that the index output here is not a completely accurate value. This is due to the nature of neural networks, which means that unless the number of neurons is large enough, it cannot fit every piece of data exactly. So set an error value for the output of the neural network. As long as the output is within the error bounds, the prediction of the neural network is considered successful. The benefits of using a layered structure instead of an entire neural network are as follows:

(1) It can effectively reduce the range of values that each neural network needs to predict. For large datasets, the relationship between query and index is generally linear, but if you zoom in on a single record, it will show more and more irregularities. However, if a single neural network only needs to satisfy relationships between thousands of queries and indexes (except in rare cases), a neural network is perfectly functional.

(2) It can help control the number of neurons. For example, with training sets with tens of millions of samples, it is difficult to determine the number of neurons in a single neural network. However, very good results can be achieved with only a few neurons for a training set of only a few thousand samples. In addition, neural networks with fewer neurons can divide longer training times into separate small parts, which are easier to observe and adjust.

(3) It can help to set the error. If a single neural network needs to fit the relationship between millions or even tens of millions of data samples and labels, it is difficult to control the allowable error between predicted and true values. But in contrast, if a single neural network only needs to adapt to the relationship between thousands of data samples and labels, then the maximum allowable error can simply be controlled to a reasonable value.

Even if the data is divided into many small parts, there are still very few data that cannot control the error between the predicted value and the true value within the maximum allowable range for the neural network. For this part of the "anomaly" part of the neural network, a hash table will be used to store them. Because their number is minimal and the time complexity of hash queries is only O(1), the time overhead and storage overhead brought by hash tables are almost negligible. So in the end, use pre-sorted data, adaptive single-layer neural networks and other hash tables as the final indexing structure. After that, in different dimensions, use the output of the neural network or hash table to find the position in the original data that corresponds to the query, then get the results of the different dimensions, perform a conjunction operation on these results, and summarize the user-provided results according to the condition, then pass the result to the front-end interface, which then completes the front-end interface for visual presentation.

Step 3: Visual Interaction and Lineage. Provides visual interaction lineage on datasets. Specifically, it includes spatial scatter plot, spatiotemporal projection view, and pattern comparison view; it is used for visual and interactive exploration of data sets, and it is convenient for users to explore data results in a visual way; and allows users to explore data sources through lineage.

Map space scatter plot.

The visualization interface mainly reflects the distribution of data on the map through scatter plots. Users can judge the amount of data distribution in the area based on the prominence of each point on the map. At the same time, the scatter plot can constrain the other four visual views. Users can select a box on the scatter plot to further explore and analyze data in local areas rather than the entire map. Use the user select box on the scatter plot as a query, return the lineage results of the query, store the results in memory, and update the other four views with on-the-fly calculations. Scatter charts support zooming, so users can browse individual data in a small area, such as a street with only a small amount of data. The scatter plot responds to the user's actions in four other visual views, and then displays the distribution of data on the map over a specific time period of interest to the user.

view component

The visualization interface mainly uses line charts, bar charts and heatmaps to reflect the time distribution of data. Users can perform lineage queries by limiting the scatter plot. Plot query results in the form of heatmaps, line graphs, and bar graphs with instant calculations, allowing users to easily explore and analyze the temporal distribution of local data. If the user does not enforce the constraints, the visual view will reflect the time period information for the entire dataset. Users can select boxes in the three view components except the heatmap to constrain the data content reflected by all other views, including the viewables. Users can frame view components based on time periods of interest. For example, to browse and analyze weekend data, the user needs to perform a box selection on the weekly projection histogram, while to browse and analyze data at night, the user needs to perform a box selection on the hourly histogram. The hourly projection histogram reflects the data distribution over 24 hours, the week projection histogram reflects the data distribution over 7 days of the week, and the day distribution histogram reflects the data distribution between start and end dates. An additional summary view has been added to the day distribution histogram, which appears as a thin line graph that reflects the distribution of the entire data over time. Users can select the time range of interest on the summary view according to their interests, and use the day distribution histogram as a detailed view to visualize query results.

resource usage.

The storage overhead of this data structure mainly comes from the neural network and pre-classification. Some details are shown in Table 1. The storage space occupied by presort is related to the dimension of the lineage query. Each dimension of the lineage query will cause the data structure to store one more sorted array using the same amount of original data, although each number in the sorted array is a minimum of 4 bytes. Another part of the storage overhead comes from the parameters of the neural network. The total parameters of a neural network are related to the number of neural networks and the number of neurons in each neural network. The number of neural networks in the data structure is determined by the resolution of different dimensions. In the time dimension, the resolution of the lineage query is one hour, and then two objects with timestamps 10h15m and 10h20m are divided into the same label, i.e. 10h. Therefore, the higher the definition, the higher the number of neural networks or the number of neurons per neural network. It is more inclined to increase the number of neural networks when implementing data structures, because the data that a neural network can fit well has a certain regularity and its range should not exceed a certain range.

During training, increasing the number of neural networks and reducing the amount of data each neural network needs to fit can effectively improve accuracy, which will result in a constant memory overhead occupied by the neural network as new data is inserted with new resolutions Does not change, changing the index value at the corresponding resolution can complete the fast update of the structure. For each dimension of the new data, add an index value corresponding to its position in the sorted array of the corresponding dimension, which is also 4 bytes in size. The number of input objects, training time and storage overhead are reported in the first three columns. The number of input objects refers to the number of valid data in the dataset. The training time is the sum of the time spent training all the networks that need to be trained. The Network column represents the number of subnets used by each dataset. The Object (Network) column indicates the number of data objects corresponding to each subnet. Due to the data structure some valuable information is discarded from the original data. So the storage overhead here may not necessarily be greater than the size of the dataset itself.

This data structure can handle very fine-grained data lineage, such as single-digit data lineage, with a precision of 1.0. At the same time, it still has good performance, low time overhead and storage overhead when dealing with large-scale data lineage. For datasets containing millions or tens of millions of data, it is difficult to find only a few of them out of so much data. This data structure enables fine-grained visualization of lineage queries on large-scale datasets with good performance.

Table 1 Resource occupation

The present invention is not limited to the embodiments described above. The above description of the specific embodiments is intended to describe and illustrate the technical solutions of the present invention, and the above-mentioned specific embodiments are only illustrative and not restrictive. Without departing from the spirit of the present invention and the protection scope of the claims, those of ordinary skill in the art can also make many specific transformations under the inspiration of the present invention, which all fall within the protection scope of the present invention.

references:

[1] K. Dursun, C. Binnig, U. Cetintemel, and T. Kraska. Revisiting reuse inmain memory database systems. arXiv preprint arXiv:1608.05678, 2016.

[2] R.Ikeda and J.Widom.Panda: Asystem for provenance and data.IEEEData Eng.Bull, 2010.

[3] Fotis Psallidas and Eugene Wu. Smoke: Fined-Grained Lineage CaptureAt Interactive Speed. Proceedings of the VLDB Endowment, 2018.

[4] F. Psallidas and E. Wu. Provenance for interactive visualizations. HILDA, 2018.

[5] J.Poco, J.Heer, Reverse-engineering visualizations: Recovering visualencodings from chart images.Comput.Graph.Forum, 2017.

[6] B.Glavic and G.Alonso.Perm:Processing provenance and data on thesame data model through query rewriting.ICDE, 2009.

[7] Muniswamy-Reddy, K.-K., Macko, P., and Seltzer, M. Provenance for the cloud. Proceedings of the 8th USENIX Conference on File and Storage Technologies (FAST), 2010.

[8] Miles, S., Groth, P., Deelman, E., Vahi, K., Mehta, G., and Moreau, L. Provenance: The bridge between experiments and data. Comput. Sci. Engin, 2008.

[9] B. Glavic. Big data provenance: Challenges and implications for benchmarking. Specifying Big Data Benchmarks-First Workshop, WBDB, 2014.

[10] J. Wang, D. Crawl, S. Purawat, M. Nguyen, I. Altintas, Big data provenance: Challenges state of the art and opportunities. Big Data, 2015.

The present invention is not limited to the embodiments described above. The above description of the specific embodiments is intended to describe and illustrate the technical solutions of the present invention, and the above-mentioned specific embodiments are only illustrative and not restrictive. Without departing from the spirit of the present invention and the protection scope of the claims, those of ordinary skill in the art can also make many specific transformations under the inspiration of the present invention, which all fall within the protection scope of the present invention.

Claims (1)

1. The large-scale data lineage method based on the neural network model is characterized by comprising the following steps of:

(1) generating a network training set; the method comprises the steps of array sequencing, dimension standard division and training subset division; sorting and storing the data in the data set according to values in different dimensions in the data set; determining a division standard for each dimension to solve the sample exhaustion problem; dividing the training set into a plurality of subsets as training subsets;

(2) training a neural network model; a layered network structure is used for replacing the traditional neural network structure so as to solve the error problem caused by large sample data difference; the hierarchical network structure specifically comprises a network selector and a subnet, wherein the network selector is used as a first layer and is used for finding a correct corresponding subnet for inquiry; for each subnet, respectively training by using the training subsets;

(3) visual interaction and lineage; mapping the output result of the neural network into a plurality of views, specifically comprising a space scatter diagram, a space-time projection view and a mode contrast view; the data set visualization interactive exploration is performed on the data set, and a visualization mode is used for facilitating exploration of data results by a user; and allows users to explore data sources in an intuitive manner.

Images