Aplicando algoritmos em grandes dados

8

Existe algum livro ou tutorial que nos ensine como aplicar eficientemente os algoritmos comuns (classificação, pesquisa etc.) em dados grandes (ou seja, dados que não podem ser totalmente carregados na memória principal) e como aplicar esses algoritmos de maneira eficiente, considerando o custo de bloquear transferência da memória externa? Por exemplo, quase todos os livros didáticos de algoritmos dizem que as árvores B e B + podem ser usadas para armazenar dados no disco. No entanto, na verdade, como isso pode ser feito, especialmente o manuseio dos ponteiros onde os dados estão presentes no disco não é explicado. Da mesma forma, embora muitos livros ensinem técnicas de busca, eles não consideram os dados presentes na memória secundária.

Eu verifiquei o livro de Knuth. Embora discuta essas idéias, ainda não entendi como aplicá-las em um idioma de alto nível. Existe alguma referência que discuta esses detalhes?

algorithms efficiency memory-management big-data Arani
fonte
1
Confira "Mining Massive Data Sets" .
22412 Dave Clarke
Você pode dar uma olhada na bibliografia abrangente do STXXL: a biblioteca de modelos padrão para conjuntos de dados XXL .
Vor
Hoje em dia, com ótimos bancos de dados como Oracle, DB2, SQL Server, normalmente ninguém trabalha com grandes conjuntos de dados; se você estiver interessado, pode ver documentos relacionados a um dos servidores de banco de dados, mas hoje Martin Fowler e outras pessoas estão tentando mover para NO SQL , você também pode verificá-lo. (mas há muitos aspectos em grandes bancos de dados, como simultaneidade, segurança, ... não apenas algoritmos rápidos).
@ Dave, Vor: Obrigado por suas referências. Vou verificá-los e informá-lo se eles são o que estou procurando.
23412 Arani
@SaeedAmiri: Entendo isso, mas pelo que entendi, armazenar dados em bancos de dados só é útil se os dados estiverem altamente estruturados de alguma forma. Portanto, a sequência de números e outros dados semelhantes geralmente não são armazenados usando bancos de dados. Além disso, os livros didáticos de banco de dados não descrevem em muitos detalhes do ponto de vista do desenvolvedor de banco de dados. Enquanto a maioria deles menciona que os bancos de dados usam árvores B e B +, a maioria não descreve realmente como eles implementam essas estruturas de dados.
23412 Arani

Respostas:

2

Os livros de banco de dados são um bom exemplo. No entanto, observe o campo de estruturas de dados eficientes de E / S (e algoritmos). Que eu saiba, existem alguns cursos sobre esse tópico, mas muito poucos livros.

Verifique este livro: U. Meyer, P. Sanders e J. Sibeyn (eds.), Algoritmos para Hierarquias de Memória, Notas de Aula em Ciência da Computação 2625, Springer, 2003.

Verifique estes cursos: http://www.win.tue.nl/~hermanh/teaching/2IL35/ http://www.daimi.au.dk/~large/ioS12/

e estes slides: algo2.iti.kit.edu/sanders/courses/algen09-10/rdslides.pdf

AJed
fonte
1

O livro do banco de dados de Ramkrishnan e Gehrke discute essas coisas com mais detalhes.

Arani
fonte
O pior e mais chato de todos os tempos :)! embora seja uma boa introdução a muitos tópicos interessantes em bancos de dados e otimização de banco de dados.
precisa saber é
0

Atualmente, esse campo é conhecido como big data e está evoluindo muito rapidamente e rapidamente, com base na forte conexão com a virtualização e a tecnologia de banco de dados relacional, que é vista apenas como um subconjunto. Além disso, como observam os comentários, os bancos de dados de chave / valor e o NoSQL são para onde muita inovação e dinâmica estão se movendo. Mas, pelos seus comentários, você parece estar mais interessado nos princípios e técnicas de design de banco de dados relacional . Tente as seguintes referências:

vzn
fonte
Eu realmente não estudei sistemas de banco de dados não relacionais e, portanto, essa pode ser uma resposta plausível. Mas, na verdade, não estou procurando livros de banco de dados que descrevam o design do banco de dados. Em vez disso, um livro que o descreva do ponto de vista do desenvolvedor de banco de dados (que nos diz explicitamente como as estruturas de dados para trabalhar em discos são implementados) seria muito útil.
Arani
odeio admitir isso, mas estragou um pouco esses árbitros. existem livros sobre algoritmos de banco de dados , mas existem muitos livros sobre design de banco de dados que são realmente sobre como organizar tabelas, datamodelling, normalização, índices etc., conceitos como esses. Embora estejam relacionados tangencialmente à sua pergunta, eles não estão realmente exatamente conectados. basicamente, muitas das estratégias para o gerenciamento de árvores-b em bancos de dados modernos estão um pouco próximas dos segredos comerciais. geralmente as árvores b são armazenadas em "páginas" que são alocadas e indexadas dinamicamente. pode procurar referências melhores neste dia.
vzn
adivinhe o que você realmente deseja é o design físico de armazenamento de banco de dados (que pode ser coberto de maneira superficial em algumas dessas referências, ou talvez não). , MS SQL server
vzn
ver também o intimamente relacionado otimização plano de consulta
vzn
1
ver também B + índices de árvore com algum ref para páginas de armazenamento e Apache Derby , uma árvore B buscar / implementação de armazenamento em java com detalhes de implementação
vzn