faiss MetricType support L1 distance or fractional distance metric Lp(p=0.5) ?

[hudengjunai]

Hi,I am using faiss lib,it is very efficency and smart. But recently I have read a paper :when is 'neareast neighbor' meaningful? ", this paper indicates that when dimension of the vector is high,Dmax-Dmin of L2 distance is small.just as noted in this paper, the paper url is : https://www.researchgate.net/profile/Jonathan_Goldstein4/publication/2845566_When_Is_Nearest_Neighbor_Meaningful/links/09e4150b3eb298bf21000000/When-Is-Nearest-Neighbor-Meaningful.pdf annot get in ,just google 'When is neareast Neighbor meaningful filetype:pdf",you can see this paper.
http://users.informatik.uni-halle.de/~hinnebur/PS_Files/icdt2001b.pdf

so my question is:"Apart from current L2_distance and inner_product MetricType, Is there any plan to add L1 distance metrictype to faiss lib,or fractional distance metric Lp(p=0.5)?"

[jegou]

Dear @hudengjunai , I know very well this paper. Why do you mention L1 ? This distance has exactly the same problem of dimensionality curse as the L2 distance, in high-dimensional spaces, and the same for the practical meaningfulness (to be clear: not the meaningfulness you mention, which IMHO is far from what we expect for kNN).

L1 is not included because we have no use-case where it is currently better than Cosine or Euclidean. The meaningfulness you mention does not necessarily translate to better retrieval in practice.

[mdouze]

See also issue #12

[hudengjunai]

Thank you very much, @jegou ,I will be appreciate if you read this paper.https://link.springer.com/chapter/10.1007/978-3-540-31865-1_32.
This paper indicates that fractional distance metric Lp(p=0.5,eg) would improve retrieval performance (use label data, mAP as practical meaningful evaluation) in nearly all circumstances and visual features like HSV,Gabor.I am wandering if this is true.
So,I have two questions:
1.Do you have any use-case experiment use Lp(p=0.5) fractional distance metrictype ?
2.I use faiss for image retrieval.the datasets vector dimension=2048(deep descriptor from CNN),and N=80million. currently I use faiss.MultiIndexQuantizer(2048,2,8) as coarsequantizer, and use IVFPQ(nlist=2**(2*8),m=256,nbit=8) as residual quantizer. Can you give me some advice if the parameter can be optimized?
Also thanks @mdouze for mentioned #12.

[mdouze]

No activity, closing.

[1049451037]

Hi @jegou , I think L1 is mathematically different from L2. Although there are not enough use-cases for now, no one can say for the future. Besides, if L1 is supported, researchers can try whether it is better than L2.

[jegou]

Hi @jegou , I think L1 is mathematically different from L2.

yes, we agree on that (I never said the contrary).

Besides, if L1 is supported, researchers can try whether it is better than L2.

You don't need to have a fully-optimized L1 GPU kernel to validate the fact that a metric is better or worse than another. Before investing in that direction, we need good reasons. Currently we don't have sufficient reasons to prioritize this feature.

[1049451037]

Oh, I get it. Thank you! @jegou

[Filco306]

Hello,

Is the L1-distance supported in faiss currently?

Thanks :)