Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-06-14
2004-06-29
Alam, Shahid (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06757686
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention is directed to a method and apparatus for representing indexing information in a database, and more particularly to a method and system for representing indexing and query information using an interval hash tree to allow efficient query object localization.
2. Description of the Related Art
As image databases grow larger and larger in size, index structures for fast navigation become important. In particular, when the goal is to locate object queries in large image databases using their spatial layout information, traditional index structures used in databases such as B-tree, R-tree, R*-tree, etc., become unsuitable, especially, since the query object must be localized in the presence of pose changes, occlusions and spurious data in images.
More particularly, when the goal is to locate object queries in large image databases, it is desirable to avoid a detailed search of either the image database or the images themselves. This is due to several reasons.
First, without a perfect segmentation, it is not clear which collection of image regions comes from the query object without exploring multiple possibilities. This becomes very time-consuming, if not computationally prohibitive. This problem is made worse when changes in imaging conditions and pose changes alter the appearance of the object in images. Finally, occlusions and background clutter make it difficult to interpret partial object appearances. Robustly locating objects under these conditions requires efficient index structures that can consolidate pose-invariant information within and across images in a compact and efficiently searchable form. This problem is often recognized but has not been explicitly addressed prior to the present invention.
To illustrate the above problem, consider locating a query based on its spatial layout of regions. This requires modeling the layout of regions in images of the database, and representing the layout in a suitable index structure. The matching of the query regions then involves finding the best subset of image regions in the database that are likely to arise from the query object regions. Frequently, the information about the regions can be represented by suitable bounding boxes, which for scene regions are overlapping windows. Then, the query localization problem reduces to the problem of finding all the image database intervals that overlap with a set of query intervals.
An efficient data structure and algorithm for the solution to this problem is important not only in content-based retrieval of image databases, but also in a number of other applications such as map-based navigation systems, VLSI design and testing, and flight simulation.
For example, state-of-the-art cars are equipped with vehicle navigation systems that help the user determine his/her position and guide to the user to his/her destination. Such a system stores a whole roadmap of for example, the entire U.S. It also keeps track of where the user is, so that it can show the appropriate part of the roadmap at any time on a small computer screen. This will usually be a rectangular region around the user's present position.
To be of any use, the map should contain sufficient detail. A detailed map, however, contains an enormous amount of data, not all of which can be displayed on the screen at one time. In that case, given a query region isolated by a user, the system must find that part of the map (roads, cities, and so on) that lie in the window, and display them. This will require finding all regions of the map represented by possibly overlapping bounding boxes that overlap with the query window(s). Checking every single feature of the map to see if it lies inside the query window is not feasible due to the amount of data.
Traditional index structures are insufficient for object localization under the above circumstances. That is, while these data structures do address the search aspect, most of the conventional indexing structures are focused on reducing the seek time on disk reads for secondary memory data storage, and the robust localization aspect has not been well-addressed.
For example, R-trees and their variants [Guttman, Proc. SIGMOD, 1984, pp. 47-57, Beckman et al., Proc. SIGMOD, 1990, pp. 322-331, Sellis, Roussopolous and Faloustous, VLDB 1987, pp. 507-519, Katayama and Satoh, SIGMOD 1997, pp. 369-380 White and Jain, Int. Conf. On Data Engg., 1996, pp. 516-523, Robinson, Proc. SIGMOD 1981, pp. 10-18] assume the object-containing region in the image can be enclosed by bounding rectangles and focus on efficient grouping of the enclosing rectangles at successive levels to yield a balanced search tree that is optimized for disk accesses. The search for object queries in such index structures involves finding all database rectangles that overlap a query rectangle. Under changes in pose, the bounding rectangles undergo considerable change including translation, so that the search using these index structures no longer yields a match to the query. Other search trees such as k-D trees are used more for point searches than rectangle searches. That is, the database access problem addressed using those trees is determining the set of database points that fall within a single query rectangle. There is also prior art in addressing the general rectangle intersection problem [Six-Wood, BIT, vol. 20, pp. 426-433, 1980] where the problem is to determine the set of intersecting rectangles in a n-D plane. Efficient implementation of the rectangle intersection algorithm also exploit the 1d-interval tree, a data structure proposed by Edelsbrunner [Edelsbrunner, Rep. F59, Tech. Univ. Graz, 1980]. This invention proposes a 2D extension to the interval tree proposed by Edelsbrunner.
Thus while representing rectangles in a conventional spatial access structure such as an R-tree is a possibility, unless the search for all query intervals can be consolidated, this would be inefficient. Another possibility is to use an index structure such as a multi-dimensional hash table as done in geometric hashing. However, these tables would require quantizing the space of rectangles into cells and recording the presence of intervals in each cell, an operation that would be computationally prohibitive, both in storage space and in search time during indexing. Finally, graph-like representations that capture the layout of query or database rectangles are not suitable either due to the complexity associated with sub-graph matching.
Thus, representing database intervals in a manner that avoids a repetitious search for query affine intervals can be a difficult problem. In fact, it turns out this is a well-known problem in computational geometry, an efficient solution of which is needed in several applications besides image databases, such as map-based navigation systems, VLSI design and testing, and flight simulation, as discussed above.
What is needed is a representation of overlapping window information in a suitable index structure which can also be quickly searched to retrieve the relevant intervals. Further, when there are multiple query intervals, it would be advantageous to consolidate the multiple searches so as to avoid repetition.
SUMMARY OF THE INVENTION
In view of the foregoing and other problems, disadvantages, and drawbacks of the conventional methods and structures, an object of the present invention is to provide a method and structure in which the above problems are solved.
In a first aspect of the present invention, a system and method for representing database information for multiple windows using a two-way interval tree called the interval hash tree is presented. A second aspect of the present invention is the notion of representing the query interval information also as an interval hash tree and matching the query interval tree nodes to the database interval tree nodes in a manner that avoids redundant exploration of nodes for overlapping query intervals.
Thus, with the unique and unobvious features of the present
Megiddo Nimrod
Raghavan Prabhakar
Syeda-Mahmood Tanveer Fathima
Alam Shahid
International Business Machines - Corporation
Johnson Daniel E.
McGinn & Gibb PLLC
Truong Cam-Y
LandOfFree
Method and apparatus for representing database and query... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for representing database and query..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for representing database and query... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3337690