Kooperativer Bibliotheksverbund

UID:

Format: 1 online resource (xix, 553 pages) : , digital, PDF file(s).

ISBN: 1-316-78956-X , 1-316-79292-7 , 1-316-58828-9

Content: Compact data structures help represent data in reduced space while allowing it to be queried, navigated, and operated in compressed form. They are essential tools for efficiently handling massive amounts of data by exploiting the memory hierarchy. They also reduce the resources needed in distributed deployments and make better use of the limited memory in low-end devices. The field has developed rapidly, reaching a level of maturity that allows practitioners and researchers in application areas to benefit from the use of compact data structures. This first comprehensive book on the topic focuses on the structures that are most relevant for practical use. Readers will learn how the structures work, how to choose the right ones for their application scenario, and how to implement them. Researchers and students in the area will find in the book a definitive guide to the state of the art in compact data structures.

Note: Title from publisher's bibliographic system (viewed on 06 Sep 2016). , Cover -- Half title -- Title -- Copyright -- Dedication -- Contents -- List of Algorithms -- Foreword -- Acknowledgments -- 1 Introduction -- 1.1 Why Compact Data Structures? -- 1.2 Why This Book? -- 1.3 Organization -- 1.4 Software Resources -- 1.5 Mathematics and Notation -- 1.6 Bibliographic Notes -- 2 Entropy and Coding -- 2.1 Worst-Case Entropy -- 2.2 Shannon Entropy -- 2.3 Empirical Entropy -- 2.3.1 Bit Sequences -- 2.3.2 Sequences of Symbols -- 2.4 High-Order Entropy -- 2.5 Coding -- 2.6 Huffman Codes -- 2.6.1 Construction -- 2.6.2 Encoding and Decoding -- 2.6.3 Canonical Huffman Codes -- 2.6.4 Better than Huffman -- 2.7 Variable-Length Codes for Integers -- 2.8 Jensen's Inequality -- 2.9 Application: Positional Inverted Indexes -- 2.10 Summary -- 2.11 Bibliographic Notes -- 3 Arrays -- 3.1 Elements of Fixed Size -- 3.2 Elements of Variable Size -- 3.2.1 Sampled Pointers -- 3.2.2 Dense Pointers -- 3.3 Partial Sums -- 3.4 Applications -- 3.4.1 Constant-Time Array Initialization -- 3.4.2 Direct Access Codes -- 3.4.3 Elias-Fano Codes -- 3.4.4 Differential Encodings and Inverted Indexes -- 3.4.5 Compressed Text Collections -- 3.5 Summary -- 3.6 Bibliographic Notes -- 4 Bitvectors -- 4.1 Access -- 4.1.1 Zero-Order Compression -- 4.1.2 High-Order Compression -- 4.2 Rank -- 4.2.1 Sparse Sampling -- 4.2.2 Constant Time -- 4.2.3 Rank on Compressed Bitvectors -- 4.3 Select -- 4.3.1 A Simple Heuristic -- 4.3.2 An O(log log n) Time Solution -- 4.3.3 Constant Time -- 4.4 Very Sparse Bitvectors -- 4.4.1 Constant-Time Select -- 4.4.2 Solving Rank -- 4.4.3 Bitvectors with Runs -- 4.5 Applications -- 4.5.1 Partial Sums Revisited -- 4.5.2 Predecessors and Successors -- 4.5.3 Dictionaries, Sets, and Hashing -- 4.6 Summary -- 4.7 Bibliographic Notes -- 5 Permutations -- 5.1 Inverse Permutations -- 5.2 Powers of Permutations -- 5.3 Compressible Permutations. , 5.4 Applications -- 5.4.1 Two-Dimensional Points -- 5.4.2 Inverted Indexes Revisited -- 5.5 Summary -- 5.6 Bibliographic Notes -- 6 Sequences -- 6.1 Using Permutations -- 6.1.1 Chunk-Level Granularity -- 6.1.2 Operations within a Chunk -- 6.1.3 Construction -- 6.1.4 Space and Time -- 6.2 Wavelet Trees -- 6.2.1 Structure -- 6.2.2 Solving Rank and Select -- 6.2.3 Construction -- 6.2.4 Compressed Wavelet Trees -- 6.2.5 Wavelet Matrices -- 6.3 Alphabet Partitioning -- 6.4 Applications -- 6.4.1 Compressible Permutations Again -- 6.4.2 Compressed Text Collections Revisited -- 6.4.3 Non-positional Inverted Indexes -- 6.4.4 Range Quantile Queries -- 6.4.5 Revisiting Arrays of Variable-Length Cells -- 6.5 Summary -- 6.6 Bibliographic Notes -- 7 Parentheses -- 7.1 A Simple Implementation -- 7.1.1 Range Min-Max Trees -- 7.1.2 Forward and Backward Searching -- 7.1.3 Range Minima and Maxima -- 7.1.4 Rank and Select Operations -- 7.2 Improving the Complexity -- 7.2.1 Queries inside Buckets -- 7.2.2 Forward and Backward Searching -- 7.2.3 Range Minima and Maxima -- 7.2.4 Rank and Select Operations -- 7.3 Multi-Parenthesis Sequences -- 7.3.1 Nearest Marked Ancestors -- 7.4 Applications -- 7.4.1 Succinct Range Minimum Queries -- 7.4.2 XML Documents -- 7.5 Summary -- 7.6 Bibliographic Notes -- 8 Trees -- 8.1 LOUDS: A Simple Representation -- 8.1.1 Binary and Cardinal Trees -- 8.2 Balanced Parentheses -- 8.2.1 Binary Trees Revisited -- 8.3 DFUDS Representation -- 8.3.1 Cardinal Trees Revisited -- 8.4 Labeled Trees -- 8.5 Applications -- 8.5.1 Routing in Minimum Spanning Trees -- 8.5.2 Grammar Compression -- 8.5.3 Tries -- 8.5.4 LZ78 Compression -- 8.5.5 XML and XPath -- 8.5.6 Treaps -- 8.5.7 Integer Functions -- 8.6 Summary -- 8.7 Bibliographic Notes -- 9 Graphs -- 9.1 General Graphs -- 9.1.1 Using Bitvectors -- 9.1.2 Using Sequences -- 9.1.3 Undirected Graphs. , 9.1.4 Labeled Graphs -- 9.1.5 Construction -- 9.2 Clustered Graphs -- 9.2.1 K[sup(2)]-Tree Structure -- 9.2.2 Queries -- 9.2.3 Reducing Space -- 9.2.4 Construction -- 9.3 K-Page Graphs -- 9.3.1 One-Page Graphs -- 9.3.2 K-Page Graphs -- 9.3.3 Construction -- 9.4 Planar Graphs -- 9.4.1 Orderly Spanning Trees -- 9.4.2 Triangulations -- 9.4.3 Construction -- 9.5 Applications -- 9.5.1 Binary Relations -- 9.5.2 RDF Datasets -- 9.5.3 Planar Routing -- 9.5.4 Planar Drawings -- 9.6 Summary -- 9.7 Bibliographic Notes -- 10 Grids -- 10.1 Wavelet Trees -- 10.1.1 Counting -- 10.1.2 Reporting -- 10.1.3 Sorted Reporting -- 10.2 K[sup(2)]-Trees -- 10.2.1 Reporting -- 10.3 Weighted Points -- 10.3.1 Wavelet Trees -- 10.3.2 K[sup(2)]-Trees -- 10.4 Higher Dimensions -- 10.5 Applications -- 10.5.1 Dominating Points -- 10.5.2 Geographic Information Systems -- 10.5.3 Object Visibility -- 10.5.4 Position-Restricted Searches on Suffix Arrays -- 10.5.5 Searching for Fuzzy Patterns -- 10.5.6 Indexed Searching in Grammar-Compressed Text -- 10.6 Summary -- 10.7 Bibliographic Notes -- 11 Texts -- 11.1 Compressed Suffix Arrays -- 11.1.1 Replacing A with Ψ -- 11.1.2 Compressing Ψ -- 11.1.3 Backward Search -- 11.1.4 Locating and Displaying -- 11.2 The FM-Index -- 11.3 High-Order Compression -- 11.3.1 The Burrows-Wheeler Transform -- 11.3.2 High-Order Entropy -- 11.3.3 Partitioning L into Uniform Chunks -- 11.3.4 High-Order Compression of Ψ -- 11.4 Construction -- 11.4.1 Suffix Array Construction -- 11.4.2 Building the BWT -- 11.4.3 Building Ψ -- 11.5 Suffix Trees -- 11.5.1 Longest Common Prefixes -- 11.5.2 Suffix Tree Operations -- 11.5.3 A Compact Representation -- 11.5.4 Construction -- 11.6 Applications -- 11.6.1 Finding Maximal Substrings of a Pattern -- 11.6.2 Labeled Trees Revisited -- 11.6.3 Document Retrieval -- 11.6.4 XML Retrieval Revisited -- 11.7 Summary. , 11.8 Bibliographic Notes -- 12 Dynamic Structures -- 12.1 Bitvectors -- 12.1.1 Solving Queries -- 12.1.2 Handling Updates -- 12.1.3 Compressed Bitvectors -- 12.2 Arrays and Partial Sums -- 12.3 Sequences -- 12.4 Trees -- 12.4.1 LOUDS Representation -- 12.4.2 BP Representation -- 12.4.3 DFUDS Representation -- 12.4.4 Dynamic Range Min-Max Trees -- 12.4.5 Labeled Trees -- 12.5 Graphs and Grids -- 12.5.1 Dynamic Wavelet Matrices -- 12.5.2 Dynamic k[sup(2)]-Trees -- 12.6 Texts -- 12.6.1 Insertions -- 12.6.2 Document Identifiers -- 12.6.3 Samplings -- 12.6.4 Deletions -- 12.7 Memory Allocation -- 12.8 Summary -- 12.9 Bibliographic Notes -- 13 Recent Trends -- 13.1 Encoding Data Structures -- 13.1.1 Effective Entropy -- 13.1.2 The Entropy of RMQs -- 13.1.3 Expected Effective Entropy -- 13.1.4 Other Encoding Problems -- 13.2 Repetitive Text Collections -- 13.2.1 Lempel-Ziv Compression -- 13.2.2 Lempel-Ziv Indexing -- 13.2.3 Faster and Larger Indexes -- 13.2.4 Compressed Suffix Arrays and Trees -- 13.3 Secondary Memory -- 13.3.1 Bitvectors -- 13.3.2 Sequences -- 13.3.3 Trees -- 13.3.4 Grids and Graphs -- 13.3.5 Texts -- Index.

Additional Edition: ISBN 1-107-15238-0

Language: English