1 of 12

CSE 163

Indexing and Trees�

Suh Young Choi�

🎶 Listening to:

💬 Before Class: Any finals this week?

2 of 12

Announcements

Project Deliverables due tonight!

  • Submit through Gradescope
  • No late submissions or resubs available!

​

No section tomorrow (we’ll be grading projects ☺)

​

Class is still happening on Friday

​

Bonus resubmission period open!

  • Congrats on getting 66% completion! :D
  • Please make sure you have the correct assignment and submission numbers for these
  • Closes 11:59pm Friday

​

​

2

3 of 12

A Note on Peer Feedback

Final part of the project

  • Opens tomorrow, due Friday night 11:59pm
  • No late submissions or resubs

​

Two forms, regardless of whether you worked by yourself or in a group

  • One form for project reflections
  • One form for peer video feedback
  • Make sure you have receipts for BOTH forms

​

​

3

4 of 12

This Time

  • How Geospatial Indexing Works
  • Intro to Binary Search Trees

Previously…

  • Decision Trees
  • Geospatial Data

​

4

5 of 12

Binary Search Tree

Can build up a tree to help us search through sorted items

  • Similar to a decision tree of sorts!

5

6 of 12

Spatial Join - Points

Imagine we had a dataset of where�people live in the UK.��Want to know if someone lives�at coordinates (x, y)��How many points would we �have to search through?

6

[Point1, Point2, Point3, …]

7 of 12

Spatial Index

7

8 of 12

Spatial Index

This forms a tree!

​

8

9 of 12

Spatial Index Visualization

How the splits are chosen is not discussed

9

10 of 12

Spatial Index Query

To find if a Point is in the dataset, follow the tree! Suppose we are looking for g (we know its coordinates, but not index)

​

​

10

11 of 12

Spatial Index Performance

  • Say we are looking for a single Point
  • How much work is it if we have n rows?
    • Without a spatial index: O(n)
    • With a spatial index? O(height of tree)
  • How tall is the tree? How many times can we divide 1 million points in half?
    • 1,000,000 / 2 / 2 / 2 / 2 / … / 2 = 1
    • 2k = 1,000,000
    • k = log2(1,000,000) ≅ 20
    • This means the lookup is O(log n)
  • A million doesn’t sound that big. What about a tree of the US?
    • 327.2 million people
    • log2(327,200,000) ≅ 28
  • The US isn’t THAT big. What about a tree of China?
    • 1.386 billion people
    • log2(1,386,000,000) ≅ 30

11

12 of 12

Before Next Time

  • Complete Lesson 25
    • Remember not for points, but do go towards Checkpoint Tokens
  • Project Report/Code/Video due tonight!
  • Course eval is still open ☺
  • Peer Feedback releasing tomorrow

Next Time

  • Victory Lap!
  • What’s Next?

​

12