Menemukan pasangan terdekat antara dua set poin di hypercube

Diberikan dua himpunan bagian dari hypercube dimensional (yaitu, M , N ⊆ { 0 , 1 } d ), saya mencari algoritma yang mengambil titik m ∈ M , n ∈ N pada jarak hamming (atau L 1 - jarak pada hypercube) d H ( m , n ) minimal. Algoritma naif yang memeriksa hanya setiap pasangan membutuhkan | M | ⋅ | N | ⋅ $d$$M, N \subseteq \{0,1\}^d$$m\in M, n\in N$$L_1$$d_H(m,n)$$|M|\cdot |N| \cdot d$ waktu, apakah ada hasil yang lebih baik diketahui?

Untuk kesederhanaan kita dapat mengasumsikan bahwa .$|M|=|N|=d$

$|M|=|N|=d$$M$$X$$N$$Y$$Y$$Z=XY$$z_{i,j}$$i$$M$$j$$N$$O(d^{2.3727})$$O(d^{2.3726999999})$

Anda bisa mendapatkan efek yang sama jika matriksnya tidak kotak. Saya pikir Uri Zwick memiliki makalah tentang perkalian matriks cepat dalam kasus ini.

$O(|M| * |N|)$$d$

$L_\infty$$L_m$$L_1$$O(dn \log n)$$d$

[1] Algoritma Optimal untuk Perkiraan Pencarian Tetangga Terdekat dalam Dimensi Tetap Arya et al, 30pp

[2] Tetangga terdekat yang efektif mencari di hyper-cube, dengan aplikasi untuk Cazals pengelompokan molekul