Application d'algorithmes sur des données volumineuses

8

Existe-t-il un livre ou un didacticiel qui nous enseigne comment appliquer efficacement les algorithmes courants (tri, recherche, etc.) sur de grandes données (c'est-à-dire des données qui ne peuvent pas être entièrement chargées dans la mémoire principale) et comment appliquer efficacement ces algorithmes compte tenu du coût de bloquer le transfert de la mémoire externe? Par exemple, presque tous les manuels d'algorithmes disent que les arbres B et B + peuvent être utilisés pour stocker des données sur disque. Cependant, en réalité, comment cela peut être fait, en particulier la gestion des pointeurs où les données sont présentes sur le disque ne sont pas expliquées. De même, bien que de nombreux livres enseignent les techniques de recherche, ils ne tiennent pas compte des données présentes dans la mémoire secondaire.

J'ai vérifié le livre de Knuth. Bien qu'il discute de ces idées, je ne comprenais toujours pas comment les appliquer réellement dans un langage de haut niveau. Y a-t-il une référence qui discute de ces détails?

algorithms efficiency memory-management big-data Arani
la source
1
Consultez "Extraction de jeux de données massifs" .
Dave Clarke
Vous pouvez jeter un œil à la bibliographie complète de STXXL: la bibliothèque de modèles standard pour les jeux de données XXL .
Vor
De nos jours, avec de superbes bases de données comme Oracle, DB2, SQL Server, normalement personne ne travaille lui-même de gros ensembles de données, si vous êtes intéressé, vous pouvez consulter les documents associés à l'un des serveurs DB, mais de nos jours Martin Fowler et d'autres personnes essaient de passer à NO SQL , vous pouvez également le vérifier. (mais il y a trop d'aspects dans les grandes bases de données, comme la concurrence, la sécurité, ... pas seulement les algorithmes rapides).
@Dave, Vor: Merci pour vos références. Je vais les vérifier et vous informer si elles sont ce que je recherche.
Arani
@SaeedAmiri: Je comprends cela, mais d'après ce que je comprends, le stockage de données dans des bases de données n'est utile que si les données sont hautement structurées d'une manière ou d'une autre. Ainsi, les séquences de nombres et autres données similaires ne sont généralement pas stockées à l'aide de bases de données. De plus, les manuels de base de données ne décrivent pas en détail du point de vue du développeur de base de données. Alors que la plupart d'entre eux mentionnent que les bases de données utilisent des arbres B et B +, la plupart ne décrivent pas réellement COMMENT ils mettent en œuvre ces structures de données.
Arani

Réponses:

2

Les livres de bases de données en sont un bon exemple. Cependant, jetez un œil aux structures de données (et algorithmes) efficaces d'E / S sur le terrain. À ma connaissance, il existe quelques cours sur ce sujet, mais très peu de livres.

Consultez ce livre: U. Meyer, P. Sanders et J. Sibeyn (éd.), Algorithms for Memory Hierarchies, Lecture Notes in Computer Science 2625, Springer, 2003.

Consultez ces cours: http://www.win.tue.nl/~hermanh/teaching/2IL35/ http://www.daimi.au.dk/~large/ioS12/

et ces diapositives: algo2.iti.kit.edu/sanders/courses/algen09-10/rdslides.pdf

AJed
la source
1

Le livre de base de données de Ramkrishnan et Gehrke discute ces choses en détail.

Arani
la source
Le pire et le plus ennuyeux jamais :)! bien que ce soit une bonne introduction à de nombreux sujets intéressants dans les bases de données et l'optimisation db.
AJed
0

Aujourd'hui, ce domaine est connu sous le nom de Big Data , et il évolue très rapidement et rapidement en fonction de la forte connexion avec la virtualisation et la technologie de base de données relationnelle n'est considérée que comme un sous-ensemble. De plus, comme le notent les commentaires, les bases de données clés / valeurs et NoSQL sont le point de départ de nombreuses innovations et impulsions. Mais d'après vos commentaires, vous semblez être plus intéressé par les principes et techniques de conception de bases de données relationnelles . Essayez les références suivantes:

vzn
la source
Je n'ai pas vraiment étudié les systèmes de bases de données non relationnelles, et cela pourrait donc être une réponse plausible. Mais je ne recherche pas réellement des manuels de base de données qui décrivent la conception de base de données. Au lieu de cela, un livre qui le décrit du point de vue du développeur de base de données (qui nous dit explicitement comment les structures de données pour travailler sur les disques sont implémentées) serait très utile.
Arani
déteste l'admettre, mais a un peu bâclé ces références. il existe des livres sur les algorithmes de base de données , mais il existe de nombreux livres sur la conception de bases de données qui traitent vraiment de l'organisation des tables, du modèle de données, de la normalisation, des index, etc., de concepts comme ceux-ci. Bien que ceux-ci soient liés tangentiellement à votre question, ils ne sont pas vraiment exactement connectés. en fait, bon nombre des stratégies de gestion des arbres b dans les bases de données modernes frôlent quelque peu les secrets commerciaux. généralement les b-arbres sont stockés dans des "pages" qui sont allouées et indexées dynamiquement. peut chercher de meilleures références à ce sujet un jour.
vzn
devinez ce que vous voulez vraiment, c'est la conception du stockage de la base de données physique (qui pourrait être couverte de manière lâche dans certaines de ces références, ou peut-être pas). , Serveur MS SQL
vzn
voir également l' optimisation du plan de requête
vzn
1
voir également les index d'arborescence B + avec quelques références aux pages de stockage et apache derby , une implémentation de récupération / stockage d'arborescence B en java avec des détails d'implémentation
vzn