×

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
First Claim
Patent Images

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.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×