Apakah ada cara saya bisa menggunakan toko Key-Value untuk data geospasial?

26

Saya telah menggunakan banyak basis data relasional di masa lalu, tetapi saya juga telah membaca tentang semua basis data NoSQL, dan toko-toko Key-Value terlihat menarik.

Ketika saya menyimpan objek geometri, saya kebanyakan menggunakan lima kolom indeks, MIN_X, MAX_X, MIN_Y dan MAX_Y (di mana X dan Y berada dalam proyeksi peta). Saya tidak perlu indeks pada data saya yang lain.

Saya membutuhkan nilai X dan Y untuk mencari objek di tempat yang ditentukan (map rectangle), dan saya membutuhkan nilai ID jika saya ingin memperbarui objek yang ditentukan.

Apakah ada cara saya bisa menggunakan toko Key-Value untuk ini?

database key-value-store nosql Jonas
sumber

Jawaban:

18

Kami menggunakan Google AppEngine untuk menjalankan kueri spasial / atribut dan masalah utama (dari hari pertama) adalah bagaimana mengindeks kumpulan garis / poligon berukuran besar secara sewenang-wenang. Data titik tidak terlalu sulit (lihat geohash, geomodel dll) tetapi kumpulan poligon kecil / besar yang dikelompokkan secara acak selalu menjadi masalah (dan dalam beberapa kasus, masih)

Saya sudah mencoba beberapa versi pengindeksan spasial yang berbeda pada GAE tetapi kebanyakan hanya dua varian di bawah ini. Tidak ada yang secepat database SQL dan semua memiliki pro / kontra. pengorbanan tampaknya masuk akal untuk sebagian besar aplikasi pemetaan berbasis internet sekalipun. Juga, dua di bawah ini perlu digabungkan dengan penyisihan geometri dalam memori (melalui JTS dll) untuk menghapus semua fitur yang tidak sesuai dengan parameter pencarian akhir. dan akhirnya, mereka bergantung pada fitur-fitur spesifik GAE tapi saya yakin itu bisa diterapkan ke arsitektur lain (atau menggunakan TyphoonAE untuk berjalan di cluster linux, EC2 dll)

Kisi - Kemas semua fitur untuk area tertentu ke dalam indeks kisi yang dikenal. Tempatkan indeks spasial kecil di grid sehingga Anda dengan cepat menavigasi set fitur yang dikandungnya. Untuk sebagian besar kueri, Anda hanya perlu menarik beberapa kisi yang cepat, karena Anda tahu konvensi penamaan kisi yang tepat dan bagaimana kaitannya dengan entitas K / V (mendapat, bukan kueri)

Pro - cukup cepat, mudah diimplementasikan, tanpa jejak memori.

Kontra - preproses diperlukan, pengguna perlu menentukan ukuran kisi, geom besar dibagikan pada beberapa kisi, pengelompokan dapat menyebabkan kisi menjadi kelebihan beban, biaya serialisasi / deserialisasi dapat menjadi masalah (bahkan ketika dikompresi melalui buffer protokol)

QuadKeys - Ini adalah implementasi saat ini. pada dasarnya sama dengan Grids kecuali tidak ada set level grid. ketika fitur ditambahkan, mereka diindeks oleh kisi-kisi kunci yang benar-benar berisi batas-batasnya (atau dalam beberapa kasus, dibagi menjadi dua ketika kunci tunggal tidak dapat digunakan, pikirkan dateline). Setelah qk ditemukan, maka dipecah menjadi jumlah maksimum qk yang lebih kecil yang memberikan representasi butir yang lebih baik dari fitur tersebut. pointer / bbox ke fitur tersebut kemudian dimasukkan ke dalam gridindex ringan (sekelompok fitur) yang dapat ditanyakan (desain asli menanyakan fitur secara langsung tetapi ini terbukti terlalu lambat / intensif CPU dalam kasus di mana hasilnya besar)

Quadline Polyline http://www.arc2earth.com/images/help/GAE_QKS_1.png Polygon Quadkeys http://www.arc2earth.com/images/help/GAE_QKS_2.png

Konvensi penamaan quadkey yang digunakan di atas sudah terkenal dan yang lebih penting, cenderung melestarikan lokalitas (dijelaskan lebih lanjut di sini )

Poligon di atas terlihat seperti ini: 0320101013123 03201010131212 03201010131213 0320101013133 0320101013133 03201010131302 03201010131303 032010101313002 032010101313003 0320101010131310

jika batas kueri cukup kecil, Anda dapat langsung mengambil melalui qk. ini optimal karena hanya satu, panggilan rpc batch ke datatore GAE. jika batasnya cukup besar sehingga mencakup terlalu banyak qks yang mungkin (> 1000) maka Anda dapat melakukan kueri menggunakan filter (mis: qk> = 0320101013 dan qk <= 0320101013 + \ ufffd). Konvensi penamaan quadkey plus cara GAE indexes strings memungkinkan kueri di atas untuk mengambil hanya grid yang ada yang jatuh di bawah nilai qk itu.

ada peringatan dan masalah perf lainnya tetapi secara umum, kemampuannya untuk query pada quadkey yang membuatnya layak

contoh - permintaan di negara bagian AS: geojson

Pro - cukup cepat, tidak ada konfigurasi ukuran grid, tidak ada jejak memori, tidak ada grid yang penuh sesak

Cons - preprocessing diperlukan, kemungkinan overfetch dalam beberapa skenario, tidak ada data polar

Space Filling Curves - Lihatlah pembahasan Alfred's NextGen Queries di Google I / O tahun ini. Dimasukkannya kurva pengisian ruang / waktu umum bersama dengan operator MultiQuery baru (berjalan secara paralel) akan memungkinkan untuk beberapa pertanyaan spasial yang sangat keren. Apakah akan mengalahkan kinerja SQL tradisional? Sulit dikatakan tetapi harus skala dengan sangat baik. Dan kami dengan cepat mendekati masa depan di mana perangkat seluler yang selalu ada dalam segala bentuk / ukuran akan secara dramatis meningkatkan lalu lintas ke situs / layanan Anda.

akhirnya, saya juga setuju bahwa Anda harus melihat dengan cermat domain masalah Anda sebelum memilih NoSQL di atas SQL. Dalam kasus kami, saya benar-benar menyukai model penetapan harga GAE sehingga benar-benar tidak ada pilihan tetapi jika Anda tidak perlu mengukur, menghemat waktu dan hanya menggunakan standar sql db

b Banjir
sumber
Anda menyebutkan GAE, tetapi basis data apa yang Anda gunakan? Ada beberapa: cloud.google.com/products/storage
Don McCurdy
11

Saya telah mendengar tentang GeoCouch, yang merupakan implementasi CouchDB untuk data berbasis lokasi. Dan saya juga berpikir bahwa MongoDB memiliki kemampuan pengindeksan geospasial.

JoshFinnie
sumber
Ya, mereka berdua melakukannya, dan SimpleGeo sedang membangun ekstensi spasial untuk Cassandra. Saya belum pernah mendengar apa pun di Voldemort atau MemCache
TheSteve0
Oh, aku suka apa yang dilakukan SimpleGeo. Saya cemburu dan ingin bekerja untuk mereka!
JoshFinnie
8

Ini terutama pertanyaan tentang algoritma. Stack Overflow juga bisa menjadi tempat yang baik untuk bertanya.

Bagaimanapun, jawaban untuk pertanyaan langsung Anda adalah "ya, Anda dapat menggunakan toko kvp untuk mewakili data spasial." Pertanyaan yang lebih baik, namun mungkin "HARUS saya menggunakan toko kvp untuk mewakili data spasial?"

Jawaban untuk pertanyaan itu (seperti banyak yang lain) adalah, "tergantung" Itu tergantung pada skala Anda, beban kerja (transaksional) Anda, sifat data, dan infrastruktur komputasi yang Anda miliki.

Toko kvp akan memiliki overhead rendah, yang dapat membantu meningkatkan throughput untuk volume tinggi memasukkan dan memperbarui paralelisme. Namun itu tidak akan menjadi pencarian pencarian spasial yang sangat cepat (temukan semua objek dalam persegi panjang). Untuk itu Anda ingin indeks spasial, seperti R-Tree.

Namun, jika Anda memiliki volume data yang sangat besar, dan sekelompok besar komputer, maka menggunakan indeks kvp dapat memberikan beberapa manfaat perormance. Satu-satunya cara untuk benar-benar tahu pasti adalah dengan melakukan pengukuran menggunakan data aktual dan mengakses pola yang Anda harapkan akan temui.

Perbarui :

Ini sedikit info lebih lanjut. Anda dapat menggunakan toko KVP untuk melakukan pencarian spasial. Masalahnya adalah lambat. Untuk mengetahui alasannya, pertimbangkan sesuatu seperti ini:

  ***********
  ***********
  ***********
  ***********
  ****###****
  ****###****
  ****###****
  ***********
  ***********
  ***********
  ***********

Di mana * dan # mewakili objek, diletakkan dalam kisi 11x11, dengan asal di sudut kiri atas. Bayangkan mencari objek dalam persegi panjang (4,4) - (7,7). Itu seharusnya menemukan semua "#". Dengan asumsi bahwa Anda menggunakan b + -tree untuk mewakili indeks Anda di toko KVP, Anda bisa menemukan hasilnya menggunakan indeks "X" atau indeks "Y". Dalam hal ini, tidak masalah yang mana. Demi diskusi, saya akan menggunakan indeks x. Anda akan melakukan pencarian log (n) dalam indeks X untuk menemukan simpul pertama dengan nilai X "4" dan kemudian beralih melalui simpul daun b + -tree sampai Anda menemukan sebuah simpul dengan nilai lebih dari 7. Ketika Anda iterate melalui indeks x Anda kemudian akan menolak apa pun yang berada di luar rentang y yang diinginkan.

Ini lambat. Bayangkan pada grid besar, dengan kepadatan yang sama, katakan 100 K * 100 K. Di sana Anda akhirnya harus memindai entri indeks "300, 000" untuk menemukan hanya 9 catatan. Namun, jika Anda menggunakan R-Tree yang seimbang dengan benar, maka pencarian indeks mungkin hanya perlu memindai sekitar 90 catatan atau lebih. Itu perbedaan besar.

Masalahnya, bagaimanapun, menjaga keseimbangan R-Tree itu mahal. Inilah sebabnya mengapa jawabannya adalah "itu tergantung", dan mengapa pertanyaan "harus saya lakukan ini" jauh lebih penting daripada "bagaimana saya melakukannya".

Jika Anda sering menyisipkan dan menghapus catatan, dan sebagian besar melakukan pencarian "ID objek", dan tidak sering melakukan pencarian "spasial", maka menggunakan indeks KVP Anda akan memberi Anda kinerja yang lebih baik untuk apa yang sebenarnya ingin Anda gunakan sistem untuk . Namun, jika Anda jarang memasukkan atau menghapus, tetapi sering melakukan pencarian spasial, maka Anda ingin menggunakan R-Tree.

Scott Wisniewski
sumber
Saya tidak akan menerima jawaban seperti "ya, Anda bisa." karena saya ingin tahu BAGAIMANA . Dan "HARUS SAYA .." bukan pertanyaan yang lebih baik, karena seperti yang Anda katakan "itu tergantung".
Jonas
1
Aku tidak setuju denganmu. Jika Anda ingin membangun sistem yang bermanfaat, atau meninggalkan referensi yang bermanfaat di internet untuk orang lain yang membangun sistem serupa, maka "haruskah saya" jauh lebih penting daripada "bagaimana". Demi membantu, bagaimanapun, saya memang mengedit jawaban saya agar Anda memberikan beberapa informasi tentang caranya.
Scott Wisniewski
@Jonas Saya percaya jawaban "saran" yang Anda dapatkan adalah karena cara Anda mengajukan pertanyaan: "tetapi saya juga telah membaca tentang semua basis data NoSQL, dan toko-toko Key-Value terlihat menarik." Ini memiliki semua keunggulan dari solusi yang mencari masalah.
JasonBirch
NoSQL memang memecahkan masalah, tetapi ini adalah masalah yang praktis tidak ada yang punya karena mereka tidak bekerja pada skala yang cukup besar. Sayangnya itu selalu baik untuk berpikir bahwa sistem kita sendiri lebih besar dalam skema besar hal daripada yang sebenarnya. :)
JamesRyan
1

Dalam sebagian besar kasus, Anda akan mendapatkan lebih banyak utilitas dari penyimpanan data relasional daripada Anda akan dari penyimpanan kunci / nilai atau kunci / nilai / jenis. Ada kompleksitas yang cukup besar seputar permintaan dan pelaporan yang efisien tentang skema data semacam ini.

Saran saya adalah mengevaluasi dengan cermat apakah skala Anda sebenarnya membutuhkan NoSQL sebelum mempertimbangkan cara menggunakannya.

JasonBirch
sumber
1
Berikut adalah contoh masalah yang mungkin Anda miliki (dan solusi untuknya) jika Anda perlu menghitung apakah suatu titik ada di dalam atau di luar geometri. code.google.com/p/giscloud/wiki/SerializedSpatialIndexes
Jon Bringhurst
Hei @ Jon, itu akan lebih baik ditambahkan sebagai Jawaban. Dengan begitu ia bisa berdiri sendiri, dan Anda akan mendapatkan kredit untuk itu jika orang berpikir itu pantas!
JasonBirch