Static Optimality Theorem for External Memory String Access

Data warehouses are increasingly storing and managing large scale string data, and dealing with large volume of transactions that update and search string data. Motivated by this context, we initiate the study of self-adjusting data structures for string dictionary operations, that is, data structures that are designed to be efficient on an entire sequence rather than individual string operations. Furthermore, we study this problem in the external memory model where string data is too massive to be stored in internal memory and has to reside in disks; each access to a disk page fetches B items, and the cost of the operations is the number of pages accessed (I/Os).

Authors

• Valentina Ciriani
• Paolo Ferragina
• Fabrizio Luccio
• S. Muthukrishnan 0001

Keywords

• XML
• Dictionaries
• Data warehouses
• Data structures
• Character generation
• Transaction databases
• Internet
• Navigation
• Tree graphs
• Large-scale systems
• External Memory
• External Access
• Memory String
• Data Structure
• Numerical Values
• Operational Costs
• Query Sequence
• Sequence Search
• Binary String
• Data Warehouse
• Tree Search
• String Length
• Internal Memory
• Classic Paper
• Random Selection
• Lower Band
• Reachable
• Head And Tail
• Search Procedure
• Part Of Column
• Search Operations
• Deterministic Part
• Random Part
• Lexicographic
• Cost Of Access