US 7,117,217 B2Granted

Apparatus and method for performing transformation-based indexing of high-dimensional data

AssigneeNational University of Singapore

InventorsBeng Chin Ooi, Kian Lee Tan, Stephen Bressan, Cui Yu

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method and apparatus for implementation in a database management system transforms high-dimensional data points to a single-dimensional space so that single-dimensional values can be used as representative index keys for high-dimensional data points and a single-dimensional index structure can be employed to index the transformed values. Upon achieving transformed values, known single-dimensional indexing structures can be employed. To achieve transformation from high-dimensions to a single-dimension, attribute values of a data item, each representing a different dimension, are mapped into a range and an integer value is assigned to each dimension. Either the minimum or maximum dimension value for the multi-dimensional data item is selected, and the minimum or maximum dimensional value is added to the integer value. As a result of this transformation, data points are mapped over a range in a single dimension and associated single-dimension values are used as a representative index key for subsequent search queries.

Claims6

Dependent claims

A method of managing a database which stores high-dimensional data items, comprising:

(a) applying a transform function to a high-dimensional data item to map the high-dimensional data item to single-dimensional space, thereby obtaining a single-dimensional value which represents the high-dimensional data item;
(b) indexing the single-dimensional value obtained by said applying step using a single-dimensional index structure;
wherein
(i) the high-dimensional data item includes a plurality of attribute values, each attribute value corresponding to a different dimension of the high-dimensional data item;
(ii) said step of applying a transform function maps each attribute value of the high-dimensional data item to a predetermined range, thereby obtaining a mapped attribute value for each attribute value, and calculates the single-dimensional value which represents the high-dimensional data item as dmin +xmin or dmax+xmax, where xmin is the smallest mapped attribute value associated with the high-dimensional data item, dmin is a value associated with the dimension which corresponds to the smallest mapped attribute value, xmax is the largest mapped attribute value associated with the high-dimensional data item, and dmax is a value associated with the dimension which corresponds to the largest mapped attribute value;
and
(iii) said applying and indexing steps are performed for a plurality of high-dimensional data items to form an indexed set of single-dimensional values;
and
(c) performing a search on the indexed set of single-dimensional values to retrieve a set of points, wherein said performing includes
transforming a range query into a set of d subqueries in the single-dimensional space represented as q1,q2, . . . ,qd, where qi=[Ii,hj], 1≦i≦d and for a jth query subrange in q, [xj1,xj2]:
q
j
=
{
[
j
+
max
i
=
1
d
⁢
x
i1
,
j
+
x
j2
]
if
⁢
⁢
min
i
=
1
d
⁢
x
i1
+
θ
≥
1
-
max
i
=
1
d
⁢
x
i1
[
j
+
x
j1
,
j
+
min
i
=
1
d
⁢
x
i2
]
if
⁢
⁢
min
i
=
1
d
⁢
x
i2
+
θ
<
1
-
max
i
=
1
d
⁢
x
i2
[
j
+
x
j1
,
j
+
x
j2
]
otherwise
,
where | is a tuning parameter, and
evaluating each subquery in said set of subqueries using the single-dimensional index structure.

108 more elements

An apparatus for managing a database which stores high-dimensional data items, comprising:

(a) transform means for applying a transform function to a high-dimensional data item to map the high-dimensional data item to single-dimensional space, thereby obtaining a single-dimensional value which represents the high-dimensional data item;
(b) indexing means for indexing the single-dimensional value obtained by said transform means using a single-dimensional index structure;
wherein
(i) the high-dimensional data item includes a plurality of attribute values, each attribute value corresponding to a different dimension of the high-dimensional data item;
(ii) said step of applying a transform function maps each attribute value of the high-dimensional data item to a predetermined range, thereby obtaining a mapped attribute value for each attribute value, and calculates the single-dimensional value which represents the high-dimensional data item as dmin+xmin or dmax+xmax, where xmin is the smallest mapped attribute value associated with the high-dimensional data item, dmin is a value associated with the dimension which corresponds to the smallest mapped attribute value, xmax is the largest mapped attribute value associated with the high-dimensional data item, and dmax is a value associated with the dimension which corresponds to the largest mapped attribute value;
and
(iii) said transform means and said index means are operable on a plurality of high-dimensional data items to form an indexed set of single-dimensional values;
and
(c) searching means for performing a search on the indexed set of single-dimensional values to retrieve a set of points, wherein said searching means is operable to transform a range query into a set of d subqueries in the single-dimensional space represented as q1,q2, . . . ,qd, where qi=[Ii,hj], 1≦i≦d, and for a jth query subrange in q, [xj1,xJ2]:
q
j
=
{
[
j
+
max
i
=
1
d
⁢
x
i1
,
j
+
x
j2
]
if
⁢
⁢
min
i
=
1
d
⁢
x
i1
+
θ
≥
1
-
max
i
=
1
d
⁢
x
i1
[
j
+
x
j1
,
j
+
min
i
=
1
d
⁢
x
i2
]
if
⁢
⁢
min
i
=
1
d
⁢
x
i2
+
θ
<
1
-
max
i
=
1
d
⁢
x
i2
[
j
+
x
j1
,
j
+
x
j2
]
otherwise
,
where | is a tuning parameter, and to evaluate each subquery in said set of subqueries using the single-dimensional index structure.

106 more elements

Dependencies are inferred from the claim text.

Facts

Application: 10/276,357Filed 27 Apr 2001
Priority: SG 200002639-315 May 2000
Published: US 2004/0006568 A18 Jan 2004
Granted: 3 Oct 2006
Term ends: Not estimatedThe source records don’t support an estimate.

Classification4 codes

G06F 16/283
Databases characterised by their database models, e.g. relational or object models: multi-dimensional databases or data warehouses, e.g. MOLAP or…
Y10S 707/99933
Database or file accessing: query processing, i.e. searching
G06F
Computing and data processing
Y10S
Technical subjects covered by former uspc cross-reference art collections [xracs] and digests