menemukan rumah dalam radius

10

Selama wawancara saya diminta diberi yang berikut: Aplikasi real estat yang mencantumkan semua rumah yang saat ini ada di pasar (yaitu, untuk dijual) dalam jarak tertentu (misalnya, pengguna ingin menemukan semua rumah dalam jarak 20 mil), bagaimana Anda mendesain aplikasi Anda (baik struktur data dan alogiritma) untuk membangun jenis layanan ini?

Ada ide? Bagaimana Anda mengimplementasikannya? Saya mengatakan kepadanya bahwa saya tidak tahu karena saya belum pernah melakukan hal-hal yang berhubungan dengan geo sebelumnya.

algorithms data-structures geospatial paul smith
sumber

Jawaban:

6

Mereka mungkin setelah jawaban yang menyebutkan pengindeksan spasial , kemungkinan besar dengan memilih database yang menyediakan pengindeksan spasial dari kotak , tetapi Anda mungkin juga mendapatkan beberapa poin dengan menyebutkan itu dapat diimplementasikan dalam aplikasi itu sendiri jika diperlukan misalnya dengan mengimplementasikan R -Tree (mungkin berguna jika pemilihan DB diperbaiki karena alasan lain? Tetapi juga menunjukkan Anda tahu bagaimana database spasial bekerja). Pengindeksan spasial akan memungkinkan Anda untuk dengan cepat mendapatkan subset lokasi yang sesuai di dalam kotak pencarian, Anda dapat memperbaiki ini lebih lanjut dengan menghitung jarak aktual (jika perlu, persegi panjang saja mungkin cukup bagus tentu saja) untuk masing-masing memberikan pencarian yang benar lingkaran / elips

Mengingat jarak yang mungkin 20M atau kurang Anda mungkin OK dengan asumsi bumi datar untuk menghitung jarak meskipun Anda akan mulai melihat kesalahan nyata menuju akhir 20M, jika rentang yang lebih besar diperlukan secara akurat Anda juga perlu mulai melihat model jarak yang lebih baik untuk globe misal jarak Haversine

tentu saja ada banyak sekali detail lain yang bisa dibahas misalnya desain UI, skema DB yang bisa menjadi keseluruhan topik sesuai dengan hak mereka.

jk.
sumber
Pada 20 mil, kesalahan karena model bumi datar akan diabaikan. Lagi pula, ketika pengguna ingin melihat daftar rumah dalam jarak 20 mil dari kantornya, ia tidak peduli jika rumah yang berjarak 20 mil dan 10 yard jauhnya termasuk dalam hasil.
kevin cline
1
memang, dan jika beberapa kesalahan positif tidak penting maka Anda mungkin juga melewatkan perhitungan jarak yang sebenarnya sama sekali dan hanya mengembalikan MBR
jk.
Satu hal yang saya ingin tahu tentang: mengingat banyaknya rumah untuk dijual, apakah perusahaan (seperti Zillo mungkin?) Menyimpan semuanya dalam db dan terus memilih dari itu? Saya membayangkan itu akan menjadi hit kinerja besar dan itu akan jauh lebih cepat untuk menyimpan semuanya dalam memori dengan representasi grafik - mungkin daftar matriks atau kedekatan dan menggunakan algoritma jarak untuk menemukan rumah terdekat. Bagaimana menurut anda?
paul smith
@ paulsmith Saya tidak tahu, tapi saya sangat curiga ada dalam DB spasial, DB spasial mungkin akan menggunakan representasi grafik secara internal (kemungkinan besar R-Tree seperti yang dibahas, tetapi ada pilihan lain) kuncinya sedang mampu memilih hanya item dalam persegi panjang batas minimum di tempat pertama
jk.
8

Setiap kali Anda dihadapkan dengan pertanyaan seperti ini dan Anda tidak memiliki keahlian dalam domain masalah, ada baiknya melakukan beberapa hal.

Pertama-tama akui bahwa Anda tidak memiliki keahlian khusus dalam domain masalah ini.

Kedua , jelaskan bagaimana Anda akan menyelesaikan masalah.

Meskipun saya tidak memiliki pengalaman khusus ketika bekerja dengan pencarian geografis, saya yakin ada algoritma yang terdokumentasi dengan baik dan teknologi yang ada untuk memecahkan masalah. Saya akan mengeksplorasi ini untuk mendapatkan pengetahuan tentang solusi umum yang tersedia bagi saya dan membuat pilihan tentang implementasi berdasarkan persyaratan proyek.

Ketiga , Selalu kurangi masalah seperti ini hingga ke komponen dasarnya. Anda tahu bahwa lokasi pada peta terdistribusi 2 dimensi. Anda tahu bahwa jika Anda diberi x acak, y koordinat jarak ke masing-masing koordinat dari koordinat lain dihitung dengan membentuk segitiga dan menyelesaikan untuk panjang yang tidak diketahui. Mudah-mudahan Anda juga tahu bahwa jika Anda diminta untuk menemukan semua koordinat dalam kotak pembatas, Anda dapat melakukan ini hanya dengan menghitung luasan dari kotak yang ingin Anda temukan dan gunakan sederhana lebih besar dari, kurang dari logika di kedua sumbu.

Terakhir , saya tidak pernah menyewa pengembang yang sepertinya menyerah pada pertanyaan. Jika saya mengajukan pertanyaan dan orang itu berkata "Saya tidak tahu" dan bahkan tidak berusaha memikirkannya secara lisan, itu memberi saya kesan mereka tidak akan berkontribusi pada sesi curah pendapat - yang sangat penting di organisasi yang menulis perangkat lunak .

Ben DeMott
sumber
semua saran bagus
jk.
@Ben, saya pasti setuju dengan semua hal yang Anda sebutkan, namun karena pewawancara dengan jelas mengatakan sebelum sesi dimulai bahwa tidak apa-apa untuk mengatakan Anda tidak tahu, saya hanya mengikuti instruksinya dan mengatakan di muka bahwa saya tidak tahu: )
paul smith
4

Ini mungkin jelas, tetapi untuk banyak aplikasi, solusi lambat si miskin mungkin baik-baik saja.

Memiliki tabel dalam database relasional yang menyimpan garis lintang dan bujur. Permintaan untuk semua lokasi yang memiliki garis lintang dalam 20 mil dan garis bujur dalam 20 mil. Ini memberi Anda persegi panjang pembatas ukuran persegi panjang pembatas terkecil yang berisi jari-jari yang benar-benar ingin Anda cari (dan mengabaikan kelengkungan bumi juga).

Lalu Anda mengambil set yang dikembalikan (oleh kueri menggunakan indeks), dan memfilternya menggunakan perhitungan jarak yang akurat.

Jadi, kinerja tidak efisien, tetapi sangat efisien dalam waktu untuk berkembang. Untuk banyak aplikasi yang mungkin bisa menjadi pilihan yang lebih baik.

psr
sumber
2

Kemungkinan cara termudah adalah dengan menggunakan quadtree untuk menyimpan lokasi rumah Anda, dengan asumsi didistribusikan dalam lanskap 2D. Pencarian harus cukup mudah.

Jika Anda menggunakan RDBMS yang mendukung GIS untuk menyimpan barang-barang Anda, maka Anda benar-benar tidak perlu khawatir tentang itu. Lihat pertanyaan ini untuk beberapa info tentang kinerja pemain utama.

vski
sumber