Method and system for data processing with spatial search

• US 7,668,817 B2
• Filed: 02/13/2007
• Issued: 02/23/2010
• Est. Priority Date: 02/28/2006
• Status: Active Grant

• Current Assignee: Hitachi Solutions Limited (Hitachi, Ltd.)
• Original Assignee: Hitachi, Ltd., Hitachi Software Engineering Co., Ltd. (Hitachi, Ltd.)
• Inventors: Atarashi, Yoshitaka, Enomoto, Masaki, Kimura, Kohji, Tanizaki, Masaaki
• Primary Examiner(s): Vy; Hung T
• Assistant Examiner(s): Thai; Hanh B
• Application Number:
  US11/674,263
• Publication Number:
  US 20080016037A1
• Time in Patent Office: 1,106 Days
• Field of Search: 707 3- 5, 707/100, 701207-208
• US Class Current: 707/760
• CPC Class Codes: G01C 21/26 specially adapted for navigation in a road network
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

A method for processing data performed in a data processing system having a storage unit is provided which includes: creating a spatial index comprising a leaf containing location information and attribute information with respect to a plurality of objects to be searched, and storing the spatial index in the storage unit; and referring to the spatial index stored in the storage unit in response to an input of a search request including location information and attribute information for searching the object to be searched, and extracting the object to be searched that agrees with the search request. With this configuration, a spatial search with subsidiary condition search can be processed at high speed, without merging results of both searches.

Claims

1. A method for processing data performed in a data processing system having a storage unit, comprising

creating a spatial index having a tree structure comprising a leaf containing location information and attribute information other than the location information with respect to a plurality of objects to be searched, and storing the spatial index in the storage unit;

and

referring to the spatial index stored in the storage unit in response to an in input of a search request including location information and attribute information for searching the object to be searched under combined search conditions of spatial search condition based on the location information and attribute condition based on the attribute information, and extracting the object to be searched that agrees with the search request;

wherein said referring to the spatial index for searching the object comprises;

determining whether or not a pertinent geometry agrees with the spatial search condition of the spatial index for each object of the plurality of objects to be searched; and

for each said object,

if the pertinent geometry agrees with the spatial search condition of the spatial search index, obtaining at least one value of subsidiary attribute added to a record of the object;

comparing the obtained value of subsidiary attribute added to the record of the object with the attribute condition of the spatial index to determine whether or not an attribute of the pertinent geometry agrees with the attribute condition of the spatial index; and

if the attribute of the pertinent geometry agrees with the attribute condition of the spatial index, extracting the object as a searched result.

2. The method for processing data according to claim 1, wherein the attribute information is formed of bit information.

3. The method for processing data according to claim 1, wherein x-coordinate data and y-coordinate data of the object to be searched are allocated to the location information, and z-coordinate data of the object to be searched is allocated to the attribute information.

4. The method for processing data according to claim 1, wherein each leaf contained in the spatial index used as an n-dimensional spatial search index stores the attribute information in an additional axis of an (n+1)-dimension as the location information, to perform an (n+1)-dimensional spatial search by referring to the n-dimensional spatial search index.

5. The method for processing data according to claim 1, wherein the attribute information is subsidiary attribute information which is not related to location.

6. The method for processing data according to claim 1,

wherein the spatial index includes a plurality of values that are designated as attribute conditions;

and

wherein the attribute of the pertinent geometry agrees with the attribute condition of the spatial index if at least one of the plurality of values that are designated as attribute conditions in the spatial index agrees with the obtained value of subsidiary attribute added to the record of the object.

7. The method for processing data according to claim 1,

wherein the spatial index includes a plurality of values that are designated as attribute conditions, which are related by an AND condition;

wherein a plurality of values of subsidiary attribute added to the record of the object are obtained;

wherein the obtained values of subsidiary attribute added to the record of the object are compared with the attribute conditions of the spatial index to determine whether or not attributes of the pertinent geometry agree with the attribute conditions of the spatial index; and

wherein the attributes of the pertinent geometry agree with the attribute conditions of the spatial index if the values that are designated as attribute conditions in the spatial index agree with the obtained values of subsidiary attribute added to the record of the object.

8. A computer-readable storage medium storing a plurality of instructions for controlling a data processor for data processing, the plurality of instructions comprising

instructions that cause the data processor to create a spatial index having a tree structure comprising a leaf containing location information and attribute information other than the location information with respect to a plurality of objects to be searched, and store the spatial index in the storage unit;

and

instructions that cause the data processor to refer to the spatial index stored in the storage unit in response to an in input of a search request including the location information and the attribute information for searching the object to be searched under combined search conditions of spatial search condition based on the location information and attribute condition based on the attribute information, and extract the object to be searched that agrees with the search request;

wherein said instructions that cause the data processor to refer to the spatial index for searching the object comprise instructions that cause the data processor to;

determine whether or not a pertinent geometry agrees with the spatial search condition of the spatial index for each object of the plurality of objects to be searched; and

for each said object,

if the pertinent geometry agrees with the spatial search condition of the spatial search index, obtain at least one value of subsidiary attribute added to a record of the object;

compare the obtained value of subsidiary attribute added to the record of the object with the attribute condition of the spatial index to determine whether or not an attribute of the pertinent geometry agrees with the attribute condition of the spatial index; and

if the attribute of the pertinent geometry agrees with the attribute condition of the spatial index, extract the object as a searched result.

9. The computer-readable storage medium according to claim 8, wherein the attribute information is subsidiary attribute information which is not related to location.

10. The computer-readable storage medium according to claim 8,

wherein the spatial index includes a plurality of values that are designated as attribute conditions;

and

wherein the attribute of the pertinent geometry agrees with the attribute condition of the spatial index if at least one of the plurality of values that are designated as attribute conditions in the spatial index agrees with the obtained value of subsidiary attribute added to the record of the object.

11. The computer-readable storage medium according to claim 8,

wherein the spatial index includes a plurality of values that are designated as attribute conditions, which are related by an AND condition;

wherein a plurality of values of subsidiary attribute added to the record of the object are obtained;

wherein the obtained values of subsidiary attribute added to the record of the object are compared with the attribute conditions of the spatial index to determine whether or not attributes of the pertinent geometry agree with the attribute conditions of the spatial index; and

wherein the attributes of the pertinent geometry agree with the attribute conditions of the spatial index if the values that are designated as attribute conditions in the spatial index agree with the obtained values of subsidiary attribute added to the record of the object.

12. The computer-readable storage medium according to claim 8, wherein the attribute information is formed of bit information.

13. The computer-readable storage medium according to claim 8, wherein x-coordinate data and y-coordinate data of the object to be searched are allocated to the location information, and z-coordinate data of the object to be searched is allocated to the attribute information.