Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-04-08
2003-03-18
Mizrahi, Diane D. (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06535872
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a method and apparatus for adaptively and dynamically representing multidimensional data using view element sets that can be used to construct aggregated and segmented views of the data.
BACKGROUND OF THE INVENTION
In applications involving online analytical processing (OLAP), image storage and retrieval (IS&T), geographic information systems (GIS) and video-on demand (VOD) systems, it is necessary to provide fast access to views of the data that involve various aggregations and segmentations of the data. To illustrate, an example aggregated and segmented view of a two-dimensional digital image corresponds to a spatial portion of a reduced-resolution version of the image. By pre-aggregating, partitioning and indexing the data accordingly, it is possible to provide more direct access to the data views of interest.
Data partitioning has been utilized in the context of database systems for the declustering and fragmentation of relational data tables to better allocate the data to sites in a communication network. In applications involving digital imagery, data partitioning in the form of quadtree segmentation has been used to split two-dimensional image data into spatial partitions, which can be stored separately or indexed as distinct units. By partitioning the data, views which comprise only portions of the full data set are more readily retrieved and assembled from the partitions.
Alternatively, the data views of interest may involve aggregations that compute averages from the data or that reduce the resolution of the data, such as thumbnail images providing reduced-resolution views of corresponding larger images. Data partitioning using filter banks has been used to split two-dimensional image data into spectral partitions, which correspond to aggregated and residual views of the images.
Aggregations of relational data involving combinations of multiple attributes can be represented using data cubes. The aggregated views of the data correspond to the cells of the data cube. By arranging the views in the data cube into a dependency hierarchy, it is possible to materialize, or precompute and store, only a subset of the views, and to compute additional views from the materialized views, as taught in H. Gupta, V. Harinarayan, A. Rajaraman and J. D. Ullman, Index Selection for OLAP,”
Proc. of the
13
th Int'l Conf. on Data Engineering
, 1997.
In the past, multiple-resolution views of images have been organized into redundant and non-redundant pyramidal forms to allow reduced-resolution views of the data to be accessed. The multidimensional data can be jointly aggregated and spatially partitioned. Data decompositions involving segmentation and aggregation of multidimensional lattice data have been developed in the Double-tree (see: C. Herley, J. Kovacevic, K. Ramchandran, and M. Vetterli, “Tilings of the Time-Frequency Plane: Constructions of Arbitrary Orthogonal Bases and Fast Tiling Algorithms, ”
IEEE Trans. on Image Processing
, December, 1993), Dual Double-tree (see: J. R. Smith and S. -F. Chang, “Frequency and Spatially Adaptive Wavelet Packets,”
Proc. IEEE ICASSP
, May, 1995), JASF Graph, and Space-Frequency Tree (see: J. R. Smith and S. -F. Chang, “Joint Adaptive Space and Frequency Graph Basis Selection,”
Proc. IEEE ICIP
, October 1997).
There can be benefit to making a good selection of which view elements to materialize in terms of storage space and view retrieval time. The selection of redundant views in a dependency hierarchy has been used for the pre-materialization of views in data cubes. A tree-based selection process has been utilized for selecting non-redundant wavelet packet bases for representing one-dimensional and two-dimensional digital signals. The process was extended to a graph that combines spatial segmentation and frequency decomposition for representing two-dimensional images.
In accordance with the aforementioned needs, it is an objective of the present invention to provide an apparatus and method for: generating representations of multidimensional data using view element sets, for adaptively and dynamically selecting representative view element sets according to patterns of view access, storage constraints and processing costs, and for assembling or synthesizing views of the data from view element sets.
It is another objective to provide a system and method having features for selecting and materializing view element sets according to storage costs and constraints, processing costs, and frequencies of view access by users.
Yet another objective is to provide a system and method having features for dynamically reconfiguring the data representation in accordance with the foregoing constraints and for adapting to emerging patterns of view access.
SUMMARY OF THE INVENTION
These and other objectives are realized by the present invention wherein an apparatus and method for generating a view element representation of multiple-attribute tabular data are provided, including converting tabular data into a multidimensional lattice form whereby each functional attribute of the relational data is mapped to a dimension in the lattice, and each cell in the lattice corresponds to an aggregation over records in the data table.
The invention further provides an apparatus and method for generating a view element representation of multidimensional lattice data comprising decomposing the multidimensional data into view elements such that the view elements retain sufficient information to reconstruct the original lattice data.
Alternatively, the invention provides for generating a view element data representation including iterative decomposition of the lattice data into aggregated and residual view elements or by spatially partitioning the lattice data.
Further taught are an apparatus and method for generating a view element data representation including the decomposition of the lattice data by iteratively and jointly aggregating and spatially partitioning the lattice data.
Under the inventive system for representing the data using view element sets, costs and benefits are assigned to the view elements and the view element sets are formed on the bases of the costs and benefits. A view of the data from a set of view elements is synthesized by selecting view elements from the view element sets and assembling the view elements together to construct the views.
REFERENCES:
patent: 5950186 (1999-09-01), Chaudhuri et al.
patent: 5960423 (1999-09-01), Chaudhuri et al.
patent: 6026390 (2000-02-01), Ross et al.
patent: 6122636 (2000-09-01), Malloy et al.
patent: 6161103 (2000-12-01), Rauer et al.
patent: 6205447 (2001-03-01), Malloy
Castelli Vittorio
Li Chung-Sheng
Smith John R.
Dougherty Anne Vachon
Jordan Kevin M.
Mizrahi Diane D.
Zarick Gail H.
LandOfFree
Method and apparatus for dynamically representing aggregated... 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 dynamically representing aggregated..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for dynamically representing aggregated... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3021781