Method and apparatus for searching in a memory-efficient manner for at least one query data element
First Claim
Patent Images
1. A method for searching in a memory-efficient manner for a query data element in a graph comprising:
- receiving or accessing the graph, which comprises a data structure including data elements arranged according to relationships between particular data elements,segmenting the query data element into multiple query data segments including at least a first query data segment and a second query data segment, using predefined segmenting metrics;
after segmenting the query data element using the predefined segmenting metrics, identifying the multiple query data segments in the graph, which comprises subordinate data elements and superordinate data elements, by an iterative process including;
identifying a first one of the multiple data segments in the graph by;
a) determining whether or not the first query data segment is present in the graph by comparing each of a plurality of existing subordinate data elements of the graph with the first query data segment, wherein each subordinate data element is connected to a superordinate data element by exactly one edge in the graph;
b) storing a particular subordinate data element as a new superordinate data element in response to determining that the particular subordinate data element features the first query data segment; and
treating the particular subordinate data element, stored as a new superordinate data element, as a superordinate data element for identifying a second one of the multiple query data segments in the graph, such that identifying the second query data segment includes comparing existing subordinate data elements of the new superordinate data element with the second query data segment.
1 Assignment
0 Petitions
Accused Products
Abstract
In a method and an apparatus (1) for searching in a memory-efficient manner for at least one query data element in a graph (2A), only as many data elements are read into a memory as are required for their subsequent processing. Increased memory efficiency is ensured as a result of this. The proposed apparatus is particularly suitable for use in terminals having very limited memory, in particular in mobile terminals.
14 Citations
20 Claims
-
1. A method for searching in a memory-efficient manner for a query data element in a graph comprising:
-
receiving or accessing the graph, which comprises a data structure including data elements arranged according to relationships between particular data elements, segmenting the query data element into multiple query data segments including at least a first query data segment and a second query data segment, using predefined segmenting metrics; after segmenting the query data element using the predefined segmenting metrics, identifying the multiple query data segments in the graph, which comprises subordinate data elements and superordinate data elements, by an iterative process including; identifying a first one of the multiple data segments in the graph by; a) determining whether or not the first query data segment is present in the graph by comparing each of a plurality of existing subordinate data elements of the graph with the first query data segment, wherein each subordinate data element is connected to a superordinate data element by exactly one edge in the graph; b) storing a particular subordinate data element as a new superordinate data element in response to determining that the particular subordinate data element features the first query data segment; and treating the particular subordinate data element, stored as a new superordinate data element, as a superordinate data element for identifying a second one of the multiple query data segments in the graph, such that identifying the second query data segment includes comparing existing subordinate data elements of the new superordinate data element with the second query data segment. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. An apparatus for searching in a memory-efficient manner for a query data element in a graph comprising:
-
a segmentation unit for; receiving or accessing the graph, which comprises a data structure including data elements arranged according to relationships between particular data elements, and segmenting the query data element into multiple query data segments including at least a first query data segment and a second query data segment, using predefined segmenting metrics; an iteration unit for, after segmenting the query data element using the predefined segmenting metrics, identifying the multiple query data segments in the graph, which comprises subordinate data elements and superordinate data elements, by an iterative process including; identifying a first one of the multiple query data segments in the graph by; a) determining whether or not the first query data segment is present in the graph by comparing each of a plurality of existing subordinate data elements of the graph with the first query data segment, wherein each subordinate data element is connected to a superordinate data element by exactly one edge in the graph; b) storing a particular subordinate data element as a new superordinate data element in response to determining that the particular subordinate data element features the first query data segment; and treating the particular subordinate data element, which was stored as a new superordinate data element, as a superordinate data element for identifying a second one of the multiple query data segments in the graph, such identifying the second query data segment includes comparing existing subordinate data elements of the new superordinate data element with the second query data segment. - View Dependent Claims (12, 13, 14, 15, 16)
-
-
17. A computer program product comprising a non-transitory data memory storing instructions which when executed on a computer perform a method for searching in a memory-efficient manner for a query data element in a graph comprising:
-
receiving or accessing the graph, which comprises a data structure including data elements arranged according to relationships between particular data elements, segmenting the query data element into multiple query data segments including at least a first query data segment and a second query data segment, using predefined segmenting metrics; after segmenting the query data element using the predefined segmenting metrics, identifying the multiple query data segments in the graph, which comprises subordinate data elements and superordinate data elements, by an iterative process including; identifying a first one of the multiple query data segments in the graph by; a) determining whether or not the first query data segment is present in the graph by comparing each of a plurality of existing subordinate data elements of the graph with the first query data segment, wherein each subordinate data element is connected to a superordinate data element by exactly one edge in the graph; b) storing a particular subordinate data element as a new superordinate data element in response to determining that the particular subordinate data element features the first query data segment; and treating the particular subordinate data element which was stored as a new superordinate data element, as a superordinate data element for identifying a second one of the multiple query data segments in the graph, such identifying the second query data segment includes comparing existing subordinate data elements of the new superordinate data element with the second query data segment. - View Dependent Claims (18, 19, 20)
-
Specification