Week 07 Lectures
Signature-based Selection
Indexing with Signatures
Signatures
Generating Codewords
Superimposed Codewords (SIMC)
SIMC Example
SIMC Queries
Example SIMC Query
SIMC Parameters
Query Cost for SIMC
Ex1: SIMC Query Cost
Page-level SIMC
Ex2: Page-level SIMC Query Cost
Bit-sliced SIMC
Ex3: Bit-sliced SIMC Query Cost
Assignment 2
Assignment 2
Bits
ADT
Reln
ADT
Query
ADT
Signature ADTs
Psig
ADT
Bsig
ADT
N-d Tree Indexes
Multi-dimensional Tree Indexes
Ex4: Query Types and Tuple Space
kd-Trees
Searching in kd-Trees
Ex5: Searching in kd-Trees
Quad Trees
Searching in Quad-tree
Ex6: Searching in Quad-trees
R-Trees
Insertion into R-tree
Query with R-trees
Ex7: Query with R-trees
Multi-d Trees in PostgreSQL
Costs of Search in Multi-d Trees
Similarity-based Selection
Relational vs Similarity Selection
Example: Content-based Image Retrieval
Similarity-based Retrieval
Approaches to
k
NN Retrieval
Similarity Retrieval in PostgreSQL
Produced: 31 Mar 2020