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

• US 7,024,402 B2
• Filed: 04/03/2001
• Issued: 04/04/2006
• Est. Priority Date: 05/09/2000
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Morimoto, Yasuhiko, Kubo, Harunobu
• Primary Examiner(s): Gaffin, Jeffrey A.
• Assistant Examiner(s): PHAM, HUNG Q
• Application Number:
  US09/825,013
• Publication Number:
  US 20010051947A1
• Time in Patent Office: 1,827 Days
• Field of Search: 707/2, 707/100, 707/3, 707/4, 707/5, 707/102, 707/103.R
• US Class Current: 707/776
• 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 apparatus for calculating an optimal distance from a database, wherein spatial information, including addresses, is stored, the apparatus 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, wherein said intermediate table generation means comprises 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 the objective function, and adding together record values, collected from said data records, that are required for optimization of each of said distances; 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,

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.

2. A spatial data mining apparatus for calculating an optimal orientation for a database, which includes spatial information, including addresses, the apparatus 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 starting points in a specific direction to generate an intermediate table in which the orientation of the locations of said query points are included, 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 the objective function, and collecting and adding record values, from said data records, that are required for optimization of each of said distances; and

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

wherein 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.