The Handbook of Data Structures and Applications was first published over a decade ago. This second edition aims to update the first by focusing on areas of research in data structures that have seen significant progress. While the discipline of data structures has not matured as rapidly as other areas of computer science, the book aims to update those areas that have seen advances.
Retaining the seven-part structure of the first edition, the handbook begins with a review of introductory material, followed by a discussion of well-known classes of data structures, Priority Queues, Dictionary Structures, and Multidimensional structures. The editors next analyze miscellaneous data structures, which are well-known structures that elude easy classification. The book then addresses mechanisms and tools that were developed to facilitate the use of data structures in real programs. It concludes with an examination of the applications of data structures.
Four new chapters have been added on Bloom Filters, Binary Decision Diagrams, Data Structures for Cheminformatics, and Data Structures for Big Data Stores, and updates have been made to other chapters that appeared in the first edition.
The Handbook is invaluable for suggesting new ideas for research in data structures, and for revealing application contexts in which they can be deployed. Practitioners devising algorithms will gain insight into organizing data, allowing them to solve algorithmic problems more efficiently.
Arvustused
This handbook is a voluminous collection of 67 articles on a variety of data structures and their applications. Many articles are written by well-known experts with a focus on explaining basic ideas and surveying results. Overall, one gets an interesting overview of this central area of computer science.
-Peter Sanders, Zentralblatt MATH
| Preface to the Second Edition |
|
xi | |
| Preface to the First Edition |
|
xiii | |
| Editors |
|
xv | |
| Contributors |
|
xvii | |
|
|
|
|
|
|
3 | (20) |
|
|
|
|
|
23 | (12) |
|
|
|
|
|
35 | (14) |
|
|
|
|
|
49 | (20) |
|
|
|
|
|
|
|
|
69 | (8) |
|
|
|
|
|
77 | (8) |
|
|
|
7 Binomial, Fibonacci, and Pairing Heaps |
|
|
85 | (12) |
|
|
|
8 Double-Ended Priority Queues |
|
|
97 | (20) |
|
|
|
PART III Dictionary Structures |
|
|
|
|
|
117 | (14) |
|
|
|
10 Bloom Filter and Its Variants |
|
|
131 | (20) |
|
|
|
11 Balanced Binary Search Trees |
|
|
151 | (20) |
|
|
|
|
|
|
|
|
|
171 | (8) |
|
|
|
|
|
179 | (18) |
|
|
|
14 Randomized Dictionary Structures |
|
|
197 | (18) |
|
|
|
15 Trees with Min Weighted Path Length |
|
|
215 | (18) |
|
|
|
|
|
233 | (18) |
|
|
|
PART IV Multidimensional/Spatial Structures |
|
|
|
17 Multidimensional Spatial Data Structures |
|
|
251 | (26) |
|
|
|
18 Planar Straight Line Graphs |
|
|
277 | (14) |
|
|
|
19 Interval, Segment, Range, Priority Search Trees |
|
|
291 | (18) |
|
|
|
|
|
20 Quadtrees and Octtrees |
|
|
309 | (20) |
|
|
|
|
|
329 | (14) |
|
|
|
|
|
343 | (16) |
|
|
|
|
|
23 Managing Spatio-Temporal Data |
|
|
359 | (18) |
|
|
|
|
|
24 Kinetic Data Structures |
|
|
377 | (12) |
|
|
|
25 Online Dictionary Structures |
|
|
389 | (8) |
|
|
|
|
|
397 | (8) |
|
|
|
27 Approximate Geom Query Structures |
|
|
405 | (14) |
|
|
|
|
|
28 Geometric and Spatial Data Structures in External Memory |
|
|
419 | (26) |
|
|
|
|
|
|
|
|
445 | (16) |
|
|
|
30 Suffix Trees and Suffix Arrays |
|
|
461 | (16) |
|
|
|
|
|
477 | (18) |
|
|
|
|
|
32 Binary Decision Diagrams |
|
|
495 | (16) |
|
|
|
33 Persistent Data Structures |
|
|
511 | (18) |
|
|
|
34 Data Structures for Sets |
|
|
529 | (16) |
|
|
|
35 Cache Oblivious Data Structures |
|
|
545 | (22) |
|
|
|
|
|
|
|
|
|
567 | (14) |
|
|
|
|
|
|
|
|
|
581 | (14) |
|
|
|
|
|
|
|
38 Succinct Representation of Data Structures |
|
|
595 | (16) |
|
|
|
|
|
39 Randomized Graph Data Structures |
|
|
611 | (16) |
|
|
|
|
|
40 Searching and Priority Queues in o(log n) Time |
|
|
627 | (12) |
|
|
|
PART VI Data Structures in Langs and Libraries |
|
|
|
41 Functional Data Structures |
|
|
639 | (14) |
|
|
|
42 LEDA, a Platform for Combinatorial and Geometric Computing |
|
|
653 | (14) |
|
|
|
43 Data Structures in C++ |
|
|
667 | (12) |
|
|
|
44 Data Structures in JDSL |
|
|
679 | (18) |
|
|
|
|
|
|
|
45 Data Structure Visualization |
|
|
697 | (10) |
|
|
|
|
|
707 | (16) |
|
|
|
|
|
723 | (18) |
|
|
|
|
|
48 Concurrent Data Structures |
|
|
741 | (24) |
|
|
|
|
|
|
|
|
|
|
765 | (18) |
|
|
|
|
|
|
|
50 Multidimensional Packet Classification |
|
|
783 | (16) |
|
|
|
51 Data Structures in Web Information Retrieval |
|
|
799 | (6) |
|
|
|
52 The Web as a Dynamic Graph |
|
|
805 | (12) |
|
|
|
53 Layout Data Structures |
|
|
817 | (16) |
|
|
|
|
|
833 | (24) |
|
|
|
|
|
|
|
|
|
857 | (14) |
|
|
|
|
|
56 Geographic Information Systems |
|
|
871 | (18) |
|
|
|
|
|
|
|
889 | (14) |
|
|
|
|
|
|
|
903 | (14) |
|
|
|
|
|
|
|
|
|
917 | (18) |
|
|
|
|
|
|
|
|
|
60 Data Structures for Cheminformatics |
|
|
935 | (10) |
|
|
|
|
|
61 Elimination Structures in Scientific Computing |
|
|
945 | (22) |
|
|
|
|
|
62 Data Structures for Databases |
|
|
967 | (16) |
|
|
|
|
|
63 Data Structures for Big Data Stores |
|
|
983 | (14) |
|
|
|
|
|
|
|
997 | (16) |
|
|
|
|
|
|
|
65 Computational Geometry: Fundamental Structures |
|
|
1013 | (14) |
|
|
|
|
|
66 Computational Geometry: Proximity and Location |
|
|
1027 | (16) |
|
|
|
|
|
67 Computational Geometry: Generalized (or Colored) Intersection Searching |
|
|
1043 | (16) |
|
|
|
|
|
|
|
|
| Index |
|
1059 | |
Dinesh P. Mehta has been on the faculty of the Colorado School of Mines since 2000, where he is currently professor in the Department of Computer Science. He earned degrees (all in computer science) from the Indian Institute of Technology Bombay, the University of Minnesota, and the University of Florida. Before joining Mines in 2000, he was on the faculty of the University of Tennessee Space Institute, where he received the Vice Presidents Award for Teaching Excellence in 1997. He was a visiting professor at Intels Strategic CAD Labs for several months in 1996 and 1997 and at the Tata Research Development and Design Center (in Pune, India) in 2007. He has also received graduate teaching awards at Mines in 2007, 2008, and 2009.
He was assistant department head from 2004 to 2008 and interim department head from 2008 to 2010 in the former Department of Mathematical and Computer Sciences and served as president of the Mines Faculty Senate in 20162017.
Dr. Mehta is the coauthor of the book, Fundamentals of Data Structures in C++ and coeditor of the Handbook of Algorithms for VLSI Physical Design Automation. He serves as associate director of the ORwE (Operations Research with Engineering) PhD program at Mines and is currently an associate editor of ACM Computing Surveys. His current research interests are in cheminformatics, computational materials, and big graph analytics.
Sartaj Sahni is a distinguished professor of computer and information sciences and engineering at the University of Florida. He is also a member of the European Academy of Sciences, a Fellow of IEEE, ACM, AAAS, and Minnesota Supercomputer Institute, and a distinguished alumnus of the Indian Institute of Technology, Kanpur. Dr. Sahni is the recipient of the 1997 IEEE Computer Society Taylor L. Booth Education Award, the 2003 IEEE Computer Society W. Wallace McDowell Award, and the 2003ACMKarl Karlstrom Outstanding Educator Award. Dr. Sahni earned his BTech (electrical engineering) degree from the Indian Institute of
Technology, Kanpur, and MS and PhD in computer science from Cornell University. Dr. Sahni has published over 400 research papers and written 15 books. His research publications are on the design and analysis of efficient algorithms, parallel computing, interconnection networks, design automation, and medical algorithms.
Dr. Sahni is the editor-in-chief of the ACM Computing Surveys, a managing editor of the International Journal of Foundations of Computer Science, and a member of the editorial boards of 17 other journals. He is a past coeditor-in-chief of the Journal of Parallel and Distributed Computing. He has served as program committee chair, general chair, and a keynote speaker at many conferences. Dr. Sahni has served on several NSF (National Science Foundation) and NIH (National Institutes of Health) panels and he has been involved as an external evaluator of several computer science and engineering departments.
Lisainfo e-raamatute kohta