COLUMBIA UNIVERSITY COMS 6113

Overview

RTrees

Balanced secondary index structure

The general optimization is the following

    min amount of X?
    s.t. Tree obeys R-tree structure

Insert E

Delete E

Search E

Node splitting heuristic

Experiments

Extensions: R * tree

GIST trees

Overview

What is an index really?

Penalty(pi, k)

Linear ordering

GIST for R-trees

Experiments