ML Wiki

Multi-Dimensional Indexes

Typical Applications

• Searching Data Cube for Data Warehousing
• Spatial Databases

Typical Queries

Point Query

Find all values for the (multi-dimensional) search key

• for product "TV" sold in Ireland with ALL for date
• does there exist a star on coordinate (10, 3, 5)

Partial Match Queries

Not all values of a search key are specified

• return the coordinates pf all stars with $x=5$ and $z=3$

Range Queries (Dicing)

• return all cube cells with date $\geqslant Q_1$ and date $\leqslant Q_2$ and sales $\leqslant 100$
• return coordinates of all stars with $x \geqslant 10$ and $20 \leqslant y \leqslant 35$

Nearest-Neighbor Queries

• return closest 3 stars to a star at (10, 15, 20)

Can Use One-Dimensional Indexes?

One-Dimensional Indexes (such as B-Tree)

• take one single key
• can use one key made of multiple attributes

B-Tree

Need to impose lexicographical order on keys in B-Tree to do that

• don't answer all our queries - see B-Tree#Multiple Keys

Hash Tables

For Hash-Based Indexes we need to compute Hash Function for tuples

• extend hash function: $h(x, y, z) = h_1(x) + h_2(y) + h_3(z)$

Problem

• cannot answer range queries at all
• age < 20
• sal < 30
• age < 20 and sal < 20
• all lead to linear scan

Types

Other Types

• Multiple-Key Index

Hash-Based Multi-Dimensional Indexes

• Grid File Index
• Partitioned Hash Function Index

Tree-Based Multi-Dimensional Indexes

• kd-Trees
• Quad Trees
• R-Tree

Sources

• Database Systems Architecture (ULB)
• Database Systems: The Complete Book (2nd edition) by H. Garcia-Molina, J. D. Ullman, and J. Widom