Advanced Data Structures

Theory and Applications

Suman Saha, Shailendra Shukla

• Publisher: Chapman and Hall/CRC
• Year: 2019
• ISBN:
  9780429949845
• Edition: 1
• Topic: Informatik
• Subtopic: Informatik Allgemein

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.

Part I

Theoretical Advancements

Chapter 1

Introduction

This book emphasises recent theoretical developments, evolving data structures for different paradigms of computations and important applications to research domains of computer science. The whole book is divided into three parts. As an introduction, the need for advanced data structures and some basic concepts pertaining to amortized analysis of algorithms have been presented in the first chapter.

Part I details advancements on basic data structures, for example, cuckoo hashing, skiplists, tango trees and Fibonacci heaps and index files. Part II details data structures of different evolving data domains such as 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 such as networks, the World Wide Web, database management systems (DBMSs), cryptography, and graphics to name a few. The concepts and techniques behind each data structure and their applications have been explained. Illustrative problems, review questions, and programming assignments are included to enable the students comprehend, implement and appreciate advanced data structures. In addition to illustrative problems, each chapter includes a detailed summary of the technical content and list of review questions to reinforced comprehension of the material.

Objective 1.1 — Advanced data structure. The rapid development of different domains (e.g. data science, the Internet of Things (IOT), artificial intelligence (AI), machine learning (ML), cloud computing and others) of computer science imposes new challenges to the field of data structures and algorithms. The traditional data structures are mainly developed to perform sequential point search on RAM models and assessment based on computational complexity is insufficient to meet the requirements of modern computer science. In this book we have incorporated important data structural concepts to be taught as an advanced course on data structure intended to meet contemporary computational challenges.

We assume students understand basic data structures like arrays, link lists, stacks, queues, trees, hashing, and other relevant concepts of data structures and algorithms. Those materials are not included in this book, but their advancements are demonstrated along with the other advanced topics.

In this chapter, the need for advanced data structures and some basic concepts pertaining to design of data structures, amortized analysis of queries over data structures and how to use data structures to solve computational problems have been presented. The last section of the chapter is included to describe organization of the book.

1.1 Data Structure

A data structure is a typical way of organizing data in a computer so that it can be accessed efficiently [1].

Definition 1.1.1 — Data structure. A data structure is an organization of data values, the relationships among them, and the functions to answer particular queries on that data.

A data structure can implement one or many abstract data types (ADT), which specify the operations that can be performed in that data structure. Moreover, the computational complexity of those operations, described in the ADT will be adopted in the data structure. In comparison, a data structure is a real implementation of the theoretical specification abstracted in an ADT.

Definition 1.1.2 — Abstract data type. An abstract data type (ADT) is a mathematical abstraction about data and its functions.

Different kinds of data structures are generally used in different problems. A data structure can implement an abstract data types, and adopt the specifications of operations and complexities. Different application tasks are often solved using various types of data structures, some of which are highly specialized for specific tasks. Data structures provide mechanisms to organize and manage large amounts of data efficiently for several uses in most domains of computer science. T...