Memahami penyimpanan lokasi dan algoritma kueri?

9

Salah satu aspek terpenting dari basis data yang dilengkapi GIS adalah bahwa ia menyediakan kemampuan kepada pengguna untuk dengan cepat menanyakan semua poin dalam beberapa area geografis yang sewenang-wenang yang cocok dengan beberapa kriteria tambahan. (Misalnya "Temukan saya 3 restoran terdekat ke titik ini di peta.")

Adakah yang bisa mengarahkan saya ke diskusi teoritis tentang algoritma yang terlibat? Saya ingin belajar cara kerjanya.

Pada akhirnya, saya ingin menerapkan kemampuan yang sama untuk set data numerik yang digeneralisasi - awan besar titik dalam ruang n-dimensional, non-euclidean yang sewenang-wenang. Misalnya, wajah seseorang dapat dicirikan sebagai vektor angka: [jarak antara mata, jarak dari mata ke mulut, lebar wajah, panjang wajah, dll]. Saya ingin memfilmkan lalu lintas trotoar, memperkirakan fitur wajah setiap orang, dan kemudian dapat membuat pertanyaan ke data nanti seperti "mengingat wajah orang ini, temukan saya 100 wajah yang paling mirip."

Apakah saat ini ada perangkat lunak yang ada yang menyediakan kemampuan untuk mencari ruang-ruang umum ini?

John Berryman
sumber

Jawaban:

4

Akun algoritma yang baik dalam dimensi 2 dan 3 muncul dalam teks klasik oleh Preparata & Shamo . Algoritma yang digunakan dalam GIS adalah spesialisasi Hanan Samet , yang telah menerbitkan beberapa buku tentang masalah ini.

Pencarian berdimensi tinggi biasanya dibantu atau dipercepat dengan cara penambangan data awal, pengelompokan, atau teknik pengurangan dimensi. Ini lebih merupakan masalah analisis data dan statistik, bukan GIS, yang pada dasarnya berfokus pada pencarian dalam satu hingga empat dimensi Euclidean. Untuk informasi lebih lanjut, cari situs adik kami stats.stackexchange.com untuk kemungkinan istilah seperti pengelompokan , pengurangan dimensi , dan penskalaan multidimensi dan untuk yang kurang jelas seperti pca (analisis komponen utama) dan svm (mesin pendukung vektor). Itu juga tempat yang bagus untuk bertanya tentang perangkat lunak yang ada.

whuber
sumber
4

Jawaban klasik (paleogeografer) adalah dengan menggunakan pohon KD untuk menyimpan data di (lihat http://en.wikipedia.org/wiki/Kd-tree ). Ini bekerja dengan membagi dua data menjadi dua bagian di setiap dimensi secara bergantian saat Anda bergerak turun pohon. Keuntungan dari mereka adalah bahwa ketika Anda menemukan barang terdekat Anda juga dapat membuat daftar barang terdekat saat Anda pergi tanpa biaya tambahan, jadi menjawab apa tiga restoran terdekat semudah menemukan yang terdekat.

Saya membaca di suatu tempat bahwa eHarmony menggunakan pohon KD untuk menemukan "kecocokan yang kompatibel" dalam 14 dimensi.

Ian Turton
sumber
+1 Deskripsi singkat yang jelas tentang metode pencarian yang efisien dilakukan dengan baik.
whuber
2

Saya pernah mendengar bahwa Netezza telah mengimplementasikan beberapa algoritma pemrosesan paralel paralel spasial yang inovatif . Whitepaper ada di sini .

Arsitektur Pengolahan Parsi Asimetris Massively Netezza memberikan kombinasi terbaik dari multiprosesor simetris (SMP) dan pemrosesan paralel masif (MPP), memfasilitasi terascale, pemrosesan query kompleks baik data spasial dan non-spasial tanpa kompleksitas, penyetelan, dan agregasi yang diperlukan dalam sistem tradisional.

Memperbarui

Saya lupa menyebutkan bahwa Netezza sangat memanfaatkan Bayes Theorem . Berikut kumpulan video di sini .

Kirk Kuykendall
sumber