High-Dimensional &

Vector Indexing
Rise of vector data
• As deep learning and neural models grow popular,
a lot of data are preprocessed and represented as
embedding vectors these days
• Text, audio, image, video…
• Objects are semantically similar embedding vectors
are similar

# dims will be
in hundreds if
not thousands!
Retrieval = similarity query
Given: a set of objects 𝐷 and a query object 𝑞
Find: 𝑘 objects in 𝐷 most similar to 𝑞
𝑞
The cat playfully encode
chased the butterfly 0.7, 0.2, 0.5, 0.8, 0.1, 0.4, …
in the garden
more similar less similar

The kitten frolicked joyfully

encode
after the fluttering insect 0.8, 0.3, 0.6, 0.7, 0.2, 0.3, …
in the flowers
The hungry fox stalked the encode
unsuspecting rabbit through 0.1, 0.1, 0.0, 0.3, 0.7, 0.6, …
the undergrowth
……
𝐷
Similarity metrics
𝑎⃗ = 𝑎1, 𝑎2, … , 𝑎𝑛 ; 𝑏 = 𝑏1, 𝑏2, … , 𝑏𝑛
• Euclidean distance: 𝑛
∑𝑖=1 2
𝑎𝑖 − 𝑏𝑖
• Probably the most frequently used one currently
𝑛
∑𝑖=1 𝑎𝑖𝑏𝑖
• Cosine similarity:
𝑛 𝑛 2
∑𝑖=1 𝑎 2𝑖 ⋅ ∑𝑖=1 𝑏𝑖

• I.e.: the cosine of the angle between 𝑎⃗ and 𝑏; 1 means

perfectly aligned; -1 means exactly opposite
• Distance can be defined as 1 minus cosine similarity
• Inner product: ∑𝑛𝑖=1 𝑎𝑖𝑏𝑖
• Same numerator as cosine similarity; no normalization
• Use only if magnitudes of 𝑎⃗ and 𝑏 matter in comparison
Indexing for similarity search
• Pre-process 𝐷 so that we can answer similarity
queries in sublinear time
• Techniques covered in this lecture
• kd-tree
• Clustering (𝑘-means) & partitioning (Voronoi)
• Quantization
• Locality-sensitive hashing (LSH)
• Hierarchical navigable small-world (HNSW)
• With a brief detour on skip lists
☞Common theme: problem is hard in high
dimensions — go for approximation to reduce cost
kd-tree (k-dimensional tree)
• Not only for similarity searches, but also for
traditional range queries
• Idea: build a balanced binary tree on objects (points
in a high-dimensional space) that splits them on
one dimension at a time
• Choose one dimension to split the the points
• Typically, round-robin
• Look at the projections of these points on this
dimension and split them evenly into two subtrees
 9

kd-tree construction example

𝑥1
𝑥5 𝑥7
𝑥1
𝐵
𝐺
𝐴
𝑦2 𝑦3
𝐸
𝑦2
𝐷 𝑦3 𝑥4 𝑥5 𝑥6 𝑥7

𝑦 𝐻 𝐶 𝐷 𝐴 𝐵 𝐹 𝐻 𝐸 𝐺
𝐶

𝐹 Each node represents a bounding box;

𝑥 𝑥4 bounding boxes form a hierarchy
𝑥6
kd-tree similarity search
Idea
• Expand search top-down
• Keep track of the closest points found so far
• Stop only when we know there cannot be any
other closer points
• We can easily compute the minimum possible distance
between the query point 𝑞 and any data point in a
bounding box
kd-tree similarity search example
𝑥1
𝑥5 𝑥7
𝑥1
𝐵
𝐺
𝐴
𝑦2 𝑦3
𝐸
𝑦2
Min. dist. to points
in 𝑦2’s right subtree 𝐷
Min. dist. to points 𝑦3 𝑥4 𝑥5 𝑥6 𝑥7
in 𝑥4 ’s right subtree

𝑞Min. dist. to points

𝑦 in 𝑥1’s right subtree 𝐻 𝐶 𝐷 𝐴 𝐵 𝐹 𝐻 𝐸 𝐺
𝐶

𝐹 Interested in top 2; found 𝐶 and 𝐷:

𝑥 𝑥4 𝑥5 may still contain an answer
𝑥6 𝑦3 cannot possibly contain an answer
kd-tree summary
• Variant: splitting doesn’t need to be on predefined
dimensions; may be on principal dimensions found
through principal component analysis (PCA)
• Supports nearest-neighbor query exactly, but has
𝑂 𝑛𝑁 1–1/𝑛 complexity where 𝑁 = # of points and
𝑛 = # of dimensions
• Simple to implement, but doesn’t work well for
very high dimensionality
Clustering & partitioning
• Idea: partition objects into clusters by similarity;
search only clusters whose “centers” similar to 𝑞
• 𝑘-means: partition objects into 𝑘 clusters to
minimize the sum of squares of the distance
between each object and its cluster centroid
• Voronoi diagram: given a set of seeds, partition the
space into disjoint cells, one for each seed, such
that each cell contains all points that are closer to
the corresponding seed than any other
Voronoi diagram example
IVF (Inverted File) indexing

Vectors in each partition can

be stored simply as a flat file
or using quantization (later)
Quantization
• In high dimension, even storing an entire vector is
expensive
• Simple quantization: e.g., for each dimension,
down-convert a 64-bit double to a 32-bit float
• Nearest-centroid quantization: partition objects
into clusters, and then represent each object by the
centroid of the cluster it represents
• Product quantization: divide the full space into
subspaces and then apply nearest-centroid
quantization to each
☞Lossy compression, but good enough for
approximate similarity search
Product quantization example
Locality-sensitive hashing (LSH)
(Intuition only)
• Design a family of hash functions ℎ that capture
“similarity” with high probability:
• If 𝑞 and 𝑥 are close (far), then ℎ 𝑞 = ℎ 𝑥 with high
(low, respectively) probability
• Design depends on the similarity metric
• To improve accuracy, use multiple hash functions
randomly chosen from the family
LSH for vector indexing
Idea: random projections
• Pick a random vector 𝑣⃗, and hash each data vector
to either 1 or 0 (depending on the sign of its dot
product with 𝑣⃗)
• Multiple random vectors → a hashed bit vector
• Approximate (dis)similarity by hamming distance
• I.e., # of bits that differ
Indexing & querying
• Partition all objects by their hash
• Search in partitions of the shortest hamming
distance from 𝑞’s hash
skip list
A simple probabilistic alternative to 1-d search trees
• Organized into layers of linked lists
• Each layer “skips” at a different scale, controlled by
a parameter 𝑝 (typically ½ or ¼)
• Bottom layer (#1) = all elements
• Layer 𝑖 + 1 has a subset of the elements of layer 𝑖 and
acts as an “express lane”
• Each element of layer 𝑖 appears in layer 𝑖 + 1 with probability 𝑝
Lookup
• Start from top layer
• In each layer, scan right until we find target, or
• If we overshoot it, descend from the last smaller
element to the next layer
Example: look up 50

Layer 4 1 ⏚
Layer 3 2 3 ⏚
Layer 2 4 ⏚
Layer 1 5 6 ⏚
10 20 30 40 50 60 70 80 90 100

1
• Expect cost is 𝑂 𝑝
log 1 𝑁
𝑝
Insert
• Follow lookup procedure to insert in bottom layer
• Until a biased coin flip turns up a tail (prob. 1 − 𝑝)
• Insert into the next layer

Example: insert 75

Layer 4
⏚
tail
Layer 3 3 ⏚
head
Layer 2 2 ⏚
Layer 1 1 ⏚
10 20 30 40 50 60 70 75 80 90 100

• Expect cost is also 𝑂 log 𝑁

HNSW
Idea: capture “similarity” as a proximity graph which
connects pairs of points within a distance threshold
• Navigable Small-World: even in a large graph, you
can go from one node to another in a small
(polylogarithmic) # of hops via “greedy routing”
• To construct the graph for navigation: for each new
point, find 𝑘 most similar existing points and add links
• There many other heuristics for picking edges
• Hierarchical: extend skip list idea to skip graph
• Layers of navigable graphs
• Each layer “skips” at a different scale
Searching within one layer
• From the current node 𝑢, greedily take the next
step to be the node among 𝑢’s neighbors that’s
closest to 𝑞
Overall search algorithm
• Start from top layer
• In each layer, once we find the local minimum,
descend to the next layer and continue from there
• Stop in the bottom layer
Who’s the winner for vector DB?
• kd-tree: don’t
• IVF (cluster & partition + quantization): reasonable
speed and memory usage; high recall †
• LSH: small memory usage but can be slow; recall
not as good as others †
• HNSW: high speed and high recall, but large
memory usage †
† according to Pinecone as of Spring 2024
• Most vector DBMS implement several alternatives
• Lots of parameter tuning still needed
• Better theoretical understanding is needed
• Automatic selection/tuning would be desirable
Further reading

[Link]