Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-03-12
2004-02-03
Alam, Shahid Al (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06687688
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a data management system, a data management method, and a computer-readable medium having stored therein a data management program suitable for managing data such as coordinate data representing points in two-or-more-dimensional spaces.
More particularly, this invention relates to a data management system, a data management method, and a computer-readable medium having stored therein a data management program capable of performing one or more of operations, such as registration, deletion, change, and search (range search, nearest data search, and so forth), on coordinate data on a plane or in a space.
2. Description of the Related art
Many methods for managing multiple-attribute data with the use of computers have been proposed. For example, image processing, computer vision, or drawing management requires computers to manage a huge amount of drawings represented by a large volume of vectors, points, symbols, and so forth. Computers are used to add or delete data, search for desired drawings, and change data.
One of known data management methods is a quad-tree method.
The quad-tree method divides an area into four with the planes each parallel to the two-dimensional plane axes. The method repeats the division recursively until the number of data pieces included in one subarea has become P or less. It then stores the data as a quad-tree. This quad-tree is described, for example, in ACM Computing Surveys, Vol. 20, No. 4, of December, 1988.
A tree generated by this division method is easy to manage because its operation is simple, that is, it only generates child nodes each time it divided a leaf Another advantage of this method is that, because the area is divided into equal-sized sub-areas, the user can identify each sub-area easily. This eliminates the need for the user to memorize each division axis.
On the other hand, this method does not take into account the distribution of data while dividing the area into equal-sized sub-areas. This means that, when data is distributed unevenly, this method generates an unbalanced tree and wastes memory.
The following describes how the quad-tree method stores data. Each sub-area shown in FIG.
13
(A) corresponds to a node with the corresponding number shown in FIG.
13
(B). Thus, the shaded sub-areas in FIG.
13
(A) correspond to the black nodes in FIG.
13
(B).
FIG. 13
was reproduced from
FIG. 3
on page 274 of the above-described document.
However, the enumeration of all the shaded areas (or data included in those areas) represented by a data structure, such as that shown in FIG.
13
(A), requires the user to traverse all the sub-trees.
A tree-structured index, used to store data in a conventional data management method, such as the quad-tree method, allows the user to identify point data in a sub-area as an internal node and/or an external node in a sub-tree whose root is a node. However, enumeration of point data in a node requires the user to traverse all sub-trees.
In this type of tree structured index, a sub-area containing many point data pieces usually corresponds to a large sub-tree. Therefore, even if a large sub-tree containing many point data pieces, it is difficult to reduce the time required for traversing to enumerate one point data piece. Rather, efficient traverse of a large sub-tree requires more memory areas for stacks and flags (provided for each node to represent the status of the traverse operation on that node).
As described above, the conventional data structures require extra memory areas and besides an amount of memory occupied by the coordinate data to be retrieved. In addition, enumeration of data found as that included in a sub-range requires the user to traverse sub-trees until all the desired data are reached. This is inefficient.
Although the conventional data structures are generally efficient for processing such data as to be changed frequently, they are inefficient for processing such data as not to be changed or as to be changed rarely. In addition, although the conventional data structures are generally suitable for processing data limited in range and distribution, they cannot cope non-limited, dynamic range (with distributed precision) data. For example, when the x-axis scale unit differs from the y-axis scale unit, normalization is required. However, the conventional data structure has no specific normalization rule.
From the viewpoint described above, the conventional data management methods disclose neither any efficient access means for accessing data determined to be in a specific range, nor any efficient nearest-coordinate search means.
SUMMARY OF THE INVENTION
This invention seeks to solve the problems associated with the conventional data management methods described above. It is an object of this invention to provide a data management system, a data management method, and a computer-readable medium having stored therein a data management program which efficiently use memory areas and significantly increase search efficiency.
The above object has been achieved by the present invention. One aspect of the present invention is a data management system. The system comprises an index containing n-dimensional coordinate data and a search means for searching the index for the coordinate data. The coordinate data in the index is sorted into lexicographic order of area codes, each code generated by taking a prefix of a predetermined length from a coordinate of each dimension in turn and by concatenating the resulting prefixes in a predetermined order of dimensions.
Another aspect of the present invention is a data management method corresponding to the data management system described above. The method comprises the step of searching an index for n-dimensional coordinate data. The coordinate data in the index is the same as that in the system described above.
Further, another aspect of the present invention is a computer-readable medium having stored therein a data management program for managing n-dimensional data stored in an index, the program searching the index for the n-dimensional coordinate data. The program comprises a means for causing a computer to search the index for the n-dimensional coordinate data. The coordinate data in the index is the same as that in the system described above.
Such a structure of the coordinate data results in that the coordinate data is easily searched based on the area codes. This improves substantially the search efficiency.
REFERENCES:
patent: 4803477 (1989-02-01), Miyatake et al.
patent: 5202986 (1993-04-01), Nickel
patent: 5345516 (1994-09-01), Boyer et al.
patent: 5551024 (1996-08-01), Waters
patent: 5615299 (1997-03-01), Bahl et al.
patent: 5627748 (1997-05-01), Baker et al.
patent: 5701467 (1997-12-01), Freeston
patent: 5799299 (1998-08-01), Fujiwara
patent: 5819286 (1998-10-01), Yang et al.
patent: 5836003 (1998-11-01), Sadeh
patent: 5844561 (1998-12-01), Tanimoto et al.
patent: 5852822 (1998-12-01), Srinivasan et al.
patent: 5963642 (1999-10-01), Goldstein
patent: 6070159 (2000-05-01), Wilson et al.
patent: 6088034 (2000-07-01), Deering
patent: 6137493 (2000-10-01), Kamimura et al.
Aho, et al., pps. 86-93, “The Design and Analysis of Computer Algorithms”, 1974.
D.W. Jones, Communications of the ACM, vol. 29, No. 4, pps. 300-311, “An Empirical Comparison of Priority-Queue and Event-Set Implementations”, Apr., 1986.
H. Samer, ACM Computing Survey, vol. 20, No. 4, pps. 271-309, “Hierarchical Representations of Collections of Small Rectangles”, Dec.,1988.
V.Y. Lum, Communications of the ACM, vol. 13, No. 11, pps. 660-665, “Multi-Attribute Retrieval with Combined Indexes”, Nov., 1970.
J. Nievergelt, et al., ACM Transctions on Database Systems, vol. 9, Nol. 1, pps. 38-71, “The Grid File: An Adaptable, Symmetric Multikey File Structure”, Mar., 1984.
H. Samet, “The Design and Analysis of Spatial Data Structures”, 1990.
V. Gaede, et al., ACM Computing Surveys, vol. 30, No. 2, pps. 170-231, “Multidimensional Access Methods”, Jun., 1998.
Fujihara Mutsumi
Kamimura Shuichi
Al Alam Shahid
Kabushiki Kaisha Toshiba
Ly Anh
LandOfFree
System and method for data management does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for data management, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for data management will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3329835