44 results about "Graph partition" patented technology

The invention discloses a method which utilizes a graph partition method to automatically extract a multi-document summarization, and the method comprises the following steps that: the sentence boundary dividing is carried out, and the document is expressed by the divided sentences; the sentences are expressed into vectors, the similarities among each two sentences are calculated to compose a sentence incidence matrix, which is reduced according to the appointed threshold value, at the same time, the normalized treatment is carried out; the crawling of the implied logical topic of a topic is introduced into the multi-document summarization, and a document set is divided into different implied sub-topics according to the topic, thereby the summarization task is changed into the selection and the extraction processes to the sub-topics; by applying the graph partition method, the importance degree of the sub-topic of the sentences is ensured from the global characteristics, and the low redundancy of the contents among the different sub-tops is ensured from the local characteristics, thereby effectively improving the quality of the summarization.

The invention discloses a multilayer k-way graphical partition method based on vertex cut and community detection. The method comprises the steps that the distribution of a natural graph is considered according to the statistic analysis property, a corresponding vertex cutting algorithm is provided, vertexes causing longer task completion time are cut, label propagation is iteratively performed on the cut graph by a community detection algorithm based on the label propagation, the label of each vertex of the graph is determined, a community where the vertexes are located is obtained, partitioning is performed by a traditional multilayer k-way graph partition algorithm, and the efficiency is consolidated. For most of application in the large-scale iteration graph processing, distributed computational nodes meet the load balancing, extra communication traffic, due to the iteration dependency necessity, produced by each processing original node between adjacent iteration processing steps is greatly reduced, the task operating efficiency of a graph processing frame is greatly reduced, and the throughput capacity of tasks is increased.

A distributed data graph storage system, to store a data graph representing information as vertices interconnected by edges denoting relationships between connected vertices, the data graph being a plurality of graph partitions. The data graph storage system includes data storage servers to store data portions, each portion encodes a graph partition; a data portion distribution controller, when the data portions each encode a same graph partition, to allocate the portions to different data storage servers; a data access module to receive access requests for the data graph and to distribute the access requests among the servers; a graph partition usage monitor to record statistics representing the distribution of data access events caused by the access requests; where the data portion distribution controller is configured to increase or decrease the number of portions in dependence upon the recorded statistics.

The invention discloses a block-based subgraph construction and distributed graph processing method. The block-based subgraph construction method comprises partitioning a graph, relabeling summits in the graph, associating intervals with shards, partitioning blocks and constructing subgraphs, and employs a heuristic and lightweight SGP (Streaming Graph Partition) method to partition a graph, and a user-defined heuristic function to designate the summits to P subgraphs in order; the method possesses the characteristics of high performance and low edge cutting rate, and considers subgraph work load balance. According to a distributed graph processing system, after partitioning, subgraphs perform communication by employing a whole memory block as a unit; compared with the fine grit communication mode of the prior art, the distributed graph processing system exchanges data based on a memory block, and can fully utilize network bandwidth and reduce communication time.

Embodiments of the invention relate to data archiving on storage medium such as magnetic tapes based on graph partitioning. One aspect of the invention concerns a method that comprises representing a file system as a graph where each node of the graph represents a file and each edge represents file chunks common to the files corresponding to the nodes connected by the edge. The graph is repeatedly partitioned into disjoint sub-graphs. If the files and duplicate file chunks associated with a sub-graph fit into a data storage medium, then the files and duplicate file chunks are stored in the medium. Otherwise, the method may partition the sub-graph into smaller disjoint sub-graphs taking into consideration of degrees of connectivity of the nodes.

The invention is suitable for the technical field of image processing, and provides a method and a device for compressing a composite image. The method comprises the following steps: S1, partitioning the composite image according to image features to obtain a plurality of partitioned areas, wherein the image features include color and grayscale, and the partitioned areas include a text / graph area and an image area; S2, compressing the partitioned areas by adopting a corresponding encoding way respectively. In the method, the composite image is partitioned into text / graph partitioned areas and natural image partitioned areas according to information of different features included in the composite image, so that corresponding compression methods can be adopted for different partitioned areas, and high compression ratio is ensured. Meanwhile, the text / graph areas are clear and readable after being reconstructed.

The invention relates to a distributed indexing method and system based on a graph database, and the method comprises the steps: generating a vertex index of a vertex through a mark ID of the vertex after a writing request of the vertex or an edge is obtained, generating an edge index of the edge through the edge type of the edge, and enabling the vertex to comprise the vertex ID and the mark ID;wherein the edge comprises a source point ID and the edge type; and performing hash operation through the vertex ID or the source point ID, storing the vertex or the edge into a corresponding graph partition, writing the generated vertex index or the edge index into the same graph partition, including a plurality of graph partitions in a graph space corresponding to a graph database, and storing the vertex or the edge into the graph partition after the vertex or the edge is written into the graph partition. The problems that the index query efficiency of the Nebula Graph is not high, and the unnecessary network overhead generated by query is relatively high are solved, so that a user can quickly query the vertex and the edge in the Nebula Graph.

A method, computer program product, and a data processing system for determining an edge for inversion in a cyclic compound directed graph. A plurality of graph nodes of a graph are evaluated for generation of a first node order subset pair. A determination that the graph requires a recursive evaluation for completing node ordering of the plurality of graph nodes is made. The graph is divided into a plurality of graph partitions, and respective node order subset pairs are generated for the graph partitions.

The invention discloses an uncertain trajectory privacy protection method based on graph partition. The method comprises the following steps: step (1) data preprocessing: preprocessing an original trajectory data set so as to make uncertain trajectories intersect on time dimension, wherein each uncertain trajectory has the same sampling point number; step (2) correlation degree constructing: extracting time features, direction features and distance features of the preprocessed trajectory data to compute the correlation degree between unknown trajectories; step (3) undirected graph constructing: mapping the trajectory data set to an undirected graph, wherein each node in the undirected graph represents one trajectory, a weight of a side between the nodes represents the correlation degree of two corresponding uncertain trajectories; and step (4) undirected graph partitioning: partitioning the undirected graph by use of a greedy algorithm to form a plurality of clusters containing k uncertain trajectories. Through the adoption of the method disclosed by the invention, a user can balance the data information loss and privacy level according to a privacy protection requirement.

The invention provides a secure spatial network query method based on a secure partition tree. The secure spatial network query method comprises the following steps: (1) construction of a partition tree index structure: constructing the partition tree index structure based on graph partition for spatial network data; (2) construction of a security index structure: encrypting the spatial network data according to attributes by using a Paillier encryption system to ensure the privacy information security of the spatial network data; meanwhile, for the division tree index structure, processing the subspace network ID by adopting a Hash function H to obtain H(ID); and (3) a secure spatial network query method: on the basis of the secure index structure, performing heuristic search on the secure index structure by using the priority queue to obtain a final query result. According to the invention, a new secure spatial network query method is established, so that the query efficiency of the secure spatial network on large-scale spatial network data is further improved; and the safety of the query process is protected, and the query result is safely output.

A method estimates an optimal power flows (OPF) in a power grid, which is represented as a graph partitioned into virtual sub-graphs, each including at least one bus, and associated with agents that measure local variables and updates consensus variables (CV). The consensus variables of adjacent virtual sub-graphs are exchanged and updated using the agents. An OPF problem is solved for the virtual sub-graphs using the agents based on the CV and the local variables. The exchanging and the solving are iterated until a termination condition is satisfied, when the optimal OPF is outputted for each virtual sub-graph.

A system for executing a graph partitioned across a plurality of reconfigurable computing units includes a processing node that has a first computing unit reconfigurable at a first level of configuration granularity and a second computing unit reconfigurable at a second, finer, level of configuration granularity. The first computing unit is configured by a host system to execute a first dataflow segment of the graph using one or more dataflow pipelines to generate a first intermediate result and to provide the first intermediate result to the second computing unit without passing through the host system. The second computing unit is configured by the host system to execute a second dataflow segment of the graph, dependent upon the first intermediate result, to generate a second intermediate result and to send the second intermediate result to a third computing unit, without passing through the host system, to continue execution of the graph.

The invention provides a tracking area list management method based on overlapping community detection in a small cellular network. For user location management in the small cellular network, the signaling expenditure of a network system is optimized, and a determination method of a TAL is provided. For the giving of the small cellular network mode after TA planning, the general idea of the methodprovided by the invention is as follows: firstly counting tracking area location updating and paging data of the user at the specific time frame and in the specific region; and then modelling a TAL management method as a graph partition problem, and giving a linear planning model; and finally giving a TAL structure by applying an overlapping community detection algorithm based on the game theory.

The invention discloses a multi-task external memory mode diagram processing method based on I / O scheduling, includes streaming partitioning graph data to obtain graph partition, evenly placing graphpartition in multiple external storage devices, selecting target external storage devices from multiple external storage devices based on I / O scheduling, and taking graph partition in the target external storage device that has not been accessed by graph processing task as designated partition; Judging whether the synchronization field of the designated partition is not mapped into the memory according to the synchronization field of the designated partition, if so, mapping the designated partition from the external storage device into the memory, and updating the synchronization field of thedesignated partition; Otherwise, the graph partition data is accessed directly through the address information mapped to memory by the specified partition. Through I / O scheduling, the invention selects the external storage device with the least number of tasks to access, thereby controlling the sequence of accessing the data of the external storage diagram partition and balancing the I / O pressure.By setting the synchronization field to realize the data sharing of graph partition, the repeated loading of the same graph partition is reduced, so as to reduce the total I / O bandwidth and improve I / O efficiency.

The invention discloses a single-camera multi-target tracking method based on an improved graph partition model, and belongs to the field of target tracking. A two-layer reasoning structure is adopted. Single-camera multi-target tracking is regarded as a graph partition problem, and a binary integer programming (BIP) is used for solving the graph partition problem. In the stage of hierarchical reasoning, a short sliding window is used in the first stage, and the same person detection box is divided into the same image partition to form short track small fragments. In the second stage, a long sliding window is used, and small track segments belonging to the same person are divided into the same image partition to form a long track. For the situation that missed detection possibly occurs near the junction of non-overlapping segments of the sliding window in the second stage, the invention provides a method for overlapping the sliding window, so that the missed detection rate is reduced,and the algorithm tracking precision is improved. Identity conversion caused by mutual shielding among targets is easy to occur during multi-target tracking, so that the invention provides a trajectory constraint method, and the occurrence of identity conversion is reduced.

A computer-implemented method for identifying pre-join operations, when accessing a database of relational tables, based on a usage history and / or a priority needs, comprises creating a graph of weighted edges and nodes, the nodes represent relational tables and edges represent join operations to be performed on the tables, partitioning the graph into a plurality of graph communities based on graph community densities, with a density indicating a number of edges touching a particular node, with the number of edges being greater than a predetermined edge number threshold, with each edge furtherincluding an edge weight indicative of a frequency of referencing within a predetermined recent duration of time and / or indicative of urgency of quick access to the corresponding join result within apredetermined recent duration of time, and generating pre-join results based on the partitioned graph communities and graph community densities.

The invention relates to a pedestrian trajectory prediction method based on a GP-CNN, and aims to solve the core problem of trajectory prediction in automatic driving, namely how to design a model to better capture associated interaction information to improve prediction precision and safety of an automatic driving automobile. According to the invention, a pedestrian trajectory prediction model applied to a complex scene is designed, based on the GP-CNN, interaction features of the scene are extracted by using a mode of combining two channels to serve as input, and information of time-domain features of the pedestrian trajectory is specially processed, meanwhile, forward and backward propagation of the prediction trajectory is smoother through residual connection, and then a pedestrian interaction prediction trajectory is generated through a trajectory prediction network.

The invention provides a Method for estimating optimal power flows in power grids using consensus-based distributed processing. The method estimates an optimal power flows (OPF) in a power grid, which is represented as a graph partitioned into virtual sub-graphs, each including at least one bus, and associated with agents that measure local variables and updates consensus variables (CV). The consensus variables of adjacent virtual sub-graphs are exchanged and updated using the agents. An OPF problem is solved for the virtual sub-graphs using the agents based on the CV and the local variables. The exchanging and the solving are iterated until a termination condition is satisfied, when the optimal OPF is outputted for each virtual sub-graph.

The invention discloses a bounded incremental graph partition method and system. The method comprises the following steps of: partitioning an initial graph structure into a plurality of first sub-graphs by a coordinator to correspondingly obtain a plurality of first sub-partitions, and distributing the first sub-partitions to a plurality of workers; performing iterative expansion on the obtained first sub-partitions by each worker, and judging whether the first sub-partitions reach a preset equilibrium upper bound or not in the iterative expansion process, and if the first sub-partitions reachthe preset equilibrium upper bound, stopping expansion of the first sub-partitions; confirming whether update data exists or not by the coordinator; and if update data exists, combining the update data with the initial graph structure to obtain an updated partial graph structure, then partitioning the partial graph structure into a plurality of second sub-graphs and corresponding second sub-partitions, distributing the second sub-partitions to the workers, and performing iterative expansion by the workers receiving the second sub-partitions. According to the method and system, the calculationoverhead during distributed graph partition can be reduced, and the partition result is more balanced.

The invention discloses a clustering method for an MIMO multi-cell base station cacheable system, and belongs to the technical field of wireless communication. The method comprises the steps of modeling according to a more practical cacheable base station system, considering a downlink model of a single-user cell, pre-clustering the cell by using a soft cluster size constrained graph partition clustering method, then carrying out cluster size balancing according to set judgment conditions, and measuring advantages and disadvantages of the clustering according to the effective rate, thereby enabling the final clustering scheme to more conform to feasible conditions of interference alignment. Compared with the prior art, a clustering scheme with more balanced cluster size and more excellentsystem performance can be obtained under the base station cacheable system capable of adapting to higher-rate transmission by using the clustering method provided by the invention.

The invention discloses a multi-scale fusion network simulation task mapping method in a heterogeneous environment, which solves the deployment problem of a virtual network topology in a heterogeneous computing cluster environment. The steps of the method include: reading into a heterogeneous computing environment; Mark the edge routers and host nodes in the topology as lightweight virtualization mapping areas, and mark the remaining nodes as converged virtualization mapping areas; according to the throughput threshold of each server, use lightweight virtualization mapping for lightweight virtualization mapping Nodes in the area; calculate the load balance parameters of the remaining servers, use the multi-level graph partition algorithm to allocate nodes in the fusion mapping area, judge whether the server is redundant, and use different optimization algorithms to optimize and map reasonably according to the results. The invention ensures load balance between computing clusters, reduces remote communication, improves the performance of large-scale network simulation, and has good scalability and scalability for large-scale network topology, and can be used for various network research and experimental networks.

The invention discloses a storage optimization-based distributed graph processing method, and belongs to the field of graph calculation. The method comprises the following steps of: carrying out data partitioning in a data pre-processing stage; distributing graph partition data; starting data iteration processing; updating message transfer; making a work node extension decision; and ending the data processing. According to the method, a consistency hash algorithm is proposed to partition and store graph data, and an external storage mode-based distributed graph processing system is designed and realized; and by utilizing a dynamic storage optimization strategy, graph data processing load balance is realized according to partition storage of load adjustment graphs, so that the graph data processing speed is improved, the problem that the overall performance is reduced as hotspots are caused by load imbalance in the graph data processing process in the prior art is solved, and then the graph processing performance is improved.

The present invention relates to a game-based method and system for streaming-graph partitioning, the method comprises: partitioning a streaming graph using one or more processors, the one or more processors being configured to: read an edge streaming having a predetermined number of edges in an unpartitioned area of the streaming graph as a sub-graph; based on a first pre-partitioning model, pre-partition the edges of the sub-graph to at least two partition blocks as an initial state of a game process; and sequentially select an optimal partition block for each edge of the sub-graph through the game process until the game process becomes convergent, the disclosed method and system can partition streaming graph using local information only, without loading the whole streaming graph into the memory, thus have good scalability and support dynamic graph partitioning; the disclosed partitioning method and system can provide better partitioning results.

The present application relates to a method, system, device, and storage medium for counting the number of vertices and edges in a graph database, wherein the method includes: obtaining a task request for counting the number of vertices and edges in the graph space, and checking the preset preparation queue in the preparation queue according to the task request. Task, returns the ID of the preset preparatory task, writes the information record of the preset preparatory task in the system table of the preset preparatory task according to the ID of the preset preparatory task, and writes the graph in the system table of statistical information according to the ID of the graph space For spatial information records, the preset preparatory tasks are grouped according to the Leader node to which the graph partition belongs, and several preset execution tasks are obtained, and the preset execution tasks are run through the storage node. It solves the problem of how to reduce the waste of computing resources and improve the efficiency of real-time statistical data, and realizes an efficient parallel strategy for point-edge statistical tasks based on the job mechanism and task mechanism in Nebula Graph.

The invention discloses a CAD data processing device and a CAD data processing method. Specifically, the invention relates to the field of computers, the device comprises a graph scanning module, a graph partitioning module, a graph extraction module, a graph locking module, a graph merging module and a graph unlocking module, the graphic scanning module comprises a graphic scanning unit; the graph partitioning module comprises a graph partitioning unit; wherein the graph extraction module comprises a graph layer new establishment unit and a graph copy unit, the graph locking module comprises a graph locking unit, the graph merging module comprises a graph merging unit and a graph layer deletion unit, and the graph unlocking module comprises a graph unlocking unit and a graph storage unit. A graph is scanned through the graph scanning module, partition is conducted through the graph partition module, a graph area needing to be modified is extracted through the graph extraction module, an area not needing to be modified is locked through the graph locking module, and the safety of the system is higher on the whole.

Embodiments of the invention relate to data archiving on storage medium such as magnetic tapes based on graph partitioning. One aspect of the invention concerns a method that comprises representing a file system as a graph where each node of the graph represents a file and each edge represents file chunks common to the files corresponding to the nodes connected by the edge. The graph is repeatedly partitioned into disjoint sub-graphs. If the files and duplicate file chunks associated with a sub-graph fit into a data storage medium, then the files and duplicate file chunks are stored in the medium. Otherwise, the method may partition the sub-graph into smaller disjoint sub-graphs taking into consideration of degrees of connectivity of the nodes.

The invention discloses a block-based subgraph construction and distributed graph processing method. The block-based subgraph construction method comprises partitioning a graph, relabeling summits in the graph, associating intervals with shards, partitioning blocks and constructing subgraphs, and employs a heuristic and lightweight SGP (Streaming Graph Partition) method to partition a graph, and a user-defined heuristic function to designate the summits to P subgraphs in order; the method possesses the characteristics of high performance and low edge cutting rate, and considers subgraph work load balance. According to a distributed graph processing system, after partitioning, subgraphs perform communication by employing a whole memory block as a unit; compared with the fine grit communication mode of the prior art, the distributed graph processing system exchanges data based on a memory block, and can fully utilize network bandwidth and reduce communication time.

The invention discloses a large-scale entity alignment method based on bidirectional graph partition and reciprocal reasoning. The method comprises the following steps: acquiring data of a source knowledge graph and a target knowledge graph; performing graph partition on the source knowledge graph and the target knowledge graph to obtain a group of sub-graph pairs of source sub-graphs and target sub-graphs; obtaining joint entity representation in all the sub-graph pairs by utilizing a representation learning model of an entity structure; performing reciprocal alignment reasoning on sub-graphs in the sub-graph pairs to obtain alignment results of the sub-graph pairs; and aggregating the alignment results of all the sub-graph pairs to obtain an alignment result of the source knowledge graph and the target knowledge graph. According to the method provided by the invention, through bidirectional partition and aggregation, the final sub-graph pairs can have a more complete structure and more seed entity pairs, so that a more accurate entity alignment result can be generated; and compared with traditional direct alignment reasoning, two-stage reciprocal modeling of reciprocal reasoning can obtain a better alignment effect.