Modeling High-Dimensional Index Structures using Sampling

Sampling

DepartmentofComputerScience

UniversityofCaliforniaSantaBarbara,CA93106

ChristianA.Lang

DepartmentofComputerScience

UniversityofCaliforniaSantaBarbara,CA93106

AmbujK.Singh

clang@cs.ucsb.edu

ABSTRACT

ambuj@cs.ucsb.edu

1.INTRODUCTION

2.RELATEDWORK

2.1UniformDataModels

2.2GloballyParametricModels

2.3LocallyParametricModels

2.4Sampling-basedModels

3.SAMPLING-BASED

PREDICTIONMODEL

3.1TheBasicModel

Sample data

(a)

(c)

Build index

Build index

(b)

Grow pages

(d)

Original page layoutSample page layout

3.2CalculationoftheCompensationFactor

hlowerhupperUpper tree

...

Lower trees

4.2PredictinginPhases

(a) Upper tree leaf pages before growingFirst sampleSecond sample

(b) Upper tree leaf pages after growing

N points(a) loadingM points. . .(b) distributingk consecutive disk areasoriginal data filemain memoryM/k points (average)4.5.3Effectof

onI/OCost

4.6I/OCostofthePredictions

4.5.2

4.7OtherIndexStructures

5.EXPERIMENTALRESULTS

5.1RuntimeofthePredictions

5.2AccuracyofthePredictions

3000

2500

2000

noitcid1500

erp1000

500

0

05001000

1500

200025003000

on-disk

3000

2500

2000

noitcid1500

erp1000

500

0

050010001500200025003000

on-disk

5.3ComparisonwithOtherModels

1.2

PredictionMeasurement

1

0.8

)s ni( tso0.6

c O/I0.4

0.2

0

40961638432768

65536

131072

Page size (in bytes)

600

PredictionMeasurement500

400

sessecca300

egaP200

100

0

0102030

405060

Index dimensionality

6.2Determiningality

theOptimalDataDimension-7.CONCLUSIONS

8.ACKNOWLEDGEMENTS

9.REFERENCES