Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Multidimensional Index Structure with Multi-Level Entry and Skip-Level Search for Partially-Specified Queries

IP.com Disclosure Number: IPCOM000118210D
Original Publication Date: 1996-Nov-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 4 page(s) / 156K

Publishing Venue

IBM

Related People

Wu, K-L: AUTHOR [+2]

Abstract

Many database applications require enhanced indexing. Examples include multidimensional data analysis in a decision support system and information retrieval on non-traditional data types, such as raster images and spatial objects, in a multimedia information system. In a decision support system, multidimensional analysis through a complex query is usually used in order to gain additional perspectives against a large collection of data. It typically involves many attributes, and an effective multidimensional database support is required. For non-traditional data types, such as images, a domain expert can perform feature extraction from the images in the database. Once features are extracted from the images, each image object can be represented by a feature vector.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 32% of the total text.

Multidimensional Index Structure with Multi-Level Entry and Skip-Level
Search for Partially-Specified Queries

      Many database applications require enhanced indexing.  Examples
include multidimensional data analysis in a decision support system
and information retrieval on non-traditional data types, such as
raster images and spatial objects, in a multimedia information
system.  In a decision support system, multidimensional analysis
through a complex query is usually used in order to gain additional
perspectives against a large collection of data.  It typically
involves many attributes, and an effective multidimensional database
support is required.  For non-traditional data types, such as images,
a domain expert can perform feature extraction from the images in the
database.  Once features are extracted from the images, each image
object can be represented by a feature vector.  Images thus become
points in a high dimensional feature space.  Therefore, an effective
multidimensional (or multiattribute) index is also required.

      However, because of the uncertainty about which of the many
attributes will be used in the predicates of a query, it is very
difficult to build a single multiattribute index that can efficiently
support all possible queries.  For example, a multiattribute index
consisting of A sub 1, A sub 2 and A sub 3 cannot help the execution
of a query with predicates involving attributes A sub 4 and A sub 5.
Without an appropriate multiattribute index, query processing may
take a long time to execute because it may involve searching through
either multiple multiattribute indexes or even a sequential scan of
the entire database records.  This problem becomes even more severe
when the database size is large.

      Generally, in order to facilitate all possible high-dimensional
partially-specified queries to search only one multiattribute index,
a large number of such indexes are needed.  A query is partially
specified if only m out of n indexed attributes are specified in the
predicates and m lt n, where n is the total number of indexed
attributes.  In (1), twenty different multiattribute indexes are
needed for a relation with only 6 indexed attributes to effectively
handle all possible partially-specified queries.  It is impractical
to maintain a large number of multiattribute indexes because it not
only requires high storage overhead for storing the indexes but also
requires high computation overhead for updating the indexes once the
data are changed.

      In the present disclosure, we propose a new multiattribute
index structure that supports Multi-level Entry and Skip-Level
search, called MESL index, so that any partially-specified queries
can be efficiently processed with a single MESL index structure.  In
a MESL index structure, there are two types of structures: Main
Structure (MS) and Entry Structure (ES).  The main structure is a
n-level multiattribute tree where a generalized B-tre...