Perhitungan tetangga terdekat berulang karena jutaan titik data terlalu lambat

Saya memiliki dataset yang mengalir ke jutaan titik data dalam 3D. Untuk perhitungan yang saya lakukan, saya perlu menghitung tetangga (pencarian rentang) untuk setiap titik data dalam radius, mencoba untuk menyesuaikan suatu fungsi, menghitung kesalahan untuk fit, ulangi ini untuk titik data berikutnya dan seterusnya. Kode saya berfungsi dengan baik tetapi butuh waktu sangat lama untuk dijalankan, sekitar 1 detik per titik data! Mungkin karena untuk setiap titik, ia harus mencari di seluruh dataset. Apakah ada cara saya bisa membuat prosesnya cepat. Saya punya ide bahwa jika saya entah bagaimana dapat membangun beberapa hubungan kedekatan antara tetangga pertama, maka ini bisa menjadi lebih lambat. Jika ini membantu, saya mencoba menemukan lebar jendela Parzen optimal dalam 3D.

Saya menyarankan googling untuk membatasi hierarki volume (khususnya pohon BSP). Dengan cloud point Anda, Anda dapat menemukan pesawat yang membaginya menjadi dua subclouds yang sama. Kemudian ketika Anda perlu menemukan kumpulan titik-titik yang berada dalam beberapa jari-jari R dari titik uji, Anda dapat pertama-tama membandingkan titik uji Anda dengan bidang itu, dan jika tingginya di atas itu lebih dari R, maka seluruh subcloud di bawah bidang itu juga harus lebih jauh dari R juga (jadi Anda tidak perlu memeriksa salah satu dari poin-poin itu). Anda dapat menerapkan ide ini secara rekursif juga, pada akhirnya menghasilkan n jenis kompleksitas dan bukannya n-kuadrat. (Ini adalah partisi ruang BSP / biner,

Ada beberapa struktur data untuk menyimpan data yang menyimpan informasi tentang posisi dan kedekatan; di sana dengan memungkinkan penentuan tetangga terdekat yang cepat.

Khususnya R-tree (dan bentuk khusus seperti R * -trees ) dan X-tree . Banyak pilihan yang dioptimalkan untuk penggunaan yang sedikit berbeda.

Memilih R * -tree daripada mencari tetangga terdekat yang naif adalah bagian besar dari saya mendapatkan faktor 10.000 percepatan dari kode tertentu. (OK, mungkin beberapa ratus yang R * -tree, sebagian besar sisanya adalah karena naif melihat-up telah dikodekan buruk sehingga menghancurkan cache. :: mendesah :: )

$O(N \log N)$$N$$O(\log N)$

Ini sangat mirip dengan salah satu tantangan terbesar di bidang dinamika molekuler — menghitung semua interaksi berpasangan antara partikel-partikel yang tidak terikat.

Di sana, kami menggunakan daftar sel (atau daftar tetangga ) untuk membantu kami mencari tahu apa yang terdekat; untuk aplikasi ini, daftar sel mungkin adalah algoritma yang lebih mudah digunakan:

• Bagilah kotak menjadi serangkaian sel.
• Untuk setiap partikel, tentukan sel mana yang harus ditetapkan (O (1) per partikel).
• Kemudian, untuk setiap partikel, periksa sel "milik sendiri" ditambah sel tetangga; jika salah satu dari ini ditempati, maka tidak ada pencarian lebih lanjut diperlukan.
• Jika semua tetangga terdekat kosong, maka perluas ke tetangga terdekat berikutnya, dan seterusnya, hingga sebuah partikel ditemukan.

Jika sistem Anda memiliki distribusi partikel yang kurang lebih seragam, ini akan sangat mengurangi biaya algoritme Anda, sesuai dengan kekasaran grid. Namun, beberapa penyempurnaan diperlukan: kisi terlalu kasar dan Anda tidak akan menghemat banyak waktu; terlalu bagus, dan Anda akan menghabiskan banyak waktu bersepeda di atas sel-sel kotak kosong!

Anda harus memeriksa pohon dan oktri KD yang merupakan metode pilihan untuk set poin (sementara BSP adalah untuk objek umum, dan grid untuk kepadatan yang kurang lebih seragam). Mereka bisa sangat kompak dan cepat, meminimalkan overhead pada memori dan komputasi, dan mudah diimplementasikan.

Ketika poin Anda lebih atau kurang terdistribusi secara seragam (bahkan dengan area kosong, tetapi tidak boleh ada singularitas kepadatan atau konsentrasi tinggi lainnya) periksa paket bola jika Anda ingin mencoba subdivisi ruang non-hierarkis seperti grid.

Anda mungkin harus mempertimbangkan membangun triangulasi Delaunay (well, analog 3D-nya). Dalam 2D, itu adalah triangulasi khusus dari titik data yang selalu berisi tetangga terdekat. Hal yang sama berlaku dalam 3D, tetapi dengan tetrahedra.

$n \log(n)$

Semoga ini bisa membantu!