ABSTRACT
This part introduction presents an overview of the key concepts discussed in the subsequent chapters. The part presents structures of various data domains in a problem-specific arrangement. It describes various data structures: spatial, temporal, external memory, distributed, and synopsis types. The part introduces data structures designed to handle spatial data. It begins by explaining range queries and suggests four popular solutions: range search trees, KD trees, quadtrees and R trees. The part explores lesser known temporal data structures: partial, full, confluent, and functional persistent types. It focuses on distributed data structures and the difficulties of implementing them, then explains distributed hashing, distributed lists and trees, and skip graphs. The part proposes synopsis data structures designed to deal with large amounts of streaming data. Specific sections discuss sampling, sketching, fingerprints, and wavelets. The part explains theoretical bounds, examples, and construction details.
