1. Field of the Invention
The present invention relates to a technique for processing stored data.
2. Description of the Related Art
In recent years, RDBMS (Relational DataBase Management System) that can manage multimedia data has increased. For example, this system has been used for storing map data as multimedia data, managing update of map data, and delivering map data to thin clients. A spatial search index technique has been also studied in order to search map data at high speed.
Also in a field of built-in device, DBMS (Database Management System) having a spatial search function has been developed, and application to other fields, such as a field of car navigation, is expected.
For the spatial search index, a space division method is frequently used, and there can be mentioned R-tree (see FIG. 11) and quad-tree (see FIG. 12). In these methods, a tree structure is formed by appropriately and consecutively dividing 2-dimensional space, in order to remarkably reduce a data processing number upon searching.
The R-tree shown in FIG. 11 is a method for managing spatial information by managing partial regions with bounding rectangles, and further by recursively and hierarchically managing bounding rectangles in the partial region. For a 1st level (1101) of the pertinent space, a bounding rectangle of the partial region is determined, and if desired, depending on a distribution of geometries to be managed in the 1st level (1101), a bounding rectangle as a 2nd level (1102) is determined. Like the 1st level (1101), if desired, depending on a distribution of geometries to be managed in the 2nd level (1102), a bounding rectangle as a 3rd level (1103) is determined. By recursively repeating this division, spatial information can be managed as a tree structure.
The quad-tree shown in FIG. 12 is a method for managing spatial information by regularly dividing a space into four parts at a predetermined proportion, and by recursively repeating the division. A pertinent space as a 1st level, (1201) is divided into four parts at a predetermined proportion, which are taken as a 2nd level (1202). Like the 1st level (1201), the 2nd level (1202) is divided into four parts at a predetermined proportion, which are taken as a 3rd level (1203). By recursively repeating this division, spatial information can be managed as a tree structure.
FIG. 13 is a flowchart showing one example of a conventional processing in which a spatial search is performed using an index of a tree structure with a space being divided into pieces, as shown in FIGS. 11 and 12. First, spatial search conditions are obtained (Step 1301); the tree structure of the spatial search index is recursively searched, to thereby extract a leaf to be searched from a node which agrees with or is included in the spatial search conditions (Step 1302); a pertinent geometry is obtained from the leaf (Step 1303); the obtained geometries are separately compared with the spatial search conditions (it is determined whether or not the pertinent geometry agrees with the spatial search region conditions) (Step 1304); and if the geometry agrees with the conditions, the pertinent geometry is output as a searched result (Step 1305). Next, it is determined whether or not another geometry is present in the pertinent leaf (Step 1306), and if there is a geometry, the procedure returns to Step 1303. When a processing with geometries in the leaf is finished, it is determined whether or not another leaf to be searched is present (Step 1307), and if there is a leaf to be searched, the procedure returns to Step 1302. With such a processing, a geometry present in the target spatial region can be searched at high speed, from among geometries distributed in the space.
With a use of the spatial search index, a search in a spatial region as shown in FIG. 9 can be performed. FIG. 9 shows a searched result for all landmarks within a circle (902) having a certain radius, taking a coordinate (901) of Tokyo station as a center. Landmarks (903) outside the spatial region are not searched, and only landmarks (904) inside the spatial region are searched. In this case, searched landmarks include B restaurant Kanda branch, Y Bank Otemachi branch and X Bank Yurakucho branch.
Such a technique is disclosed in Japanese patent No. 3649430 (Japanese unexamined patent application Kokai No. 2001-14338).
One common application of the RDBMS having the above-mentioned spatial search function is a search under combined conditions of “spatial search conditions” and “other refining conditions”. Examples of the spatial search conditions combined with additional conditions include “gas station along a route” in a field of car navigation, “condominium with 3 bed rooms or more located within a 1-kilometer radius of a station” in a real estate search system, “rival store within a 2-kilometer radius of an existing store” in a local area marketing field.
As one advanced search, there can be mentioned a search under combined conditions of spatial search conditions with attribute conditions (see FIG. 10). FIG. 10 shows a searched result for landmarks tagged with “bank” category, from among landmarks located within a circle (1002) having a certain radius, taking a coordinate (1001) of Tokyo station as a center. As in FIG. 9 that shows a processing result of a general spatial search, landmarks (1003) outside the spatial region are not searched. In addition to this, landmarks (1004) inside the spatial region having attributes that do not agree with conditions are not searched. In other words, only landmarks (1005) inside the spatial region having attributes (also referred to as ‘attribute information’) that agree with the conditions are searched. In this embodiment, B restaurant Kanda branch is located within a circle of the search, but the attribute condition is not bank, and therefore B restaurant Kanda branch is not a targeted landmark. Only Y Bank Otemachi branch and X Bank Yurakucho branch are included in the searched result.
If a conventional RDBMS is used, this search may be performed by adding an attribute column to an existing spatial data column, connecting a plurality of search conditions via AND condition of SQL, and merging and outputting searched result in the RDBMS. In this case, the spatial search alone is not useful for refining the search, since the additional conditions remarkably refines the search. However, high performance is not expected if the searches are separately performed. Moreover, such conditions are frequently used, and thus a search processing takes time. As a result, technique to perform a search processing at high speed has been desired.
Therefore, it would be desirable to provide a technique to perform a spatial search processing at high speed, by including additional information as hint for combined conditions in a spatial search index, to thereby search additional information during the search of the spatial search index.