Spatial data mining method, spatial data mining apparatus and storage medium

• US 20010051947A1
• Filed: 04/03/2001
• Published: 12/13/2001
• Est. Priority Date: 05/09/2000
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kubo, Harunobu, Morimoto, Yasuhiko
• Granted Patent: US 7,024,402 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: Y10S 707/921 Spatial
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

A spatial data mining apparatus for calculating an optimal distance from a database, wherein spatial information, such as addresses, is stored, includes an input mechanism, for the input of an objective function required for the optimization of a distance, an intermediate table generator 30, for employing in the database starting point data and query point data for calculating the distances between each starting point and each query point and for generating an intermediate table, and an optimal distance calculator for calculating a distance based on the intermediate table generated by the intermediate table generator, in order to optimize the value of the objective function that is entered by the input mechanism.

Claims

1. A spatial data mining method, for introducing spatial rules from a database in which spatial information, such as addresses, is stored, comprising the steps of:

providing from said database a starting point or a starting point group;

defining an objective function that is examined in order to introduce said spatial rules; and

calculating a distance from or an orientation block originating at said starting point or said starting point group in order to optimize said objective function that is defined.

2. The spatial data mining method according to

claim 1

, wherein said objective function is a function for which a distance or an orientation requested by an analyzation business is not provided.

3. The spatial data mining method according to

claim 1

, further comprising a step of:

entering as input parameters the definition of a distance, the definition of said starting point or said starting point group and the definition of said objective function.

4. The spatial data mining method according to

claim 1

, wherein, at said step of calculating said distances, an intermediate table is generated based on starting point set data consisting of said starting point group and said objective function, and in accordance with distance values, attribute values for query points in said database are added together, based on said intermediate table.

5. The spatial data mining method according to

claim 1

, further comprising a step of:

displaying on a map said distance or said orientation block relative to said starting point or said starting point group.

6. A spatial data mining method, for introducing spatial rules from a database in which spatial information, such as addresses, is stored, comprising the steps of:

providing from said database a starting point or a starting point group;

employing said starting point or said starting point group to define an orientation;

defining an objective function that is examined in order to introduce said spatial rules; and

calculating a distance from or an orientation block originating at said starting point or said starting point group in order to optimize said objective function that is defined.

7. The spatial data mining method according to

claim 6

, wherein said objective function is a function for which a distance or an orientation requested by an analyzation business is not provided.

8. The spatial data mining method according to

claim 6

, wherein said orientation block is obtained by employing the numerical value of said orientation used to optimize said objective function.

9. The spatial data mining method according to

claim 6

, wherein a search objective data range, at equal distances from said starting point and from said starting point group, that is appropriate for calculating an orientation is selected as said orientation block.

10. The spatial data mining method according to

claim 6

, further comprising a step of:

displaying on a map said distance or said orientation block relative to said starting point or said starting point group.

11. A spatial data mining method, for generating a data table used to introduce a spatial rule obtained from a spatial information database, comprising the steps of:

providing a set of starting points and a set of query points in a database;

designating an upper limit for a distance between said set of starting points and said set of query points;

calculating a distance between each starting point and each query point;

calculating an angle formed between a starting point and a query point whose distance from said starting point does not exceed said designated upper limit; and

generating a data table using said angle formed with said starting point.

12. A spatial data mining apparatus for calculating an optimal distance from a database, wherein spatial information, such as addresses, is stored, comprising:

input means for inputting of an objective function required for the optimization of a distance;

intermediate table generation means for employing in said database starting point data and query point data for calculating the distances between each starting point and each query point and generating an intermediate table; and

optimal distance calculation means for calculating a distance, based on said intermediate table generated by said intermediate table generation means, in order to optimize the value of said objective function that is entered by said input means.

13. The spatial data mining apparatus according to

claim 12

, wherein said intermediate table generation means includes:

Voronoi diagram preparation means for preparing a Voronoi diagram by using said starting point data in said database;

distance calculation means for employing said Voronoi diagram, prepared by said Voronoi diagram preparation means, and said query point data in said database to calculate distances between individual starting points and individual query points and to generate data records; and

individual distance calculation means for selecting an optimization function from among objective functions to be examined, and adding together record values, collected from said data records, that are required for optimization of each of said distances.

14. The spatial data mining apparatus according to

claim 13

, wherein said Voronoi diagram preparation means repeats plane quarter division in accordance with the number of starting points that are entered, sorts said starting points into end plane pixels obtained by division and selects one starting point in each of said end plane pixels as a representative point for the pertinent pixel, prepares a quaternary incremental tree with pixels at individual levels being defined as intermediate nodes, scans said individual nodes of said quaternary incremental tree in the breadth-first order, beginning at the topmost level, and outputs a set of starting points that are positioned in ranks.

15. A spatial data mining apparatus for calculating an optimal orientation for a database, which includes spatial information, such as addresses, comprising:

input means for inputting of an objective function required for the optimization of an orientation;

intermediate table generation means for employing, based on starting point data and query point data in said database, angles of 0 degrees from said starting points in a specific direction to generate an intermediate table in which the orientation of the locations of said query points are included; and

optimal orientation calculation means for calculating, based on said intermediate table generated by said intermediate table generation means, an orientation for optimizing the value of said objective function that is entered by said input means.

16. The spatial data mining apparatus according to

claim 15

, wherein said intermediate table generation means includes:

Voronoi diagram preparation means for preparing a Voronoi diagram by using said starting point data in said database;

distance calculation means for employing said Voronoi diagram prepared by said Voronoi diagram preparation means and said query point data in said database to calculate distances between individual starting points and individual query points;

orientation calculation means for calculating, based on said distances obtained by said distance calculation means, orientations of said starting points with said query points that fall within a designated distance upper limit, and storing said orientations as data records for said intermediate table; and

individual orientation calculation means for selecting an optimization function from among objective functions to be examined, and collecting and adding record values, from said data records, that are required for optimization of each of said distances.

17. A spatial data mining apparatus, for calculating an optimal distance from or an optimal orientation with a database in which spatial information, such as addresses, is stored, and for outputting said optimal distance or said optimal orientation, comprising:

input means for the input of an objective function for which a distance or an orientation requested by an analyzation business is not provided;

optimal distance/orientation calculation means for employing starting point data and query point data in said database for calculating a distance between, or the orientation of each of the starting points with each of the query points, and calculating said optimal distance or said optimal orientation for the optimization of the value of said objective function; and

display means for displaying, on the screen of a geographical information system, said optimal distance or said optimal orientation calculated by said optimal distance/orientation calculation means.

18. The spatial data mining apparatus according to

claim 17

, wherein said display means uses said optimal distance calculated by said optimal distance/orientation calculation means for the display of circular areas, the centers of which are starting points.

19. The spatial data mining apparatus according to

claim 17

, wherein said display means uses said optimal orientation, calculated by said optimal distance/orientation calculation means, for the display of fan-shaped portions of said circular areas, the origins of said fan-shaped portions being said starting points at said centers of said circular areas.

20. A spatial data mining apparatus, for introducing a spatial rule from a database, which also includes spatial information, such as addresses, comprising:

starting point provision means for providing starting points or starting point groups obtained from said database;

objective function definition means for defining an objective function that is to be examined in order to introduce said spatial rule; and

distance calculation means for calculating distances originating at said starting points or at said starting point groups for optimizing said objective function that is defined.

21. A spatial data mining apparatus, for introducing a spatial rule from a database, which also includes spatial information, such as addresses, comprising:

starting point provision means for providing starting points or starting point groups obtained from said database;

orientation definition means for employing said starting points or said starting point groups to define distances or orientations;

objective function definition means for defining an objective function that is to be examined in order to introduce said spatial rule; and

orientation block calculation means for calculating orientation blocks beginning at said starting points or said starting point groups to optimize said objective function that is defined.

22. A spatial data mining apparatus, for generating data table for introducing a spatial rule from a database, which also includes spatial information, such as orientation, comprising:

starting point/query point provision means for providing a set of starting points and a set of query points in said database;

distance upper limit designation means for designating the upper limit for a distance between said set of starting points and said set of query points;

distance calculation means for calculating a distance between each starting point and each query point;

angle calculation means for calculating an angle formed between a starting point and a query point whose distance from said starting point does not exceed said designated upper limit; and

a data table generation means for generating a data table using said angle formed with said starting point.

23. A storage medium on which is stored a spatial data mining program, which introduces a spatial rule extracted from a database that includes spatial information, such as addresses, based on an objective function for which neither a distance nor an orientation is provided, said program comprising the steps of:

providing a starting point or a starting point group from said database;

employing said starting point or said starting point group to define a distance or an orientation;

defining an objective function that is to be examined; and

calculating a distance measured from said start point or said starting point group, or an orientation block to optimize said objective function that is defined.