Databases Reference
In-Depth Information
25
18
13
10
9
0
9
10
13
18
2
2
1
1
1
0
1
1
2
2
20
13
8
5
4
0
4
5
8
13
17
10
5
2
1
0
1
2
5
10
1
1
0
0
0
0
0
0
1
1
16
9
4
1
0
0
0
1
4
9
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
16
9
4
1
0
0
0
1
4
9
17
10
5
2
1
0
1
2
5
10
1
1
0
0
0
0
0
0
1
1
20
13
8
5
4
0
4
5
8
13
25
18
13
10
9
0
9
10
13
18
2
2
1
1
1
0
1
1
2
2
32
25
20
17
16
0
16
17
20
25
(a)
α=
2
(b)
α=
4
Fig. 20.
Space tiling and resulting index for a two-dimensional example. Note that the index in
both subfigures was generated for exactly the same portion of space. The black dot stands for the
position of
ω
.
We call the vector (
c
1
,...,
c
n
) the coordinates of the cube
C
. Each point
ω∈Ω
lies in the
cube
C
(
ω
) with coordinates (
ω
i
/Δ
)
i
=
1
...
n
. Given such a space tiling, it is obvious that
V
(
ω,θ
) consists of the union of the cubes such that
∀
i
∈{
1
...
n
}
:
|
c
i
−
c
(
ω
)
i
|≤α
.
3
's Indexing Scheme.
Let
HR
ω ∈ Ω =
S
∪
T
be an arbitrary reference point. Fur-
thermore, let
δ
be the Minkowski distance of order
p
.The
index
function is defined as
follows:
⎩
0if
∃
i
:
|
c
i
−
c
(
ω
)
i
|≤
1 with
i
∈{
1
,...,
n
}
,
i
=
1
(
index
(
C
,ω
)
=
n
(8)
1)
p
|
c
i
−
c
(
ω
)
i
|−
else,
where
C
is a hypercube resulting from a space tiling and
ω ∈ Ω
. Figure 20 shows an
example of such indexes for
p
=
2 with
α =
2 (Figure 20a) and
α =
4 (Figure 20b).
Note that the blue square with index 0 contains the reference point
. All elements of
C
must only be compared with the elements of cubes
C
such that
index
(
C
ω
p
.The
authors of [110] prove formally that given this approach to space tiling, the following
theorem holds:
C
)
,
≤α
3
Theorem 1.
lim
α→∞
RRR
(
HR
,α
)
=
1
.
This conclusion is illustrated by Figure 21, which shows the space tiling computed by
HR
3
ff
α
=
=
α
, the closer the
approximation is to a circle. Note that these results allow to conclude that for any
RRR
-
value
r
larger than 1, there is a setting of
for di
erent values of
with
p
2and
n
2. The higher
3
HR
that can compute links with a
RRR
smallerorequalto
r
.
