# US 8,788,483 B2 · Method and apparatus for searching in a memory-efficient manner for at least one query data element > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,788,483 B2 - Document ID: US8788483B2 - Status: Granted - Kind: B2 - Application number: 12/819,280 - Filed: 2010-06-21 - Published: 2010-12-23 - Granted: 2014-07-22 - Earliest claimed: 2009-06-19 - Assignees: Siemens Aktiengesellschaft - Applicants: Jörg Heuer; Roland Kind; Richard Kuntschke; Daniel Peintner - Inventors: Jörg Heuer; Roland Kind; Richard Kuntschke; Daniel Peintner - Web page: https://patentgrep.com/patent/US8788483B2 ## CPC - G06F 16/9027: {Trees} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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. ## Claims ### Claim 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. ### Claim 2 (depends on 1) The method according to claim 1, wherein the storage of the particular subordinate data element as a superordinate data element is executed in such a way that a previously stored superordinate data element is overwritten by the particular subordinate data element. ### Claim 3 (depends on 1) The method according to claim 1, wherein the storage of the particular subordinate data element as a superordinate data element is executed in such a way that a previously stored superordinate data element is deleted from a memory and the particular subordinate data element is written into the memory. ### Claim 4 (depends on 1) The method according to claim 1, wherein the query data element is segmented into a plurality of ordered query data segments, and the identification of the query data segments in the graph is executed in accordance with an order of the multiple query data segments. ### Claim 5 (depends on 1) The method according to claim 1, wherein the query data element describes a path in the graph. ### Claim 6 (depends on 1) The method according to claim 1, wherein the query data segment features a binary code, a superordinate data element, a subordinate data element, a node, a URL, a URI, a virtual folder and/or a file name. ### Claim 7 (depends on 1) The method according to claim 1, wherein at least part of the graph is described by an XML document, a binary code, a graphical representation, a textual description, an ontological language, a formal model, a relational database and/or a graph description language. ### Claim 8 (depends on 1) The method according to claim 1, wherein the superordinate data element corresponds to a root data element in the context of a first comparison of the subordinate data element with the query data segment. ### Claim 9 (depends on 1) The method according to claim 1, wherein at least one of the query data segment, the query data element, the subordinate data element and the superordinate data element comprise at least one attribute. ### Claim 10 (depends on 1) The method according to claim 1, wherein the method is used in a mobile terminal. ### Claim 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. ### Claim 12 (depends on 11) The apparatus according to claim 11, comprising a data memory for storing at least part of the graph. ### Claim 13 (depends on 11) The apparatus according to claim 11, comprising a readout unit for reading out at least part of the graph from a remote data memory. ### Claim 14 (depends on 12) The apparatus according to claim 12, comprising a first interface unit for receiving at least part of at least one of the graph, of the query data element, of the query data segment, of the superordinate data element and of the subordinate data element. ### Claim 15 (depends on 12) The apparatus according to claim 12, comprising a second interface unit for providing at least part of at least one of the graph, of the query data element, of the query data segment, of the superordinate data element and of the subordinate data element. ### Claim 16 (depends on 15) The apparatus according to claim 15, wherein the first interface unit and the second interface unit are available as a combined interface. ### Claim 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. ### Claim 18 (depends on 17) The computer program product according to claim 17, wherein the storage of the particular subordinate data element as a superordinate data element is executed in such a way that a previously stored superordinate data element is overwritten by the particular subordinate data element. ### Claim 19 (depends on 17) The computer program product according to claim 17, wherein the storage of the particular subordinate data element as a superordinate data element is executed in such a way that a previously stored superordinate data element is deleted from a memory and the particular subordinate data element is written into the memory. ### Claim 20 (depends on 17) The computer program product according to claim 17, wherein the query data element is segmented into a plurality of ordered query data segments, and the identification of the query data segments in the graph is executed in accordance with a order of the multiple query data segments.