CN109359156B - Data storage structure processing method and device - Google Patents
Data storage structure processing method and device Download PDFInfo
- Publication number
- CN109359156B CN109359156B CN201810925045.8A CN201810925045A CN109359156B CN 109359156 B CN109359156 B CN 109359156B CN 201810925045 A CN201810925045 A CN 201810925045A CN 109359156 B CN109359156 B CN 109359156B
- Authority
- CN
- China
- Prior art keywords
- vertex
- edge
- adjacency list
- field
- pointing
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 238000003672 processing method Methods 0.000 title claims abstract description 23
- 238000013500 data storage Methods 0.000 title claims abstract description 22
- 238000000034 method Methods 0.000 claims abstract description 38
- 238000012545 processing Methods 0.000 claims description 17
- 230000008569 process Effects 0.000 claims description 14
- 230000009191 jumping Effects 0.000 claims description 13
- 230000004048 modification Effects 0.000 claims description 11
- 238000012986 modification Methods 0.000 claims description 11
- 238000002910 structure generation Methods 0.000 claims description 7
- 230000008520 organization Effects 0.000 abstract description 4
- 239000011159 matrix material Substances 0.000 description 15
- 238000010586 diagram Methods 0.000 description 14
- 230000006870 function Effects 0.000 description 9
- 238000012217 deletion Methods 0.000 description 5
- 230000037430 deletion Effects 0.000 description 5
- 238000004590 computer program Methods 0.000 description 4
- 230000002085 persistent effect Effects 0.000 description 4
- UPPMZCXMQRVMME-UHFFFAOYSA-N valethamate Chemical compound CC[N+](C)(CC)CCOC(=O)C(C(C)CC)C1=CC=CC=C1 UPPMZCXMQRVMME-UHFFFAOYSA-N 0.000 description 4
- 239000010410 layer Substances 0.000 description 3
- 230000003287 optical effect Effects 0.000 description 3
- 239000002356 single layer Substances 0.000 description 3
- 238000003491 array Methods 0.000 description 2
- 230000008901 benefit Effects 0.000 description 2
- 230000011218 segmentation Effects 0.000 description 2
- 238000007792 addition Methods 0.000 description 1
- 239000002355 dual-layer Substances 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
- 238000004880 explosion Methods 0.000 description 1
- 238000003780 insertion Methods 0.000 description 1
- 230000037431 insertion Effects 0.000 description 1
- 230000002441 reversible effect Effects 0.000 description 1
- 239000004065 semiconductor Substances 0.000 description 1
- 230000003068 static effect Effects 0.000 description 1
- 230000002123 temporal effect Effects 0.000 description 1
Images
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
A data storage structure processing method and organization are disclosed, the method comprising: generating a vertex structure, wherein the vertex structure comprises an edge pointing field pointing to an edge to which the vertex belongs; and generating an edge structure comprising a vertex pointing field pointing to the edge containing the vertex. The vertex structure can form a vertex adjacency list, the edge structure can form an edge adjacency list, and the vertex structure and the edge structure form a multi-stage adjacency list. Therefore, the invention adopts a data organization scheme of the multi-level adjacency list to accurately model and describe the multi-dimensional association relation between the vertexes. The multi-level adjacency list abandons the relation between the points in the traditional adjacency list, and the relation between the points and the edges is used as a structural basis, so that the multi-dimensionality of the data relation is also kept on the basis of ensuring convenient access.
Description
Technical Field
The present invention relates to data structures, and in particular, to a method and an apparatus for processing a data storage structure.
Background
In the present day that data explosion type growth and connection between things are more and more complex, the appearance of graph structures enables people to simply and intuitively simulate the relation between things.
The adjacency matrix is a common stored representation that represents a graph. It uses two arrays to store information on data elements (vertices) and relationships (edges or arcs) between data elements, respectively. Fig. 1A shows an example of representing a connection relationship between data elements using an adjacency matrix. For example, as shown in 1A, a 1 in the adjacency matrix on the right indicates a connection between data elements, and a 0 indicates no connection. Further, in case that a connection has a weight, the value of 1 may be replaced by the corresponding weight. Since the adjacency matrix needs to allocate a value for each possible connection, the storage space required for the adjacency matrix is large, especially in the case of a sparse matrix where the connections are relatively simple.
Adjacency lists are a way of organizing the data of a graph so that arbitrary vertices or edges can be accessed (i.e., directly accessed) within the temporal complexity of O (1). Fig. 1B shows an example of representing a connection relationship between data elements using an adjacency matrix. For example, as shown in fig. 1B, it is possible to conveniently access its neighboring nodes through one vertex, and compared with an adjacency graph in the form of a matrix (especially a sparse matrix with relatively simple relationship), the adjacency graph has less space and less access complexity, which makes the adjacency list more favored in data organization structure.
However, as the relation between things is more and more dimensional, the adjacency list which can only represent the relation between two points cannot meet the requirement of data storage in many cases. If there are three or more vertices linked together by some relation, the common adjacency list can only be modeled by building a complete graph among the vertices, but this method not only causes a sharp increase in data storage amount, but also loses the original relationship between the vertices.
Therefore, a new data storage structure that can facilitate multi-dimensional associations between data elements is needed.
Disclosure of Invention
In order to solve at least one problem, the invention adopts a data organization scheme of a multi-level adjacency list to accurately model and describe the multi-dimensional association relation between vertexes. The multi-level adjacency list abandons the relation between the points in the traditional adjacency list, and the relation between the points and the edges is used as a structural basis, so that the multi-dimensionality of the data relation is also kept on the basis of ensuring convenient access.
According to an aspect of the present invention, a data storage structure processing method is provided, including: generating a vertex structure, wherein the vertex structure comprises an edge pointing field pointing to an edge to which the vertex belongs; and generating an edge structure comprising a vertex pointing field pointing to the edge containing the vertex. Here, the vertices may indicate data elements and the edges may indicate relationships between the data elements. Thus, an efficient representation of the multi-dimensional data structure is achieved by cross-correlation of vertices and edges.
Specifically, the edge-pointing field of the vertex structure may include a head node of a linked list composed of a set of edges to which the vertex belongs; and the vertex pointing field of the edge structure may include the head node of a linked list of all vertices contained by the edge. Therefore, the mutual jumping of the vertex and the edge is facilitated.
Preferably, the generated vertex structure includes a vertex structure identifier field uniquely identifying the vertex structure, and a vertex structure meta-information field storing the vertex attribute information; and the generated edge structure comprises an edge structure identifier field for uniquely identifying the edge structure and an edge structure meta information field for indicating attribute information of the edge. The vertex structure meta information field may include at least one of: weight information of the vertex; description information of the vertex; custom information, and the edge structure meta-information field includes at least one of: weight information of the edge; description information of the edge; and (5) self-defining information. This enables rational storage of the required information in the most efficient data structure.
Preferably, the processing method may further include: forming a vertex adjacency list structure by using the generated plurality of vertex structures; and forming an edge adjacency list structure by using the generated plurality of edge structures, thereby constructing a multi-dimensional relationship through two layers of adjacency lists and preventing data loss of a single-layer adjacency list.
Preferably, the processing method may further include adding a new structure, and specifically, may include: adding a new vertex structure to the vertex adjacency list structure, wherein the edges to which the vertices belong comprise existing edges; based on the edge structure indication field of the new vertex structure, adding information of the new vertex structure to a vertex pointing field of an existing edge structure to which the new vertex structure belongs, and/or adding a new edge structure to the edge adjacency list structure, wherein the vertex contained in the edge comprises the existing vertex; and adding the information of the new edge structure to the edge pointing field of the existing vertex structure contained in the new edge structure.
Preferably, the processing method may further include deleting the existing structure, and specifically, may include: deleting an existing vertex structure from the vertex adjacency list structure; deleting the indication of the deleted vertex structure in the edge structure of the edge to which the deleted vertex belongs and/or deleting the existing edge structure from the edge adjacency list structure based on the edge structure indication field of the deleted vertex structure; and deleting the indication of the deleted edge structure in the vertex structure of which the deleted edge comprises the vertex based on the vertex structure indication field of the deleted edge structure.
Preferably, the processing method may further include searching for a specific structure, and specifically, may include: directly searching a corresponding vertex structure in the vertex adjacency list structure based on a vertex identifier; directly jumping to the edge structure of the edge to which the vertex belongs in the edge adjacency list structure based on the edge structure pointing field of the vertex structure, and/or directly searching the corresponding edge structure in the edge adjacency list structure based on the edge identifier; and directly jumping to the vertex structure of which the edge contains the vertex based on the vertex structure pointing field of the edge structure.
Preferably, the processing method may further include performing list traversal using any vertex or edge as an entry, and specifically, may include: directly searching a corresponding vertex structure in the vertex adjacency list structure based on the obtained arbitrary vertex identifier; accessing vertex structure meta information of the vertex; judging whether the edge structure of each edge to which the vertex belongs is accessed or not based on the edge identifier contained in the edge structure pointing field of the vertex structure; skipping over the edge structure if the access is over, otherwise skipping over to the edge structure; accessing the edge structure meta information of the edge structure jumped to; judging whether the vertex structure of each vertex contained in the edge is accessed or not based on the vertex identifier contained in the vertex structure pointing field of the edge structure; if the access is over, skipping the vertex structure, otherwise, skipping to the vertex structure; repeating the above process until each item in the vertex adjacency list structure and the edge adjacency list structure is accessed, and/or directly searching the corresponding edge structure in the edge adjacency list structure based on the obtained arbitrary edge identifier; accessing edge structure meta information of the edge; judging whether the vertex structure of each vertex contained in the edge is accessed or not based on the vertex identifier contained in the vertex structure pointing field of the edge structure; if the access is over, skipping the vertex structure, otherwise, skipping to the vertex structure; accessing the vertex structure meta information of the vertex structure jumped to; judging whether the edge structure of each edge to which the vertex belongs is accessed or not based on the edge identifier contained in the edge structure pointing field of the vertex structure; skipping over the edge structure if the access is over, otherwise skipping over to the edge structure; the above process is repeated until each entry in the edge adjacency table structure and the vertex adjacency table structure is accessed.
According to another aspect of the present invention, there is provided a data storage structure processing apparatus, including: vertex structure generating means for generating a vertex structure including an edge pointing field pointing to an edge to which the vertex belongs; and edge structure generating means for generating an edge structure including a vertex pointing field pointing to the edge containing a vertex.
The edge-pointing field of the vertex structure generated by the vertex structure generation means may comprise the head node of a linked list consisting of the set of edges to which the vertex belongs. The vertices may indicate data elements. The vertex structure may include a vertex structure identifier field that uniquely identifies the vertex structure, and a vertex structure meta-information field that stores the vertex attribute information. Specifically, the vertex structure meta information field may include at least one of: weight information of the vertex; description information of the vertex; and custom information.
On the other hand, the vertex pointing field of the edge structure generated by the edge structure generating means may include the head node of the linked list composed of all the vertices contained by the edge. Edges may indicate relationships between data elements. The edge structure may include an edge structure identifier field that uniquely identifies the edge structure, and an edge structure meta information field that indicates attribute information for the edge. In particular, the edge structure meta information field may include at least one of: weight information of the edge; description information of the edge; and custom information.
In another embodiment, the vertex structure generating means and the edge structure generating means may be included in the adjacency list structure generating means. Further, the adjacency list structure generating means may be configured to construct a vertex adjacency list structure using the generated plurality of vertex structures; and constructing an edge adjacency list structure using the generated plurality of edge structures. Preferably, the adjacency list structure generating means may include vertex adjacency list generating means and edge adjacency list generating means, respectively. The vertex adjacency table generating means may function as vertex structure generating means to generate each vertex structure item by item, and compose the generated vertex structures into a vertex adjacency table. Accordingly, the edge adjacency list generation means may function as edge structure generation means to generate each edge structure item by item, and compose the generated edge structures into the edge adjacency list.
The processing means may further comprise adjacency list structure modification means for modifying the adjacency list structure, and in particular may be configured to add a new vertex structure to the vertex adjacency list structure, the edge to which the vertex belongs including an existing edge; based on the edge structure indication field of the new vertex structure, adding information of the new vertex structure to a vertex pointing field of an existing edge structure to which the new vertex structure belongs, and/or adding a new edge structure to the edge adjacency list structure, wherein the vertex contained in the edge comprises the existing vertex; and adding the information of the new edge structure to the edge pointing field of the existing vertex structure contained in the new edge structure. In other embodiments, the adjacency list structure modification means may further comprise sub-means for modifying the vertex and edge structures, respectively.
In one embodiment, the adjacency list structure modification means may also be adapted to delete an existing structure. Specifically, the adjacency list structure modification apparatus may be further configured to: deleting an existing vertex structure from the vertex adjacency list structure; deleting the indication of the deleted vertex structure in the edge structure of the edge to which the deleted vertex belongs and/or deleting the existing edge structure from the edge adjacency list structure based on the edge structure indication field of the deleted vertex structure; and deleting the indication of the deleted edge structure in the vertex structure of which the deleted edge comprises the vertex based on the vertex structure indication field of the deleted edge structure.
The processing means may further comprise adjacency list structure lookup means for looking up a specific structure, and specifically, may directly look up a corresponding vertex structure in the vertex adjacency list structure based on a vertex identifier; directly jumping to the edge structure of the edge to which the vertex belongs in the edge adjacency list structure based on the edge structure pointing field of the vertex structure, and/or directly searching the corresponding edge structure in the edge adjacency list structure based on the edge identifier; and directly jumping to the vertex structure of which the edge contains the vertex based on the vertex structure pointing field of the edge structure.
The adjacency list structure lookup means may be included in the adjacency list traversal means, which has a structure lookup function and may traverse the MAL, and the traversal may start from any vertex structure or edge structure. In particular, the adjacency list traversal apparatus may be configured to: directly searching a corresponding vertex structure in the vertex adjacency list structure based on the obtained arbitrary vertex identifier; accessing vertex structure meta information of the vertex; judging whether the edge structure of each edge to which the vertex belongs is accessed or not based on the edge identifier contained in the edge structure pointing field of the vertex structure; skipping over the edge structure if the access is over, otherwise skipping over to the edge structure; accessing the edge structure meta information of the edge structure jumped to; judging whether the vertex structure of each vertex contained in the edge is accessed or not based on the vertex identifier contained in the vertex structure pointing field of the edge structure; if the access is over, skipping the vertex structure, otherwise, skipping to the vertex structure; repeating the above process until each item in the vertex adjacency list structure and the edge adjacency list structure is accessed, and/or directly searching the corresponding edge structure in the edge adjacency list structure based on the obtained arbitrary edge identifier; accessing edge structure meta information of the edge; judging whether the vertex structure of each vertex contained in the edge is accessed or not based on the vertex identifier contained in the vertex structure pointing field of the edge structure; if the access is over, skipping the vertex structure, otherwise, skipping to the vertex structure; accessing the vertex structure meta information of the vertex structure jumped to; judging whether the edge structure of each edge to which the vertex belongs is accessed or not based on the edge identifier contained in the edge structure pointing field of the vertex structure; skipping over the edge structure if the access is over, otherwise skipping over to the edge structure; the above process is repeated until each entry in the edge adjacency table structure and the vertex adjacency table structure is accessed.
According to yet another aspect of the invention, there is provided a computing device comprising: a processor; and a memory having executable code stored thereon, which when executed by the processor, causes the processor to perform the method of any of the above.
According to yet another aspect of the invention, a non-transitory machine-readable storage medium is presented having executable code stored thereon, which when executed by a processor of an electronic device, causes the processor to perform the method of any of the above.
The invention adopts a brand new MAL (multilevel adjacency list) data structure. The MAL structure abandons the mode of establishing the connection between the points of the traditional adjacency list, and instead adopts the connection between the points and the edges to establish a data structure, and the multi-dimensional relation is established through two layers of adjacency lists, so that the data loss of a single-layer adjacency list is prevented. MAL is implemented using a linked list infrastructure, and the operations of adding, finding, and deleting vertices or edges can also be accomplished within O (1) time complexity. In addition, only the id of the vertex or the edge can be stored in the relation chain table, and data redundancy is avoided. Compared with a point-to-edge relation matrix (particularly a sparse matrix), the MAL which only stores effective association information can greatly save storage space.
Drawings
The above and other objects, features and advantages of the present disclosure will become more apparent by describing in greater detail exemplary embodiments thereof with reference to the attached drawings, in which like reference numerals generally represent like parts throughout.
Fig. 1A and 1B show an example of representing a connection relationship between data elements using an existing adjacency matrix and adjacency table.
FIG. 2 is a flow diagram illustrating a data storage structure processing method according to an embodiment of the invention.
FIG. 3 illustrates an example of a vertex adjacency list structure according to one embodiment of the invention.
FIG. 4 shows an example of an edge adjacency list structure according to an embodiment of the invention.
Fig. 5 shows a hypergraph structure as described by the examples of fig. 3 and 4.
Fig. 6 shows a flow diagram of a data processing method according to another embodiment of the invention.
Fig. 7 shows a schematic diagram of a data processing device according to an embodiment of the invention.
Fig. 8 shows a schematic diagram of a data processing device according to another embodiment of the invention.
Fig. 9 is a schematic structural diagram of a computing device that can be used to implement the data storage structure processing method according to an embodiment of the present invention.
Detailed Description
Preferred embodiments of the present disclosure will be described in more detail below with reference to the accompanying drawings. While the preferred embodiments of the present disclosure are shown in the drawings, it should be understood that the present disclosure may be embodied in various forms and should not be limited to the embodiments set forth herein. Rather, these embodiments are provided so that this disclosure will be thorough and complete, and will fully convey the scope of the disclosure to those skilled in the art.
As described above, neither the existing adjacency matrices nor adjacency lists efficiently represent multidimensional connections between things. For this reason, a data structure capable of representing multidimensional relationships between nodes is required.
In order to meet the convenience of storing and accessing multidimensional relationships between nodes, the following problems need to be solved: (1) the data is convenient to construct, and the addition and deletion of nodes or edges are required to be completed within O (1) time complexity; (2) the relation between the nodes is searched quickly, and the requirement is not lower than the complexity of searching and traversing of a common adjacency list; (3) the multidimensional relation between the nodes is effectively reserved, and effective information is not lost; (4) no storage space is wasted, especially in sparse relationships. Therefore, the invention considers that the data structure of the multi-level adjacency list is adopted to ensure the integrity of the effective information and the access convenience. For convenience of description, the multi-level adjacency list may also be referred to as mal (multilayered adjacency list) for short.
Different from the relationship between points constructed by a common adjacency list, the two ends of the MAL relationship are respectively a vertex and an edge, all the edges to which the vertex belongs are associated through the vertex, and all the vertices contained in the edges are associated through the edges to form a multi-level adjacency list. Therefore, the multidimensional data relation is also reserved on the basis of ensuring convenient access.
FIG. 2 is a flow diagram illustrating a data storage structure processing method according to an embodiment of the invention. More specifically, the method may be a method of generating a multi-level adjacency list according to the present invention.
In step S210, a vertex structure is generated, which includes an edge-pointing field pointing to the edge to which the vertex belongs. In step S220, an edge structure is generated that includes a vertex pointing field that points to the edge containing a vertex. Thus, by introducing a point field, it is convenient to associate points and edges.
The MAL of the invention has two basic data structures, namely a vertex structure and an edge structure, which respectively maintain a link relation taking the vertex or the edge as an entrance. In particular, the edge-pointing field of the vertex structure may include the head node of a linked list composed of the set of edges to which the vertex belongs. The vertex pointing field of the edge structure may then include the head node of the linked list of all vertices contained by the edge.
Further, the generated vertex structure may include a vertex structure identifier field that uniquely identifies the vertex structure, and a vertex structure meta-information field that stores the vertex attribute information. The generated edge structure may include an edge structure identifier field that uniquely identifies the edge structure, and an edge structure meta information field that indicates attribute information of the edge. Here, the vertices may indicate data elements, and the edges may indicate relationships between the data elements.
In one embodiment, a single vertex structure may be, for example, as follows:
| vid | Meta | EdgeArcHead |
the data structure for a single vertex contains a total of three fields: the first field identifies the id (vertex identifier vid) of the vertex, which is the unique identifier of the vertex in the MAL; the second field is Meta (Meta information) information of the vertex, which may include information such as vertex weight and description, or may be customized by the user; the third field is the head node EdgeArcHead of the linked list consisting of the set of edges to which the vertex belongs, through which all the edges to which the vertex belongs can be accessed.
All vertex structures are combined to form an adjacency list structure VList with vertices as entries. FIG. 3 shows an example of a vertex adjacency table structure according to an embodiment of the invention, where v (vertex) represents a vertex and e (edge) represents an edge.
As shown in FIG. 3, the vertex adjacency list can be used to conveniently find the edge to which the vertex belongs, and preferably, only the id information of the edge is stored in the edge structure linked with the EdgeArcHead, and more data related to the edge is stored in a separate edge structure.
In one embodiment, the single edge structure may be, for example, as follows:
| eid | Meta | VertexArcHead |
the data structure of a single edge is preferably similar to that of a single vertex, also containing three fields: the first field marks the id of the edge, which is the unique identifier of the edge in the MAL; the second field is that the Meta information of the edge can contain information such as the weight and description of the edge, and can also be customized by the user; the third field is the head node VertexArcHead of the linked list of all vertices contained by the edge, linking all vertices within the edge.
Combining all edges together, it is also possible to form an adjacency list Elist, which takes an edge as an entry and links the ids of all relevant vertices of all edges. FIG. 4 illustrates an example of a vertex adjacency list structure according to one embodiment of the invention.
Combining the vertex-entered adjacency list Vlist and the edge-entered adjacency list Elist forms the final multi-level adjacency list MAL. The multi-level adjacency list MAL can effectively describe the multi-dimensional relationship shown in fig. 5. Fig. 5 shows a hypergraph structure as described by the examples of fig. 3 and 4. In fig. 5, multiple vertices are linked together because of a uniform relationship, and a data structure that is easy to access and invoke is needed to model such multidimensional relationships. The MAL completely stores the multidimensional relation between the vertexes in a data structure, so that the multidimensional relation can be accurately obtained by using algorithms such as clustering and recommending on the basis of the MAL, and the accuracy of the result is guaranteed.
In the hypergraph structure shown in fig. 5 representing a multidimensional relationship, MAL can effectively improve the search efficiency of hierarchical segmentation. The insertion and deletion operations of the top point and the side of the time complexity of the MAL constant can effectively improve the efficiency of node dynamic adjustment in the segmentation process.
Specifically, the data storage structure processing method of the present invention may further include the addition of a vertex structure and an edge structure. Preferably, the method may comprise: adding a new vertex structure to the vertex adjacency list structure, wherein the edges to which the vertices belong comprise existing edges; based on the edge structure indication field of the new vertex structure, adding information of the new vertex structure to a vertex pointing field of an existing edge structure to which the new vertex structure belongs, and/or adding a new edge structure to the edge adjacency list structure, wherein the vertex contained in the edge comprises the existing vertex; and adding the information of the new edge structure to the edge pointing field of the existing vertex structure contained in the new edge structure. Thus, the addition of a new structure can be conveniently realized.
The data storage structure processing method of the present invention may further include deletion of a vertex structure and an edge structure. Preferably, the method may comprise: deleting an existing vertex structure from the vertex adjacency list structure; deleting the indication of the deleted vertex structure in the edge structure of the edge to which the deleted vertex belongs and/or deleting the existing edge structure from the edge adjacency list structure based on the edge structure indication field of the deleted vertex structure; and deleting the indication of the deleted edge structure in the vertex structure of which the deleted edge comprises the vertex based on the vertex structure indication field of the deleted edge structure. Therefore, the existing structure can be deleted conveniently.
The above deletion of existing structures and addition of new structures may belong to the modification step to MAL. The modifying step may also include modification of specific fields of an existing structure.
In addition, the MAL structure of the invention is convenient for searching the vertex structure and the edge structure. Preferably, the method may comprise: directly searching a corresponding vertex structure in the vertex adjacency list structure based on a vertex identifier; directly jumping to the edge structure of the edge to which the vertex belongs in the edge adjacency list structure based on the edge structure pointing field of the vertex structure, and/or directly searching the corresponding edge structure in the edge adjacency list structure based on the edge identifier; and directly jumping to the vertex structure of which the edge contains the vertex based on the vertex structure pointing field of the edge structure.
From the above, the searching, adding and deleting operations of the MAL on the nodes or edges are all kept at the same level as the traditional adjacency list (the adding, searching and deleting operations of the vertices or edges in the MAL structure can be completed within the O (1) time complexity as well), so that the multidimensional relationship between the nodes is effectively preserved; and the basic structure of the linked list also ensures the absolute advantage of the MAL in comparison with the adjacent matrix in terms of access efficiency and storage space.
Further, the MAL of the present invention can conveniently implement traversal. In one embodiment, when the vertex is taken as an entry, the data storage structure processing method of the present invention may further include: directly searching a corresponding vertex structure in the vertex adjacency list structure based on the obtained arbitrary vertex identifier; accessing vertex structure meta information of the vertex; judging whether the edge structure of each edge to which the vertex belongs is accessed or not based on the edge identifier contained in the edge structure pointing field of the vertex structure; skipping over the edge structure if the access is over, otherwise skipping over to the edge structure; accessing the edge structure meta information of the edge structure jumped to; judging whether the vertex structure of each vertex contained in the edge is accessed or not based on the vertex identifier contained in the vertex structure pointing field of the edge structure; if the access is over, skipping the vertex structure, otherwise, skipping to the vertex structure; the above process is repeated until each entry in the vertex adjacency table structure and the edge adjacency table structure is accessed.
In one embodiment, when the edge is used as an entry, the data storage structure processing method of the present invention may further include: directly searching a corresponding edge structure in the edge adjacency list structure based on the acquired arbitrary edge identifier; accessing edge structure meta information of the edge; judging whether the vertex structure of each vertex contained in the edge is accessed or not based on the vertex identifier contained in the vertex structure pointing field of the edge structure; if the access is over, skipping the vertex structure, otherwise, skipping to the vertex structure; accessing the vertex structure meta information of the vertex structure jumped to; judging whether the edge structure of each edge to which the vertex belongs is accessed or not based on the edge identifier contained in the edge structure pointing field of the vertex structure; skipping over the edge structure if the access is over, otherwise skipping over to the edge structure; the above process is repeated until each entry in the edge adjacency table structure and the vertex adjacency table structure is accessed.
Specifically, in the case of the MAL composed of the previous Vlist and Elist, the MAL traversal process is as follows (taking depth-first traversal of vertex entry as an example):
i) acquiring a vertex id, and acquiring the entry position of the vertex in the Vlist through the id;
ii) accessing Meta information for the vertex;
iii) acquiring a linked list of all edges to which the vertex belongs through the EdgeArcHead of the vertex;
iv) traversing the EdgeArcHead linked list, acquiring the id of the corresponding edge of each edge node in the linked list, and continuing to obtain the next edge node if the edge has been visited;
v) acquiring the entry position of the edge in Elist according to the id of the edge;
vi) accessing Meta information of the edge;
vii) acquiring a linked list of all vertexes contained in the edge through the VertexArcHead of the edge;
viii) traversing the VertexArcHead linked list, acquiring a vertex id corresponding to each node in the linked list, and if the vertex has been visited, continuing to obtain the next node of the linked list;
ix) returning to the step i according to the acquired vertex id; until the end.
Fig. 6 shows a flow diagram of a data processing method according to another embodiment of the invention. At step S610, an MAL comprising a vertex adjacency table and an edge adjacency table may be constructed as described above. Subsequently, the constructed MAL may be modified in step S620 (e.g., for addition or deletion or modification of vertices and/or edges), may be subjected to processing that does not involve content changes in step S630, such as a query, or traversal processing that includes a query, and so on.
The data structure processing method according to the present invention is described above based on fig. 2 to 6. A data structure processing device according to the present invention will be described below in conjunction with fig. 7-8.
Fig. 7 shows a schematic diagram of a data processing device according to an embodiment of the invention. As shown in fig. 7, the processing means 700 may comprise vertex structure generating means 710 and edge structure generating means 720. The vertex structure generating means 710 may generate a vertex structure comprising an edge pointing field pointing to an edge to which the vertex belongs, and the edge structure generating means 720 may generate an edge structure comprising a vertex pointing field pointing to an edge containing a vertex.
Similarly to the above, the edge-pointing field of the vertex structure generated by the vertex structure generating means 710 may include the head node of the linked list consisting of the set of edges to which the vertex belongs. The vertices may indicate data elements. The vertex structure may include a vertex structure identifier field that uniquely identifies the vertex structure, and a vertex structure meta-information field that stores the vertex attribute information. Specifically, the vertex structure meta information field may include at least one of: weight information of the vertex; description information of the vertex; and custom information.
On the other hand, the vertex pointing field of the edge structure generated by the edge structure generating means 720 may include the head node of the linked list composed of all the vertices contained by the edge. Edges may indicate relationships between data elements. The edge structure may include an edge structure identifier field that uniquely identifies the edge structure, and an edge structure meta information field that indicates attribute information for the edge. In particular, the edge structure meta information field may include at least one of: weight information of the edge; description information of the edge; and custom information.
In another embodiment, the vertex structure generating means and the edge structure generating means may be included in the adjacency list structure generating means. Further, the adjacency list structure generating means may be configured to construct a vertex adjacency list structure using the generated plurality of vertex structures; and constructing an edge adjacency list structure using the generated plurality of edge structures. Preferably, the adjacency list structure generating means may include vertex adjacency list generating means and edge adjacency list generating means, respectively. The vertex adjacency table generating means may function as vertex structure generating means to generate each vertex structure item by item, and compose the generated vertex structures into a vertex adjacency table. Accordingly, the edge adjacency list generation means may function as edge structure generation means to generate each edge structure item by item, and compose the generated edge structures into the edge adjacency list.
FIG. 8 shows a schematic diagram of a data storage structure processing apparatus according to an embodiment of the invention. The processing means 800 may optionally comprise means for performing various processing on the generated adjacency list, in addition to the adjacency list structure (MAL) generating means 810 described above.
In one embodiment, the processing apparatus 800 further comprises an adjacency list structure (MAL) modification apparatus 820 configured to modify an adjacency list structure, and in particular, configured to add a new vertex structure to the vertex adjacency list structure, where the edge to which the vertex belongs includes an existing edge; based on the edge structure indication field of the new vertex structure, adding information of the new vertex structure to a vertex pointing field of an existing edge structure to which the new vertex structure belongs, and/or adding a new edge structure to the edge adjacency list structure, wherein the vertex contained in the edge comprises the existing vertex; and adding the information of the new edge structure to the edge pointing field of the existing vertex structure contained in the new edge structure. In other embodiments, the MAL modifying means 820 may further comprise sub-means for modifying vertex and edge structures, respectively.
In one embodiment, the MAL modifying means 820 may also be used to delete existing structures. Specifically, the MAL modifying apparatus 820 may further be configured to: deleting an existing vertex structure from the vertex adjacency list structure; deleting the indication of the deleted vertex structure in the edge structure of the edge to which the deleted vertex belongs and/or deleting the existing edge structure from the edge adjacency list structure based on the edge structure indication field of the deleted vertex structure; and deleting the indication of the deleted edge structure in the vertex structure of which the deleted edge comprises the vertex based on the vertex structure indication field of the deleted edge structure.
In other embodiments, the MAL modifying means 820 may also modify specific fields of the existing structure.
In one embodiment, the processing apparatus 800 further comprises an adjacency list structure (MAL) lookup apparatus 830 for performing lookup on a specific structure, and specifically, may directly lookup a corresponding vertex structure in the vertex adjacency list structure based on a vertex identifier; directly jumping to the edge structure of the edge to which the vertex belongs in the edge adjacency list structure based on the edge structure pointing field of the vertex structure, and/or directly searching the corresponding edge structure in the edge adjacency list structure based on the edge identifier; and directly jumping to the vertex structure of which the edge contains the vertex based on the vertex structure pointing field of the edge structure.
In one embodiment, the MAL lookup means 830 may be included in an adjacency list traversal means having a structure lookup function and being capable of traversing the MAL, which may start from any vertex structure or edge structure. In particular, the adjacency list traversal apparatus may be configured to: directly searching a corresponding vertex structure in the vertex adjacency list structure based on the obtained arbitrary vertex identifier; accessing vertex structure meta information of the vertex; judging whether the edge structure of each edge to which the vertex belongs is accessed or not based on the edge identifier contained in the edge structure pointing field of the vertex structure; skipping over the edge structure if the access is over, otherwise skipping over to the edge structure; accessing the edge structure meta information of the edge structure jumped to; judging whether the vertex structure of each vertex contained in the edge is accessed or not based on the vertex identifier contained in the vertex structure pointing field of the edge structure; if the access is over, skipping the vertex structure, otherwise, skipping to the vertex structure; repeating the above process until each item in the vertex adjacency list structure and the edge adjacency list structure is accessed, and/or directly searching the corresponding edge structure in the edge adjacency list structure based on the obtained arbitrary edge identifier; accessing edge structure meta information of the edge; judging whether the vertex structure of each vertex contained in the edge is accessed or not based on the vertex identifier contained in the vertex structure pointing field of the edge structure; if the access is over, skipping the vertex structure, otherwise, skipping to the vertex structure; accessing the vertex structure meta information of the vertex structure jumped to; judging whether the edge structure of each edge to which the vertex belongs is accessed or not based on the edge identifier contained in the edge structure pointing field of the vertex structure; skipping over the edge structure if the access is over, otherwise skipping over to the edge structure; the above process is repeated until each entry in the edge adjacency table structure and the vertex adjacency table structure is accessed.
Fig. 9 is a schematic structural diagram of a computing device that can be used to implement the data storage structure processing method according to an embodiment of the present invention.
Referring to fig. 9, computing device 900 includes memory 910 and processor 920.
The processor 920 may be a multi-core processor or may include multiple processors. In some embodiments, processor 920 may include a general-purpose main processor and one or more special purpose coprocessors such as a Graphics Processor (GPU), Digital Signal Processor (DSP), or the like. In some embodiments, processor 920 may be implemented using custom circuits, such as Application Specific Integrated Circuits (ASICs) or Field Programmable Gate Arrays (FPGAs).
The memory 910 may include various types of storage units, such as system memory, Read Only Memory (ROM), and permanent storage. Wherein the ROM may store static data or instructions for the processor 920 or other modules of the computer. The persistent storage device may be a read-write storage device. The persistent storage may be a non-volatile storage device that does not lose stored instructions and data even after the computer is powered off. In some embodiments, the persistent storage device employs a mass storage device (e.g., magnetic or optical disk, flash memory) as the persistent storage device. In other embodiments, the permanent storage may be a removable storage device (e.g., floppy disk, optical drive). The system memory may be a read-write memory device or a volatile read-write memory device, such as a dynamic random access memory. The system memory may store instructions and data that some or all of the processors require at runtime. In addition, the memory 910 may include any combination of computer-readable storage media, including various types of semiconductor memory chips (DRAM, SRAM, SDRAM, flash memory, programmable read-only memory), magnetic and/or optical disks, may also be employed. In some embodiments, memory 910 may include a removable storage device that is readable and/or writable, such as a Compact Disc (CD), a digital versatile disc read only (e.g., DVD-ROM, dual layer DVD-ROM), a Blu-ray disc read only, an ultra-dense disc, a flash memory card (e.g., SD card, min SD card, Micro-SD card, etc.), a magnetic floppy disk, or the like. Computer-readable storage media do not contain carrier waves or transitory electronic signals transmitted by wireless or wired means.
The memory 910 has stored thereon executable code, which when processed by the processor 920, causes the processor 920 to perform the data storage structure processing methods described above.
The data storage structure processing method and apparatus according to the present invention have been described in detail above with reference to the accompanying drawings. Specifically, the present invention employs a completely new MAL (Multi-level adjacency List) data structure. The MAL structure abandons the mode of establishing the connection between the points of the traditional adjacency list, and instead adopts the connection between the points and the edges to establish a data structure, and the multi-dimensional relation is established through two layers of adjacency lists, so that the data loss of a single-layer adjacency list is prevented. MAL is implemented using a linked list infrastructure, and the operations of adding, finding, and deleting vertices or edges can also be accomplished within O (1) time complexity. In addition, only the id of the vertex or the edge can be stored in the relation chain table, and data redundancy is avoided. Compared with a point-to-edge relation matrix (particularly a sparse matrix), the MAL which only stores effective association information can greatly save storage space.
Furthermore, the method according to the invention may also be implemented as a computer program or computer program product comprising computer program code instructions for carrying out the above-mentioned steps defined in the above-mentioned method of the invention.
Alternatively, the invention may also be embodied as a non-transitory machine-readable storage medium (or computer-readable storage medium, or machine-readable storage medium) having stored thereon executable code (or a computer program, or computer instruction code) which, when executed by a processor of an electronic device (or computing device, server, etc.), causes the processor to perform the steps of the above-described method according to the invention.
Those of skill would further appreciate that the various illustrative logical blocks, modules, circuits, and algorithm steps described in connection with the disclosure herein may be implemented as electronic hardware, computer software, or combinations of both.
The flowchart and block diagrams in the figures illustrate the architecture, functionality, and operation of possible implementations of systems and methods according to various embodiments of the present invention. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of code, which comprises one or more executable instructions for implementing the specified logical function(s). It should also be noted that, in some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustration, can be implemented by special purpose hardware-based systems which perform the specified functions or acts, or combinations of special purpose hardware and computer instructions.
Having described embodiments of the present invention, the foregoing description is intended to be exemplary, not exhaustive, and not limited to the embodiments disclosed. Many modifications and variations will be apparent to those of ordinary skill in the art without departing from the scope and spirit of the described embodiments. The terminology used herein is chosen in order to best explain the principles of the embodiments, the practical application, or improvements made to the technology in the marketplace, or to enable others of ordinary skill in the art to understand the embodiments disclosed herein.
Claims (20)
1. A data storage structure processing method, comprising:
generating a vertex structure, wherein the vertex structure comprises an edge pointing field pointing to an edge to which the vertex belongs;
generating an edge structure comprising a vertex pointing field pointing to the edge containing a vertex; and
combining each of the plurality of vertex structures and the plurality of edge structures to form a multi-level adjacency list comprising a vertex adjacency list structure and an edge adjacency list structure,
where the vertices indicate data elements and the edges indicate relationships between the data elements.
2. The method of claim 1, wherein the edge pointing field of the vertex structure comprises a head node of a linked list consisting of a set of edges to which the vertex belongs; and
the vertex pointing field of the edge structure includes the head node of the linked list composed of all the vertices contained in the edge.
3. The method of claim 1, wherein the generated vertex structure includes a vertex structure identifier field that uniquely identifies the vertex structure, and a vertex structure meta-information field that stores the vertex attribute information; and
the generated edge structure includes an edge structure identifier field that uniquely identifies the edge structure, and an edge structure meta information field that indicates attribute information of the edge.
4. The method of claim 3, wherein the vertex structure meta information field comprises at least one of:
weight information of the vertex;
description information of the vertex;
custom information, and
the edge structure meta information field includes at least one of:
weight information of the edge;
description information of the edge;
and (5) self-defining information.
5. The method of claim 3, further comprising:
constructing the vertex adjacency list structure using the generated plurality of vertex structures; and
and constructing the edge adjacency list structure by using the generated plurality of edge structures.
6. The method of claim 5, comprising:
adding a new vertex structure to the vertex adjacency list structure, wherein the edges to which the vertices belong comprise existing edges;
based on the edge structure indication field of the new vertex structure, adding the information of the new vertex structure to the vertex pointing field of the existing edge structure to which the new vertex structure belongs, and/or
Adding a new edge structure to the edge adjacency list structure, wherein the vertex contained by the edge comprises an existing vertex;
and adding the information of the new edge structure to the edge pointing field of the existing vertex structure contained in the new edge structure.
7. The method of claim 5, comprising:
deleting an existing vertex structure from the vertex adjacency list structure;
based on the indication field of the edge structure of the deleted vertex structure, deleting the indication of the deleted vertex structure in the edge structure of the edge to which the deleted vertex belongs, and/or
Deleting an existing edge structure from the edge adjacency list structure;
and deleting the indication of the deleted edge structure in the vertex structure of which the deleted edge comprises the vertex based on the vertex structure indication field of the deleted edge structure.
8. The method of claim 5, comprising:
directly searching a corresponding vertex structure in the vertex adjacency list structure based on a vertex identifier;
based on the edge structure pointing field of the vertex structure, directly jumping to the edge structure of the edge of the vertex in the edge adjacency list structure, and/or
Directly looking up a corresponding edge structure in the edge adjacency table structure based on an edge identifier;
and directly jumping to the vertex structure of which the edge contains the vertex based on the vertex structure pointing field of the edge structure.
9. The method of claim 5, further comprising:
directly searching a corresponding vertex structure in the vertex adjacency list structure based on the obtained arbitrary vertex identifier;
accessing vertex structure meta information of the vertex;
judging whether the edge structure of each edge to which the vertex belongs is accessed or not based on the edge identifier contained in the edge structure pointing field of the vertex structure;
skipping over the edge structure if the access is over, otherwise skipping over to the edge structure;
accessing the edge structure meta information of the edge structure jumped to;
judging whether the vertex structure of each vertex contained in the edge is accessed or not based on the vertex identifier contained in the vertex structure pointing field of the edge structure;
if the access is over, skipping the vertex structure, otherwise, skipping to the vertex structure;
repeating the above process until each entry in the vertex adjacency list structure and the edge adjacency list structure is accessed, and/or
Directly searching a corresponding edge structure in the edge adjacency list structure based on the acquired arbitrary edge identifier;
accessing edge structure meta information of the edge;
judging whether the vertex structure of each vertex contained in the edge is accessed or not based on the vertex identifier contained in the vertex structure pointing field of the edge structure;
if the access is over, skipping the vertex structure, otherwise, skipping to the vertex structure;
accessing the vertex structure meta information of the vertex structure jumped to;
judging whether the edge structure of each edge to which the vertex belongs is accessed or not based on the edge identifier contained in the edge structure pointing field of the vertex structure;
skipping over the edge structure if the access is over, otherwise skipping over to the edge structure;
the above process is repeated until each entry in the edge adjacency table structure and the vertex adjacency table structure is accessed.
10. A data storage structure processing apparatus, comprising:
vertex structure generating means for generating a vertex structure including an edge pointing field pointing to an edge to which the vertex belongs;
edge structure generating means for generating an edge structure including a vertex pointing field pointing to the edge containing a vertex; and
adjacency list structure generating means for combining each of the plurality of vertex structures and the plurality of edge structures to form a multi-level adjacency list including the vertex adjacency list structure and the edge adjacency list structure,
where the vertices indicate data elements and the edges indicate relationships between the data elements.
11. The apparatus of claim 10, wherein the edge-pointing field of the vertex structure comprises a head node of a linked list consisting of a set of edges to which the vertex belongs; and
the vertex pointing field of the edge structure includes the head node of the linked list composed of all the vertices contained in the edge.
12. The apparatus of claim 10, wherein the vertex structure generated by the vertex structure generation means includes a vertex structure identifier field that uniquely identifies the vertex structure, and a vertex structure meta information field that stores the vertex attribute information; and
the edge structure generated by the edge structure generating means includes an edge structure identifier field that uniquely identifies the edge structure, and an edge structure meta information field that indicates attribute information of the edge.
13. The apparatus of claim 12, wherein the vertex structure meta information field comprises at least one of:
weight information of the vertex;
description information of the vertex;
custom information, and
the edge structure meta information field includes at least one of:
weight information of the edge;
description information of the edge;
and (5) self-defining information.
14. The apparatus of claim 12, wherein the adjacency list structure generation means comprises the vertex structure generation means and the edge structure generation means, and is further configured to:
constructing the vertex adjacency list structure using the generated plurality of vertex structures; and
and constructing the edge adjacency list structure by using the generated plurality of edge structures.
15. The apparatus of claim 14, comprising:
adjacency list structure modification means for:
adding a new vertex structure to the vertex adjacency list structure, wherein the edges to which the vertices belong comprise existing edges;
based on the edge structure indication field of the new vertex structure, adding the information of the new vertex structure to the vertex pointing field of the existing edge structure to which the new vertex structure belongs, and/or
Adding a new edge structure to the edge adjacency list structure, wherein the vertex contained by the edge comprises an existing vertex;
and adding the information of the new edge structure to the edge pointing field of the existing vertex structure contained in the new edge structure.
16. The apparatus of claim 15, wherein the adjacency list structure modification means is further for:
deleting an existing vertex structure from the vertex adjacency list structure;
based on the indication field of the edge structure of the deleted vertex structure, deleting the indication of the deleted vertex structure in the edge structure of the edge to which the deleted vertex belongs, and/or
Deleting an existing edge structure from the edge adjacency list structure;
and deleting the indication of the deleted edge structure in the vertex structure of which the deleted edge comprises the vertex based on the vertex structure indication field of the deleted edge structure.
17. The apparatus of claim 14, further comprising:
adjacency list structure lookup means for:
directly searching a corresponding vertex structure in the vertex adjacency list structure based on a vertex identifier;
based on the edge structure pointing field of the vertex structure, directly jumping to the edge structure of the edge of the vertex in the edge adjacency list structure, and/or
Directly looking up a corresponding edge structure in the edge adjacency table structure based on an edge identifier;
and directly jumping to the vertex structure of which the edge contains the vertex based on the vertex structure pointing field of the edge structure.
18. The apparatus of claim 14, wherein the adjacency list traversal means comprises the adjacency list structure lookup means and is operable to:
directly searching a corresponding vertex structure in the vertex adjacency list structure based on the obtained arbitrary vertex identifier;
accessing vertex structure meta information of the vertex;
judging whether the edge structure of each edge to which the vertex belongs is accessed or not based on the edge identifier contained in the edge structure pointing field of the vertex structure;
skipping over the edge structure if the access is over, otherwise skipping over to the edge structure;
accessing the edge structure meta information of the edge structure jumped to;
judging whether the vertex structure of each vertex contained in the edge is accessed or not based on the vertex identifier contained in the vertex structure pointing field of the edge structure;
if the access is over, skipping the vertex structure, otherwise, skipping to the vertex structure;
repeating the above process until each entry in the vertex adjacency list structure and the edge adjacency list structure is accessed, and/or
Directly searching a corresponding edge structure in the edge adjacency list structure based on the acquired arbitrary edge identifier;
accessing edge structure meta information of the edge;
judging whether the vertex structure of each vertex contained in the edge is accessed or not based on the vertex identifier contained in the vertex structure pointing field of the edge structure;
if the access is over, skipping the vertex structure, otherwise, skipping to the vertex structure;
accessing the vertex structure meta information of the vertex structure jumped to;
judging whether the edge structure of each edge to which the vertex belongs is accessed or not based on the edge identifier contained in the edge structure pointing field of the vertex structure;
skipping over the edge structure if the access is over, otherwise skipping over to the edge structure;
the above process is repeated until each entry in the edge adjacency table structure and the vertex adjacency table structure is accessed.
19. A computing device, comprising:
a processor; and
a memory having executable code stored thereon, which when executed by the processor, causes the processor to perform the method of any one of claims 1-9.
20. A non-transitory machine-readable storage medium having stored thereon executable code, which when executed by a processor of an electronic device, causes the processor to perform the method of any one of claims 1-9.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201810925045.8A CN109359156B (en) | 2018-08-14 | 2018-08-14 | Data storage structure processing method and device |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201810925045.8A CN109359156B (en) | 2018-08-14 | 2018-08-14 | Data storage structure processing method and device |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN109359156A CN109359156A (en) | 2019-02-19 |
| CN109359156B true CN109359156B (en) | 2021-10-08 |
Family
ID=65349974
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201810925045.8A Active CN109359156B (en) | 2018-08-14 | 2018-08-14 | Data storage structure processing method and device |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN109359156B (en) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN112417226B (en) * | 2020-12-02 | 2024-01-30 | 江苏赛融科技股份有限公司 | Big data processing method based on DAG conversion |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8356040B2 (en) * | 2005-03-31 | 2013-01-15 | Robert T. and Virginia T. Jenkins | Method and/or system for transforming between trees and arrays |
| CN103701469A (en) * | 2013-12-26 | 2014-04-02 | 华中科技大学 | Compression and storage method for large-scale image data |
| CN104615677A (en) * | 2015-01-20 | 2015-05-13 | 同济大学 | Graph data access method and system |
| CN105354297A (en) * | 2015-11-03 | 2016-02-24 | 浪潮(北京)电子信息产业有限公司 | Method and system for storing data in database |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR20130063589A (en) * | 2011-12-07 | 2013-06-17 | 한국전자통신연구원 | Method and apparatus for searching file by using tag-graph |
-
2018
- 2018-08-14 CN CN201810925045.8A patent/CN109359156B/en active Active
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US8356040B2 (en) * | 2005-03-31 | 2013-01-15 | Robert T. and Virginia T. Jenkins | Method and/or system for transforming between trees and arrays |
| CN103701469A (en) * | 2013-12-26 | 2014-04-02 | 华中科技大学 | Compression and storage method for large-scale image data |
| CN104615677A (en) * | 2015-01-20 | 2015-05-13 | 同济大学 | Graph data access method and system |
| CN105354297A (en) * | 2015-11-03 | 2016-02-24 | 浪潮(北京)电子信息产业有限公司 | Method and system for storing data in database |
Also Published As
| Publication number | Publication date |
|---|---|
| CN109359156A (en) | 2019-02-19 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US7734714B2 (en) | Spatial Sieve Tree | |
| US9842149B2 (en) | Population and/or animation of spatial visualization(s) | |
| US20070192301A1 (en) | Systems and methods for indexing and searching data records based on distance metrics | |
| CN103973810B (en) | The data processing method and device of internet protocol-based IP disks | |
| CN113901279A (en) | Graph database retrieval method and device | |
| CN110825794A (en) | Partition merge method and database server | |
| CN102243660A (en) | Data access method and device | |
| CN103942301B (en) | Distributed file system oriented to access and application of multiple data types | |
| US11868328B2 (en) | Multi-record index structure for key-value stores | |
| US6745198B1 (en) | Parallel spatial join index | |
| CN108628969B (en) | A spatial keyword indexing method, platform and storage medium | |
| WO2016188280A1 (en) | Write-in method and device for database sub-tables | |
| CN108073595B (en) | A method and device for realizing data update and snapshot in OLAP database | |
| CN113779286B (en) | Method and device for managing graph data | |
| US12417247B2 (en) | Systems and methods for metadata based path finding | |
| Hu et al. | Towards big linked data: a large-scale, distributed semantic data storage | |
| CN109359156B (en) | Data storage structure processing method and device | |
| CN111008198A (en) | Business data acquisition method, device, storage medium, and electronic device | |
| CN108073596B (en) | Data deletion method and device for OLAP database | |
| KR20210077975A (en) | Spatial indexing method and apparatus for blockchain-based geospatial data | |
| CN112307272B (en) | Method, device, computing equipment and storage medium for determining relation information between objects | |
| CN114579537A (en) | Distributed graph database optimization method and device, electronic equipment and storage medium | |
| CN109800241A (en) | A kind of set operation method and terminal | |
| CN115270731A (en) | Collaborative editing method and device for mixed document | |
| Kondybayeva et al. | Voronoi diagrams for the distributed sensor network system data processing |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| TA01 | Transfer of patent application right |
Effective date of registration: 20200813 Address after: 310052 room 508, floor 5, building 4, No. 699, Wangshang Road, Changhe street, Binjiang District, Hangzhou City, Zhejiang Province Applicant after: Alibaba (China) Co.,Ltd. Address before: 510627 Guangdong city of Guangzhou province Whampoa Tianhe District Road No. 163 Xiping Yun Lu Yun Ping square B radio tower 13 layer self unit 01 Applicant before: Guangdong Shenma Search Technology Co.,Ltd. |
|
| TA01 | Transfer of patent application right | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |