Report a bug about computing query norm in MIPS mode

[HannanKan]

DiskANN/src/pq_flash_index.cpp

Line 849 in bc39cd0

for (uint32_t i = 0; i < this->data_dim; i++) {

loop condition should be
for (uint32_t i = 0; i < (this->data_dim-1); i++) {
this->data_dim is assigned at

DiskANN/src/pq_flash_index.cpp

Line 619 in bc39cd0

this->data_dim = pq_file_dim;

and pq_file_dim is assigned at

DiskANN/src/pq_flash_index.cpp

Line 608 in bc39cd0

get_bin_metadata(pq_table_bin, pq_file_num_centroids, pq_file_dim);

pq_file_dim is equal to number of dimensions of vectors in index file. However, In MIPS, original vectors are transformed with an additional dimension, which is sqrt(1-||x||/||w||). So vectors in index file are 1 more dimension than original vectors, whose number of dimensions are equal to queries'.

[ShikharJ]

Hannankan (@HannanKan) This is not a bug, when using DiskANN, both the input vectors and query vectors are expected to be of the same dimensionality. So the queries are expected to be padded with zeros for MIPS case.

[HannanKan]

I have a question. In building phase, each of input vectors has d dimensions. How many dimensions should a query have in search phase?

[ShikharJ]

Same as the input vector dimensions. In the regular case, it is just d. In MIPS, both become d+1.

[HannanKan]

Yeah. Both input of building phase and search phase should have same dimensions. But in building phases, input are changed to have an extra dimension. I debug with gdb and find that my query has actually d dimension but following codes read d+1.

DiskANN/src/pq_flash_index.cpp

Line 849 in bc39cd0

for (uint32_t i = 0; i < this->data_dim; i++) {

[ShikharJ]

For MIPS, you'll need to use tests/utils/vector_analysis functionality to convert both input and query files, and then use them while building and searching. Use ./vector_analysis float /path_to_data_file 4 /path_to_converted_data_file.

[HannanKan]

In that case, the README may have to update.

[ShikharJ]

I agree, unfortunately, we're stretched thin at the moment. Thanks for bringing this to our notice, we appreciate it.

[HannanKan]

For MIPS, you'll need to use tests/utils/vector_analysis functionality to convert both input and query files, and then use them while building and searching. Use ./vector_analysis float /path_to_data_file 4 /path_to_converted_data_file.

I just read tests/util/vector_analysis codes. I think it may be used for small data because it load all data from disk into memory in one shot. Apart from that, if I choose mips when building index using ./test/build_disk_index, input will be added an extra coordinate. An alternative way to use diskann without changing codes to use tests/util/vector_analysis is to convert query data.

[ShikharJ]

I see, let's leave this issue open for now.

[JingyuanHe1222]

Hi, as I looked at /src/pq_flash_index.cpp, the cached_beam_search() function seems to handle the extra dimension by 1. normalizing the queries; 2. make the last dimension 0 (the d+1 th dimension). In this case, do we still need to manually prepend an extra dimension and normalize the query vectors?
Thanks in advance!