Algorithms and Data Structures for External Memory

The essence of knowledge FnT TCS 2:4 Algorithms and Data Structures f or External Memor y Jeffre y Scott Vitter Algorithms and Data Structures for External Memory Jeffrey Scott Vitter Data sets in large applications are often too massive to fit completely inside the computer's internal memory. The resulting input/output communication (or I/O) between fast internal memory and slower external memory (such as disks) can be a major performance bottleneck. Algorithms and Data Structures for External Memory surveys the state

of the art in the design and analysis of external memory (or EM) algorithms and data structures, where the goal is to exploit locality in order to reduce the I/O costs. A variety of EM paradigms are considered for solving batched and online problems efficiently in external memory. Algorithms and Data Structures for External Memory describes several useful paradigms for the design and implementation of efficient EM algorithms and data structures. The problem domains considered include sorting, permuting, FFT, scientific computing, computational geometry, graphs, databases, geographic information systems, and text and string processing. Algorithms and Data Structures for External Memory is an invaluable reference for anybody interested in, or conducting research in the design, analysis, and implementation of algorithms and data structures. This book is originally published as Foundations and Trends ® in Theoretical Computer Science Volume 2 Issue 4, ISSN: 1551-305X. Foundations and Trends ® in Theoretical Computer Science 2:4 Algorithms and Data Structures for External Memory Jeffrey Scott Vitter now now TCSv2n4.qxd 4/24/2008 11:56 AM Page 1 Algorithms and Data Structures for External Memory Algorithms and Data Structures for External Memory Jeffrey Scott Vitter Department of Computer Science Purdue University West Lafayette Indiana, 47907–2107 USA jsv@purdue.edu Boston – Delft Foundations and Trends R© in Theoretical Computer Science Published, sold and distributed by: now Publishers Inc. PO Box 1024 Hanover, MA 02339 USA Tel. +1-781-985-4510 www.nowpublishers.com sales@nowpublishers.com Outside North America: now Publishers Inc. PO Box 179 2600 AD Delft The Netherlands Tel. +31-6-51115274 The preferred citation for this publication is J. S. Vitter, Algorithms and Data Structures for External Memory, Foundation and Trends R© in Theoretical Computer Science, vol 2, no 4, pp 305–474, 2006 ISBN: 978-1-60198-106-6 c© 2008 J. S. Vitter All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, mechanical, photocopying, recording or otherwise, without prior written permission of the publishers. Photocopying. In the USA: This journal is registered at the Copyright Clearance Cen- ter, Inc., 222 Rosewood Drive, Danvers, MA 01923. Authorization to photocopy items for internal or personal use, or the internal or personal use of specific clients, is granted by now Publishers Inc. for users registered with the Copyright Clearance Center (CCC). The ‘services’ for users can be found on the internet at: www.copyright.com For those organizations that have been granted a photocopy license, a separate system of...

Website: www.ittc.ku.edu | Filesize: -
No of Page(s): 191
Download Algorithms and Data Structures for External Memory.pdf