Investigate hierarchical centroid storage for ivf format

[benwtrent]

Description

After #128675 we will be utilizing a type of hierarchical kmeans for clustering.

I wonder if we can keep 1 or two layers (or possibly rebuild them....) when storing the centroids.

The idea would be we can score blocks of centroids at a time, but at different layers.

I am not fully convinced we actually need a bottom layer graph like SPTAG (or spfresh), generally because segments (our partitions) are generally much smaller and we want to have fairly large posting lists (generally).

I am not ruling out the benefit of a bottom layer graph with an upper layer tree. I just like the idea of starting simple first :).

[elasticsearchmachine]

Pinging @elastic/es-search-relevance (Team:Search Relevance)

[john-wagster]

Writing down thoughts here.

One thing to consider is currently when we don't store the parent centroids. The logic overwrites the parent with the child centroids and then subsequent iterations will shift recursively smaller partitions (children's children) and replace those as well. So I believe to retain a layer we would need to retain the parent centroids separately and presumably pointers to each of the children within the sub partitions (for some fixed number of layers).

If considering rebuilding as an alternative then we probably want to recalculate new parent centroids at each layer. This strikes me as both reasonable and maybe the easiest thing to do initially as we do currently do a similar calculation to adjust the global centroid, and it may be a better reflection of a representative point in any given partition of the space at some layer since subsequent centroids that are in the partition would have been shifted to better represent vectors in that partition. To do more each layers additional information would need to be stored but only the groupings (pointers) of centroids that form a partition at each layer.

[benwtrent]

To do more each layers additional information would need to be stored but only the groupings (pointers) of centroids that form a partition at each layer.

Yeah, so doing a "rebuilding" would be clustering the centroids. Then I think we need to ensure that child centroids are on disk in order given their parent centroids. This way we don't need to have a complicated centroid ordinal translation. Think of it like a flattened tree where the children are all in-line and available at a given offset.

This will require adjusting the centroid ordinals for the postings list as well to ensure we don't have a complicated ordinal translation scheme.

[benwtrent]

One other thing to consider is if we quantize the centroids according to their higher level centroid membership or keep the quantization to be global...

[john-wagster]

Bringing together several stats that I collected as I was doing this investigation. I or others may do further investigation but we reached a point where there's enough information here to checkpoint and consider next steps. So I wanted to document some of what I explored and the conclusions I reached for posterity.

PR to track work related to this is here: #129950

summary

running a second hkmeans only on the centroids seems like the best compromise for now with a 5% buffer on the parent scores and forming up sqrt(centroids.len) numbers of parent centroids. This seemed to produce good results for recall and latency improvements for lower nprobe and the same results for higher nprobe but at the cost of overhead during merge. We are seeing a 50% improvement in latency for some lower nprobe values on Cohere.

However, GloVe is a lot less well behaved. We see drops in recall at 5% buffer so a higher buffer value may be needed or otherwise large nprobe will cause search explosions. This particular point needs further discussion before the aforementioned PR can be merged.

approach

I started by trying to do some minimal modifications to the hkmeans algorithm to see if we could minimize the impact to the merge time while maintaining recall and reducing search time. Ultimately I've settled on the running a second hkmeans pass.

data formats

There were a handful of different data formats for the centroids that I tried and considered. The intention with the current approach is to degenerate nicely when no parents exist and also to sort the centroids into groups based on the parent centroid. The current format is as follows: pq cq cr for instance pq1 pq2 cq1 cq2 cq3 cq4 cq5 cr1 cr2 cr3 cr4 cr5 where:

• pq = parent quantized centroid and offset and length of child centroid block
• cq = child / leaf quantized centroid
• cr = raw centroids

The downside of this approach is that "orphan" leaf nodes where no parent was constructed duplicate the quantized centroid in both the parent block (pq) and the centroid block (cq).

A reasonable alternative might be to structure to remove the orphans but this has a downside of not knowing exactly where to offset into the centroids making it difficult to read in blocks blindly or having to store additional information on the centroid or parent block such a boolean indicating that a centroid is an orphan. It's potentially an optimization for the future.

algorithms

Initially I tried to pull out the hierarchy from the hkmeans algorithm. This proved easy but lacked the fix up steps of the local kmeans algorith. This caused many of the centroid to need to be explored particularly for datasets like GloVe effectively rendering the parent centroids extra overhead in finding the top k.

Subsequently I tried to do clustering with the kmeans and hkmeans algorithms separately as a whole additional step. Both of these approaches seemed to do equally well. I've gone with running hkmeans for now because it does have that fix up step. Subsequent work here could consider merging the two approaches.

It's worth noting that in both cases comparing parent and leaf scores on search we expand the list of known centroids to explore by comparing the next closest parent with the next closet leaf centroid. However, directly comparing these two did not produce optimal exploration of centroids. There seems to be in both Cohere and GloVe outlier centroids that even when running hkmeans a second time causes missed exploration. To get around this I introduced a 5% buffer on the parent score. I feel like there's got to be a better approach here but I have yet to reason through it. I tried a variety of values here as well. It's not clear to me that 5% is ideal but it seems to minimize unnecessary parent exploration. Other higher buffers seem to work well up to about 20% or so before we degenerate into just loading all the centroids. A 0% (no buffer) seems to fail to be optimal in all configurations (picking different numbers of parent centroids and approaches for how the parent centroids are formed).

I also explored how many parent centroids to form up. Initially I started with 128 as a fixed value. I tried as small as 32. I found that the sqrt(centroids.len) typically produced the best results across both glove and cohere.

One alternative I explored initially was attempting to identify the right number of parent centroids to read rather than comparing the next parent centroid with the closest leaf centroid. The hope being that a small fixed number of parent centroids would be sufficient to consistently get higher recall. This became an obvious dead-end when I realized that sometimes large numbers of parent centroids needed to be explored. I tried increasing nprobe to compensate but latency tanked as this caused more overall vectors to be explored while seeking out the top k. The top k are often mostly contained to the first 5 or so parent centroids but unfortunately there seems to frequently be outliers.

evaluations

Cohere 3m Main vs 2 hkmeans passes + 5% buffer

# main cohere 3m
index_name                          index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
----------------------------------  ----------  --------  --------------  --------------------  ------------  
cohere-wikipedia-10m-docs-768d.vec         ivf   3000000          255033                414750             0

index_name                          index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
----------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
cohere-wikipedia-10m-docs-768d.vec         ivf      100         2.51              0.00           0.00  399.04    0.84   18520.24
cohere-wikipedia-10m-docs-768d.vec         ivf      200         3.94              0.00           0.00  254.00    0.90   40415.19
cohere-wikipedia-10m-docs-768d.vec         ivf      500         5.68              0.00           0.00  176.15    0.94  109366.77

index_name                          index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
----------------------------------  ----------  --------  --------------  --------------------  ------------  
cohere-wikipedia-10m-docs-768d.vec         ivf   3000000          267109                450013             0

index_name                          index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
----------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
cohere-wikipedia-10m-docs-768d.vec         ivf      100         1.96              0.00           0.00  510.46    0.84   18548.50
cohere-wikipedia-10m-docs-768d.vec         ivf      200         3.04              0.00           0.00  328.95    0.90   40336.97
cohere-wikipedia-10m-docs-768d.vec         ivf      500         5.99              0.00           0.00  166.83    0.94  108747.67

index_name                          index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
----------------------------------  ----------  --------  --------------  --------------------  ------------  
cohere-wikipedia-10m-docs-768d.vec         ivf   3000000           95074                382921             0

index_name                          index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
----------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
cohere-wikipedia-10m-docs-768d.vec         ivf      100         1.98              0.00           0.00  505.05    0.83   17869.12
cohere-wikipedia-10m-docs-768d.vec         ivf      200         3.11              0.00           0.00  322.06    0.90   38784.74
cohere-wikipedia-10m-docs-768d.vec         ivf      500         5.88              0.00           0.00  170.15    0.94  105227.83



# additional kmeans on parents after hkmeans by clustering sqrt(centroids.len) + relaxing parent score constraint by 5%
index_name                          index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
----------------------------------  ----------  --------  --------------  --------------------  ------------  
cohere-wikipedia-10m-docs-768d.vec         ivf   3000000           83505                292800             0

index_name                          index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
----------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
cohere-wikipedia-10m-docs-768d.vec         ivf      100         1.25              0.00           0.00  800.00    0.85   22609.29
cohere-wikipedia-10m-docs-768d.vec         ivf      200         2.51              0.00           0.00  398.88    0.90   46184.88
cohere-wikipedia-10m-docs-768d.vec         ivf      500         5.46              0.00           0.00  183.15    0.94  116547.52

10m GloVe Main vs Extra HKmeans at Different Buffer Levels

# main glove 3m
index_name                         index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
---------------------------------  ----------  --------  --------------  --------------------  ------------  
enwiki-20120502-lines-1k-200d.vec         ivf  10000000          247174                308327             0

index_name                         index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
---------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
enwiki-20120502-lines-1k-200d.vec         ivf      100         2.56              0.00           0.00  390.02    0.63   41113.10
enwiki-20120502-lines-1k-200d.vec         ivf      200         3.45              0.00           0.00  289.86    0.67   82298.04
enwiki-20120502-lines-1k-200d.vec         ivf      500         6.02              0.00           0.00  166.17    0.71  203404.07
enwiki-20120502-lines-1k-200d.vec         ivf      800         8.83              0.00           0.00  113.24    0.73  323039.94


# additional kmeans on parents after hkmeans by clustering sqrt(centroids.len) + relaxing parent score constraint by 5%
index_name                         index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
---------------------------------  ----------  --------  --------------  --------------------  ------------  
enwiki-20120502-lines-1k-200d.vec         ivf  10000000           79781                298974             0

index_name                         index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
---------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
enwiki-20120502-lines-1k-200d.vec         ivf      100         1.37              0.00           0.00  728.33    0.44   42880.97
enwiki-20120502-lines-1k-200d.vec         ivf      200         2.17              0.00           0.00  460.83    0.50   85113.16
enwiki-20120502-lines-1k-200d.vec         ivf      500         4.90              0.00           0.00  204.00    0.57  208772.63
enwiki-20120502-lines-1k-200d.vec         ivf      800         7.95              0.00           0.00  125.71    0.60  330331.73


# additional kmeans on parents after hkmeans by clustering sqrt(centroids.len) + relaxing parent score constraint by 10%
index_name                         index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
---------------------------------  ----------  --------  --------------  --------------------  ------------  
enwiki-20120502-lines-1k-200d.vec         ivf  10000000          235454                451539             0

index_name                         index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
---------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
enwiki-20120502-lines-1k-200d.vec         ivf      100         1.92              0.00           0.00  521.38    0.55   41900.72
enwiki-20120502-lines-1k-200d.vec         ivf      200         2.84              0.00           0.00  352.24    0.60   83546.21
enwiki-20120502-lines-1k-200d.vec         ivf      500         6.12              0.00           0.00  163.40    0.67  206063.47
enwiki-20120502-lines-1k-200d.vec         ivf      800         8.08              0.00           0.00  123.70    0.70  326456.32

# additional kmeans on parents after hkmeans by clustering sqrt(centroids.len) + relaxing parent score constraint by 15%
index_name                         index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
---------------------------------  ----------  --------  --------------  --------------------  ------------  
enwiki-20120502-lines-1k-200d.vec         ivf  10000000           72403                467028             0

index_name                         index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
---------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
enwiki-20120502-lines-1k-200d.vec         ivf      100         2.07              0.00           0.00  483.56    0.61   41710.03
enwiki-20120502-lines-1k-200d.vec         ivf      200         3.13              0.00           0.00  319.90    0.65   83207.98
enwiki-20120502-lines-1k-200d.vec         ivf      500         5.61              0.00           0.00  178.19    0.70  205152.32
enwiki-20120502-lines-1k-200d.vec         ivf      800         8.30              0.00           0.00  120.50    0.72  325526.28

# additional kmeans on parents after hkmeans by clustering sqrt(centroids.len) + relaxing parent score constraint by 20%
index_name                         index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
---------------------------------  ----------  --------  --------------  --------------------  ------------  
enwiki-20120502-lines-1k-200d.vec         ivf  10000000           86063                429810             0

index_name                         index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
---------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
enwiki-20120502-lines-1k-200d.vec         ivf      100         2.32              0.00           0.00  430.66    0.61   41304.84
enwiki-20120502-lines-1k-200d.vec         ivf      200         3.59              0.00           0.00  278.32    0.65   82758.13
enwiki-20120502-lines-1k-200d.vec         ivf      500         6.15              0.00           0.00  162.50    0.70  204086.07
enwiki-20120502-lines-1k-200d.vec         ivf      800         8.88              0.00           0.00  112.56    0.73  323684.95

3m Cohere Main vs Extra Kmeans vs Extra HKmeans vs Extra HKMeans fixed 32 parents

# main cohere 3m
index_name                          index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
----------------------------------  ----------  --------  --------------  --------------------  ------------  
cohere-wikipedia-10m-docs-768d.vec         ivf   3000000          234759                525989             0

index_name                          index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
----------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
cohere-wikipedia-10m-docs-768d.vec         ivf      500         5.59              0.00           0.00  178.76    0.94  104958.44


# extra hkmeans on parents after first hkmeans with vectorsPerCluster = clusters.len / sqrt(clusters.len) + relaxing parent score constraint by 5%
index_name                          index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
----------------------------------  ----------  --------  --------------  --------------------  ------------  
cohere-wikipedia-10m-docs-768d.vec         ivf   3000000          207079                277827             0

index_name                          index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
----------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
cohere-wikipedia-10m-docs-768d.vec         ivf      500         5.28              0.00           0.00  189.29    0.94  114408.50


# additional kmeans on parents after hkmeans by clustering sqrt(centroids.len) + relaxing parent score constraint by 5%
index_name                          index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
----------------------------------  ----------  --------  --------------  --------------------  ------------  
cohere-wikipedia-10m-docs-768d.vec         ivf   3000000          182521                279628             0

index_name                          index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
----------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
cohere-wikipedia-10m-docs-768d.vec         ivf      500         5.27              0.00           0.00  189.68    0.94  115391.59


# extra hkmeans on parents after first hkmeans with vectorsPerCluster = clusters.len / 32 + relaxing parent score constraint by 5%
index_name                          index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
----------------------------------  ----------  --------  --------------  --------------------  ------------  
cohere-wikipedia-10m-docs-768d.vec         ivf   3000000          181160                293293             0

index_name                          index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
----------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
cohere-wikipedia-10m-docs-768d.vec         ivf      500         5.30              0.00           0.00  188.79    0.94  115732.71

3m Cohere Main vs Extra Kmeans at different parent score thresholds

# main cohere 3m
index_name                          index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
----------------------------------  ----------  --------  --------------  --------------------  ------------  
cohere-wikipedia-10m-docs-768d.vec         ivf   3000000          234759                525989             0

index_name                          index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
----------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
cohere-wikipedia-10m-docs-768d.vec         ivf      500         5.59              0.00           0.00  178.76    0.94  104958.44

# kmeansstruc2 branch cohere 3m w forming up parents after hkmeans by clustering sqrt(centroids.len) + relaxing parent score constraint by 5%
index_name                          index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
----------------------------------  ----------  --------  --------------  --------------------  ------------  
cohere-wikipedia-10m-docs-768d.vec         ivf   3000000          182521                279628             0

index_name                          index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
----------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
cohere-wikipedia-10m-docs-768d.vec         ivf      500         5.27              0.00           0.00  189.68    0.94  115391.59




# kmeansstruc2 branch cohere 3m w forming up parents after hkmeans by clustering sqrt(centroids.len) + relaxing parent score constraint by 20%
index_name                          index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
----------------------------------  ----------  --------  --------------  --------------------  ------------  
cohere-wikipedia-10m-docs-768d.vec         ivf   3000000          204701                318844             0

index_name                          index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
----------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
cohere-wikipedia-10m-docs-768d.vec         ivf      500         5.47              0.00           0.00  182.72    0.94  105666.79


# kmeansstruc2 branch cohere 3m w forming up parents after hkmeans by clustering sqrt(centroids.len) + relaxing parent score constraint by 15%
index_name                          index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
----------------------------------  ----------  --------  --------------  --------------------  ------------  
cohere-wikipedia-10m-docs-768d.vec         ivf   3000000          175298                287989             0

index_name                          index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
----------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
cohere-wikipedia-10m-docs-768d.vec         ivf      500         5.57              0.00           0.00  179.60    0.94  107076.95


# kmeansstruc2 branch cohere 3m w forming up parents after hkmeans by clustering sqrt(centroids.len) + relaxing parent score constraint by 10%
index_name                          index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
----------------------------------  ----------  --------  --------------  --------------------  ------------  
cohere-wikipedia-10m-docs-768d.vec         ivf   3000000           79219                283895             0

index_name                          index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
----------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
cohere-wikipedia-10m-docs-768d.vec         ivf      500         5.63              0.00           0.00  177.75    0.93  107505.31




# kmeansstruc2 branch cohere 3m w forming up parents after hkmeans by clustering sqrt(centroids.len) + relaxing parent score constraint by 0%
index_name                          index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
----------------------------------  ----------  --------  --------------  --------------------  ------------  
cohere-wikipedia-10m-docs-768d.vec         ivf   3000000          185891                277921             0

index_name                          index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
----------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
cohere-wikipedia-10m-docs-768d.vec         ivf      500         5.82              0.00           0.00  171.67    0.88  141103.76


# 10m kmeans struc 2 w forming up parents after hkmeans by clustering half fixed parent clusters + relaxing parent score constraint by 5%
index_name                          index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
----------------------------------  ----------  --------  --------------  --------------------  ------------  
cohere-wikipedia-10m-docs-768d.vec         ivf   3000000           86769                325262             0

index_name                          index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
----------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
cohere-wikipedia-10m-docs-768d.vec         ivf      500         6.27              0.00           0.00  159.52    0.89  140329.46

GloVe Using Top Layer in HKmeans vs Running Extra KMeans

Show cases one query where when exploring all parents we find there are outlier centroids that contain at least one vector that is part of the top K. This makes it difficult to optimize when to explore parents vs child / leaf centroids.

The results below are in order of shorted parent partition distance to the query vector order. So any counts toward the bottom are really painful to see as that means to get all top k we have to explore most parents.

For instance in the first output there is at least one vector in the top k that is in a centroid that's part of a parent partition that is 3rd from the last parent partition that gets explored.

# this is with using the top level partitioning that came out of running clusterAndSplit.  You can see that the top level parents overlap too much with the underlying centroids and so we essentially have to explore all parents eventually to get the top k
# Parent Ordinal :: Number of Centroids that Contains at Least One Top K Vector
56 :: 168
74 :: 12
45 :: 7
20 :: 31
4 :: 85
120 :: 7
50 :: 5
111 :: 0
42 :: 11
46 :: 8
63 :: 8
9 :: 0
67 :: 1
119 :: 0
51 :: 0
52 :: 3
81 :: 2
36 :: 74
72 :: 0
6 :: 0
41 :: 5
93 :: 0
48 :: 1
78 :: 0
64 :: 0
30 :: 0
98 :: 5
89 :: 1
44 :: 1
26 :: 1
126 :: 0
110 :: 0
122 :: 0
27 :: 1
13 :: 2
10 :: 0
103 :: 0
62 :: 2
125 :: 0
18 :: 5
113 :: 2
85 :: 0
29 :: 25
70 :: 0
21 :: 0
102 :: 0
8 :: 1
40 :: 0
97 :: 0
68 :: 0
43 :: 5
17 :: 0
96 :: 0
127 :: 0
33 :: 0
77 :: 0
84 :: 0
22 :: 0
12 :: 1
61 :: 0
112 :: 0
19 :: 0
124 :: 0
106 :: 0
57 :: 0
118 :: 0
23 :: 0
82 :: 0
75 :: 0
73 :: 0
83 :: 0
99 :: 0
47 :: 0
79 :: 3
16 :: 0
105 :: 0
32 :: 0
24 :: 2
53 :: 0
109 :: 0
60 :: 5
90 :: 0
92 :: 1
117 :: 2
88 :: 0
121 :: 0
54 :: 0
86 :: 0
31 :: 0
65 :: 0
116 :: 0
28 :: 0
55 :: 0
37 :: 0
108 :: 1
1 :: 0
107 :: 0
91 :: 2
35 :: 0
101 :: 0
7 :: 0
34 :: 0
100 :: 0
71 :: 1
95 :: 0
39 :: 0
14 :: 0
69 :: 1
76 :: 0
0 :: 0
104 :: 0
3 :: 0
66 :: 0
2 :: 0
25 :: 0
94 :: 0
123 :: 0
5 :: 0
87 :: 1
38 :: 0
49 :: 0
59 :: 0
58 :: 0
114 :: 0
115 :: 0
80 :: 1
11 :: 0
15 :: 0

# this is clustering just the centroids after running hkmeans and then pick sqrt(centroids.len) parent centroids.  This approach is more expensive but does produce a better result.  Less overall centroids need to be searched.
# Parent Ordinal :: Number of Centroids that Contains at Least One Top K Vector
146 :: 48
49 :: 83
83 :: 53
21 :: 36
59 :: 50
78 :: 70
23 :: 18
29 :: 9
99 :: 24
37 :: 9
44 :: 6
145 :: 0
70 :: 0
150 :: 0
126 :: 13
128 :: 0
52 :: 0
116 :: 2
66 :: 0
57 :: 0
183 :: 1
162 :: 5
181 :: 0
38 :: 5
113 :: 2
79 :: 5
153 :: 0
9 :: 0
60 :: 0
71 :: 0
14 :: 1
109 :: 0
159 :: 1
112 :: 0
75 :: 0
69 :: 0
11 :: 0
87 :: 4
28 :: 0
178 :: 4
45 :: 2
53 :: 1
15 :: 0
135 :: 4
7 :: 1
61 :: 0
30 :: 0
90 :: 0
47 :: 0
190 :: 0
147 :: 2
119 :: 0
39 :: 0
82 :: 3
50 :: 0
34 :: 0
31 :: 2
42 :: 2
65 :: 1
148 :: 0
142 :: 0
127 :: 0
167 :: 0
143 :: 0
17 :: 0
161 :: 0
36 :: 1
189 :: 0
111 :: 0
102 :: 0
100 :: 5
177 :: 0
86 :: 0
172 :: 3
46 :: 2
152 :: 0
121 :: 0
107 :: 0
106 :: 0
1 :: 0
131 :: 0
77 :: 0
89 :: 0
95 :: 0
108 :: 0
156 :: 0
140 :: 0
186 :: 0
98 :: 0
96 :: 0
33 :: 0
25 :: 1
48 :: 0
175 :: 1
139 :: 1
2 :: 0
130 :: 0
187 :: 0
157 :: 0
20 :: 0
169 :: 0
0 :: 0
164 :: 0
149 :: 0
16 :: 1
3 :: 0
10 :: 0
40 :: 0
74 :: 1
176 :: 0
179 :: 0
168 :: 0
182 :: 0
18 :: 0
185 :: 0
5 :: 0
55 :: 0
163 :: 1
188 :: 0
110 :: 0
35 :: 0
43 :: 0
54 :: 2
32 :: 1
27 :: 0
73 :: 0
91 :: 0
160 :: 0
171 :: 0
141 :: 2
104 :: 0
8 :: 0
158 :: 0
154 :: 0
26 :: 1
125 :: 0
118 :: 1
84 :: 2
64 :: 0
122 :: 0
80 :: 0
133 :: 0
72 :: 0
92 :: 0
134 :: 0
68 :: 1
138 :: 0
63 :: 0
94 :: 0
56 :: 1
165 :: 0
120 :: 0
174 :: 0
184 :: 0
136 :: 0
103 :: 0
19 :: 0
93 :: 0
85 :: 1
129 :: 1
24 :: 1
132 :: 0
144 :: 0
180 :: 0
4 :: 0
88 :: 0
155 :: 1
115 :: 0
58 :: 0
117 :: 0
114 :: 1
123 :: 0
137 :: 0
151 :: 0
67 :: 0
173 :: 0
13 :: 0
62 :: 0
166 :: 0
51 :: 0
81 :: 0
41 :: 0
170 :: 0
12 :: 0
97 :: 0
6 :: 0
101 :: 0
22 :: 0
76 :: 0
105 :: 0
124 :: 0

Variety of GloVe Runs with Different Configurations

# profiled 10m main
index_name                         index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
---------------------------------  ----------  --------  --------------  --------------------  ------------  
enwiki-20120502-lines-1k-200d.vec         ivf  10000000          295019                451881             0

index_name                         index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
---------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
enwiki-20120502-lines-1k-200d.vec         ivf      500         6.51              0.00           0.00  153.59    0.71  208789.91



# profiled 10m kmeans struc 2
index_name                         index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
---------------------------------  ----------  --------  --------------  --------------------  ------------  
enwiki-20120502-lines-1k-200d.vec         ivf  10000000          362708                749371             0

index_name                         index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count   QPS  recall     visited
---------------------------------  ----------  -------  -----------  ----------------  -------------  ----  ------  ----------  
enwiki-20120502-lines-1k-200d.vec         ivf    18000       211.26              0.00           0.00  4.73    0.75  5870760.04



# 10m kmeans struc 2 w forced -1 parent
index_name                         index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
---------------------------------  ----------  --------  --------------  --------------------  ------------  
enwiki-20120502-lines-1k-200d.vec         ivf  10000000          123180                680711             0

index_name                         index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count   QPS  recall     visited
---------------------------------  ----------  -------  -----------  ----------------  -------------  ----  ------  ----------  
enwiki-20120502-lines-1k-200d.vec         ivf    18000       218.07              0.00           0.00  4.59    0.88  5941788.30



# 10m kmeans struc 2 w 34% greater threshold on parent score checks
total parent centroids: 128
total child centroids: 39174
total centroids (parent & child) read: 37601
index_name                         index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
---------------------------------  ----------  --------  --------------  --------------------  ------------  
enwiki-20120502-lines-1k-200d.vec         ivf  10000000          406762                710576             0

index_name                         index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
---------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
enwiki-20120502-lines-1k-200d.vec         ivf      500         7.59              0.00           0.00  131.80    0.73  209086.89



# 10m kmeans struc 2 w forming up parents after hkmeans by clustering sqrt(centroids.len) ~194 + relaxing parent score constraint by 10%
total parent centroids: 194
total child centroids: 39147
total centroids (parent & child) read: 26101
index_name                         index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
---------------------------------  ----------  --------  --------------  --------------------  ------------  
enwiki-20120502-lines-1k-200d.vec         ivf  10000000           79398                297743             0

index_name                         index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
---------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
enwiki-20120502-lines-1k-200d.vec         ivf      500         5.76              0.00           0.00  173.58    0.69  204608.11


# same as above but removed diagnostics
index_name                         index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
---------------------------------  ----------  --------  --------------  --------------------  ------------  
enwiki-20120502-lines-1k-200d.vec         ivf  10000000           81998                311929             0

index_name                         index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
---------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
enwiki-20120502-lines-1k-200d.vec         ivf      500         5.46              0.00           0.00  183.12    0.69  206379.39

# same as above but w 15% buffer instead of 10%
index_name                         index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
---------------------------------  ----------  --------  --------------  --------------------  ------------  
enwiki-20120502-lines-1k-200d.vec         ivf  10000000          197766                297962             0

index_name                         index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
---------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
enwiki-20120502-lines-1k-200d.vec         ivf      500         5.68              0.00           0.00  176.21    0.70  204818.53

# same as above but w 20% buffer instead of 15%
index_name                         index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
---------------------------------  ----------  --------  --------------  --------------------  ------------  
enwiki-20120502-lines-1k-200d.vec         ivf  10000000          207330                282189             0

index_name                         index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
---------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
enwiki-20120502-lines-1k-200d.vec         ivf      500         6.01              0.00           0.00  166.44    0.71  204885.44


# 10m kmeans struc 2 w forming up parents after hkmeans by clustering 2000 fixed parent clusters + relaxing parent score constraint by 10%
total parent centroids: 1835
total child centroids: 39059
total centroids (parent & child) read: 26115
index_name                         index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
---------------------------------  ----------  --------  --------------  --------------------  ------------  
enwiki-20120502-lines-1k-200d.vec         ivf  10000000           87634                391934             0

index_name                         index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
---------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
enwiki-20120502-lines-1k-200d.vec         ivf      500         6.50              0.00           0.00  153.75    0.69  208894.34







# 10m kmeans struc 2 w forming up parents after hkmeans by clustering sqrt(centroids.len) ~194 + relaxing parent score constraint by 20% w cohere wiki 768d instead
index_name                      index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
------------------------------  ----------  --------  --------------  --------------------  ------------  
cohere-wikipedia-docs-768d.vec         ivf  10000000          416613               2647815             0

index_name                      index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall   visited
------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  --------  
cohere-wikipedia-docs-768d.vec         ivf      500         7.26              0.00           0.00  137.74    0.77  99157.07


# main for the same thing as above




# 10m kmeans struc 2 w forming up parents after hkmeans by clustering sqrt(centroids.len) ~194 + relaxing parent score constraint by 20% w cohere wiki 768d instead
index_name                      index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
------------------------------  ----------  --------  --------------  --------------------  ------------  
cohere-wikipedia-docs-768d.vec         ivf   1000000           42735                 64920             0

index_name                      index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
cohere-wikipedia-docs-768d.vec         ivf      500         5.23              0.00           0.00  191.20    0.93  120278.95






# main cohere 1m
index_name                      index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
------------------------------  ----------  --------  --------------  --------------------  ------------  
cohere-wikipedia-docs-768d.vec         ivf   1000000           36089                 70702             0

index_name                      index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
cohere-wikipedia-docs-768d.vec         ivf      500         7.74              0.00           0.00  129.13    0.93  124208.42



# kmeansstruc2 branch cohere 1m w forming up parents after hkmeans by clustering sqrt(centroids.len) + relaxing parent score constraint by 20%
index_name                      index_type  num_docs  index_time(ms)  force_merge_time(ms)  num_segments
------------------------------  ----------  --------  --------------  --------------------  ------------  
cohere-wikipedia-docs-768d.vec         ivf   1000000           30121                 63389             0

index_name                      index_type  n_probe  latency(ms)  net_cpu_time(ms)  avg_cpu_count     QPS  recall    visited
------------------------------  ----------  -------  -----------  ----------------  -------------  ------  ------  ---------  
cohere-wikipedia-docs-768d.vec         ivf      500         5.27              0.00           0.00  189.86    0.93  119665.52

[benwtrent]

we have done a basic two layered approach for now. This will likely evolve, but closing for now.