The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
The purpose of this introductory chapter is twofold. On the one hand, it serves the rather prosaic purpose of introducing the basic models and notations used in the subsequent chapters. On the other hand, it explains why these simple abstract models can be used to develop better algorithms for complex real world hardware.
This chapter is a tutorial on basic data structures that perform well in memory hierarchies. These data structures have a large number of applications and furthermore serve as an introduction to the basic principles of designing data structures for memory hierarchies.
This survey is meant to give an introduction to elementary techniques used for designing I/O-efficient algorithms. We do not intend to give a complete survey of all state-of-the-art techniques; but rather we aim to provide the reader with a good understanding of the most elementary techniques. Our focus is on general techniques and on techniques used in the design of I/O-efficient graph algorithms...
Solving real-world optimization problems frequently boils down to processing graphs. The graphs themselves are used to represent and structure relationships of the problem’s components. In this chapter we review external-memory (EM) graph algorithms for a few representative problems:
Massive graphs arise naturally in many applications. Recent web crawls, for example, produce graphs with on the order of 200 million nodes and 2 billion edges. Recent research in web modelling uses depth-first search, breadth-first search, and the computation of shortest paths and connected components as primitive routines for investigating the structure of the web [158]. Massive graphs are also often...
Computational Geometry is an area in Computer Science basically concerned with the design and analysis of algorithms and data structures for problems involving geometric objects. This field started in the 1970’s and has evolved into a discipline reaching out to areas such as Complexity Theory, Discrete and Combinatorial Geometry, or Algorithm Engineering. Geometric problems occur in a variety...
A full-text index is a data structure storing a text (a string or a set of strings) and supporting string matching queries: Given a pattern string P, find all occurrences of P in the text. The best-known full-text index is the suffix tree [761], but numerous others have been developed. Due to their fast construction and the wealth of combinatorial information they reveal, full-text indexes (and suffix...
Over the last 20 years or so CPU clock rates have grown explosively, and CPUs with clock rates exceeding 2 GHz are now available in the mass market. Unfortunately, the speed of main memory has not increased as rapidly: today’s main memory typically has a latency of about 60 ns. This implies that the cost of accessing main memory can be 120 times greater than the cost of performing an operation on...
The cache oblivious model is a simple and elegant model to design algorithms that perform well in hierarchical memory models ubiquitous on current systems. This model was first formulated in [321] and has since been a topic of intense research. Analyzing and designing algorithms and data structures in this model involves not only an asymptotic analysis of the number of steps executed in terms of the...
In order to mitigate the impact of the growing gap between CPU speed and main memory performance, today’s computer architectures implement hierarchical memory structures. The idea behind this approach is to hide both the low main memory bandwidth and the latency of main memory accesses which is slow in contrast to the floating-point performance of the CPUs. Usually, there is a small and expensive...
Artificial Intelligence (AI) deals with structuring large amounts of data. As a very first example of an expert system [424], take the oldest known scientific treatise surviving from the ancient world, the surgical papyrus [146] of about 3000 BC. It discusses cases of injured men for whom a surgeon had no hope of saving and lay many years unnoticed until it was rediscovered and published...
Persistent storage in modern computers is usually realized by magnetic hard disk drives. They form the last, and therefore the slowest level in the memory hierarchy. Disk drive technology is very sophisticated and complex, making an accelerated growth in disk capacity possible. Nowadays, a single of-the-self disk drive is capable of storing up to 180 GB and this number is doubled every 14 – 18 month...
The ever increasing gap between processor and memory speeds on one side and disk systems on the other side has exposed the I/O subsystems as a bottleneck for the applications with intensive I/O requirements. Consequently, file systems, as low-level managers of storage resources, have to offer flexible and efficient services in order to allow a high utilization of disks.
The exploitation of locality has proven to be paramount for getting the most out of today’s computers. Both data and instruction locality can be exploited from different perspectives, including hardware, base software and software design.
Hierarchically structured architectures are becoming more and more pervasive in the field of parallel and high performance computing. While memory hierarchies have been recognized for a long-time, only in the last years hierarchical parallel structures have gained importance, mainly as a result of the trend towards cluster architectures and high-performance application of computational grids.
The efficient parallelization of an algorithm is a hard task that requires a good command of software techniques and a considerable knowledge of the target computer. In such a task, either the programmer or the compiler have to tune different parameters to adapt the algorithm to the computer network topology and the communication libraries, or to expose the data locality of the algorithm on the memory...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.