Log In
Or create an account ->
Imperial Library
Home
About
News
Upload
Forum
Help
Login/SignUp
Index
Cover
Half Title
Title Page
Copyright Page
Dedication
Contents
Foreword
Acknowledgments
Preface
Authros
Part I: 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 II: 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 III: 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
← Prev
Back
Next →
← Prev
Back
Next →