algoritma Cara menemukan POI terdekat dengan 1 juta koordinat secara efisien

Ini adalah pasca wawancara di mana saya diminta untuk menerapkan ini--

Jadi saya diberikan daftar POI restoran (sekitar 2000 di antaranya) dalam koordinat Euclidean

Saya kemudian diberikan daftar koordinat pengguna (1 juta di antaranya)

Saya ditugaskan untuk mengembalikan berapa banyak pengguna yang berada dalam radius tertentu (10,15) dari satu POI, dan kedua, radius yang diperlukan agar 75% pengguna berada dalam jarak POI.

Jarak adalah sesuatu yang bisa saya hitung, tapi memaksanya berarti memeriksa 1 juta koordinat untuk 1000 koordinat, yang memakan waktu sangat lama.

Apa cara yang lebih efisien untuk melakukan ini?


java geocoding algorithm
person user3394313    schedule 30.10.2017    source sumber
comment
Banyak cara untuk melakukannya, tetapi pada dasarnya Anda harus membagi ruang menjadi bagian-bagian yang layak untuk dicari, dan bagian-bagian yang tidak layak untuk dicari.   -  person Andy Turner    schedule 31.10.2017
comment
Anda mungkin ingin mencari 'struktur data spasial', terutama R-tree.   -  person Ivan Smirnov    schedule 31.10.2017
comment
Untuk masalah pertama: Pengurangan Peta bisa menjadi cara lain (memonopoli sumber daya). Untuk masalah kedua: Kelompokkan titik-titiknya lalu hitung POI yang paling dekat dengan pengguna. Kemudian tingkatkan radiusnya hingga mencakup 75% jarak user_poi tersebut.   -  person displayName    schedule 01.11.2017

Jawaban (2)


arrow_upward
1
arrow_downward

Lebih baik menggunakan kerangka kerja yang memungkinkan Anda mengindeks koordinat secara spasial dan menjalankan operator spasial yang efisien. Mapinfo, database spasial (Oracle Spatial - yang mungkin memerlukan lisensi tambahan untuk penggunaan produksi), ESRI, open source, dll.

Biasanya tindakan akan dilakukan

  1. memuat POI dalam wadah yang diindeks secara spasial (Tabel dengan indeks spasial).
  2. Muat pengguna dalam wadah yang diindeks secara spasial
  3. memperluas POI sebagai objek melingkar dengan radius jarak yang diperlukan.
  4. Gabung/gabungkan secara spasial untuk pengguna dalam lingkaran POI

Gabungan/penggabung spasial tersebut tersedia dalam berbagai jenis operator spasial.

Jika Anda hanya ingin memperoleh hasil sebagai bagian dari latihan, dan Anda tidak dapat menggunakan kerangka kerja apa pun, saya sarankan untuk mengambil beberapa pendekatan sederhana.

1 juta pengguna sebenarnya tidak terlalu besar - hal ini dapat dikelola - masalahnya adalah poin-poin ini harus dievaluasi terhadap 2000 POI. Saya yakin cara terbaik adalah melakukannya

  1. buat kotak pembatas terlebih dahulu di sekitar POI menggunakan radius 2 x sebagai sisinya.
  2. Hal ini akan memungkinkan Anda dengan cepat mengevaluasi poin mana yang menarik bagi setiap POI. Pada prinsipnya hanya lebih besar dari, kurang dari yang akan digunakan sebagai operator.
  3. Dengan memiliki sekumpulan pengguna untuk setiap POI, Anda dapat mempersempitnya lebih lanjut dengan melakukan penghitungan jarak sebenarnya.

Anda dapat memanfaatkan semua jenis pengindeksan dan penyortiran cerdas agar prosesnya berjalan lebih cepat. R-Tree yang disarankan dalam komentar tampaknya sangat cocok jika Anda punya waktu untuk menerapkannya. Ini akan membantu Anda pada langkah kedua di atas.

Pendekatan yang lebih sederhana - bergantung pada bagaimana koordinat Anda ditata (seperti apa dunia Anda), adalah dengan membagi dunia Anda dalam kotak yang lebih besar, dan terlebih dahulu menentukan untuk setiap pengguna dan setiap POI di kotak mana mereka berada. Anda dapat dengan cepat menentukan semua pengguna dalam kotak POI yang sama, atau kotak tetangga mana pun sebagai pengguna yang diminati. Buatlah skema pengindeksan/penomoran cerdas yang dapat membantu Anda mengidentifikasi tetangga juga. Minta daftar pengguna diindeks ke kotak mereka melalui Hashmaps.

person YoYo    schedule 30.10.2017
comment
Maaf atas kendala tambahannya, saya tidak diperbolehkan menggunakan framework luar yang sudah dibuat - person user3394313; 31.10.2017

arrow_upward
0
arrow_downward

Gunakan struktur data atau database pencarian spasial dan buat kueri yang sesuai.

Agar radius mencakup 75% pengguna, Anda selalu dapat mencari jari-jari biner menggunakan jumlah total pengguna yang diketahui dan koordinat terluar.

person sleeplessnerd    schedule 30.10.2017