Skip to content

Latest commit

 

History

History

clustering

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 
centroids.py
centroids.py
 
 
config_bigann_large.py
config_bigann_large.py
 
 
config_bigann_small.py
config_bigann_small.py
 
 
config_bigann_xlkmeans.py
config_bigann_xlkmeans.py
 
 
config_deep_small.py
config_deep_small.py
 
 
config_msspacev_small.py
config_msspacev_small.py
 
 
config_msturing_small.py
config_msturing_small.py
 
 
config_ssnpp_small.py
config_ssnpp_small.py
 
 
config_text2image_small.py
config_text2image_small.py
 
 
deploy.sh
deploy.sh
 
 
distributions.py
distributions.py
 
 
komolgorovsmirnov.py
komolgorovsmirnov.py
 
 
komolgorovsmirnov_config_bigann_small.csv
komolgorovsmirnov_config_bigann_small.csv
 
 
komolgorovsmirnov_config_deep_small.csv
komolgorovsmirnov_config_deep_small.csv
 
 
komolgorovsmirnov_config_msspacev_small.csv
komolgorovsmirnov_config_msspacev_small.csv
 
 
komolgorovsmirnov_config_msturing_small.csv
komolgorovsmirnov_config_msturing_small.csv
 
 
komolgorovsmirnov_config_ssnpp_small.csv
komolgorovsmirnov_config_ssnpp_small.csv
 
 
komolgorovsmirnov_config_text2image_small.csv
komolgorovsmirnov_config_text2image_small.csv
 
 
komolgorovsmirnov_heatmap_config_bigann_small.png
komolgorovsmirnov_heatmap_config_bigann_small.png
 
 
komolgorovsmirnov_heatmap_config_bigann_small_half.png
komolgorovsmirnov_heatmap_config_bigann_small_half.png
 
 
komolgorovsmirnov_heatmap_config_deep_small.png
komolgorovsmirnov_heatmap_config_deep_small.png
 
 
komolgorovsmirnov_heatmap_config_deep_small_half.png
komolgorovsmirnov_heatmap_config_deep_small_half.png
 
 
komolgorovsmirnov_heatmap_config_msspacev_small.png
komolgorovsmirnov_heatmap_config_msspacev_small.png
 
 
komolgorovsmirnov_heatmap_config_msspacev_small_half.png
komolgorovsmirnov_heatmap_config_msspacev_small_half.png
 
 
komolgorovsmirnov_heatmap_config_msturing_small.png
komolgorovsmirnov_heatmap_config_msturing_small.png
 
 
komolgorovsmirnov_heatmap_config_msturing_small_half.png
komolgorovsmirnov_heatmap_config_msturing_small_half.png
 
 
komolgorovsmirnov_heatmap_config_ssnpp_small.png
komolgorovsmirnov_heatmap_config_ssnpp_small.png
 
 
komolgorovsmirnov_heatmap_config_ssnpp_small_half.png
komolgorovsmirnov_heatmap_config_ssnpp_small_half.png
 
 
komolgorovsmirnov_heatmap_config_text2image_small.png
komolgorovsmirnov_heatmap_config_text2image_small.png
 
 
komolgorovsmirnov_heatmap_config_text2image_small_half.png
komolgorovsmirnov_heatmap_config_text2image_small_half.png
 
 
komolgorovsmirnov_network.ipynb
komolgorovsmirnov_network.ipynb
 
 
multicollinearity.py
multicollinearity.py
 
 
multicollinearity_config_bigann_small.csv
multicollinearity_config_bigann_small.csv
 
 
multicollinearity_config_deep_small.csv
multicollinearity_config_deep_small.csv
 
 
multicollinearity_config_msspacev_small.csv
multicollinearity_config_msspacev_small.csv
 
 
multicollinearity_config_msturing_small.csv
multicollinearity_config_msturing_small.csv
 
 
multicollinearity_config_ssnpp_small.csv
multicollinearity_config_ssnpp_small.csv
 
 
multicollinearity_config_text2image_small.csv
multicollinearity_config_text2image_small.csv
 
 
multicollinearity_heatmap2_config_bigann_small.png
multicollinearity_heatmap2_config_bigann_small.png
 
 
multicollinearity_heatmap2_config_deep_small.png
multicollinearity_heatmap2_config_deep_small.png
 
 
multicollinearity_heatmap2_config_msspacev_small.png
multicollinearity_heatmap2_config_msspacev_small.png
 
 
multicollinearity_heatmap2_config_msturing_small.png
multicollinearity_heatmap2_config_msturing_small.png
 
 
multicollinearity_heatmap2_config_ssnpp_small.png
multicollinearity_heatmap2_config_ssnpp_small.png
 
 
multicollinearity_heatmap2_config_text2image_small.png
multicollinearity_heatmap2_config_text2image_small.png
 
 
multicollinearity_heatmap_config_bigann_small.png
multicollinearity_heatmap_config_bigann_small.png
 
 
multicollinearity_heatmap_config_deep_small.png
multicollinearity_heatmap_config_deep_small.png
 
 
multicollinearity_heatmap_config_msspacev_small.png
multicollinearity_heatmap_config_msspacev_small.png
 
 
multicollinearity_heatmap_config_msturing_small.png
multicollinearity_heatmap_config_msturing_small.png
 
 
multicollinearity_heatmap_config_ssnpp_small.png
multicollinearity_heatmap_config_ssnpp_small.png
 
 
multicollinearity_heatmap_config_text2image_small.png
multicollinearity_heatmap_config_text2image_small.png
 
 
multicollinearity_network.ipynb
multicollinearity_network.ipynb
 
 
network_blended.py
network_blended.py
 
 
network_komolgorovsmirnov.py
network_komolgorovsmirnov.py
 
 
network_mutlicollinearity.py
network_mutlicollinearity.py
 
 
recall.py
recall.py
 
 
receive.sh
receive.sh
 
 
search_by_cluster.py
search_by_cluster.py
 
 
shard.py
shard.py
 
 
shard_by_cluster.py
shard_by_cluster.py
 
 
variance.py
variance.py
 
 
variance_config_bigann_small.csv
variance_config_bigann_small.csv
 
 
visualize_distributions-overlap.ipynb
visualize_distributions-overlap.ipynb
 
 
visualize_distributions.ipynb
visualize_distributions.ipynb
 
 

README.md

K-Means based sharding algorithm

This sharding algorithm is based on K-Means:

  1. Cluster the input dataset using K-Means algorithm into M clusters (also shards).
  2. For each centroid create a new shard graph.
  3. The shard is an HNSW graph with neighborhoods of the parent centroid.
  4. The shard is persisted to disk for each addition.
  5. The shard is loaded from disk and searched when a query is in its centroid neighborhood.

Experiments

These settings took 7 minutes on my macbook pro with other stuff running to fit KMeans: RANDOM_SEED = 505 SAMPLE_SIZE = 100000 M = 1000 MAX_ITER = 50 BATCH_SIZE = 1000000 """

""" The idea is to go very wide with the clustering, to increase the number of shards For 10k centroids there are 10k shards (each with 100k vectors) For 100k centroids there are 100k shards (each with 10k vectors) For 1m centroids there are 1m shards (each with 1k vectors)