Muutke küpsiste eelistusi

E-raamat: Advanced Data Structures: Theory and Applications [Taylor & Francis e-raamat]

,
  • Formaat: 260 pages, 3 Tables, black and white; 48 Illustrations, black and white
  • Ilmumisaeg: 25-Jun-2019
  • Kirjastus: CRC Press
  • ISBN-13: 9780429488757
Teised raamatud teemal:
  • Taylor & Francis e-raamat
  • Hind: 216,96 €*
  • * hind, mis tagab piiramatu üheaegsete kasutajate arvuga ligipääsu piiramatuks ajaks
  • Tavahind: 309,94 €
  • Säästad 30%
Advanced Data Structures: Theory and ApplicationsSuurem pilt
  • Formaat: 260 pages, 3 Tables, black and white; 48 Illustrations, black and white
  • Ilmumisaeg: 25-Jun-2019
  • Kirjastus: CRC Press
  • ISBN-13: 9780429488757
Teised raamatud teemal:
Taylor & Francis e-raamatudRohkem infot Taylor & Francis e-raamatute kohta
Raamatu kodulehekülg: https://www.taylorfrancis.com/books/9780429488757
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.
I Theoretical Advancements
1 Introduction
3(12)
1.1 Data Structure
4(1)
1.2 Design of Data Structure
5(1)
1.3 Analysis of Data Structure
5(1)
1.4 Amortized Complexity
6(2)
1.5 Computational Models
8(2)
1.5.1 RAM model
8(1)
1.5.2 Word RAM model
9(1)
1.5.3 Cell-probe model of computation
9(1)
1.6 Bounds of Fundamental Data Structures
10(1)
1.7 Lazy Delete
10(1)
1.8 Organization of Part I
11(1)
1.9 Exercises
12(3)
2 O(1) Search by Hashing
15(18)
2.1 Basic Hashing
15(3)
2.1.1 Hash function
16(1)
2.1.2 Load factor
17(1)
2.1.3 Collision resolution
17(1)
2.2 Perfect Hashing
18(1)
2.2.1 Construction
18(1)
2.2.2 Remarks
19(1)
2.3 Universal Hashing
19(3)
2.3.1 Important properties
21(1)
2.3.2 Mathematical guarantees
22(1)
2.4 Cuckoo Hashing
22(4)
2.4.1 Operations
23(1)
2.4.2 Bipartite graph of cuckoo hashing
23(3)
2.5 Bloom Filters
26(4)
2.5.1 Construction of bloom filter
26(2)
2.5.2 Probability of false positives
28(1)
2.5.3 Optimal values of parameters
29(1)
2.6 Locality-Sensitive Hashing
30(2)
2.6.1 Use in nearest neighbor search problem
31(1)
2.7 Exercises
32(1)
3 O(log(n)) Ordered Search (Trees and Lists)
33(22)
3.1 Balanced Binary Search Trees (BSTs)
33(3)
3.1.1 Height bound of balanced BST
35(1)
3.2 Randomized BSTs
36(3)
3.2.1 Static randomized BSTs
37(1)
3.2.2 Dynamic randomized BSTs
37(1)
3.2.3 Analysis of randomized BSTs
38(1)
3.3 Splay Tree
39(6)
3.3.1 Splaying
40(1)
3.3.2 Splaying algorithms
40(4)
3.3.3 Performance
44(1)
3.4 Tango Tree
45(1)
3.4.1 Creation of tango tree
45(1)
3.4.2 Tango analysis
45(1)
3.5 Skiplists
46(4)
3.5.1 Skipping
47(1)
3.5.2 Dynamic updates
48(1)
3.5.3 Probabilistic analysis of skiplist
49(1)
3.6 Static and Dynamic Optimality
50(2)
3.6.1 Search optimality in BST
50(1)
3.6.2 Static optimality
51(1)
3.6.3 Dynamic optimality
51(1)
3.7 Exercises
52(3)
4 Findset, Find Min, and Find Word
55(28)
4.1 Disjoint Sets
55(5)
4.1.1 Operations on disjoint-set data structure
55(1)
4.1.2 Representations of disjoint sets
56(1)
4.1.3 Link-list representations of disjoint sets
56(2)
4.1.4 Forest representations of disjoint sets
58(2)
4.2 Binomial Heap
60(5)
4.2.1 Creation and updates of binomial heap
61(1)
4.2.2 Operations of Binomial Heap
62(2)
4.2.3 Complexity
64(1)
4.3 Fibonacci Heaps
65(4)
4.3.1 Properties of a Fibonacci heap
65(1)
4.3.2 Inserting, merging, cutting, and marking
65(1)
4.3.3 Decreasing keys and delete-min operation
66(1)
4.3.4 Algorithm for Fibonacci heaps
67(1)
4.3.5 Amortized analysis for Fibonacci heaps
68(1)
4.3.6 Tree size
69(1)
4.4 Tries
69(6)
4.4.1 Insertion
71(1)
4.4.2 Searching
72(1)
4.4.3 Deletion
72(1)
4.4.4 Complexity
73(1)
4.4.5 Compact trie
74(1)
4.4.6 Patricia
74(1)
4.4.7 Suffix tree
75(1)
4.5 Inverted Index
75(3)
4.5.1 Inverted index creation
76(1)
4.5.2 Index compression
77(1)
4.5.3 Key words search
78(1)
4.6 Exercises
78(5)
II Evolving Paradigms
5 Evolving Paradigms of Data Structures
83(6)
5.1 Geometric Queries
83(1)
5.2 I/O Complexities
84(1)
5.3 Communication Complexities
85(1)
5.4 Large Data Problem
86(1)
5.5 Exercise
87(2)
6 Spatial Data Structures
89(18)
6.1 Range Search Trees
89(3)
6.1.1 Construction
90(1)
6.1.2 Range query search
91(1)
6.2 KD Trees
92(4)
6.2.1 Creation of KD tree
92(3)
6.2.2 Range search in KD tree
95(1)
6.2.3 Nearest neighbor search in KD tree
96(1)
6.3 Quadtree
96(5)
6.3.1 Inserting data into a quadtree
97(1)
6.3.2 Properties of quadtree
97(1)
6.3.3 Region quadtree
98(1)
6.3.4 Point quadtree
99(2)
6.4 R Tree
101(3)
6.4.1 Indexing structure of R tree
101(1)
6.4.2 Search in R tree
102(1)
6.4.3 Dynamic update of R tree
103(1)
6.5 Exercises
104(3)
7 Temporal Data Structures
107(10)
7.1 Partial Persistence
107(6)
7.1.1 Partial persistence
108(3)
7.1.2 Full persistence
111(1)
7.1.3 Confluent persistence
112(1)
7.1.4 Functional persistence
112(1)
7.2 Retroactivity
113(2)
7.2.1 Decomposable search problem
114(1)
7.3 Exercises
115(2)
8 External Memory Data Structures
117(18)
8.1 Input/Output (I/O) Model
118(1)
8.2 Cache Oblivious Algorithms
119(1)
8.2.1 Cache aware model
119(1)
8.2.2 Cache oblivious model
119(1)
8.3 B, B+ Tree
120(8)
8.3.1 Searching
121(1)
8.3.2 Insertion
121(2)
8.3.3 Removal
123(2)
8.3.4 Amortized analysis of B trees
125(2)
8.3.5 B+ tree
127(1)
8.4 (a,b) Tree
128(2)
8.4.1 Insertion
129(1)
8.4.2 Deletion
129(1)
8.5 Buffer Tree
130(2)
8.6 Exercises
132(3)
9 Distributed Data Structures (DDSs)
135(14)
9.1 Descriptions of Structures
135(1)
9.1.1 Properties of DDS
136(1)
9.2 Distributed Hashing
136(4)
9.2.1 Structure of distributed hashing
137(3)
9.3 Distributed Trees
140(3)
9.3.1 Construction of distributed BST
141(1)
9.3.2 Insertion
142(1)
9.3.3 Deletion
142(1)
9.3.4 Rotation
143(1)
9.4 Skip Graphs
143(5)
9.4.1 Design
144(1)
9.4.2 Search
145(1)
9.4.3 Insertion
146(1)
9.4.4 Deletion
147(1)
9.4.5 Correctness and concurrency
147(1)
9.5 Exercises
148(1)
10 Synopsis Data Structures
149(20)
10.1 Data Synopsis
149(2)
10.1.1 Synopsis methods
150(1)
10.1.2 Application
151(1)
10.2 Sampling
151(5)
10.2.1 Sampling technique
151(2)
10.2.2 Reservoir sampling
153(2)
10.2.3 Sampling with updates
155(1)
10.2.4 Sliding window sampling
156(1)
10.3 Sketching
156(4)
10.3.1 Count-min sketches
157(3)
10.4 Fingerprint
160(2)
10.4.1 Fingerprinting scheme of Rabin
160(2)
10.5 Wavelets
162(3)
10.5.1 Wavelet decomposition
162(3)
10.6 Exercises
165(4)
III Recent Applications
11 Introduction to Applications
169(2)
11.1 Various Domain Applications
169(1)
11.2 Project
170(1)
12 Applications to Cryptography
171(8)
12.1 MD5
171(2)
12.1.1 Password hashing
172(1)
12.2 Secure Socket Layers (SSLs)
173(1)
12.2.1 Data structure of open SSL
174(1)
12.3 Block Chains
174(1)
12.4 Digital Signature
175(2)
12.5 Projects
177(2)
13 Application to IR and WWW
179(6)
13.1 Crawl Frontier
179(1)
13.2 Posting List Intersection
180(1)
13.3 Text Retrieval from Inverted Index
181(1)
13.4 Auto Complete Using Tries
182(1)
13.5 Projects
183(2)
14 Applications to Data Science
185(6)
14.1 Heavy Hitters and Count-Min Structures
185(1)
14.2 Approximate Nearest Neighbor Searches
186(1)
14.2.1 Approximate nearest neighbor
186(1)
14.2.2 Locality-sensitive hashing (LSH)
186(1)
14.3 Low Rank Approximation by Sampling
187(2)
14.3.1 Nystrom approximation
187(1)
14.3.2 Random sketching
188(1)
14.4 Near-Duplicate Detection by Min Hashing
189(1)
14.5 Projects
189(2)
15 Application to Network and IOT
191(6)
15.1 Click-Stream Processing Using Bloom Filters
191(1)
15.1.1 GBF Algorithm
192(1)
15.2 Fast IP-Address Lookup Using Tries
192(2)
15.3 Integrity Verification: Cloud and IOT Data
194(1)
15.4 Projects
195(2)
16 Applications to Systems
197(6)
16.1 Queue Spilling
197(1)
16.2 Completely Fair Schedulers in Kernels
198(2)
16.2.1 CFS internals
199(1)
16.3 Distributed Caching
200(1)
16.4 Data Structures for Building File Systems
201(1)
16.5 Projects
201(2)
17 Applications to Databases
203(6)
17.1 Database Problems
203(1)
17.1.1 Searching sorted files
203(1)
17.1.2 Index for first search
203(1)
17.1.3 Insertion deletion in database
204(1)
17.2 B and B+ Trees for Database Creation and Block Search
204(1)
17.2.1 Applications of B trees in databases and file systems
205(1)
17.3 CouchDB
205(1)
17.4 Bloomjoins
206(1)
17.5 Projects
207(2)
18 Applications to Images and Graphics
209(8)
18.1 R Trees for Map Searches
209(1)
18.1.1 R trees for mapping
209(1)
18.1.2 Insertion
210(1)
18.1.3 Deletion
210(1)
18.1.4 Search
210(1)
18.2 Spatial Proximity in GIS
210(2)
18.2.1 GIS objects
210(1)
18.2.2 Data access in GIS
211(1)
18.2.3 Computational requirements
211(1)
18.2.4 Solution using k-d tree
211(1)
18.3 Ray Shooting
212(2)
18.3.1 Rays
212(1)
18.3.2 Camera-ray intersections
213(1)
18.3.3 Shadow rays
213(1)
18.3.4 Reflection rays
213(1)
18.3.5 Transmission rays
213(1)
18.3.6 Recursive ray tracing
213(1)
18.3.7 Ray intersection
214(1)
18.3.8 Bounding volume hierarchies
214(1)
18.4 Data Structures Used in Ray Shooting
214(1)
18.4.1 Octrees
214(1)
18.4.2 KD trees
214(1)
18.4.3 BSP trees
215(1)
18.4.4 Uniform grids
215(1)
18.4.5 Hierarchical grids
215(1)
18.5 Projects
215(2)
Bibliography 217(20)
Index 237
Dr. Suman Saha had spent the last 14 years developing as a scientist in the recent research areas of Data and information science covering information retrieval, web mining, decision theory, social network analysis and big data technologies. He started his research in the field of web mining as a senior research scientist in the Center for Soft Computing Research: A National Facility, Indian Statistical Institute, Kolkata, India for a duration of almost five years. After that his research continued as Assistant Professor in the dept. of computer science, Jaypee University of Information Technology, Himachal, India in addition to the teaching and other departmental responsibilities for last eight years. He obtained his PhD from Jaypee University of Information Technology preceded by M.Tech in computer science, from Indian Statistical Institute and M.Sc. in Mathematics, from University of Calcutta. His thesis title is Community Detection in Complex Network: Metric Space, Nearest Neighbor Search, Low-Rank Approximation and Optimality During his last eight years stay at Jaypee University of Information Technology as assistant professor he had taught various courses like advanced web mining, cloud computing, advanced algorithm, fundamentals of algorithm, advanced data structure and many others. He is supervising 2 PhD students and guided around 15 master thesis as well as around 50 bachelor thesis.



Dr. Shailendra Shukla has completed MS-(Information Security) from Indian Institute of Information Technology Allahabad, and then completed PhD from Indian Institute of Technology Patna in computer science. His doctorial work is based on On Boundary Detection and Localization in Wireless Sensor Networks. In this work he proposed a collection of networking algorithms which addresses the security problems like routing in Internet of Things, localization, boundary node detection (surveillance), virtual coordinate assignment (Geography routing/localizations), cyber physical systems, monitoring and surveillance. He has published articles in various publication houses like in Elsevier, Springer, IEEE. Currently he is working as an assistant professor at Jaypee University Waknaghat. He is supervising 2 PhD students and guided 5 master student.
Püsilink: https://www.kriso.ee/db/9780429488757_pe.html
Märksõnad: