Multidimensional data management method, multidimensional data management apparatus and medium onto which is stored a multidimensional data management program

• US 6,137,493 A
• Filed: 10/16/1997
• Issued: 10/24/2000
• Est. Priority Date: 10/16/1996
• Status: Expired due to Term

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Hasegawa, Yoshiaki, Wada, Kiyoshi, Fujihara, Mutsumi, Kamimura, Shuichi
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US08/951,636
• Time in Patent Office: 1,104 Days
• Field of Search: 345/419, 345/427, 345/440, 345/433, 345/117, 345/118, 345/423, 345/435, 345/420
• US Class Current: 345/423
• CPC Class Codes: G06F 16/2264 Multidimensional index structures

Abstract

In order to manage a plurality of sets of multidimensional data positioned in a specific area of a computer, when hierarchically dividing a first area within the specific area into second areas that are to constitute child areas thereof, a decision is made as to whether or not a division condition, which is based upon the state achieved when the sets of multidimensional data are allocated to the first area and the state achieved when the sets of multidimensional data are allocated to the second areas, is satisfied. When it is decided that the division condition will be satisfied, the first area is hierarchically divided into the second areas to allocate the sets of multidimensional data to the second areas.

Claims

1. A multidimensional data management method for managing a plurality of sets of multidimensional data positioned in a specific area of a computer, said method comprising:

when hierarchically dividing a first area within said specific area into second areas which are to constitute child areas thereof, making a decision as to whether or not a division condition based upon a state achieved when said sets of multidimensional data are allocated to said first area and a state achieved when said sets of multidimensional data are allocated to said second areas is satisfied;

dividing hierarchically said first area into said second areas, if said division condition is determined to be satisfied; and

allocating said sets of multidimensional data to said second areas.

3. A multidimensional data management method according to claim 1 or 2, wherein:

a decision is made as to whether or not division is to be performed based upon said division condition in which the total number of sets of multidimensional data in said second areas when said sets of multidimensional data belong to said second areas and the number of sets of multidimensional data in said first area when said sets of multidimensional data belong to said first area are compared.

4. A multidimensional data management method according to claim 1 or 2, wherein:

a decision is made as to whether or not division is to be performed based upon said division condition in which the number of sets of multidimensional data in said first area when said sets of multidimensional data belong to said first area and the number of sets of multidimensional data in a plurality of areas among said second areas when said sets of multidimensional data belong to said plurality of areas among said second areas are compared.

5. A multidimensional data management method according to claim 1 or 2, wherein:

when said first area is divided, registering each of said sets of multidimensional data by making a decision as to whether each of said sets of multidimensional data is to be reregistered in second areas created through division or in said first area.

6. A multidimensional data management method according to claim 5, wherein:

decision making as to whether each of said sets of multidimensional data is to be reregistered in said first area or in said second areas is based upon a condition that said set of multidimensional data does not include said first area completely.

7. A multidimensional data management method according to claim 5, wherein:

decision making as to whether each of said sets of multidimensional data is to be reregistered in said first area or in said second areas is based upon a condition that the number of said second areas over which said set of multidimensional data overlaps is equal to or smaller than a preset value.

8. A multidimensional data management method according to claim 5, wherein:

decision making as to whether each of said sets of multidimensional data are to be reregistered in said first area or in said second areas is based upon a condition that, with an upper limit on the number of areas over which overlapping registrations may be made for each set of said multidimensional data set in advance, the number of overlapping registrations is equal to or smaller than said upper limit if said set of multidimensional data is registered in said second areas.

18. A multidimensional data management method according to any of claims 1, 2, 3 and 13, further comprising a range search step of searching sets of multidimensional data belonging in a specified range within said specific area.

19. A multidimensional data management method according to any of claims 1, 2, 3 and 13, further comprising a nearest neighbor data search step of searching a set of multidimensional data nearest to a specified point within said specific area.

20. A multidimensional data management method according to claim 19, wherein said nearest data search step further comprises:

a step of expanding the search range until one candidate for nearest neighbor set of multidimensional data is determined, when no sets of multidimensional data are registered in the smallest area containing said specific point.

2. A multidimensional data management method for managing a plurality of sets of multidimensional data positioned in a specific area of a computer, said method comprising:

when hierarchically dividing a first area within said specific area into second areas which are to constitute child areas thereof, making a decision as to whether or not a division condition based upon a state achieved when said sets of multidimensional data are allocated to said first area and a state achieved when said sets of multidimensional data are allocated to said second areas is satisfied;

dividing hierarchically said first area into said second areas and allocating said sets of multidimensional data to said second areas, if said division condition is determined to be satisfied;

making a decision as to whether or not a merging condition based upon a state achieved when said sets of multidimensional data are allocated to said second areas and a state achieved when said sets of multidimensional data are allocated to said first area is satisfied; and

merging said second areas with said first area and allocating said sets of multidimensional data to said first area, if said merging condition is determined to be satisfied.

10. A multidimensional data management method according to claim 9 or 2, wherein:

a decision is made as to whether or not merging is to be performed based upon said merging condition in which the total number of sets of multidimensional data in said second areas when said sets of multidimensional data belong to said second areas and the number of sets of multidimensional data in said first area when said sets of multidimensional data belong to said first area are compared.

11. A multidimensional data management method according to claim 9 or 2, wherein:

a decision is made as to whether or not merging is to be performed based upon said merging condition in which the number of sets of multidimensional data in said first area when said sets of multidimensional data belong to said first area and the number of sets of multidimensional data in a plurality of areas among said second areas when said sets of multidimensional data belong to said plurality of areas among said second areas are compared.

12. A multidimensional data management method according to claim 9 or 2, wherein:

said merging condition allows said second areas to be merged when, with the number of sets of multidimensional data that may be registered in each of said second areas set equal to or lower than a specific value, the number of sets of multidimensional data registered in each of said second areas sharing one common parent area is smaller than said specific value.

9. A multidimensional data management method for managing a plurality of sets of multidimensional data positioned in a specific area of a computer, said method comprising:

when a first area within said specific area has been hierarchically divided into second areas which are to constitute child areas thereof, making a decision as to whether or not a merging condition based upon a state achieved when said sets of multidimensional data are allocated to said second areas and a state achieved when said sets of multidimensional data are allocated to said first area is satisfied;

merging said second areas with said first area, if said merging condition is determined to be satisfied; and

allocating said sets of multidimensional data to said first area.

13. A multidimensional data management method for managing a plurality of sets of multidimensional data positioned in a specific area of a computer, said method comprising a step of making a decision, when a first area within said specific area has been hierarchically divided into second areas where are to constitute child areas thereof, as to whether said set of multidimensional data is to be registered in said first area or in said second areas.

14. A multidimensional data management method according to claim 13, wherein:

a decision is made as to whether said set of multidimensional data is to be registered in said first area or in said second areas, based upon a condition whereby areas where said set of multidimensional data is to be registered is selected in correspondence to the number of said second areas over which said set of multidimensional data overlaps.

15. A multidimensional data management method according to claim 13, wherein:

a decision is made as to whether said set of multidimensional data is to be registered in said first area or in said second areas, based upon a condition whereby, with a limit on the size of an area where each set of multidimensional data may be registered set in advance respectively, areas where said set of multidimensional data is to be registered are selected in conformance to said limit.

16. A multidimensional data management method according to claim 13, wherein:

a decision is made as to whether said set of multidimensional data is to be registered in said first area or in said second areas, based upon a condition whereby, with a limit on the number of areas over which overlapping registrations may be made for each set of said multidimensional data set in advance respectively, areas where said set of multidimensional data is to be registered are selected in conformance to said limit.

17. A multidimensional data management method according to claim 13, wherein:

a decision is made as to whether said set of multidimensional data is to be registered in said first area or in said second areas, based upon a condition whereby areas where said set of multidimensional data is to be registered is selected through comparison of the size of said set of multidimensional data and the size of said first area or said second areas.

21. A multidimensional data management apparatus for managing a plurality of sets of multidimensional data positioned in a specific area of a computer, said apparatus comprising:

means for making a decision, when hierarchically dividing a first area within said specific area into second areas which are to constitute child areas thereof, as to whether or not a division condition based upon a state achieved when said sets of multidimensional data are allocated to said first area and a state achieved when said sets of multidimensional data are allocated to said second areas is satisfied;

means for hierarchically dividing said first area into said second areas when said division condition is determined to be satisfied; and

means for allocating said sets of multidimensional data to said second areas.

23. A multidimensional data management apparatus according to claim 21 or 22, wherein:

a decision is made as to whether or not division is to be performed based upon said division condition in which the total number of sets of multidimensional data in said second areas when said sets of multidimensional data belong to said second areas and the number of sets of multidimensional data in said first area when said sets of multidimensional data belong to said first area are compared.

24. A multidimensional data management apparatus according to claim 21 or 22, wherein:

a decision is made as to whether or not division is to be performed based upon said division condition in which the number of sets of multidimensional data in said first area when said sets of multidimensional data belong to said first area and the number of sets of multidimensional data in a plurality of areas among said second areas when said sets of multidimensional data belong to said plurality of areas among said second areas are compared.

25. A multidimensional data management apparatus according to claim 21 or 22, wherein:

when said first area is divided, each of said sets of multidimensional data are reregistered by making a decision as to whether each of said sets of multidimensional data is to be reregistered in second areas created through division or to said first area.

26. A multidimensional data management apparatus according to claim 25, wherein:

decision making as to whether each of said sets of multidimensional data is to be reregistered in said first area or in said second areas is based upon a condition that said set of multidimensional data does not include said first area completely.

27. A multidimensional data management apparatus according to claim 25, wherein:

decision making as to whether each of said sets of multidimensional data is to reregistered in said first area or in said second areas is based upon a condition that the number of said second areas over which said set of multidimensional data overlaps is equal to or smaller than a preset value.

28. A multidimensional data management apparatus according to claim 25, wherein:

decision making as to whether each of said sets of multidimensional data are to be reregistered in said first area or in said second areas is based upon a condition that, with an upper limit on the number of areas over which overlapping registrations may be made for each set of said multidimensional data set in advance, the number of overlapping registrations is equal to or smaller than said upper limit if said set of multidimensional data is registered in said second areas.

38. A multidimensional data management apparatus according to any of claims 21, 29, 22, and 33, further comprising range search means for searching sets of multidimensional data belonging in a specified range within said specific area.

39. A multidimensional data management apparatus according to any of claims 21, 29, 22, and 33, further comprising nearest neighbor data search means for searching a set of multidimensional data nearest to a specified point within said specific area.

40. A multidimensional data management apparatus according to claim 39, wherein said nearest data search means, when no sets of multidimensional data are registered in the smallest area containing said specific point, expands the search range until one candidate for nearest neighbor set of multidimensional data is determined.

22. A multidimensional data management apparatus for managing a plurality of sets of multidimensional data positioned in a specific area of a computer, said apparatus comprising:

means for making a decision, when hierarchically dividing a first area within said specific area into second areas which are to constitute child areas thereof, as to whether or not a division condition based upon a state achieved when said sets of multidimensional data are allocated to said first area and a state achieved when said sets of multidimensional data are allocated to said second areas is satisfied;

means for hierarchically dividing said first area into said second areas when said are determined to be satisfied;

means for making a decision as to whether or not a merging condition based upon a state achieved when said sets of multidimensional data are allocated to said second areas and a state achieved when said sets of multidimensional data are allocated to said first area is satisfied;

means for merging said second areas with said first area when said merging condition is determined to be satisfied; and

means for allocating said sets of multidimensional data in at least either said first area or said second areas based upon results of said decision.

30. A multidimensional data management apparatus according to claim 29 or 22, wherein:

a decision is made as to whether or not merging is to be performed based upon said merging condition in which the total number of sets of multidimensional data in said second areas when said sets of multidimensional data belong to said second areas and the number of sets of multidimensional data in said first area when said sets of multidimensional data belong to said first area are compared.

31. A multidimensional data management apparatus according to claim 29 or 22, wherein:

a decision is made as to whether or not merging is to be performed based upon said merging condition in which the number of sets of multidimensional data in said first area when said sets of multidimensional data belong to said first area and the number of sets of multidimensional data in a plurality of areas among said second areas when said sets of multidimensional data belong to said second areas are compared.

32. A multidimensional data management apparatus according to claim 29 or 22, wherein:

said merging condition allows said second areas to be merged when, with the number of sets of multidimensional data that may be registered in each of said second areas set equal to or lower than a specific value, the number of sets of multidimensional data registered in each of said second areas sharing one common parent area is smaller than said specific value.

29. A multidimensional data management apparatus for managing a plurality of sets of multidimensional data positioned in a specific area of a computer, said apparatus comprising:

means for making a decision, when a first area within said specific area has been hierarchically divided into second areas which are to constitute child areas thereof, as to whether or not a merging condition based upon a state achieved when said sets of multidimensional data are allocated to said second areas and a state achieved when said sets of multidimensional data are allocated to said first area is satisfied;

means for merging said second areas with said first area when said merging condition is determined to be satisfied; and

means for allocating said sets of multidimensional data to said first area.

33. A multidimensional data management apparatus for managing a plurality of sets of multidimensional data positioned in a specific area of a computer, comprising:

means for making a decision, when a first area within said specific area has been hierarchically divided into second areas where are to constitute child areas thereof, as to whether said set of multidimensional data is to be registered in said first area or in said second areas.

34. A multidimensional data management apparatus according to claim 33, wherein:

a decision is made as to whether said set of multidimensional data is to be registered in said first area or in said second areas, based upon a condition whereby areas where said set of multidimensional data is to be registered is selected in correspondence to the number of said second areas over which said set of multidimensional data overlaps.

35. A multidimensional data management apparatus according to claim 33, wherein:

a decision is made as to whether said set of multidimensional data is to be registered in said first area or in said second areas, based upon a condition whereby, with a limit on the size of an area where each set of multidimensional data may be registered set in advance respectively, areas where said set of multidimensional data is to be registered are selected in conformance to said limit.

36. A multidimensional data management apparatus according to claim 33, wherein:

a decision is made as to whether said set of multidimensional data is to be registered in said first area or in said second areas, based upon a condition whereby, with a limit on the number of areas over which overlapping registrations may be made for each set of said multidimensional data set in advance respectively, areas where said set of multidimensional data is to be registered are selected in conformance to said limit.

37. A multidimensional data management apparatus according claim 33, wherein:

a decision is made as to whether said set of multidimensional data is to be registered in said first area or in said second areas, based upon a condition whereby an area where said set of multidimensional data is to be registered selected through comparison of the size of said set of multidimensional data and the size of said first area or said second areas.

41. A storage medium onto which is stored a computer program that implements a multidimensional data management method for managing a plurality of sets of multidimensional data positioned in a specific area of a computer, said multidimensional data management method comprising the steps of:

making a decision, when hierarchically dividing a first area within said specific area into second areas which are to constitute child areas thereof, as to whether or not a division condition based upon a state achieved when said sets of multidimensional data are allocated to said first area and a state achieved when said sets of multidimensional data are allocated to said second areas is satisfied;

divided hierarchically said first area into said second areas, if said division condition is determined to be satisfied; and

allocating said sets of multidimensional data to said second areas.

42. A storage medium onto which is stored a computer program that implements a multidimensional data management method for managing a plurality of sets of multidimensional data positioned in a specific area of a computer, said multidimensional data management method comprising the steps of:

making a decision, when a first area within said specific area has been hierarchically divided into second areas which are to constitute child areas thereof, as to whether or not a merging condition based upon a state achieved when said sets of multidimensional data are allocated to said second areas and a state achieved when said sets of multidimensional data are allocated to said first area is satisfied;

merging said second areas with said first area, if said merging condition is determined to be satisfied; and

allocating said sets of multidimensional data to said first area.

43. A storage medium onto which is stored a computer program that implements a multidimensional data management method for managing a plurality of sets of multidimensional data positioned in a specific area of a computer, said multidimensional data management method comprising the steps of:

making a decision, when hierarchically dividing a first area within said specific area into second areas which are to constitute child areas thereof, as to whether or not a division condition based upon a state achieved when said sets of multidimensional data are allocated to said first area and a state achieved when said sets of multidimensional data are allocated to said second areas is satisfied;

dividing hierarchically said first area into said second areas if said division condition is determined to be satisfied;

allocating said sets of multidimensional data to said second areas;

making a decision as to whether or not a merging condition based upon a state achieved when said sets of multidimensional data are allocated to said second areas and a state achieved when said sets of multidimensional data are allocated to said first area is satisfied;

merging said second areas with said first area if said merging condition is determined to be satisfied; and

allocating said sets of multidimensional data to said first area.

44. A storage medium onto which is stored a computer program that implements a multidimensional data management method for managing a plurality of sets of multidimensional data positioned in a specific area of a computer, said multidimensional data management method comprising a step of making a decision, when a first area within said specific area has been hierarchically divided into second areas where are to constitute child areas thereof, as to whether said set of multidimensional data is to be registered in said first area or in said second areas.