Menerapkan algoritma pada data besar

8

Apakah ada buku atau tutorial yang mengajarkan kita cara efisien menerapkan algoritma umum (pengurutan, pencarian, dll.) Pada data besar (yaitu data yang tidak dapat sepenuhnya dimuat ke dalam memori utama) dan bagaimana cara efisien menerapkan algoritma tersebut dengan mempertimbangkan biaya memblokir transfer dari memori eksternal? Sebagai contoh, hampir semua buku teks algoritma mengatakan bahwa B dan B + -trees dapat digunakan untuk menyimpan data pada disk. Namun, sebenarnya bagaimana hal ini dapat dilakukan, terutama menangani pointer di mana data ada pada disk tidak dijelaskan. Demikian pula, meskipun banyak buku mengajarkan teknik pencarian, mereka tidak menganggap data ada dalam memori sekunder.

Saya telah memeriksa buku Knuth. Meskipun membahas ide-ide ini, saya masih tidak mengerti bagaimana cara menerapkannya dalam bahasa tingkat tinggi. Apakah ada referensi yang membahas perincian ini?

algorithms efficiency memory-management big-data Arani
sumber
1
Lihat "Menambang Kumpulan Data Masif" .
Dave Clarke
Anda dapat melihat bibliografi komprehensif STXXL: perpustakaan templat standar untuk kumpulan data XXL .
Vor
Hari ini dengan memiliki DB hebat seperti Oracle, DB2, SQL Server, biasanya tidak ada yang bekerja dengan dataset besar sendiri, jika Anda tertarik, Anda dapat melihat dokumen terkait ke salah satu Server DB, tetapi hari ini Martin Fowler dan beberapa orang lain mencoba untuk pindah ke NO SQL , Anda juga bisa memeriksanya. (tetapi ada terlalu banyak aspek dalam database besar, seperti konkurensi, keamanan, ... bukan hanya algoritma cepat).
@ Dave, Vor: Terima kasih atas referensi Anda. Saya akan memeriksa mereka dan memberi tahu Anda apakah itu yang saya cari.
Arani
@ SaeedAmiri: Saya mengerti itu, tetapi dari apa yang saya mengerti, menyimpan data dalam database hanya berguna jika data tersebut sangat terstruktur dalam beberapa cara. Jadi, urutan angka dan data serupa lainnya umumnya tidak disimpan menggunakan basis data. Selain itu, buku teks basis data tidak menjelaskan secara rinci dari sudut pandang pengembang basis data. Sementara sebagian besar dari mereka menyebutkan bahwa basis data menggunakan B dan B + -tree, sebagian besar tidak menggambarkan sebenarnya BAGAIMANA mereka mengimplementasikan struktur data ini.
Arani

Jawaban:

2

Buku-buku basis data adalah contoh yang bagus. Namun, lihatlah pada bidang I / O struktur data yang efisien (dan algoritma). Setahu saya, ada beberapa kursus tentang topik ini, tetapi sangat sedikit buku.

Periksa buku ini: U. Meyer, P. Sanders, dan J. Sibeyn (eds.), Algoritma untuk Hirarki Memori, Catatan Kuliah dalam Ilmu Komputer 2625, Springer, 2003.

Lihat kursus-kursus ini: http://www.win.tue.nl/~hermanh/teaching/2IL35/ http://www.daimi.au.dk/~large/ioS12/

dan slide ini: algo2.iti.kit.edu/sanders/courses/algen09-10/rdslides.pdf

Dipotong
sumber
1

Buku basis data Ramkrishnan dan Gehrke membahas hal-hal ini secara terperinci.

Arani
sumber
Yang terburuk dan paling membosankan yang pernah ada :)! meskipun itu adalah pengantar yang bagus untuk banyak topik menarik dalam database dan optimasi db.
AJed
0

Saat ini bidang ini dikenal sebagai data besar , dan berkembang sangat cepat dan cepat berdasarkan koneksi yang kuat dengan virtualisasi dan teknologi basis data relasional hanya dilihat sebagai subset. Juga seperti catatan komentar, database kunci / nilai dan NoSQL adalah tempat banyak inovasi dan momentum baru bergerak. Namun dari komentar Anda, Anda tampaknya lebih tertarik pada prinsip dan teknik desain basis data relasional . Coba referensi berikut:

vzn
sumber
Saya belum benar-benar mempelajari sistem basis data non-relasional, dan mungkin itu salah satu jawaban yang masuk akal. Tapi saya sebenarnya tidak mencari buku teks basis data yang menjelaskan desain basis data. Sebaliknya, sebuah buku yang menggambarkannya dari sudut pandang pengembang basis data (yang secara eksplisit memberi tahu kita bagaimana struktur data untuk bekerja pada disk diimplementasikan) akan sangat membantu.
Arani
benci untuk mengakui hal ini tetapi sedikit mengecewakan referensi ini. ada buku-buku tentang algoritma database tetapi ada banyak buku tentang desain database yang benar-benar tentang bagaimana mengatur tabel, datamodelling, normalisasi, indeks, dll, konsep-konsep seperti ini. sementara ini terkait secara tangensial dengan pertanyaan Anda, mereka tidak benar-benar terhubung. pada dasarnya banyak strategi untuk mengelola b-tree dalam database modern agak mendekati rahasia dagang. umumnya pohon-b disimpan di "halaman" yang dialokasikan secara dinamis & diindeks. mungkin mencari referensi yang lebih baik tentang ini kapan-kapan.
vzn
tebak apa yang benar-benar Anda inginkan adalah desain penyimpanan basis data fisik (yang mungkin dibahas secara longgar di beberapa referensi tersebut, atau mungkin tidak) .. misalkan ada kertas putih untuk studi kasus dengan beberapa konten terkait yaitu "Internal penyimpanan penyimpanan desain fisik SQL Server" , MS SQL server
vzn
lihat juga optimisasi rencana kueri yang
vzn
1
lihat juga indeks pohon B + dengan beberapa referensi ke halaman penyimpanan & apache derby , implementasi pengambilan pohon B / penyimpanan di java dengan detail implementasi
vzn