INFORMATION PROCESSING APPARATUS AND CONTROL METHOD THEREOF

• US 20130212107A1
• Filed: 01/22/2013
• Published: 08/15/2013
• Est. Priority Date: 02/13/2012
• Status: Abandoned Application

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Uchida, Yumiko
• Application Number:
  US13/747,195
• Publication Number:
  US 20130212107A1
• Time in Patent Office: Days
• US Class Current: 707/739
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/51 Indexing; Data structures therefor; Storage structures

Abstract

Enlargement values indicating a degree of enlargement when spatial data is stored in a partial spatial region are calculated for one or more partial spatial regions within a multidimensional index, and in the case where the enlargement value is greater than or equal to a threshold value, a new partial spatial region that contains at least the spatial data is generated.

Claims

1. An information processing apparatus that executes a multidimensional indexing process that divides a multidimensional space into partial spatial regions, stores the partial spatial regions in nodes, and when registering spatial data, enlarges the partial spatial regions to contain the spatial data, the apparatus comprising:

an input unit configured to input spatial data configured of points or spatial regions into a multidimensional index that is constructed within a storage apparatus;

a calculation unit configured to calculate enlargement values, for one or more partial spatial regions in the nodes of the multidimensional index, for the case where the spatial data is stored;

a selection unit configured to select, from among the partial spatial regions whose enlargement values have been calculated by the calculation unit, a partial spatial region to serve as a storage destination candidate of the spatial data; and

a generation unit configured to generate a new partial spatial region that contains at least the spatial data in the case where the enlargement value for the storage destination candidate partial spatial region selected by the selection unit is greater than or equal to a threshold.

2. The information processing apparatus according to claim 1,

wherein the selection unit is configured to use, as the storage destination candidate, the partial spatial region whose enlargement value calculated by the calculation unit is the lowest.

3. The information processing apparatus according to claim 1,

wherein the threshold is set based on a maximum value or an average value of the partial spatial regions in the multidimensional index.

4. The information processing apparatus according to claim 1,

wherein the enlargement value is represented as a difference or a ratio between the area of the partial spatial region after the spatial data has been stored and the area of the partial spatial region before the spatial data has been stored.

5. The information processing apparatus according to claim 1,

wherein the enlargement value is represented as a difference or a ratio between the volume of the partial spatial region after the spatial data has been stored and the volume of the partial spatial region before the spatial data has been stored.

6. The information processing apparatus according to claim 1, further comprising:

a first time information acquisition unit configured to acquire first time information added to the spatial data; and

a second time information acquisition unit configured to acquire the second time information for one or more pieces of spatial data in the nodes of the multidimensional index,

wherein the generation unit generates a new partial spatial region that contains at least the spatial data in the case where the enlargement value is greater than or equal to the threshold and the difference between the first time information and the second time information is greater than or equal to a set value.

7. A control method for an information processing apparatus that executes a multidimensional indexing process that divides a multidimensional space into partial spatial regions, stores the partial spatial regions in nodes, and when registering spatial data, enlarges the partial spatial regions to contain the spatial data, the method comprising:

an input step of an input unit inputting spatial data configured of points or spatial regions into the multidimensional index that is constructed within a storage apparatus;

a calculation step of a calculation unit calculating enlargement values, for one or more partial spatial regions in the nodes of the multidimensional index, for the case where the spatial data is stored;

a selection step of a selection unit selecting, from among the partial spatial regions whose enlargement values have been calculated in the calculation step, a partial spatial region to serve as a storage destination candidate of the spatial data; and

a generation step of a generation unit generating a new partial spatial region that contains at least the spatial data in the case where the enlargement value for the storage destination candidate partial spatial region selected in the selection step is greater than or equal to a threshold.

8. A computer-readable storage medium in which is stored a program that causes a computer to implement control of an information processing apparatus that executes a multidimensional indexing process that divides a multidimensional space into partial spatial regions, stores the partial spatial regions in nodes, and when registering spatial data, enlarges the partial spatial regions to contain the spatial data, the program causing a computer to function as:

an input unit configured to input spatial data configured of points or spatial regions into the multidimensional index that is constructed within a storage apparatus;

a calculation unit configured to calculate enlargement values, for one or more partial spatial regions in the nodes of the multidimensional index, for the case where the spatial data is stored;

a selection unit configured to select, from among the partial spatial regions whose enlargement values have been calculated by the calculation unit, a partial spatial region to serve as a storage destination candidate of the spatial data; and

a generation unit configured to generate a new partial spatial region that contains at least the spatial data in the case where the enlargement value for the storage destination candidate partial spatial region selected by the selection unit is greater than or equal to a threshold.

9. An information processing apparatus that executes a multidimensional indexing process that divides a multidimensional space into partial spatial regions, associates the partial spatial regions with nodes in a multidimensional index, and when registering spatial data, enlarges the partial spatial regions corresponding to the nodes so as to contain the spatial data, the apparatus comprising:

an input unit configured to input spatial data configured of points or spatial regions into the multidimensional index that is constructed within a storage apparatus;

an acquisition unit configured to acquire an enlargement value of the partial spatial region in the case where the inputted spatial data is registered in the node of the multidimensional index corresponding to the partial spatial region; and

a registration unit configured to generate a new node corresponding to a new partial spatial region that contains at least the spatial data and register the spatial data in the new node in the case where the magnitude of the enlargement value is greater than a threshold.

10. The information processing apparatus according to claim 9,

wherein the enlargement values of one or more partial spatial regions are obtained by the acquisition unit and the partial spatial region having the lowest enlargement value is used as a registration destination candidate.

11. The information processing apparatus according to claim 9,

wherein the threshold is set based on a maximum value or an average value of the partial spatial regions in the multidimensional index.

12. The information processing apparatus according to claim 9,

wherein the enlargement value is represented as a difference or a ratio between the area of the partial spatial region after the spatial data has been registered and the area of the partial spatial region before the spatial data has been registered.

13. The information processing apparatus according to claim 9,

wherein the enlargement value is the area of the partial spatial region after the spatial data has been registered.

14. The information processing apparatus according to claim 9, further comprising:

a designation unit configured to designate a search region for the spatial data;

a determination unit configured to determine whether or not the search region and the partial spatial region overlap; and

a search unit configured to search for a node corresponding to the partial spatial region determined by the determination unit to overlap.

15. The information processing apparatus according to claim 9,

wherein the multidimensional index is configured of hierarchically-structured nodes.

16. The information processing apparatus according to claim 9,

wherein there are cases where the partial spatial region is contained in another partial spatial region and cases where the partial spatial region is not contained in another partial spatial region.

17. The information processing apparatus according to claim 15,

wherein the hierarchical structure is a hierarchy based on the containment relationships between the partial spatial regions.

18. The information processing apparatus according to claim 14,

wherein the search unit is configured to search for the node in a plurality of hierarchies corresponding to the partial spatial region determined by the determination unit to overlap.

19. A control method for an information processing apparatus that executes a multidimensional indexing process that divides a multidimensional space into partial spatial regions, associates the partial spatial regions with nodes in a multidimensional index, and when registering spatial data, enlarges the partial spatial regions corresponding to the nodes so as to contain the spatial data, the method comprising:

an input step of inputting spatial data configured of points or spatial regions into the multidimensional index that is constructed within a storage apparatus;

an acquisition step of acquiring an enlargement value of the partial spatial region in the case where the inputted spatial data is registered in the node of the multidimensional index corresponding to the partial spatial region; and

a registration step of generating a new node corresponding to a new partial spatial region that contains at least the spatial data and registering the spatial data in the new node in the case where the magnitude of the enlargement value is greater than a threshold.

20. A computer-readable storage medium in which is stored a program that causes a computer to implement control of an information processing apparatus that executes a multidimensional indexing process that divides a multidimensional space into partial spatial regions, associates the partial spatial regions with nodes in a multidimensional index, and when registering spatial data, enlarges the partial spatial regions corresponding to the nodes so as to contain the spatial data, the program causing a computer to function as:

an input unit configured to input spatial data configured of points or spatial regions into the multidimensional index that is constructed within a storage apparatus;

an acquisition unit configured to acquire an enlargement value of the partial spatial region in the case where the inputted spatial data is registered in the node of the multidimensional index corresponding to the partial spatial region; and

a registration unit configured to generate a new node corresponding to a new partial spatial region that contains at least the spatial data and register the spatial data in the new node in the case where the magnitude of the enlargement value is greater than a threshold.