Temukan kandidat terdekat

Pertanyaan

Bagaimana menemukan kandidat dalam radius tertentu tanpa memeriksa semua titik, dan apa yang terjadi bila titiknya ada di seberang batas sel?

Setelah baca ini, kamu bisa memilih ukuran sel untuk radius tertentu, menyusun query sembilan sel, dan menghitung berapa banyak kandidat yang akan terbaca versus yang benar-benar lolos.

Prasyarat dan contoh

Kamu sudah bisa memilih model jarak dan menyimpan akurasi lokasi (M14.01), paham indeks B-tree (M04), dan tahu bahwa partition key menentukan data mana yang dibaca satu node (M07).

Ada 200.000 driver aktif di Jabodetabek. Pelanggan membuka aplikasi dan butuh driver dalam radius 1 km. Dengan haversine, satu pass terhadap seluruh tabel berarti 200.000 perhitungan per request. Pada 100 request per detik jadi 20 juta perhitungan per detik. Itu jelas boros, dan hampir seluruhnya membandingkan driver di Bekasi dengan pelanggan di Tangerang.

Tujuannya: baca puluhan atau ratusan kandidat, bukan ratusan ribu.

Mekanisme

1. Kenapa indeks (lat, lon) biasa kurang. B-tree gabungan mengurutkan dulu berdasarkan lat, baru lon. Query lat BETWEEN a AND b AND lon BETWEEN c AND d hanya menyempitkan rentang pada lat, lalu memindai semua baris dengan lintang itu dari ujung barat sampai timur kota. Pada koordinat yang sebaran lintangnya rapat (kota), kamu tetap membaca puluhan ribu baris.

2. Ada tiga pendekatan umum.

• Indeks spasial asli (R-tree, GiST di PostGIS, indeks 2dsphere di MongoDB). Menyimpan kotak pembatas bersarang. Cocok untuk data yang jarang berubah dan query bentuk bebas.
• Sel grid sebagai kunci. Ubah lokasi jadi string atau angka sel, lalu cari dengan kesamaan atau prefix. Murah di key-value store dan mudah dipartisi.
• Pemindaian penuh dengan filter kasar. Masih masuk akal di bawah sekitar 10.000 titik.

Di sini kita pakai sel geohash karena paling mudah dilihat. Geohash membagi dunia menjadi persegi panjang dan menamai tiap persegi dengan string base32. Semakin panjang string, semakin kecil selnya:

| Panjang | Lebar × tinggi sel (di khatulistiwa) | | ------- | ------------------------------------ | | 4 | sekitar 39 km × 19.5 km | | 5 | sekitar 4,9 km × 4,9 km | | 6 | sekitar 1,2 km × 0,6 km | | 7 | sekitar 153 m × 153 m |

3. Alur query sel.

1. Hitung geohash titik pelanggan pada panjang tertentu, misalnya 6 karakter.
2. Hitung sel-sel di sekitarnya (delapan tetangga, total sembilan sel).
3. Ambil semua driver dari sel-sel itu lewat key lookup cell_id.
4. Hitung jarak sebenarnya ke tiap kandidat dan buang yang lebih jauh dari radius.
5. Urutkan dan ambil K teratas.

Langkah 3 adalah filter kasar, langkah 4 adalah filter presisi. Keduanya wajib. Sel hanya bilang "mungkin dekat", bukan "dekat".

4. Kenapa tetangga wajib. Pelanggan yang berdiri 20 m dari tepi sel bisa punya driver terdekat di sel sebelah. Query satu sel akan melewatkannya. Contoh nyata dengan panjang 5 di lintang -6,2: dua titik pada lon 106,8749 dan 106,8751 hanya berjarak sekitar 22 m, tapi geohash-nya qqgux dan qquh8. Hanya dua karakter pertama yang sama.

5. Ukuran sel harus mengikuti radius. Sembilan sel menutup radius penuh hanya bila sisi sel terpendek minimal sama dengan radius. Dengan radius 1 km:

• Panjang 6 (tinggi 0,6 km) gagal. Titik di tepi sel bisa punya kandidat dua sel ke atas.
• Panjang 5 (4,9 km) aman. Sembilan sel menutup 14,7 × 14,7 km, jauh lebih luas dari lingkaran 3,14 km². Itu pemborosan, tapi benar.

Saat rancangan ini gagal

• Hanya query sel sendiri. Pelanggan di tepi sel melewatkan driver terdekat. Bug ini hilang di pengujian karena titik uji biasanya berada di tengah sel.
• Sel terlalu besar di area padat. Sel 5 karakter di Sudirman bisa memuat 3.000 driver sekaligus. Kamu membaca ribuan baris untuk menemukan 20.
• Sel terlalu kecil di area sepi. Di pinggiran kota, sel 7 karakter (153 m) kosong. Kamu perlu memperluas cincin berkali-kali, dan tiap perluasan adalah satu round trip.
• Lupa filter presisi. Sel adalah persegi panjang, bukan lingkaran. Sudut kotak 3 × 3 berjarak lebih dari radius, dan memakai isinya mentah-mentah menawarkan driver di luar radius.
• Pemanasan sel. Satu event besar (konser) memadatkan semua lalu lintas ke satu sel dan satu partisi (lihat M07).

Contoh tandingan: untuk 5.000 titik toko yang hampir nggak pernah berubah, indeks GiST di Postgres menjawab ST_DWithin dalam beberapa milidetik dan lebih sedikit bagian yang bergerak daripada membangun sistem sel sendiri.

Latihan

Radius pencarian 2 km. Kepadatan 40 driver per km². Bandingkan dua pilihan:

• A: geohash panjang 5 (sel 4,9 × 4,9 km, 24 km²), query 9 sel.
• B: geohash panjang 6 (sel 1,2 × 0,6 km, 0,74 km²), cincin tetangga sebanyak yang diperlukan agar radius tertutup.

Hitung jumlah sel yang dibaca, jumlah kandidat yang terbaca, jumlah yang benar-benar dalam radius, dan beri rekomendasi.

Lihat pembahasan+

Kandidat yang benar-benar dalam radius: lingkaran π × 2² = 12,6 km², jadi 12,6 × 40 ≈ 503 driver.

A. 9 sel × 24 km² = 216 km², jadi 216 × 40 = 8.640 kandidat. Efisiensi 503 / 8.640 ≈ 5,8%. Hanya 9 key lookup, tapi membaca dan menyaring 8.640 record per request.

B. Sisi terpendek 0,6 km. Agar radius 2 km tertutup dari titik mana pun di dalam sel, perlu ceil(2 / 0,6) = 4 cincin ke arah tinggi. Itu kotak 9 × 9 = 81 sel × 0,74 km² ≈ 60 km², jadi sekitar 2.400 kandidat. Efisiensi sekitar 21%, tapi 81 key lookup.

Rekomendasi: kalau penyimpanan melayani lookup paralel dengan murah (satu round trip batch), pilih B karena membaca empat kali lebih sedikit data. Kalau tiap lookup mahal (round trip terpisah ke partisi berbeda), A lebih sederhana. Dan keduanya bisa dikalahkan oleh panjang 6 dengan cincin dua pada radius 1 km. Jawaban yang bagus menyebut asumsi kepadatan seragam, yang nggak pernah benar di kota.

Terkait

• Sebelumnya: M14.01 Representasikan lokasi.
• Lanjut ke M14.03 Pilih grid spasial, tempat kelemahan geohash di batas sel dibandingkan dengan H3 dan S2.
• Lab L14 dan rancangan D17 belum tersedia.

Catatan

• Asumsi: sebaran driver seragam, sel dihitung di khatulistiwa. Di lintang tinggi lebar sel menyusut.
• Yang nggak dibahas: jarak tempuh jalan, indeks kd-tree, dan kuantisasi lokasi di sisi klien.
• Ukuran sel geohash berasal dari pembagian bit: panjang 5 memakai 13 bit bujur dan 12 bit lintang.
• Terakhir ditinjau: 26 Oktober 2026.