# US 2015/0178338 A1 · Method, device, and computer program for merge-sorting record groups having tree structure efficiently

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2015/0178338 A1
- Document ID: US20150178338A1
- Status: Published application
- Kind: A1
- Application number: 14/569,062
- Filed: 2014-12-12
- Published: 2015-06-25
- Earliest claimed: 2013-12-20
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Hiroshige Hayashizaki; Megumi Ito
- Web page: https://patentgrep.com/patent/US20150178338A1

## CPC

- G06F 7/16: Combined merging and sorting
- G06F 7/32: Merging, i.e. combining data contained in ordered sequence on at least two record carriers to produce a single carrier or set of carriers having all the original data in the ordered sequence {merging methods in general}(G06F7/36 takes precedence)
- G06F 16/9027: {Trees}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A first record group and a second record group having a tree structure are merge-sorted. The first record group and the second record group are acquired, and depth information indicative of the hierarchical depth of the tree structure is attached as metadata to key information on each node of each record included in the acquired first record group and second record group. The depth information is compared in preference to the key information to perform merge sort sequentially.

## Claims

### Claim 1

A method executable by a device for merge-sorting a first record group and a second record group having a tree structure, wherein the device performs:
a first step of acquiring the first record group and the second record group;
a second step of attaching depth information as metadata, indicative of a hierarchical depth in the tree structure, to key information on each node of each record included in the acquired first record group and second record group; and
a third step of comparing the depth information in preference to the key information to perform merge sort sequentially.

### Claim 2 (depends on 1)

The method according to claim 1, wherein
the depth information is set to a larger value as the hierarchical depth is deeper, and
the third step includes the steps of:
comparing the depth information and the key information on each node of each record included in the acquired first record group and second record group; and
when one piece of the depth information is larger than another piece of the depth information, outputting the key information whose depth information is larger;
when both pieces of the depth information are identical, outputting the key information having a smaller value; or
when both pieces of the depth information are identical and both pieces of the key information are identical, outputting either one piece of the key information.

### Claim 3 (depends on 1)

The method according to claim 1, wherein
the depth information is set to a smaller value as the hierarchical depth is deeper, and
the third step includes the steps of:
comparing the depth information and the key information on each node of each record included in the acquired first record group and second record group; and
when one piece of the depth information is smaller than another piece of the depth information, outputting the key information whose depth information is smaller;
when both pieces of the depth information are identical, outputting the key information having a smaller value; or
when both pieces of the depth information are identical and both pieces of the key information are identical, outputting either one piece of the key information.

### Claim 4 (depends on 2)

The method according to claim 2, further comprising:
responsive to outputting the key information whose depth information is larger, selecting a next node in a record group corresponding to the outputted key information;
responsive to outputting the key information having a smaller value, selecting a next node in a record group corresponding to the outputted key information; and
comparing, for the next node, the depth information in preference to the key information to perform merge sort sequentially.

### Claim 5 (depends on 3)

The method according to claim 3, further comprising:
responsive to outputting either one piece of the key information, selecting a next node in the acquired first record group and second record group; and
comparing, for the next node, the depth information in preference to the key information to perform merge sort sequentially.

### Claim 6 (depends on 1)

The method according to claim 1, further comprising:
generating a comparison information, wherein the comparison information is generated as an integer number with the depth information as higher bits and the key information as lower bits.

### Claim 7 (depends on 6)

The method according to claim 6, further comprising:
the third step includes the steps of:
comparing the comparison information on each node of each record included in the acquired first record group and second record group.

### Claim 8

A device for merge-sorting a first record group and a second record group having a tree structure, the device capable of performing a method comprising:
acquiring the first record group and the second record group;
attaching depth information as metadata, indicative of a hierarchical depth in the tree structure, to key information on each node of each record included in the acquired first record group and second record group; and
comparing the depth information in preference to the key information to perform merge sort sequentially.

### Claim 9 (depends on 8)

The device according to claim 8, wherein
the depth information is set to a larger value as the hierarchy is deeper, and
the comparing step includes:
comparing the depth information and the key information on each node of each record included in the acquired first record group and second record group; and
outputting the key information based on a result of the comparison means, wherein the outputting includes:
a first output which, when one piece of the depth information is larger than another piece of the depth information, outputs the key information whose depth information is larger,
a second output which, when both pieces of the depth information are identical, outputs the key information having a smaller value, or
a third output which, when both pieces of the depth information are identical and both pieces of the key information are identical, outputs either one piece of the key information.

### Claim 10 (depends on 8)

The device according to claim 8, wherein
the depth information is set to a smaller value as the hierarchy is deeper, and
the comparing step includes:
comparing the depth information and the key information on each node of each record included in the acquired first record group and second record group; and
outputting the key information based on a result of the comparison means, wherein the outputting includes:
a first output which, when one piece of the depth information is smaller than another piece of the depth information, outputs the key information whose depth information is smaller,
a second output which, when both pieces of the depth information are identical, outputs the key information having a smaller value, or
a third output which, when both pieces of the depth information are identical and both pieces of the key information are identical, outputs either one piece of the key information.

### Claim 11 (depends on 9)

The device according to claim 9, further comprising:
responsive to outputting the first output, selecting a next node in a record group corresponding to the outputted key information;
responsive to outputting the second output, selecting a next node in a record group corresponding to the outputted key information; and
comparing, for the next node, the depth information in preference to the key information to perform merge sort sequentially.

### Claim 12 (depends on 10)

The device according to claim 10, further comprising:
responsive to outputting the third output, selecting a next node in the acquired first record group and second record group; and
comparing, for the next node, the depth information in preference to the key information to perform merge sort sequentially.

### Claim 13 (depends on 8)

The device according to claim 8, further comprising:
generating a comparison information, wherein the comparison information is generated as an integer number with the depth information as higher bits and the key information as lower bits.

### Claim 14

A computer program product executable on a device for merge-sorting a first record group and a second record group having a tree structure, the computer program causing the device to perform a method comprising:
acquiring the first record group and the second record group;
attaching depth information as metadata, indicative of a hierarchical depth in the tree structure, to key information on each node of each record included in the acquired first record group and second record group; and
comparing the depth information in preference to the key information to perform merge sort sequentially.

### Claim 15 (depends on 14)

The computer program product according to claim 14, wherein
the depth information is set to a larger value as the hierarchy is deeper, and
the comparing step includes:
comparing the depth information and the key information on each node of each record included in the acquired first record group and second record group; and
outputting the key information based on a result of the comparison means, wherein the outputting includes:
a first output which, when one piece of the depth information is larger than another piece of the depth information, outputs the key information whose depth information is larger,
a second output which, when both pieces of the depth information are identical, outputs the key information having a smaller value, or
a third output which, when both pieces of the depth information are identical and both pieces of the key information are identical, outputs either one piece of the key information.

### Claim 16 (depends on 14)

The computer program product according to claim 14, wherein
the depth information is set to a smaller value as the hierarchy is deeper, and
the comparing step includes:
comparing the depth information and the key information on each node of each record included in the acquired first record group and second record group; and
outputting the key information based on a result of the comparison means, wherein the outputting includes:
a first output which, when one piece of the depth information is smaller than another piece of the depth information, outputs the key information whose depth information is smaller,
a second output which, when both pieces of the depth information are identical, outputs the key information having a smaller value, or
a third output which, when both pieces of the depth information are identical and both pieces of the key information are identical, outputs either one piece of the key information.

### Claim 17 (depends on 15)

The computer program product according to claim 15, the computer program causing the device to perform a method further comprising:
responsive to outputting the first output, selecting a next node in a record group corresponding to the outputted key information;
responsive to outputting the second output, selecting a next node in a record group corresponding to the outputted key information; and
comparing, for the next node, the depth information in preference to the key information to perform merge sort sequentially.

### Claim 18 (depends on 16)

The computer program product according to claim 16, the computer program causing the device to perform a method further comprising:
responsive to outputting the third output, selecting a next node in the acquired first record group and second record group; and
comparing, for the next node, the depth information in preference to the key information to perform merge sort sequentially.

### Claim 19 (depends on 14)

The computer program product according to claim 14, the computer program causing the device to perform a method further comprising:
generating a comparison information, wherein the comparison information is generated as an integer number with the depth information as higher bits and the key information as lower bits.

### Claim 20 (depends on 19)

The computer program product according to claim 19, the computer program causing the device to perform a method further comprising:
comparing the comparison information on each node of each record included in the acquired first record group and second record group.
