Abstract
In this thesis I will address three dynamic data structure problems using the concept of invariants. The first problem is maintaining a dynamically changing set of keys – a dictionary – where the queries we can ask are: does it contain a given key? and what is the preceding (or succeeding) key to a given key? The updates we can do are: inserting a new key or deleting a given key. Our dictionary has the working set property, which means that the running time of a query depends on the query distribution. Specifically the time to search for a key depends on when we last searched for it. Our data structure is implicit, meaning that we do not use any extra space than that of the input keys. Our data structure is implicitly encoded through the permutation of the input keys. Other dictionaries with the working set property have constant factor overhead in the space usage, our dictionary has no overhead and thus has optimal space usage, while still attaining the working set bound. Our result is even cache-oblivious and hence also efficient in external memory.
The second problem is to keep a first-in-first-out queue where each element also has a priority – called a priority queue with attrition. We delete elements at the front and insert elements at the back. When we insert an element then all elements in the queue with an equal or larger priority are deleted – also called attrited. We extend previous solutions by Sundar [Sun89] with the concatenation operation. When we concatenate two queues, all elements in the first queue which are larger or equal to the smallest in the second queue are attrited, and the second queue is appended to the first queue. Our result is also efficient in external memory.
The third problem is to maintain a two-dimensional dynamic point set, where the queries ask for the skyline of the points contained within a rectangular query area, i.e., all the points which have no point above them and to the right, within the query area. These points are called the undominated points of the query area. Our results are the first dynamic results, that are efficient in external memory. The central concept we use, throughout this thesis, to solve data structure problems is invariants. In the design of dynamic data structures we have some set of query and update operations which we want our data structure to support, but we do not choose the order that they are performed in. Invariants are logical statements about our data structure, which are based on the structure of the underlying problem, that we are trying to solve. We can rely on the properties of the invariants when performing queries, and in return we need to ensure that the invariants remain true after we perform updates. When designing data structures there is an interplay between proposing invariants and checking if they can be efficiently maintained in updates and are sufficient for answering queries efficiently. We have solved our data structure problem when we have found a set of "good" invariants that balances these two sides.
The second problem is to keep a first-in-first-out queue where each element also has a priority – called a priority queue with attrition. We delete elements at the front and insert elements at the back. When we insert an element then all elements in the queue with an equal or larger priority are deleted – also called attrited. We extend previous solutions by Sundar [Sun89] with the concatenation operation. When we concatenate two queues, all elements in the first queue which are larger or equal to the smallest in the second queue are attrited, and the second queue is appended to the first queue. Our result is also efficient in external memory.
The third problem is to maintain a two-dimensional dynamic point set, where the queries ask for the skyline of the points contained within a rectangular query area, i.e., all the points which have no point above them and to the right, within the query area. These points are called the undominated points of the query area. Our results are the first dynamic results, that are efficient in external memory. The central concept we use, throughout this thesis, to solve data structure problems is invariants. In the design of dynamic data structures we have some set of query and update operations which we want our data structure to support, but we do not choose the order that they are performed in. Invariants are logical statements about our data structure, which are based on the structure of the underlying problem, that we are trying to solve. We can rely on the properties of the invariants when performing queries, and in return we need to ensure that the invariants remain true after we perform updates. When designing data structures there is an interplay between proposing invariants and checking if they can be efficiently maintained in updates and are sufficient for answering queries efficiently. We have solved our data structure problem when we have found a set of "good" invariants that balances these two sides.
| Translated title of the contribution | Dynamiske Datastrukturer: Samspillet mellem Invarianter og Algoritmedesign |
|---|---|
| Original language | English |
| Publisher | Department of Computer Science, Aarhus University |
|---|---|
| Number of pages | 94 |
| Publication status | Published - 2013 |
Keywords
- invariants
- I/O efficient
- cache-oblivious
- data structures
- dictionary
- external memory
- implicit
- priority queues
- range reporting
- skyline
- working-set property
- worst-case