Menggunakan geohash untuk pencarian kedekatan?

Saya mencari untuk mengoptimalkan waktu kedekatan geo titik pencarian.

Input saya adalah lat, titik lng dan saya sedang mencari pada set lokasi yang telah dikomputasi ke n titik terdekat.

Saya tidak peduli berapa banyak waktu / ruang pembangunan indeks prekomputasi lokasi akan mengambil tapi saya peduli pertanyaan akan sangat cepat.

Saya sedang berpikir tentang menggunakan geohash sebagai kunci pencarian, di mana saya pertama kali akan memeriksa apakah saya mendapatkan hasil untuk karakter X kunci dan kemudian terus memangkas karakter dari akhir kunci sampai saya mulai melihat hasil.

Untuk pemahaman saya (sangat jarang untuk saat ini) tentang teknik indeks geo, pendekatan ini harus dapat menghasilkan hasil tercepat (dalam hal waktu permintaan) dibandingkan dengan semua implementasi yang diketahui lainnya (seperti R Tree dan rekan).

Anda pasti bisa. Dan itu bisa sangat cepat. (Bit komputasi intensif juga dapat didistribusikan)

Ada beberapa cara, tetapi satu cara yang telah saya kerjakan adalah dengan menggunakan daftar urutan geohash berbasis integer, dan menemukan semua rentang geohash tetangga terdekat untuk resolusi geohash tertentu (resolusi mendekati distancekriteria Anda ), dan kemudian menanyakan rentang geohash tersebut untuk mendapatkan daftar poin terdekat. Saya menggunakan redis dan nodejs (mis. Javascript) untuk ini. Redis sangat cepat dan dapat mengambil rentang yang dipesan dengan sangat cepat, tetapi itu tidak dapat melakukan banyak hal manipulasi pengindeksan kueri yang dapat dilakukan oleh database SQL.

Metodenya diuraikan di sini: https://github.com/yinqiwen/ardb/wiki/Spatial-Index

Tetapi intinya adalah (untuk memparafrasekan tautannya):

1. Anda menyimpan semua poin geohashed Anda dalam resolusi terbaik yang Anda inginkan (maks biasanya 64bit integer jika itu dapat diakses, atau dalam kasus javascript, 52bits) dalam set yang dipesan (mis. Zset in redis). Sebagian besar pustaka geohash akhir-akhir ini memiliki fungsi bilangan bulat geohash, dan Anda harus menggunakannya sebagai ganti geohash base32 yang lebih umum.
2. Berdasarkan radius yang ingin Anda cari di dalamnya, Anda perlu menemukan kedalaman / resolusi bit yang cocok dengan area pencarian Anda dan ini harus kurang dari atau sama dengan kedalaman bit geohash yang Anda simpan. Situs yang ditautkan memiliki tabel yang menghubungkan kedalaman bit geohash dengan area kotak pembatasnya dalam meter.
3. Kemudian Anda mengulangi koordinat asli Anda pada resolusi yang lebih rendah ini.
4. Pada resolusi yang lebih rendah itu juga menemukan area geohash 8 tetangga (n, ne, e, se, s, sw, w, nw). Alasan mengapa Anda harus melakukan metode tetangga, adalah karena dua koordinat yang hampir tepat di samping satu sama lain dapat memiliki geohash yang sama sekali berbeda, jadi Anda perlu melakukan beberapa rata-rata area yang dicakup oleh pencarian.
5. Setelah Anda mendapatkan semua geohash tetangga pada resolusi yang lebih rendah ini, tambahkan ke daftar geohash koordinat Anda dari langkah 3.
6. Maka Anda perlu membangun rentang nilai geohash untuk mencari di dalamnya yang mencakup 9 area ini. Nilai dari langkah 5 adalah batas rentang bawah Anda, dan jika Anda menambahkan 1 untuk masing-masing, Anda akan mendapatkan batas rentang atas Anda. Jadi Anda harus memiliki array 9 rentang, masing-masing dengan batas bawah dan dan batas geohash atas (total 18 geohash). Geohash ini masih dalam resolusi yang lebih rendah dari langkah 2.
7. Kemudian Anda mengonversi 18 geohash ini ke kedalaman bit / resolusi apa pun yang telah Anda simpan semua geohash di basis data Anda. Secara umum Anda melakukan ini dengan menggeser bit itu ke kedalaman bit yang diinginkan.
8. Sekarang Anda dapat melakukan kueri rentang untuk poin dalam 9 rentang ini dan Anda akan mendapatkan semua poin kira-kira dalam jarak dari titik awal Anda. Tidak akan ada tumpang tindih sehingga Anda tidak perlu melakukan persimpangan, hanya kueri rentang murni, sangat cepat. (mis. dalam redis: ZRANGEBYSCORE zsetname lowerLimit upperLimit, selama 9 rentang yang dihasilkan pada langkah ini)

Anda dapat lebih mengoptimalkan (kecepatan bijaksana) ini dengan:

1. Mengambil 9 rentang dari langkah 6 dan menemukan di mana mereka mengarah satu sama lain. Biasanya Anda dapat mengurangi 9 rentang terpisah menjadi sekitar 4 atau 5 tergantung di mana koordinat Anda. Ini dapat mengurangi setengah waktu permintaan Anda.
2. Setelah Anda memiliki rentang akhir, Anda harus menahannya untuk digunakan kembali. Perhitungan rentang ini dapat menghabiskan sebagian besar waktu pemrosesan, jadi jika koordinat awal Anda tidak banyak berubah tetapi Anda harus membuat kueri jarak yang sama lagi, Anda harus tetap siap alih-alih menghitungnya setiap kali.
3. Jika Anda menggunakan redis, cobalah untuk menggabungkan kueri menjadi MULTI / EXEC sehingga mem-pipeline mereka untuk kinerja yang sedikit lebih baik.
4. Bagian TERBAIK: Anda dapat mendistribusikan langkah 2-7 pada klien alih-alih melakukan perhitungan itu di satu tempat. Ini sangat mengurangi beban CPU dalam situasi di mana jutaan permintaan akan masuk.

Anda selanjutnya dapat meningkatkan akurasi dengan menggunakan fungsi tipe circle distance / haversine pada hasil yang dikembalikan jika Anda sangat peduli dengan presisi.

Berikut teknik serupa menggunakan geohash base32 biasa dan kueri SQL alih-alih redis: https://github.com/davetroy/geohash-js

Saya tidak bermaksud menyambungkan hal saya sendiri, tetapi saya telah menulis modul untuk nodejs & redis yang membuat ini sangat mudah diimplementasikan. Lihat kode jika Anda ingin: https://github.com/arjunmehta/node-georedis

Pertanyaannya bisa dibaca dalam beberapa cara. Saya menafsirkannya berarti Anda memiliki sejumlah besar poin dan Anda berniat untuk menyelidikinya berulang kali dengan titik arbitrer, diberikan sebagai pasangan koordinat, dan berharap untuk mendapatkan n poin terdekat ke penyelidikan, dengan n diperbaiki sebelumnya. (Pada prinsipnya, jika n akan bervariasi, Anda dapat mengatur struktur data untuk setiap kemungkinan n dan memilihnya dalam waktu O (1) dengan setiap probe: ini bisa memakan waktu setup yang sangat lama dan membutuhkan banyak RAM, tetapi kami diberitahu untuk mengabaikan masalah tersebut.)

Buatlah diagram urutan-n Voronoi dari semua poin. Ini mempartisi pesawat menjadi wilayah yang terhubung, yang masing-masing memiliki n tetangga yang sama. Ini mengurangi situasi menjadi masalah point-in-polygon, yang memiliki banyak solusi efisien.

Menggunakan struktur data vektor untuk diagram Voronoi, pencarian titik-dalam-poligon akan memakan waktu O (log (n)) waktu. Untuk tujuan praktis, Anda dapat membuat O (1) ini dengan koefisien implisit yang sangat kecil hanya dengan membuat versi diagram raster. Nilai sel dalam raster dapat berupa (i) penunjuk ke daftar n titik terdekat atau (ii) indikasi bahwa sel ini mengangkangi dua atau lebih daerah dalam diagram. Tes untuk titik arbitrer di (x, y) menjadi:

Fetch the cell value for (x,y).
If the value is a list of points, return it.
Else apply a vector point-in-polygon algorithm to (x,y).

Untuk mencapai kinerja O (1), mesh raster harus cukup baik sehingga titik probe yang relatif sedikit akan jatuh dalam sel yang mengangkangi beberapa wilayah Voronoi. Ini selalu dapat dicapai, dengan potensi biaya yang besar dalam penyimpanan untuk grid.

Saya menggunakan geohash untuk hal ini. Alasan saya adalah karena saya perlu menerapkan pencarian kedekatan menggunakan sistem informasi gaya piramida .. di mana geohash dengan tingkat presisi 8 adalah 'basis' dan membentuk total baru untuk geohash dari ketepatan ke-7 .. dan seterusnya dan seterusnya . Total ini adalah area, jenis penutup tanah, dll. Itu adalah cara yang sangat mewah untuk melakukan beberapa hal yang sangat mewah.

Jadi geohash level 8 akan berisi informasi seperti:

jenis: rumput acre: 1.23

dan 7, 6 .. dll. akan berisi informasi seperti:

grass_types: 123 acre: 6502

Ini selalu dibangun dari presisi terendah. Ini memungkinkan saya untuk melakukan segala macam statistik yang menyenangkan dengan sangat cepat. Saya juga dapat menetapkan referensi geometri untuk setiap referensi geohash menggunakan GeoJSON.

Saya dapat menulis beberapa fungsi untuk menemukan geohash terbesar yang membentuk viewport saya saat ini dan kemudian menggunakannya untuk menemukan geohash dengan presisi terbesar kedua di dalam viewport. Ini dapat dengan mudah diperluas ke kueri rentang terindeks di mana saya akan meminta minimum '86ssaaaa' dan maksimum '86sszzzz' untuk presisi apa pun yang saya inginkan.

Saya melakukan ini menggunakan MongoDB.

Memperbarui untuk tahun 2018-an, dan beberapa dana matematika atau sumber bersejarah Geohash:

• inspirasi untuk Geohash adalah interlave sederhana dari angka-angka biner , mungkin suatu optimasi dari algoritma naif yang interleave digit desimal, seperti dari C-square .

• pertautan biner menghasilkan strategi indeks kurva Z-order secara alami, penemu Geohash tidak mulai "mencari kurva fraktal terbaik" ... Tapi yang pasti, optimasi desain ini, kurva fraktal yang lebih baik, dimungkinkan (!).

Gunakan Perpustakaan Geometri S2

Pendekatan S2-geometri lebih baik daripada Geohash karena menggunakan topologi bola dunia (kubus), gunakan proyeksi opsional (jadi semua sel memiliki bentuk yang hampir sama dan dekat), dan karena pengindeksan dengan kurva Hilbert lebih baik daripada Z- urutan-kurva :

... kita bisa melakukan yang lebih baik ... Ketidaksinambungan saat kita bergerak dari kanan atas ke quad kiri menghasilkan kita harus membagi beberapa rentang yang seharusnya bisa kita buat bersebelahan. (...) kita dapat sepenuhnya menghilangkan diskontinuitas (...)
blog.notdot.net/2009 tentang pengindeksan spasial dengan Quadtrees dan Hilbert Curves

Sekarang ini adalah perpustakaan yang gratis dan efisien, lihat https://s2geometry.io

PS: ada juga versi disederhanakan yang tidak resmi (baik) seperti NodeJSs2-geometry , dan banyak "taman bermain", tambahan dan demo, seperti s2.sidewalklabs.com .

Saya akan merekomendasikan menggunakan kueri GEORADIUS di redis.

Dorong data yang terbagi-bagi oleh level geohash yang paling cocok menggunakan panggilan GEOADD.

Juga, lihat ini -> ProximityHash .

ProximityHash menghasilkan satu set geohash yang mencakup area melingkar, mengingat koordinat pusat dan radius. Ia juga memiliki opsi tambahan untuk menggunakan GeoRaptor yang menciptakan kombinasi geohash terbaik di berbagai tingkatan untuk mewakili lingkaran, mulai dari tingkat tertinggi dan iterasi hingga campuran optimal diseduh. Akurasi hasil tetap sama dengan tingkat geohash awal, tetapi ukuran data berkurang secara signifikan, sehingga meningkatkan kecepatan dan kinerja.