zbMATH — the first resource for mathematics

Handbook of data structures and applications. 2nd edition. (English) Zbl 1390.68002
Chapman & Hall/CRC Computer and Information Science Series. Boca Raton, FL: Chapman & Hall/CRC (ISBN 978-1-4987-0185-3/hbk; 978-1-4987-0188-4/ebook). xx, 1099 p. (2018).

Show indexed articles as search result.

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. The 2004 first edition shows 191 citations at Google Scholar. For individual chapters I saw numbers between 10 and 50. This is solid but less than comparable handbooks on other algorithmic subjects, e.g., on computational geometry or on scheduling.
The added value of the 2018 second edition over the 2004 first edition [Zbl 1077.68023] is smaller than it could be. There are 4 new and 15 updated chapters. However, the sample I took revealed little changes in most chapters where I know that significant developments have happened. For example, the hashing chapter ignores recent results on (generalized) cuckoo hashing, space-efficient perfect hashing, retrieval data structures etc. The succinct data structure chapter was not updated, although this is a quite hot topic (some results are mentioned in the updated chapter on bioinformatics). Even more important, the book almost completely ignores the renaissance of parallel algorithms and its impact on data structures. For example, the chapter on concurrent data structures was not updated at all. I saw nothing on parallel construction or bulk updates, although this should at least be a section in most chapters. Overall, I disagree with the foreword “As one would expect, the discipline of data structures has matured with advances not as rapidly forthcoming as in the twentieth century” – the book misses an opportunity to show that data structures are still a very dynamic area of research.
The articles of this volume will be announced individually.
Indexed articles:
Sahni, Sartaj, Analysis of algorithms, 3-21 [Zbl 1387.68317]
Mehta, Dinesh P., Basic structures, 23-34 [Zbl 1390.68221]
Mehta, Dinesh P., Trees, 35-48 [Zbl 1390.68222]
Deo, Narsingh, Graphs, 49-66 [Zbl 1387.68084]
Sahni, Sartaj, Leftist trees, 69-75 [Zbl 1390.68233]
Pandu Rangan, C., Skew heaps, 77-83 [Zbl 1390.68230]
Fredman, Michael L., Binomial, Fibonacci, and pairing heaps, 85-95 [Zbl 1390.68210]
Sahni, Sartaj, Double-ended priority queues, 97-114 [Zbl 1390.68234]
Morin, Pat, Hash tables, 117-129 [Zbl 1390.68226]
Chen, Shigang, Bloom filter and its variants, 131-149 [Zbl 1390.68204]
Andersson, Arne; Fagerberg, Rolf; Larsen, Kim S., Balanced binary search trees, 151-170 [Zbl 1390.68201]
Brodal, Gerth Stølting, Finger search trees, 171-178 [Zbl 1387.68079]
Saxena, Sanjeev, Splay trees, 179-196 [Zbl 1390.68237]
Pandu Rangan, C., Randomized dictionary structures, 197-213 [Zbl 1390.68231]
Rytter, Wojciech, Trees with minimum weighted path length, 215-232 [Zbl 1387.68101]
Zhang, Donghui, B trees, 233-247 [Zbl 1390.68242]
Samet, Hanan, Multidimensional spatial data structures, 251-275 [Zbl 1390.68236]
Cheng, Siu-Wing, Planar straight line graphs, 277-290 [Zbl 1387.68081]
Lee, D. T.; Yu, Hung-I, Interval, segment, range, priority search trees, 291-307 [Zbl 1390.68218]
Aluru, Srinivas, Quadtrees and octtrees, 309-327 [Zbl 1390.68199]
Naylor, Bruce F., BSP trees, 329-342 [Zbl 1390.68228]
Leutenegger, Scott; Lopez, Mario A., R-trees, 343-358 [Zbl 1390.68219]
Dua, Sumeet; Iyengar, S. S., Managing spatio-temporal data, 359-375 [Zbl 1390.68207]
Guibas, Leonidas, Kinetic data structures, 377-388 [Zbl 1390.68212]
Gonzalez, Teofilo F., Online dictionary structures, 389-396 [Zbl 1390.68211]
Chazelle, Bernard, Cuttings, 397-404 [Zbl 1387.68249]
Duncan, Christian A.; Goodrich, Michael T., Approximate geometric query structures, 405-417 [Zbl 1387.68085]
Vitter, Jeffrey Scott, Geometric and spatial data structures in external memory, 419-442 [Zbl 1390.68240]
Sahni, Sartaj, Tries, 445-460 [Zbl 1390.68235]
Aluru, Srinivas, Suffix trees and suffix arrays, 461-475 [Zbl 1390.68200]
Ehrenfeucht, Andrzej; McConnell, Ross M., String searching, 477-494 [Zbl 1387.68087]
Minato, Shin-ichi, Binary decision diagrams, 495-509 [Zbl 1390.68224]
Kaplan, Haim, Persistent data structures, 511-527 [Zbl 1390.68216]
Raman, Rajeev, Data structures for sets, 529-544 [Zbl 1390.68232]
Arge, Lars; Brodal, Gerth Stølting; Fagerberg, Rolf, Cache oblivious data structures, 545-565 [Zbl 1387.68078]
Demetrescu, Camil; Finocchi, Irene; Italiano, Giuseppe F., Dynamic trees, 567-580 [Zbl 1390.68206]
Demetrescu, Camil; Finocchi, Irene; Italiano, Giuseppe F., Dynamic graphs, 581-594 [Zbl 1387.68083]
Munro, J. Ian; Rao, S. Srinivasa, Succinct representation of data structures, 595-610 [Zbl 1390.68227]
Baswana, Surender; Sen, Sandeep, Randomized graph data structures, 611-625 [Zbl 1390.68202]
Andersson, Arne, Searching and priority queues in \(o(\log n)\) time, 627-636 [Zbl 1387.68076]
Okasaki, Chris, Functional data structures, 639-651 [Zbl 1390.68229]
Naeher, Stefan, LEDA, a platform for combinatorial and geometric computing, 653-666 [Zbl 1387.68098]
Weiss, Mark Allen, Data structures in C++, 667-677 [Zbl 1387.68103]
Goodrich, Michael T.; Tamassia, Roberto; Vismara, Luca, Data structures in JDSL, 679-695 [Zbl 1387.68090]
Stasko, John, Data structure visualization, 697-705 [Zbl 1390.68239]
Leipert, Sebastian, Drawing trees, 707-721 [Zbl 1387.68096]
Eades, Peter; Hong, Seok-Hee, Drawing graphs, 723-740 [Zbl 1387.68086]
Moir, Mark; Shavit, Nir, Concurrent data structures, 741-762 [Zbl 1390.68225]
Sahni, Sartaj; Kim, Kun Suk; Lu, Haibin, IP router tables, 765-781 [Zbl 1387.68102]
Gupta, Pankaj, Multidimensional packet classification, 783-798 [Zbl 1387.68091]
Henzinger, Monika, Data structures in web information retrieval, 799-803 [Zbl 1387.68093]
Maheshwari, S. N., The web as a dynamic graph, 805-815 [Zbl 1387.68034]
Mehta, Dinesh P., Layout data structures, 817-831 [Zbl 1390.68223]
Feng, Zhou; Yao, Bo; Cheng, Chung-Kuan, Floorplan representation in VLSI, 833-855 [Zbl 1387.68088]
McMullin, Dale; Rockwood, Alyn, Computer graphics, 857-869 [Zbl 1387.68270]
Seeger, Bernhard; Widmayer, Peter, Geographic information systems, 871-888 [Zbl 1387.68291]
Lin, Ming C.; Manocha, Dinesh, Collision detection, 889-902 [Zbl 1387.68267]
Iyengar, S. S.; Vaishnavi, V. K.; Gunasekaran, S., Image data structures, 903-916 [Zbl 1387.68286]
Ferragina, Paolo; Kurtz, Stefan; Lonardi, Stefano; Manzini, Giovanni, Computational biology, 917-934 [Zbl 1387.68089]
Mehta, Dinesh P.; Crabtree, John D., Data structures for cheminformatics, 935-944 [Zbl 1387.68097]
Pothen, Alex; Toledo, Sivan, Elimination structures in scientific computing, 945-965 [Zbl 1387.68099]
Hammer, Joachim; Schneider, Markus, Data structures for databases, 967-981 [Zbl 1387.68092]
Ravindran, Arun A.; Mehta, Dinesh P., Data structures for big data stores, 983-995 [Zbl 1387.68100]
Kumar, Vipin; Tan, Pang-Ning; Steinbach, Michael, Data mining, 997-1012 [Zbl 1387.68095]
de Berg, Mark; Speckmann, Bettina, Computational geometry: fundamental structures, 1013-1026 [Zbl 1387.68283]
Arya, Sunil; Mount, David M., Computational geometry: proximity and location, 1027-1042 [Zbl 1387.68232]
Gupta, Prosenjit; Janardan, Ravi; Rahul, Saladi; Smid, Michiel, Computational geometry: generalized (or colored) intersection searching, 1043-1058 [Zbl 1387.68261]
68-00 General reference works (handbooks, dictionaries, bibliographies, etc.) pertaining to computer science
68P05 Data structures
Full Text: Link