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