METHOD AND APPARATUS FOR SEARCHING IN A MEMORY-EFFICIENT MANNER FOR AT LEAST ONE QUERY DATA ELEMENT

• US 20100325151A1
• Filed: 06/21/2010
• Published: 12/23/2010
• Est. Priority Date: 06/19/2009
• Status: Active Grant

• Current Assignee: Siemens AG
• Original Assignee: Siemens AG
• Inventors: Heuer, Jorg, Peintner, Daniel, Kuntschke, Richard, Kind, Roland
• Granted Patent: US 8,788,483 B2
• Time in Patent Office: Days
• US Class Current: 707/769
• CPC Class Codes: G06F 16/9027 Trees

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

1. A method for searching in a memory-efficient manner for at least one query data element in a graph comprising:

segmenting the query data element into at least one query data segment;

iteratively executing the following subsidiary steps for identifying the at least one query data segment in the graph;

a) comparing a subordinate data element with a query data segment, wherein the subordinate data element is connected to a superordinate data element by means of exactly one edge in the graph; and

b) storing the subordinate data element as a superordinate data element, if the subordinate data element features at least one query data segment;

providing the stored superordinate data element, if at least one query data segment is identified in the graph.

2. The method according to claim 1, wherein the storage of the 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 subordinate data element.

3. The method according to claim 1, wherein the storage of the 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 subordinate data element is written into the memory.

4. 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 this order.

5. The method according to claim 1, wherein the query data element describes a path in the graph.

6. 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.

7. 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.

8. 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.

9. 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.

10. The method according to claim 1, wherein the method is used in a mobile terminal.

11. An apparatus for searching in a memory-efficient manner for at least one query data element in a graph comprising:

a segmentation unit for segmenting the query data element into at least one query data segment;

an iteration unit for iteratively executing the following subsidiary steps for identifying the at least one query data segment in the graph;

a) comparing a subordinate data element with a query data segment, wherein the subordinate data element is connected to a superordinate data element by means of exactly one edge in the graph; and

b) storing the subordinate data element as a superordinate data element, if the subordinate data element features at least one query data segment;

a superordinate data element provision unit for providing the stored superordinate data element if the at least one query data segment is identified in the graph.

12. The apparatus according to claim 11, comprising a data memory for storing at least part of the graph.

13. The apparatus according to claim 11, comprising a readout unit for reading out at least part of the graph from a remote data memory.

14. 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.

15. 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.

16. The apparatus according to claim 15, wherein the first interface unit and the second interface unit are available as a combined interface.

17. A computer program product comprising a computer readable medium storing instructions which when executed on a computer perform a method for searching in a memory-efficient manner for at least one query data element in a graph comprising:

segmenting a query data element into at least one query data segment;

iteratively executing the following subsidiary steps for identifying the at least one query data segment in the graph;

a) comparing a subordinate data element with a query data segment, wherein the subordinate data element is connected to a superordinate data element by means of exactly one edge in the graph; and

b) storing the subordinate data element as a superordinate data element, if the subordinate data element features at least one query data segment;

providing the stored superordinate data element, if at least one query data segment is identified in the graph.

18. The computer program product according to claim 17, wherein the storage of the 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 subordinate data element.

19. The computer program product according to claim 17, wherein the storage of the 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 subordinate data element is written into the memory.

20. 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 this order.