Database Reference
In-Depth Information
=
{
(
)
,
(
)
,
(
)
}
=
{
(
)
,
(
)
,
(
)
}
F
1
1; 2
1; 3
2; 3
F
10
10; 11
10; 12
11; 12
F
2
=
{
(
2; 3
)
,
(
2; 4
)
,
(
3; 4
)
}
F
11
=
{
(
11; 12
)
,
(
11; 13
)
,
(
12; 13
)
}
F
3
=
{
(
3; 4
)
,
(
3; 5
)
,
(
4; 5
)
}
F
12
=
{
(
12; 13
)
,
(
12; 14
)
,
(
13; 14
)
}
F
4
=
{
(
4; 5
)
,
(
4; 6
)
,
(
5; 6
)
}
F
13
=
{
(
13; 14
)
,
(
13; 15
)
,
(
14; 15
)
}
F
5
=
{
(
5; 6
)
,
(
5; 7
)
,
(
6; 7
)
}
F
14
=
{
(
14; 15
)
,
(
14; 16
)
,
(
15; 16
)
}
F
6
=
{
(
6; 7
)
,
(
6; 8
)
,
(
7; 8
)
}
F
15
=
{
(
15; 16
)
,
(
15; 17
)
,
(
16; 17
)
}
F
7
=
{
(
7; 8
)
,
(
7; 9
)
,
(
8; 9
)
}
F
16
=
{
(
16; 17
)
,
(
16; 18
)
,
(
17; 18
)
}
F
8
=
{
(
8; 9
)
,
(
8; 10
)
,
(
9; 10
)
}
F
17
=
{
(
17; 18
)
,
(
17; 19
)
,
(
18; 19
)
}
F
9
=
{
(
9; 10
)
,
(
9; 11
)
,
(
10; 11
)
}
F
18
=
{
(
18; 19
)
,
(
18; 20
)
,
(
19; 20
)
}
B
1
=
{
(
1; 2
)
,
(
1; 3
)
;
(
1; 4
)
,
(
1; 5
)
,
(
2; 3
)
,
(
2; 4
)
,
(
2; 5
)
,
(
3; 4
)
,
(
3; 5
)
,
(
4; 5
)
}
B
2
=
{
(
6; 7
)
,
(
6; 8
)
;
(
6; 9
)
,
(
6; 10
)
,
(
7; 8
)
,
(
7; 9
)
,
(
7; 10
)
,
(
8; 9
)
,
(
8; 10
)
,
(
)
}
9; 10
B
3
=
{
(
11; 12
)
,
(
11; 13
)
;
(
11; 14
)
,
(
11; 15
)
,
(
12; 13
)
,
(
12; 14
)
,
(
12; 15
)
,
(
13; 14
)
,
(
13; 15
)
,
(
14; 15
)
}
B
4
=
{
(
16; 17
)
,
(
16; 18
)
;
(
16; 19
)
,
(
16; 20
)
,
(
17; 18
)
,
(
17; 19
)
,
(
17; 20
)
,
(
18; 19
)
,
(
18; 20
)
,
(
19; 20
)
}
F
\
B
=
{
(
4; 6
)
,
(
5; 6
)
,
(
5; 7
)
,
(
9; 11
)
,
(
10; 11
)
,
(
10; 12
)
,
(
14; 16
)
,
(
15; 16
)
,
(
15; 17
)
}
\
=
{
(
)
,
(
)
,
(
)
,
(
)
,
(
)
,
(
)
,
(
)
,
B
F
1; 4
1; 5
2; 5
6; 9
6; 10
7; 10
11; 14
(
11; 15
)
,
(
12; 15
)
,
(
16; 19
)
,
(
16; 20
)
,
(
17; 20
)
}
Tabelle 5.1: Übersicht der Tupelvergleiche
Neighborhood-Methode ein Tupel mit
w
1 nachfolgenden
Tupeln verglichen wird, sind es beim Blocking in Summe
Blockgröße
−
1 vorherigen und
w
−
−
1 Tupel.
Vergleich der Komplexität
In Tabelle 5.2 ist noch einmal die Komplexität der Algorithmen dargestellt, so-
wie zusätzlich die Anzahl der Tupelvergleiche der Verfahren in Abhängigkeit von
Block- bzw. Fenstergröße. Der Aufwand für Schlüsselbildung und Sortierung ist
für Blocking und die Sorted-Neighborhood-Methode gleich, wobei der jeweilige
Aufwand für die Berechnung des Schlüssels nicht berücksichtigt ist. Bei einem
vollständigen Vergleich entfallen die Schritte Schlüsselbildung und Sortierung.
Der Unterschied zwischen Blocking und der Sorted-Neighborhood-Methode liegt
also im Aufwand für den paarweisen Vergleich der Tupel. Blocking und der voll-
Search WWH ::
Custom Search