Indexing hierarchical data

Patent metadata

Field	Value
Publication number	US-9280575-B2
Application number	US-201313946081-A
Country	US
Kind code	B2
Filing date	Jul 19, 2013
Priority date	Jul 20, 2012
Publication date	Mar 8, 2016
Grant date	Mar 8, 2016

Abstract

A system includes generation of an encoding for each of a hierarchy of nodes, each of the nodes associated with one or more attributes, and the encoding for each node including a first pointer and a second pointer, and generation of an order tree comprising a hierarchy of entries, where each pointer of the encoding points to a respective one of the entries, wherein the encoding and the order tree indicate a position of each node in the hierarchy of nodes.

First claim

What is claimed is:

1. A computing system comprising:
one or more memory storing processor-executable program code; and
one or more processor to execute the processor-executable program code in order to cause the computing system to:
generate an encoding for each of a hierarchy of nodes, each of the nodes associated with one or more attributes, and the encoding for each node including a first pointer and a second pointer;
generate an order tree comprising a hierarchy of entries that is different from the hierarchy of nodes and the encoding, wherein each pointer of the encoding points to a respective one of the entries, and wherein the encoding and the order tree indicate a position of each node in the hierarchy of nodes; and
use the order tree to support queries on the hierarchy of the nodes;

wherein the processor is to execute the processor-executable program code in order to cause the computing system to:
determine an order relation between a first entry of the order tree and a second entry of the order tree based on a structure of the order tree; and

wherein determination of the order relation comprises:
determination of a number p 1 where each digit of p 1 corresponds to a position of each entry on a first path from the first entry to a root entry of the order tree, and a least significant digit of p 1 corresponds to a position of the first entry;
determination of a number p 2 where each digit of p 2 corresponds to a position of each entry on a second path from the second entry to the root entry of the order tree, and a least significant digit of p 2 corresponds to a position of the second entry; and
comparison of p 1 and p 2 .

2. A computing system according to claim 1 , wherein the order tree is a balanced binary tree of entries.

3. A computing system according to claim 2 , wherein the encoding comprises an interval encoding, and
wherein, for each node, the first pointer indicates a lower interval bound of the node and the second pointer indicates an upper interval bound of the node.

4. A computing system according to claim 1 , wherein the encoding comprises an interval encoding, and
wherein, for each node, the first pointer indicates a lower interval bound of the node and the second pointer indicates an upper interval bound of the node.

5. A non-transitory computer-readable medium storing program code, the program code executable by one or more processor of a computing system to cause the computing system to:
generate an encoding for each of a hierarchy of nodes, each of the nodes associated with one or more attributes, and the encoding for each node including a first pointer and a second pointer;
generate an order tree comprising a hierarchy of entries that is different from the hierarchy of nodes and the encoding, wherein each pointer of the encoding points to a respective one of the entries, and wherein the encoding and the order tree indicate a position of each node in the hierarchy of nodes; and
use the order tree to support queries on the hierarchy of the nodes;
the program code further executable by a processor of a computing system to cause the computing system to:
determine an order relation between a first entry of the order tree and a second entry of the order tree based on a structure of the order tree; and

wherein determination of the order relation comprises:
determination of a number p 1 where each digit of p 1 corresponds to a position of each entry on a first path from the first entry to a root entry of the order tree, and a least significant digit of p 1 corresponds to a position of the first entry;
determination of a number p 2 where each digit of p 2 corresponds to a position of each entry on a second path from the second entry to the root entry of the order tree, and a least significant digit of p 2 corresponds to a position of the second entry; and
comparison of p 1 and p 2 .

6. A medium according to claim 5 , wherein the order tree is a balanced binary tree of entries.

7. A medium according to claim 6 , wherein the encoding comprises an interval encoding, and
wherein, for each node, the first pointer indicates a lower interval bound of the node and the second pointer indicates an upper interval bound of the node.

8. A medium according to claim 5 , wherein the encoding comprises an interval encoding, and
wherein, for each node, the first pointer indicates a lower interval bound of the node and the second pointer indicates an upper interval bound of the node.

9. A computer-implemented method comprising:
generating an encoding for each of a hierarchy of nodes, each of the nodes associated with one or more attributes, and the encoding for each node including a first pointer and a second pointer;
generating an order tree comprising a hierarchy of entries that is different from the hierarchy of nodes and the encoding, wherein each pointer of the encoding points to a respective one of the entries, and wherein the encoding and the order tree indicate a position of each node in the hierarchy of nodes; and
using the order tree to support queries on the hierarchy of the nodes;
the method further comprising:
determining an order relation between a first entry of the order tree and a second entry of the order tree based on a structure of the order tree; and

wherein determining the order relation comprises:
determining a number p 1 where each digit of p 1 corresponds to a position of each entry on a first path from the first entry to a root entry of the order tree, and a least significant digit of p 1 corresponds to a position of the first entry;
determining a number p 2 where each digit of p 2 corresponds to a position of each entry on a second path from the second entry to the root entry of the order tree, and a least significant digit of p 2 corresponds to a position of the second entry; and
comparing p 1 and p 2 .

10. A method according to claim 9 , wherein the order tree is a balanced binary tree of entries.

11. A method according to claim 10 , wherein the encoding comprises an interval encoding, and
wherein, for each node, the first pointer indicates a lower interval bound of the node and the second pointer indicates an upper interval bound of the node.

12. A method according to claim 11 , wherein the encoding comprises an interval encoding, and
wherein, for each node, the first pointer indicates a lower interval bound of the node and the second pointer indicates an upper interval bound of the node.

13. A computing system comprising:
a memory storing processor-executable program code; and
a processor to execute the processor-executable program code in order to cause the computing system to:
generate an encoding for each of a hierarchy of nodes, each of the nodes associated with one or more attributes, and the encoding for each node including a first pointer and a second pointer;
generate an order tree comprising a hierarchy of entries, where each pointer of the encoding points to a respective one of the entries, wherein the encoding and the order tree indicate a position of each node in the hierarchy of nodes; and
determine an order relation between a first entry of the order tree and a second entry of the order tree based on a structure of the order tree;

wherein determination of the order relation comprises:
determination of a number p 1 where each digit of p 1 corresponds to a position of each entry on a first path from the first entry to a root entry of the order tree, and a least significant digit of p 1 corresponds to a position of the first entry;
determination of a number p 2 where each digit of p 2 corresponds to a position of each en

Assignees

• Finis Jan
• Brunel Robert
• Sap Se

Inventors

• Finis Jan
• Brunel Robert

Classifications

• G06F16/9027

  Trees · CPC title

• G06F16/185

  Hierarchical storage management [HSM] systems, e.g. file migration or policies thereof (details of archiving G06F16/11) · CPC title

• G06F16/2246 Primary

  Trees, e.g. B+trees · CPC title

• G06F17/30961

  Physics · mapped topic

• G06F17/30327 Primary

  Physics · mapped topic