# US 10,353,881 B2 · Data processing apparatus, method, and non-transitory tangible machine-readable medium thereof for recursively structured data

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

- Number: US 10,353,881 B2
- Document ID: US10353881B2
- Status: Granted
- Kind: B2
- Application number: 15/157,112
- Filed: 2016-05-17
- Published: 2017-11-23
- Granted: 2019-07-16
- Earliest claimed: 2016-05-17
- Assignees: BigObject, Inc.
- Applicants: BigObject, Inc.
- Inventors: Wenwey Hseush; Yi-Cheng Huang; Yu-Chun Lai
- Web page: https://patentgrep.com/patent/US10353881B2

## CPC

- G06F 16/22: Indexing; Data structures therefor; Storage structures
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Data processing apparatus, method, and non-transitory tangible machine-readable medium thereof for recursively structured data are provided. The data processing apparatus accesses a piece of recursively structured data having a Location Independent Structure and arranges the piece of recursively structured data in a one-dimensional memory space according to LIS:=e0∘e1∘ . . . ∘ep−1∘LIS0∘LIS1∘ . . . ∘LISp−1. The notation ei represents an element of the piece of recursively structured data. The notation LISi represents a sub-LIS of the recursively structured data and corresponds to the element ei. The operator ‘∘’ indicates “contiguous to” in the one-dimensional memory space. When the elements in all depths are of the element size and the LIS sizes of the sub-LISs within the same depth are the same, the piece of recursively structured data is a complete LIS.

## Claims

### Claim 1

A data processing apparatus, comprising:
a one-dimensional memory space; and
a processor, being electrically connected to the one-dimensional memory space and configured to access a piece of recursively structured data, wherein the piece of recursively structured data has a Location Independent Structure (LIS),
wherein the processor further arranges the piece of recursively structured data in the one-dimensional memory space in the following way:
LIS:=e0∘e1∘∘ep−1∘LIS0∘LIS1∘ . . . ∘LISp−1,
wherein the variable p is a positive integer, the notation ei represents an element of the piece of recursively structured data, the notation LISi represents a sub-LIS of the recursively structured data and corresponds to the element ei, the variable i is an index of the elements and is between 0 and p−1, the operator ‘∘’ indicates “contiguous to” in the one-dimensional memory space, each of the sub-LISs is of an LIS size, a depth associated to each sub-LIS is a number of recursions from the top LIS, the depth of each LISi equals the depth of the LIS plus one, and the depth of the top LIS is zero,
wherein each of the elements is of an element size, the element sizes are the same, and the LIS sizes of the sub-LISs within the same depth are the same,
wherein the piece of recursively structured data arranged in the one-dimensional memory space defines an array as LIS T X [D0, D1, D2, . . . , Dn],
wherein X is the name of the piece of recursively structured data, the variable n is the maximum LIS depth and is a nonnegative integer, the array is of n+1 dimensions, each of the dimensions corresponds to a dimension size, the notation T represents a data type of the elements, the variable Dj represents the dimension size of the j-th dimension, the j-th dimension corresponds to the j-th depth of the piece of recursively structured data, and the variable j is an index of the dimension between 0 and n,
wherein each of the elements is denoted as X[I0, . . . , Im], the variable m is an integer between 0 and n, the variable Im represents an index corresponding to the m-th dimension, Im, is between 0 and Dm−1, the notation X[I0] is the I0-th element of the LIS, the notation X[I0, . . . , Im−1, Im], is the Im-th element of LISmIm−1, and the notation LISmIm−1 represents the Im−1-th sub-LIS of the depth m.

### Claim 2 (depends on 1)

The data processing apparatus of claim 1, wherein the element X[I0, . . . , Im−1, Im] is located by the following path:
LIS→X[I0]→LIS1I0→X[I0,I1]→LIS2I1→ . . . →X[I0, . . . ,Im−1]→LISmIm−1→X[I0, . . . ,Im],
wherein the notation LISjIj−1 represents the sub-LIS corresponding to the element X[I0, . . . , Ij−1] and 0<j≤m.

### Claim 3 (depends on 1)

The data processing apparatus of claim 1, further comprising:
an input interface, being electrically connected to the processor and configured to receive an instruction comprising an index combination, wherein the index combination is represented as (I0, . . . , Im),
wherein the processor further retrieves the element corresponding to the index combination and the sub-LIS corresponding to the index combination from the one-dimensional memory space according to the following equations:
⁢
{
S
m
=
D
m
×
(
t
+
S
m
+
1
)
for
⁢
⁢
0
≤
m
≤
n
S
m
=
0
for
⁢
⁢
m
>
n
,
⁢
{
X
⁡
[
I
0
]
=
LIS
⁡
(
X
)
+
I
0
×
t
X
⁡
[
I
0
,
…
⁢
,
I
m
]
=
LIS
⁢
(
X
⁡
[
I
0
,
…
⁢
,
I
m
-
1
]
)
+
I
m
×
t
for
⁢
⁢
0
<
m
≤
n
,
and
⁢
⁢
{
LIS
⁡
(
X
⁡
[
I
0
]
)
=
LIS
⁡
(
X
)
+
D
0
×
t
+
I
0
×
S
1
LIS
⁡
(
X
⁡
[
I
0
,
…
⁢
,
I
m
]
)
=
LIS
⁡
(
X
⁡
[
I
0
,
…
⁢
,
I
m
-
1
]
)
+
D
m
×
t
+
I
m
×
S
m
+
1
for
⁢
⁢
0
<
m
<
n
,
wherein the notation S1 represents the LIS size of the first dimension, the notation Sm represents the LIS size of the mth dimension, the notation Sm+1 represents the LIS size of the m+1th dimension, the variable t represents the element size, the notation X[I0, . . . , Im] represents the element for the index combination (I0, . . . , Im), the notation LIS(X) represents an offset of the LIS X, the notation LIS(X[I0]) represents an offset of the sub-LIS corresponding to the element X[I0], the notation LIS(X[I0, . . . , Im−1, Im]) represents an offset of the sub-LIS corresponding to the element X[I0, . . . , Im−1, Im], and the notation LIS(X[I0, . . . , Im]) represents an offset of the sub-LIS for the index combination (I0, . . . , Im) and corresponds to the element X[I0, . . . , Im].

### Claim 4 (depends on 1)

The data processing apparatus of claim 1, further comprising:
an input interface, being electrically connected to the processor and configured to receive an instruction comprising an index combination, wherein the index combination is represented as (I0, . . . , Im), the variable m is a non-negative integer between zero and n, the notation Ik represents an index corresponding to the kth dimension, and the variable k is an index between 0 and m,
wherein the processor calculates a value for the element corresponding to the index combination by an aggregation function according to the following equation:
X
⁡
[
I
0
,
…
⁢
,
I
m
]
=
f
⁡
(
LIS
⁡
(
X
⁡
[
I
0
,
…
⁢
,
I
m
]
)
)
=
f
⁡
(
X
⁡
[
I
0
,
…
⁢
,
I
m
,
0
]
,
X
⁡
[
I
0
,
…
⁢
,
I
m
,
1
]
,
…
⁢
,
X
⁡
[
I
0
,
…
⁢
,
I
m
,
D
m
+
1
-
1
]
)
⁢
⁢
for
⁢
⁢
0
≤
m
<
n
,
wherein the notation X[I0, . . . , Im] represents the element for the index combination (I0, . . . , Im), the notation f( ) represents the aggregation function, the notation LIS(X[I0, . . . , Im]) represents the sub-LIS for the index combination (I0, . . . , Im), the notation X[I0, . . . , Im, 0] represents the element for an index combination (I0, . . . , Im, 0), the notation X[I0, . . . , Im, 1] represents the element for an index combination (I0, . . . , Im, 1), the notation X[I0, . . . , Im, Dm+1−1] represents the element for an index combination (I0, . . . , Im, Dm+1−1), and the notation Dm+1 represents the dimension size of the m+1th dimension.

### Claim 5 (depends on 1)

The data processing apparatus of claim 1, further comprising:
an input interface, being electrically connected to the processor and configured to receive an instruction comprising an index combination, wherein the index combination is represented as (I0, . . . , Im), the variable m is a non-negative integer between zero and n, the notation Ik represents an index corresponding to the kth dimension, and the variable k is an index between 0 and m,
wherein the processor calculates a value for the element corresponding to the index combination by a distribution function according to the following equation:
(X[I0, . . . ,Im,0],X[I0, . . . ,Im,1], . . . ,X[I0, . . . ,Im,Dm+1−1])=g(X[I0, . . . ,Im]) for 0≤m<n′
wherein the notation X[I0, . . . , Im] represents the element for the index combination (I0, . . . , Im), the notation g( ) represents the distribution function, the notation X[I0, . . . , Im, 0] represents the element for an index combination (I0, . . . , Im, 0), the notation X[I0, . . . , Im, 1] represents the element for an index combination (I0, . . . , Im, 1), the notation X[I0, . . . , Im, Dm+1−1] represents the element for an index combination (I0, . . . , Im, Dm+1−1), and the notation Dm+1 represents the dimension size of the m+1th dimension.

### Claim 6

A data processing method for use in an electronic apparatus, comprising the following steps of:
accessing a piece of recursively structured data, wherein the piece of recursively structured data has a Location Independent Structure (LIS); and
arranging the piece of recursively structured data in a one-dimensional memory space in the following way:
LIS:=e0∘e1∘ . . . ∘ep−1∘LIS0∘LIS1∘ . . . ∘LISp−1,
wherein the variable p is a positive integer, the notation ei represents an element of the piece of recursively structured data, the notation LISi represents a sub-LIS of the recursively structured data and corresponds to the element ei, the variable i is an index of the elements and is between 0 and p−1, the operator ‘∘’ indicates “contiguous to” in the one-dimensional memory space, each of the sub-LISs is of an LIS size, a depth associated to each sub-LIS is a number of recursions from the top LIS, the depth of each of the LISi equals the depth of the LIS plus one, and the depth of the top LIS is zero,
wherein each of the elements is of an element size, the element sizes are the same, and the LIS sizes of the sub-LISs within the same depth are the same,
wherein the piece of recursively structured data arranged in the one-dimensional memory space defines an array as LIS T X[D0, D1, D2, . . . , Dn],
wherein X is the name of the piece of recursively structured data, the variable n is the maximum LIS depth and is a nonnegative integer, the array is of n+1 dimensions, each of the dimensions corresponds to a dimension size, the notation T represents a data type of the elements, the variable Dj represents the dimension size of the j-th dimension, the j-th dimension corresponds to the j-th depth of the piece of recursively structured data, and the variable j is an index of the dimension between 0 and n,
wherein each of the elements is denoted as X[I0, . . . , Im], the variable m is an integer between 0 and n, the variable Im represents an index corresponding to the m-th dimension, Im is between 0 and Dm−1, the notation X[I0] is the I0-th element of the LIS, the notation X[I0, . . . , Im−1, Im] is the Im-th element of LISmIm−1, and the notation LISmIm−1 represents the Im−1-th sub-LIS of the depth m.

### Claim 7 (depends on 6)

The data processing method of claim 6, wherein the element X[I0, . . . , Im−1, Im] is located by the following path:
LIS→X[I0]→LIS1I0→X[I0,I1]→LIS2I1→ . . . →X[I0, . . . ,Im−1]→LISmIm−1→X[I0, . . . ,Im],
wherein the notation LISjIj−1 represents the sub-LIS corresponding to the element X[I0, . . . , Ij−1] and 0<j≤m.

### Claim 8 (depends on 6)

The data processing method of claim 6, further comprising the following steps of:
receiving an instruction comprising an index combination, wherein the index combination is represented as (I0, . . . , Im); and
retrieving the element corresponding to the index combination and the sub-LIS corresponding to the index combination from the one-dimensional memory space according to the following equations:
⁢
{
S
m
=
D
m
×
(
t
+
S
m
+
1
)
for
⁢
⁢
0
≤
m
≤
n
S
m
=
0
for
⁢
⁢
m
>
n
,
⁢
{
X
⁡
[
I
0
]
=
LIS
⁡
(
X
)
+
I
0
×
t
X
⁡
[
I
0
,
…
⁢
,
I
m
]
=
LIS
⁢
(
X
⁡
[
I
0
,
…
⁢
,
I
m
-
1
]
)
+
I
m
×
t
for
⁢
⁢
0
<
m
≤
n
,
and
⁢
⁢
{
LIS
⁡
(
X
⁡
[
I
0
]
)
=
LIS
⁡
(
X
)
+
D
0
×
t
+
I
0
×
S
1
LIS
⁡
(
X
⁡
[
I
0
,
…
⁢
,
I
m
]
)
=
LIS
⁡
(
X
⁡
[
I
0
,
…
⁢
,
I
m
-
1
]
)
+
D
m
×
t
+
I
m
×
S
m
+
1
for
⁢
⁢
0
<
m
<
n
,
wherein the notation S1 represents the LIS size of the first dimension, the notation Sm represents the LIS size of the mth dimension, the notation Sm+1 represents the LIS size of the m+1th dimension, the variable t represents the element size, the notation X[I0, . . . , Im] represents the element for the index combination (I0, . . . , Im), the notation LIS(X) represents an offset of the LIS X, the notation LIS(X[I0]) represents an offset of the sub-LIS corresponding to the element X[I0], the notation LIS(X[I0, . . . , Im−1, Im]) represents an offset of the sub-LIS corresponding to the element X[I0, . . . , Im−1, Im], and the notation LIS(X[I0, Im]) represents an offset of the sub-LIS for the index combination (I0, . . . , Im) and corresponds to the element X[I0, . . . , Im].

### Claim 9 (depends on 6)

The data processing method of claim 6, further comprising the following step of:
receiving an instruction comprising an index combination, wherein the index combination is represented as (I0, . . . , Im), the variable m is a non-negative integer between zero and n, the notation Ik represents an index corresponding to the kth dimension, and the variable k is an index between 0 and m; and
calculating a value for the element corresponding to the index combination by an aggregation function according to the following equation:
X
⁡
[
I
0
,
…
⁢
,
I
m
]
=
f
⁡
(
LIS
⁡
(
X
⁡
[
I
0
,
…
⁢
,
I
m
]
)
)
=
f
⁡
(
X
⁡
[
I
0
,
…
⁢
,
I
m
,
0
]
,
X
⁡
[
I
0
,
…
⁢
,
I
m
,
1
]
,
…
⁢
,
X
⁡
[
I
0
,
…
⁢
,
I
m
,
D
m
+
1
-
1
]
)
⁢
⁢
for
⁢
⁢
0
≤
m
<
n
,
wherein the notation X[I0, . . . , Im] represents the element for the index combination (I0, . . . , Im), the notation f( ) represents the aggregation function, the notation LIS(X[I0, . . . , Im]) represents the sub-LIS for the index combination (I0, . . . , Im), the notation X[I0, . . . , Im, 0] represents the element for an index combination (I0, . . . , Im, 0), the notation X[I0, . . . , Im, 1] represents the element for an index combination (I0, . . . , Im, 1), the notation X[I0, . . . , Im, Dm+1−1] represents the element for an index combination (I0, . . . , Im, Dm+1−1), and the notation Dm+1 represents the dimension size of the m+1th dimension.

### Claim 10 (depends on 6)

The data processing method of claim 6, further comprising the following step of:
receiving an instruction comprising an index combination, wherein the index combination is represented as (I0, . . . , Im), the variable m is a non-negative integer between zero and n, the notation Ik represents an index corresponding to the kth dimension, and the variable k is an index between 0 and m; and
calculates a value for the element corresponding to the index combination by a distribution function according to the following equation:
(X[I0, . . . ,Im,0],X[I0, . . . ,Im,1], . . . ,X[I0, . . . ,Im,Dm+1−1])=g(X[I0, . . . ,Im]) for 0≤m<n′
wherein the notation X[I0, . . . , Im] represents the element for the index combination (I0, . . . , Im), the notation g( ) represents the distribution function, the notation X[I0, . . . , Im, 0] represents the element for an index combination (I0, . . . , Im, 0), the notation X[I0, . . . , Im, 1] represents the element for an index combination (I0, . . . , Im, 1), the notation X[I0, . . . , Im, Dm+1−1] represents the element for an index combination (I0, . . . , Im, Dm+1−1), and the notation Dm+1 represents the dimension size of the m+1th dimension.

### Claim 11

A non-transitory tangible machine-readable medium, being stored with a computer program, the computer program comprising a plurality of codes, the codes being able to execute a data processing method when the computer program is loaded into an electronic apparatus, the data processing method comprising the steps of:
accessing a piece of recursively structured data, wherein the piece of recursively structured data has a Location Independent Structure (LIS); and
arranging the piece of recursively structured data in an LIS in a one-dimensional memory space in the following way:
LIS:=e0∘e1∘ . . . ∘ep−1∘LIS0∘LIS1∘ . . . ∘LISp−1,
wherein the variable p is a positive integer, the notation ei represents an element of the piece of recursively structured data, the notation LISi represents a sub-LIS of the recursively structured data and corresponds to the element ei, the variable i is an index of the elements and is between 0 and p−1, the operator ‘∘’ indicates “contiguous to” in the one-dimensional memory space, each of the sub-LISs is of an LIS size, a depth associated to each sub-LIS is a number of recursions from the top LIS, the depth of each of the LISi equals the depth of the LB plus one, and the depth of the top LIS is zero,
wherein each of the elements is of an element size, the element sizes are the same, and the LB sizes of the sub-LISs within the same depth are the same,
wherein the piece of recursively structured data arranged in the one-dimensional memory space defines an array as LIS T X[D0, D1, D2, . . . , Dn],
wherein X is the name of the piece of recursively structured data, the variable n is the maximum LIS depth and is a nonnegative integer, the array is of n+1 dimensions, each of the dimensions corresponds to a dimension size, the notation T represents a data type of the elements, the variable Dj represents the dimension size of the j-th dimension, the j-th dimension corresponds to the j-th depth of the piece of recursively structured data, and the variable j is an index of the dimension between 0 and n,
wherein each of the elements is denoted as X[I0, . . . , Im], the variable m is an integer between 0 and n, the variable Im represents an index corresponding to the m-th dimension, Im is between 0 and Dm−1, the notation X[I0] is the I0-th element of the LIS, the notation X[I0, . . . , Im−1, Im] is the Im-th element of LISmIm−1, and the notation LISmIm−1 represents the Im−1-th sub-LIS of the depth m.

### Claim 12 (depends on 11)

The non-transitory tangible machine-readable medium of claim 11, wherein the element X[I0, . . . , Im−1, Im] is located by the following path:
LIS→X[I0]→LIS1I0→X[I0,I1]→LIS2I1→ . . . →X[I0, . . . ,Im−1]→LISmIm−1→X[I0, . . . ,Im],
wherein the notation LISjIj−1 represents the sub-LIS corresponding to the element X[I0, . . . , Ij−1] and 0<j≤m.

### Claim 13 (depends on 11)

The non-transitory tangible machine-readable medium of claim 11, wherein the data processing method further comprises the following steps of:
receiving an instruction comprising an index combination, wherein the index combination is represented as (I0, . . . , Im); and
retrieving the element corresponding to the index combination and the sub-LIS corresponding to the index combination from the one-dimensional memory space according to the following equations:
⁢
{
S
m
=
D
m
×
(
t
+
S
m
+
1
)
for
⁢
⁢
0
≤
m
≤
n
S
m
=
0
for
⁢
⁢
m
>
n
,
⁢
{
X
⁡
[
I
0
]
=
LIS
⁡
(
X
)
+
I
0
×
t
X
⁡
[
I
0
,
…
⁢
,
I
m
]
=
LIS
⁢
(
X
⁡
[
I
0
,
…
⁢
,
I
m
-
1
]
)
+
I
m
×
t
for
⁢
⁢
0
<
m
≤
n
,
and
⁢
⁢
{
LIS
⁡
(
X
⁡
[
I
0
]
)
=
LIS
⁡
(
X
)
+
D
0
×
t
+
I
0
×
S
1
LIS
⁡
(
X
⁡
[
I
0
,
…
⁢
,
I
m
]
)
=
LIS
⁡
(
X
⁡
[
I
0
,
…
⁢
,
I
m
-
1
]
)
+
D
m
×
t
+
I
m
×
S
m
+
1
for
⁢
⁢
0
<
m
<
n
,
wherein the notation S1 represents the LIS size of the first dimension, the notation Sm represents the LIS size of the mth dimension, the notation Sm+1 represents the LIS size of the m+1th dimension, the variable t represents the element size, the notation X[I0, . . . , Im] represents the element for the index combination (I0, . . . , Im), the notation LIS(X) represents an offset of the LIS X, the notation LIS(X[I0]) represents an offset of the sub-LIS corresponding to the element X[I0], the notation LIS(X[I0, . . . , Im−1, Im]) represents an offset of the sub-LIS corresponding to the element X[I0, . . . , Im−1, Im], and the notation LIS(X[I0, . . . , Im]) represents an offset of the sub-LIS for the index combination (I0, . . . , Im) and corresponds to the element X[I0, . . . , Im].

### Claim 14 (depends on 11)

The non-transitory tangible machine-readable medium of claim 11, wherein the data processing method further comprises the following step of:
receiving an instruction comprising an index combination, wherein the index combination is represented as (I0, . . . , Im), the variable m is a non-negative integer between zero and n, the notation Ik represents an index corresponding to the kth dimension, and the variable k is an index between 0 and m; and
calculating a value for the element corresponding to the index combination by an aggregation function according to the following equation:
X
⁡
[
I
0
,
…
⁢
,
I
m
]
=
f
⁡
(
LIS
⁡
(
X
⁡
[
I
0
,
…
⁢
,
I
m
]
)
)
=
f
⁡
(
X
⁡
[
I
0
,
…
⁢
,
I
m
,
0
]
,
X
⁡
[
I
0
,
…
⁢
,
I
m
,
1
]
,
…
⁢
,
X
⁡
[
I
0
,
…
⁢
,
I
m
,
D
m
+
1
-
1
]
)
⁢
⁢
for
⁢
⁢
0
≤
m
<
n
,
wherein the notation X[I0, . . . , Im] represents the element for the index combination (I0, . . . , Im), the notation f( ) represents the aggregation function, the notation LIS(X[I0, . . . , Im]) represents the sub-LIS for the index combination (I0, . . . , Im), the notation X[I0, . . . , Im, 0] represents the element for an index combination (I0, . . . , Im, 0), the notation X[I0, . . . , Im, 1] represents the element for an index combination (I0, . . . , Im, 1), the notation X[I0, . . . , Im, Dm+1−1] represents the element for an index combination (I0, . . . , Im, Dm+1−1), and the notation Dm+1 represents the dimension size of the m+1th dimension.

### Claim 15 (depends on 11)

The non-transitory tangible machine-readable medium of claim 11, wherein the data processing method further comprises the following step of:
receiving an instruction comprising an index combination, wherein the index combination is represented as (I0, . . . , Im), the variable m is a non-negative integer between zero and n, the notation Ik represents an index corresponding to the kth dimension, and the variable k is an index between 0 and m; and
calculates a value for the element corresponding to the index combination by a distribution function according to the following equation:
(X[I0, . . . ,Im,0],X[I0, . . . ,Im,1], . . . ,X[I0, . . . ,Im,Dm+1−1])=g(X[I0, . . . ,Im]) for 0≤m<n′
wherein the notation X[I0, . . . , Im] represents the element for the index combination (I0, . . . , Im), the notation g( ) represents the distribution function, the notation X[I0, . . . , Im, 0] represents the element for an index combination (I0, . . . , Im, 0), the notation X[I0, . . . , Im, 1] represents the element for an index combination (I0, . . . , Im, 1), the notation X[I0, . . . , Im, Dm+1−1] represents the element for an index combination (I0, . . . , Im, Dm+1−1), and the notation Dm+1 represents the dimension size of the m+1th dimension.