Advanced Data Structures : Theory and Applications

Advanced data structures is a core course in Computer Science which most graduate program in Computer Science, Computer Science and Engineering, and other allied engineering disciplines, offer during the first year or first semester of the curriculum. The objective of this course is to enable students to have the much-needed foundation for advanced technical skill, leading to better problem-solving in their respective disciplines. Although the course is running in almost all the technical universities for decades, major changes in the syllabus have been observed due to the recent paradigm shift of computation which is more focused on huge data and internet-based technologies. Majority of the institute has been redefined their course content of advanced data structure to fit the current need and course material heavily relies on research papers because of nonavailability of the redefined text book advanced data structure. To the best of our knowledge well-known textbook on advanced data structure provides only partial coverage of the syllabus. The book offers comprehensive coverage of the most essential topics, including: Part I details advancements on basic data structures, viz., cuckoo hashing, skip list, tango tree and Fibonacci heaps and index files. Part II details data structures of different evolving data domains like special data structures, temporal data structures, external memory data structures, distributed and streaming data structures. Part III elucidates the applications of these data structures on different areas of computer science viz, network, www, DBMS, cryptography, graphics to name a few. The concepts and techniques behind each data structure and their applications have been explained. Every chapter includes a variety of Illustrative Problems pertaining to the data structure(s) detailed, a summary of the technical content of the chapter and a list of Review Questions, to reinforce the comprehension of the concepts. The book could be used both as an introductory or an advanced-level textbook for the advanced undergraduate, graduate and research programmes which offer advanced data structures as a core or an elective course. While the book is primarily meant to serve as a course material for use in the classroom, it could be used as a starting point for the beginner researcher of a specific domain. Cover Half Title Title Page Copyright Page Dedication Contents Foreword Acknowledgments Preface Authors Part 1: Theoretical Advancements 1. Introduction 1.1 Data Structure 1.2 Design of Data Structure 1.3 Analysis of Data Structure 1.4 Amortized Complexity 1.5 Computational Models 1.5.1 RAM model 1.5.2 Word RAM model 1.5.3 Cell-probe model of computation 1.6 Bounds of Fundamental Data Structures 1.7 Lazy Delete 1.8 Organization of Part I 1.9 Exercises 2. O(1)Search by Hashing 2.1 Basic Hashing 2.1.1 Hash function 2.1.2 Load factor 2.1.3 Collision resolution 2.2 Perfect Hashing 2.2.1 Construction 2.2.2 Remarks 2.3 Universal Hashing 2.3.1 Important properties 2.3.2 Mathematical guarantees 2.4 Cuckoo Hashing 2.4.1 Operations 2.4.2 Bipartite graph of cuckoo hashing 2.5 Bloom Filters 2.5.1 Construction of bloom filter 2.5.2 Probability of false positives 2.5.3 Optimal values of parameters 2.6 Locality-Sensitive Hashing 2.6.1 Use in nearest neighbor search problem 2.7 Exercises 3. O(log(n)) Ordered Search (Trees and Lists) 3.1 Balanced Binary Search Trees (BSTs) 3.1.1 Height bound of balanced BST 3.2 Randomized BSTs 3.2.1 Static randomized BSTs 3.2.2 Dynamic randomized BSTs 3.2.3 Analysis of randomized BSTs 3.3 Splay Tree 3.3.1 Splaying 3.3.2 Splaying algorithms 3.3.3 Performance 3.4 Tango Tree 3.4.1 Creation of tango tree 3.4.2 Tango analysis 3.5 Skiplists 3.5.1 Skipping 3.5.2 Dynamic updates 3.5.3 Probabilistic analysis of skiplist 3.6 Static and Dynamic Optimality 3.6.1 Search optimality in BST 3.6.2 Static optimality 3.6.3 Dynamic optimality 3.7 Exercises 4. Findset, Find Min, and Find Word 4.1 Disjoint Sets 4.1.1 Operations on disjoint-set data structure 4.1.2 Representations of disjoint sets 4.1.3 Link-list representations of disjoint sets 4.1.4 Forest representations of disjoint sets 4.2 Binomial Heap 4.2.1 Creation and updates of binomial heap 4.2.2 Operations of Binomial Heap 4.2.3 Complexity 4.3 Fibonacci Heaps 4.3.1 Properties of a Fibonacci heap 4.3.2 Inserting, merging, cutting, and marking 4.3.3 Decreasing keys and delete-min operation 4.3.4 Algorithm for Fibonacci heaps 4.3.5 Amortized analysis for Fibonacci heaps 4.3.6 Tree size 4.4 Tries 4.4.1 Insertion 4.4.2 Searching 4.4.3 Deletion 4.4.4 Complexity 4.4.5 Compact trie 4.4.6 Patricia 4.4.7 Suffix tree 4.5 Inverted Index 4.5.1 Inverted index creation 4.5.2 Index compression 4.5.3 Key words search 4.6 Exercises Part 2: Evolving Paradigms 5. Evolving Paradigms of Data Structures 5.1 Geometric Queries 5.2 I/O Complexities 5.3 Communication Complexities 5.4 Large Data Problem 5.5 Exercise 6. Spatial Data Structures 6.1 Range Search Trees 6.1.1 Construction 6.1.2 Range query search 6.2 KD Trees 6.2.1 Creation of KD tree 6.2.2 Range search in KD tree 6.2.3 Nearest neighbor search in KD tree 6.3 Quadtree 6.3.1 Inserting data into a quadtree 6.3.2 Properties of quadtree 6.3.3 Region quadtree 6.3.4 Point quadtree 6.4 R Tree 6.4.1 Indexing structure of R tree 6.4.2 Search in R tree 6.4.3 Dynamic update of R tree 6.5 Exercises 7. Temporal Data Structures 7.1 Partial Persistence 7.1.1 Partial persistence 7.1.2 Full persistence 7.1.3 Confluent persistence 7.1.4 Functional persistence 7.2 Retroactivity 7.2.1 Decomposable search problem 7.3 Exercises 8. External Memory Data Structures 8.1 Input/Output (I/O) Model 8.2 Cache Oblivious Algorithms 8.2.1 Cache aware model 8.2.2 Cache oblivious model 8.3 B, B+ Tree 8.3.1 Searching 8.3.2 Insertion 8.3.3 Removal 8.3.4 Amortized analysis of B trees 8.3.5 B+ tree 8.4 (a,b) Tree 8.4.1 Insertion 8.4.2 Deletion 8.5 Buffer Tree 8.6 Exercises 9. Distributed Data Structures (DDSs) 9.1 Descriptions of Structures 9.1.1 Properties of DDS 9.2 Distributed Hashing 9.2.1 Structure of distributed hashing 9.3 Distributed Trees 9.3.1 Construction of distributed BST 9.3.2 Insertion 9.3.3 Deletion 9.3.4 Rotation 9.4 Skip Graphs 9.4.1 Design 9.4.2 Search 9.4.3 Insertion 9.4.4 Deletion 9.4.5 Correctness and concurrency 9.5 Exercises 10. Synopsis Data Structures 10.1 Data Synopsis 10.1.1 Synopsis methods 10.1.2 Application 10.2 Sampling 10.2.1 Sampling technique 10.2.2 Reservoir sampling 10.2.3 Sampling with updates 10.2.4 Sliding window sampling 10.3 Sketching 10.3.1 Count-min sketches 10.4 Fingerprint 10.4.1 Fingerprinting scheme of Rabin 10.5 Wavelets 10.5.1 Wavelet decomposition 10.6 Exercises Part 3: Recent Applications 11. Introduction to Applications 11.1 Various Domain Applications 11.2 Project 12. Applications to Cryptography 12.1 MD5 12.1.1 Password hashing 12.2 Secure Socket Layers (SSLs) 12.2.1 Data structure of open SSL 12.3 Block Chains 12.4 Digital Signature 12.5 Projects 13. Application to IR and WWW 13.1 Crawl Frontier 13.2 Posting List Intersection 13.3 Text Retrieval from Inverted Index 13.4 Auto Complete Using Tries 13.5 Projects 14. Applications to Data Science 14.1 Heavy Hitters and Count-Min Structures 14.2 Approximate Nearest Neighbor Searches 14.2.1 Approximate nearest neighbor 14.2.2 Locality-sensitive hashing (LSH) 14.3 Low Rank Approximation by Sampling 14.3.1 Nystrom approximation 14.3.2 Random sketching 14.4 Near-Duplicate Detection by Min Hashing 14.5 Projects 15. Application to Network and IOT 15.1 Click-Stream Processing Using Bloom Filters 15.1.1 GBF Algorithm 15.2 Fast IP-Address Lookup Using Tries 15.3 Integrity Verification: Cloud and IOT Data 15.4 Projects 16. Applications to Systems 16.1 Queue Spilling 16.2 Completely Fair Schedulers in Kernels 16.2.1 CFS internals 16.3 Distributed Caching 16.4 Data Structures for Building File Systems 16.5 Projects 17. Applications to Databases 17.1 Database Problems 17.1.1 Searching sorted files 17.1.2 Index for first search 17.1.3 Insertion deletion in database 17.2 B and B+ Trees for Database Creation and Block Search 17.2.1 Applications of B trees in databases and file systems 17.3 CouchDB 17.4 Bloomjoins 17.5 Projects 18. Applications to Images and Graphics 18.1 R Trees for Map Searches 18.1.1 R trees for mapping 18.1.2 Insertion 18.1.3 Deletion 18.1.4 Search 18.2 Spatial Proximity in GIS 18.2.1 GIS objects 18.2.2 Data access in GIS 18.2.3 Computational requirements 18.2.4 Solution using k-d tree 18.3 Ray Shooting 18.3.1 Rays 18.3.2 Camera-ray intersections 18.3.3 Shadow rays 18.3.4 Reflection rays 18.3.5 Transmission rays 18.3.6 Recursive ray tracing 18.3.7 Ray intersection 18.3.8 Bounding volume hierarchies 18.4 Data Structures Used in Ray Shooting 18.4.1 Octrees 18.4.2 KD trees 18.4.3 BSP trees 18.4.4 Uniform grids 18.4.5 Hierarchical grids 18.5 Projects Bibliography Index The aim of this book is to give basic as well advance understanding of data structure to undergraduate and graduate students. The design of the book is simple. Part I consist of chapters covering the basics of data structure. Part-II covers highly advanced data structure. While part-III covers the applications.