Foundations of multidimensional and metric data structures. (Q2488572): Difference between revisions

This book provides a thorough treatment of data structures for storing and manipulating multidimensional data. Organization of multidimensional data, or data extracted from a higher dimensional space, is of fundamental importance in databases, image processing, vision, data mining, CAD, VLSI design, and many other fields. The book is organized in four encyclopedic chapters. The first one deals with the representation of point data. Data structures are classified in two main groups depending on whether they represent and organize the data or the space from which the data is extracted. A significant portion of the chapter deals with the case of massive data sets that do not fit in main memory and, thus, must reside in disk. Chapter 2 deals with representations of objects. Manipulation of objects is very important in areas like vision, modelling, and spatial databases. Two main classes of queries are the central topic of this chapter: what is the location of a particular object? and what object is located at a particular position? Chapter 3 focuses on representations of intervals and rectangles. These representations are of fundamental relevance for VLSI design, CAD, and any other applications dealing with temporal data or moving objects (like game programming). The chapter focuses on representations for large collections of rectangles and emphasis is placed on how to solve proximity queries. Chapter 4 deals with very high dimensional data, like that arising from multi-media applications where objects are described through a large collection of features like color, textures, shape descriptions, and so on. The chapter centers on solutions for the similarity searching problem, where the goal is to find groups of ``similar'' objects. Three appendices at the end of the book contain tutorials on B-trees, linear hashing, and spiral hashing. This book is not for everyone. It will be a valuable reference for those professionals dealing with the representation of multidimensional data. The book might also be appropriate for teaching a graduate level course on multidimensional data structures. Prior knowledge of unidimensional data structures, algorithm design and analysis is required to fully enjoy this work. Descriptions of data structures and algorithms are clear and very concise. The use of pseudocode is very convenient as it makes it considerably easier for the reader to understand some of the algorithms contained in the book. The author also has taken the time to provide a large number of examples showing how some of the most complex data structures and algorithms work. He has also spent considerable effort including a large number of figures to carefully illustrate the workings and organization of a number of data structures. Exercises are liberally provided and the solutions are given at the end of the book. Even though the main focus of the author is on the algorithmic aspects of the solutions for the problems considered in the book, there is also extensive formal mathematical treatment of the algorithms and data structures. The author analyzes the time and space complexity of many of the algorithms and data structures presented in the book. It also compares the performance of different data structures and gives indications on where one is superior to the other. The book contains a remarkably large amount of information. Throughout the text most of the over 2000 references are cited by providing concise descriptions of them and how they are related to the material that is being presented. Overall, this is a must have reference for anyone interested in organization and manipulation of multidimensional data.