Data processing: structural design – modeling – simulation – and em – Modeling by mathematical expression
Reexamination Certificate
2000-10-17
2004-08-17
Paladini, Albert W. (Department: 2125)
Data processing: structural design, modeling, simulation, and em
Modeling by mathematical expression
C703S006000, C703S008000, C703S007000, C703S007000
Reexamination Certificate
active
06778946
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to multimedia database systems and, more particularly, to query processing operations of composite multimedia objects. The invention provides an algorithm which prunes the search space by filtering multimedia objects in a ranked fuzzy cartesian query.
BACKGROUND OF THE INVENTION
A composite object in a multimedia database is specified by a set of simple objects and the relationships among them. Each of the simple objects is characterized by one or many of its feature, spatial, temporal and semantic attributes. Relationships among simple objects can be spatial or temporal. Using an image database as an example, an image object may be defined by its color, shape, texture, or size. Relationships between two objects may be characterized using spatial relations such as “on top of,” “near,” or “to the west of.” As an example, one may define a composite object consisting of a “red,” “round” image object “within” a “large,” “white” image area. This composite object is then used to search for images matching its description, such as one with a red beach ball on a white-sand beach. In the above example, “red,” “round,” “large” and “white” characterize features of simple objects. “Within” defines the spatial relationship between the two simple objects.
In a multimedia database, object attributes and relationships are generally defined in fuzzy specifications and searches are targeted at retrieving top-K ranked objects in similarity, often known as a similarity search. For example, a search may involve searching for simple image objects which look “red” and “round.” The property “red” is measured by a fuzzy score on how close its color attribute is to “red.” The property “round” is measured by a fuzzy score on how close its shape attribute is to “round.” The overall score of the image object is calculated by taking a “fuzzy AND” operation of the two individual property scores. Objects with their total scores ranked among the top-K are retrieved. Searches for composite objects are evaluated in a similar fashion, with the addition of fuzzy scores measuring object relationships.
While there have been extensive studies on querying simple objects, much less research is performed on processing composite objects. A composite object query involves evaluations of fuzzy cartesian products of the simple objects.
The present invention addresses a key issue in composite object queries, which is the reduction of the number of simple objects participating in evaluations of fuzzy cartesian products. Since fuzzy cartesians involve a lot of computation and disk retrieval, the smaller the number, the faster the query processing. The algorithm described in this invention guarantees the filtering of candidate objects does not cause any false dismissal. Top-K ranked composite objects retrieved from the filtered set of objects will be the same as those without filtering.
Techniques in retrieving image or video objects by their content features have progressed significantly in recent years. The cited publications below address indexing and query processing of similarity searches on simple objects, which may be characterized by multiple features. Related works include the IBM Query by Image Content (QBIC) system (M. Flickner et al., “Query by image and video content: The (QBIC) system,” IEEE Computer, 28(9):23-32, September 1995), the Virage visual information retrieval system (J. R. Bach et al., “Virage image search engine: an open framework for image management,” Symposium on Electronic Imaging: Science and Technology—Storage & Retrieval for Image and Video Databases (IV), volume 2670, pages 76-87, 1996), the MIT Photobook (A. Pentland et al., “Tools for content-based manipulation of image databases,” Proceedings of the SPIE Storage and Retrieval Image and Video Databases II, February 1994), the Alexandria project at UCSB (B. S. Manjunath et al., “Texture features for browsing and retrieval of image data,” IEEE Trans. Pattern Analysis Machine Intell. Special Issue on Digital Libraries, (8), 1996, and M. Beatty et al., “Dimensionality reduction using multidimensional scaling for image search,” Proc. IEEE International Conference on Image Processing, October 1997) and the IBM/NASA Satellite Image Retrieval System (C.-S. Li et al., “Progressive content-based retrieval from distributed image/video databases,” Proceeding of the International Symposium of Circuit and System, IEEE, 1997).
In recent years, the increasing importance for multimedia databases to provide search capabilities for not only simple but also composite objects has been recognized. Practical applications for composite object queries arise in both scientific and engineering disciplines. For example, they include:
Environmental epidemiology: Retrieve locations of houses which are vulnerable to epidemic diseases such as Hantavirus and Denge fever based on a combination of environmental factors (e.g., isolated houses that are near bushes or wetlands), and weather patterns (e.g., a wet summer followed by a dry summer).
Precision farming: (1) Retrieve locations of cauliflower crop developments that are exposed to clubroot, which is a soil-borne disease that infects cauliflower crop. Cauliflower and clubroot are recognized spectral signatures, and exposure results from their spatial and temporal proximity. (2) Retrieve those fields which have abnormal irrigation, (3) Retrieve those regions which have higher than normal soil temperature.
Precision forestry: (1) Calculate areas of forests that have been damaged by hurricane, forest fire, or storms. (2) Estimate the amount of the yield of a particular forest.
Petroleum exploration: Retrieve those regions which exemplify specific characteristics in the collection of seismic data, core images, and other sensory data.
Insurance: (1) Retrieve those regions which may require immediate attention due to natural disasters such as earthquake, forest fire, hurricane, and tornadoes. (2) Retrieve those regions having higher than normal claim rate (or amount) that are correlated to the geography—close to coastal regions, close to mountains, in high crime rate regions, etc.
Medical image diagnosis: Retrieve all MRI images of brains that have tumors located within the hypothalamus. The tumors are characterized by shape and texture, and the hypothalamus is characterized by shape and spatial location within the brain.
Real estate marketing: Retrieve all houses that are near a lake (color and texture), have a wooded yard (texture) and are within 100 miles of skiing (mountains are also given by texture).
While composite object queries may be processed by evaluating each and every possible combination of fuzzy cartesian products, the computational complexity of this simple scan method is on the order of O(L
N
), where a composite object is defined by the relationships of N simple objects in a database of L candidates. In a recently filed patent application, the inventors described an algorithm to reduce the computational complexity to the order of O(K*N*L
2
), assuming top-K ranked composite objects are requested, see U.S. patent application identified as Ser. No. 09/237,734 filed on Jan. 26, 1999 in the names of Chung-Sheng Li et al. and entitled “System and method for sequential processing of content-based retrieval of composite objects,” the disclosure of which is incorporated by reference herein. A key idea behind the above-referenced Li et al. patent application is the observation that if the query only asked for top-K objects, at each node of the fuzzy cartesian, only K paths need to be kept, instead of L. As a result, the composite object query problem becomes much more tractable. However, there is still room for improvements since L is typically a large number exceeding 1,000.
A main contribution of the present invention is to further reduce the computational complexity to the order of O(K*N*M
2
), where M is a number less than or equal to L. The actual value of M is found through an algorithmic procedure detailed below in accordance with some illustrative embodimen
Chang Yuan-Chi
Li Chung-Sheng
Dang Thu Ann
International Business Machines - Corporation
Paladini Albert W.
Ryan & Mason & Lewis, LLP
LandOfFree
Methods and apparatus for processing ranked fuzzy cartesian... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for processing ranked fuzzy cartesian..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for processing ranked fuzzy cartesian... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3282589