View
106
Download
0
Category
Preview:
Citation preview
1
Kapitel 5: Mehrdimensionale
Suchstrukturen
2
Mehrdimensionale Suchstrukturen
Alter zwischen 20 und 30
Einkommen zwischen 2000 und 3000
PLZ zwischen 40000 und 50000
3
Query-Rechteck
y2
y1
y
xx1 x2
E
D
C
B
G
F H I
K
AJ
4
k-d-Baum
zur Verwaltung von mehrdimensionalen Datenpunkten
Verallgemeinerung des binären Suchbaumsmit k-dimensionalem Sortierschlüssel
Homogene Variante: Baumknoten enthält Datenrecord + Zeiger
Inhomogene Variante: Baumknoten enthält Schlüssel + ZeigerBlätter enthalten Zeiger auf Datenrecord
Ebene i modulo k diskriminiert bzgl. Dimension i
x
y
z
5
2-d-Baum
Im 2-dimensionalen Fall gilt für Knoten mit Schlüssel [x/y]:
im linken Sohn im rechten Sohn
Auf ungerader Ebene alle Schlüssel x alle Schlüssel > x
Auf gerader Ebene alle Schlüssel y alle Schlüssel > y
6
2-d-Baum
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1
2
3
4
5
6
7
8
9
10
A
C
B
D
E
FG
H
7
Beispiel für 2-d-Baum
D 6/2 H 8/5
C 9/4
B14/3B 14/3
A 5/6
G 1/8 F 12/7
E 7/9
bzgl. y kleiner
bzgl. x kleiner
bzgl. y kleiner
bzgl. y grösser
bzgl. y grösser
bzgl. x grösserbzgl. x grösser
Insert z.B. füge Record [3/9]
I 3/9
8
Beispiel für 2-d-Baum
D 6/2 H 8/5
C 9/4
B14/3B 14/3
A 5/6
G 1/8 F 12/7
E 7/9
bzgl. y kleiner
bzgl. x kleiner
bzgl. y kleiner
bzgl. y grösser
bzgl. y grösser
bzgl. x grösserbzgl. x grösser
Exact Match z.B. finde Record [15/5]
9
Beispiel für 2-d-Baum
D 6/2 H 8/5
C 9/4
B14/3B 14/3
A 5/6
G 1/8 F 12/7
E 7/9
bzgl. y kleiner
bzgl. x kleiner
bzgl. y kleiner
bzgl. y grösser
bzgl. y grösser
bzgl. x grösserbzgl. x grösser
Partial Match z.B. finde alle Records [x/y] mit x=7
10
Beispiel für 2-d-Baum
D 6/2 H 8/5
C 9/4
B14/3B 14/3
A 5/6
G 1/8 F 12/7
E 7/9
bzgl. y kleiner
bzgl. x kleiner
bzgl. y kleiner
bzgl. y grösser
bzgl. y grösser
bzgl. x grösserbzgl. x grösser
Range-Query z.B. finde alle Records [x/y] mit 8 x 13, 5 y 8
11
Beispiel für 2-d-Baum
D 6/2 H 8/5
C 9/4
B14/3B 14/3
A 5/6
G 1/8 F 12/7
E 7/9
bzgl. y kleiner
bzgl. x kleiner
bzgl. y kleiner
bzgl. y grösser
bzgl. y grösser
bzgl. x grösserbzgl. x grösser
Best Match z.B. finde nächsten Nachbarn zu [7/3]
=> Traversierung mit schrumpfender Rangequery
12
2-d-Baum
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1
2
3
4
5
6
7
8
9
10
A
C
B
D
E
FG
H
13
Traversierung für Best Match zu [7/3]
D 6/2 H 8/5
C 9/4
B14/3B 14/3
A 5/6
G 1/8 F 12/7
E 7/9
bzgl. y kleiner
bzgl. x kleiner
bzgl. y kleiner
bzgl. y grösser
bzgl. y grösser
bzgl. x grösserbzgl. x grösser
14
Inhomogene Variante
15
Partitionierungen
16
Gitterverfahren mit konstanter Gittergröße
17
Grid File
Alternative zu fester Gittergröße
1981 vorgestellt von Hinrichs & Nievergelt
2-Platten-Zugriffsgarantie
Bei k-dimensionalen Tupeln:
• k Skalen zum Einstieg ins Grid-Directory (im Hauptspeicher)
• Grid Directory zum Finden der Bucket-Nr. (Hintergrundspeicher)
• Bucket für Datensätze (Hintergrundspeicher)
18
Grid File im 2-dimensionalen Fall
Alle Records der roten Gitterzelle sind im Bucket mit Adresse G[1,2]
0
y[i],i=0,.. max_y
3030
2500
2050
800
y
30 40 85 120 x
x x[i],i=0,.. max_x0 30 40 85 120
y0 800 2050 2500 3030
Region: benachbarte Gitterzellen
Gitterzelle: rechteckiger Teilbereich
Bucket: speichert Records einer Region
19
Bucket Directory
0 30 40 85 120
0 1 2 3 4
43210
303025002050
8000
Suche Record [35 / 2400]
Befrage Skalen
asp07nk99jh056509
aasdf0cß03j400d0v
9v8asßfimo98csi98a
dxcvß98dspa0s9fxc0
wi00808ß3jsßsa9ßß
Lade Block mit G[1,2] vom Bucketdirectory
Lade Datenblock
20
Bucket-Überlauf
Eine Zelle in Region
Mehrere Zellen in Region
21
Aufspalten der Regionen
8
6
4
2
2 4 6 8 10 12 14
Insert A = [5 / 6]
22
Aufspalten der Regionen
8
6
4
2
2 4 6 8 10 12 14
A
A Insert B = [14 / 3]
23
Aufspalten der Regionen
8
6
4
2
2 4 6 8 10 12 14
A
B
A B Insert C = [9 / 4]
24
Aufspalten der Regionen
8
6
4
2
2 4 6 8 10 12 14
A
C
B
B CA Insert D = [6 / 2]
25
Aufspalten der Regionen
8
6
4
2
2 4 6 8 10 12 14
A
C
B
B CA D
D
Insert E = [7 / 9]
26
Aufspalten der Regionen
B C
8
6
4
2
2 4 6 8 10 12 14
E
A
C
B
D
A E
D
Insert F = [12 / 7]
27
Aufspalten der Regionen
B C
8
6
4
2
2 4 6 8 10 12 14
E
A
C
B
FF
D
A E
D
Insert G = [1 / 8]
28
Aufspalten der Regionen
B C
8
6
4
2
2 4 6 8 10 12 14
E
A
C
B
FF
D
G A E
D
G
29
Gridfile Beispiel
12 18 34
2000
1600
1100
110012
2000
34
1800
1700
1600
1500
1400
1300
15 16 17 18 26 30 32
30
Gridfile Zahlen
Größe eines Datenrecords: 100 Byte
mittlere Zahl der Datenrecords pro Block: 7.5
maximale Zahl der Datenrecords pro Block 10
Zahl der Datenrecords: 300.000
Zahl der Datenblöcke: 40.000
Zahl der Directoryblöcke: 225
mittlere Zahl von Adressen pro Directoryblock 175
maximale Zahl von Adressen pro Directoryblock: 256
Größe des Root-Directory: 15 x 15
31
Dynamik des Grid Directory
300
200 10 50
Insert A=[12 / 280]
3 Datenrecords pro Bucket
32
Dynamik des Grid Directory
10 50
300
200
A
10 50
300
200
300
200 10 50
Insert B=[25 / 220]
33
Dynamik des Grid Directory
10 50
300
200
A
B
10 50
300
200
300
200 10 50
Insert C=[45 / 270]
34
Dynamik des Grid Directory
10 50
300
200
A
B
C
10 50
300
200
300
200 10 50
Insert D=[22 / 275]
35
Dynamik des Grid Directory
300
200
10 30 50
300
200
A
B
C
10 50
300
200
D
10 30 50
Insert E=[24 / 260]
36
Dynamik des Grid Directory
250
200
C
300
10 30 50
A
B
10 50
300
200
D
10 30 50
300
200
E
250
Insert F=[26 / 280]
37
Dynamik des Grid Directory
10 30 50
300
200
30 50
10 20 30
250
200
A
B
CD
10 30 50
300
200
E
250
300 F
250
200
300
Directory Blockvergröbern
38
Dynamik des Grid Directory
10 20 30
250
200
A
B
C
10 30 50
300
200
D
10 30 50
300
200
E
250
300 F
30 50
300
200
39
Vereinigung von Regionen
bei zu geringer Bucketauslastung:
• Benachbarte Regionen vereinigen
• Vereinigung muß Rechteck ergeben
Vereinigung wird ausgelöst
• wenn Bucket < 30 % Auslastung
• wenn vereinigtes Bucket < 70 % Auslastung
40
Nearest Neighbor
Q
P
R
41
Verwaltung von geometrischen Objekten
Grid File unterstützt Range-Query
bisher: k Attribute
Jetzt: k-dimensionale Punkte
42
Verwaltung von Intervallen
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1
2
3
4
5
E
A
B
C
D
F
A
[Anfang / Ende]
E
A
B C
D F
Besser: [Mittelpunkt / halbe Länge]
43
Query-Punkt gegen Intervall
Punkt p liegt im Intervall mit Mitte m und halber Länge d
m-d p m+d
m-d m+dm
44
Query-Punkt gegen Intervall
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1
2
3
4
5
E
A
B
C
D
F
E
A
B C
D F
Punkt p liegt im Intervall mit Mitte m und halber Länge d
m-d p m+d p=5 m-d 5 m+d
45
Query-Intervall gegen Intervall
Intervall mit Mitte s und halber Länge t schneidet Intervall mit Mitte m und halber Länge d
m-d s+t und s-t m+d
m-d m+d
s+ts-t
46
Query-Intervall gegen Intervall
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1
2
3
4
5
E
A
B
C
D
F
E
A
B C
D F
Intervall mit Mitte s und halber Länge t schneidet Intervall mit Mitte m und halber Länge d
m-d s+t und s-t m+d s=10, t=1 m-d 11 und 9 m+d
47
Query-Rechteck gegen Rechteck
Stelle Rechteck durch vierdimensionalen Punkt dar
Recommended