Database Reference
In-Depth Information
00
02
04
06
01
03
05
07
(a) Spherical indexing by base octahedron
00
01
02
03
04
09
07
06
05
08
10
11
12
14
13
15
17
19
16
18
(b) Spherical indexing by base icosahedron
Figure 6.14
Spherical indexing with quaternary/hierarchical triangular
mesh.
the indexed dimensions are used, the effectiveness of the index deteriorates
dramatically.
Many index methods have been proposed to address the curse of dimension-
ality, including the well-known X-Tree
13
and pyramid tree.
12
These methods
typically address the index size issue, but fail to address the performance is-
sue on partial-range queries. For both the X-Tree and the pyramid tree, where
a
k
-dimensional data structure is partitioned into
n
buckets, the complexity
of processing a partial-range query that specifies
s
out of
k
dimensions, is
O
(
n
1
−
s
/
k
+
r
)
.If
s
=
d
, which is the case for an exact-match query or a full
range query,
O
1, nearly all the
pages are accessed. This prompted the question of whether a simple sequential
scan is satisfactory for high-dimensional datasets.
14
,
82
In the case of similarity
searches in high-dimensional space, one effective method is the use of sequen-
tial scan but with the attribute values mapped onto fixed length-strings of
about 64
~
128 bits. The method is termed the VA-File approach.
97
Other,
more ecient, methods are the bitmap indexes described in the next section.
(
1
)
buckets are accessed. If
k
is large and
s
=
6.6 Bitmap Index
In this section, we separately review the current work on bitmap indexes
because they are more effective in accelerating query processing on large sci-
entific datasets than other techniques reviewed earlier. The bitmap indexes
