Konstantinos Tsakalidis

TCS Journal 2020 Journal Article

Fully persistent B-trees

• Gerth Stølting Brodal
• Spyros Sioutas
• Konstantinos Tsakalidis
• Kostas Tsichlas

We present efficient fully persistent B-trees in the I/O model with block size B that support range searches on t reported elements at any accessed version of size n in O ( log B ⁡ n + t / B ) I/Os and updates at any accessed version in O ( log B ⁡ n + log 2 ⁡ B ) amortized I/Os, using O ( m / B ) disk blocks after m updates. This improves both the query and update I/O-efficiency of the previous fully persistent B-trees of Lanka and Mays (ACM SIGMOD ICMD 1991). To achieve the result, we introduce an implementation for ephemeral B-trees that supports searches and updates in O ( log B ⁡ n ) I/Os, using O ( n / B ) blocks, where moreover every update makes a worst-case constant number of modifications to the structure. We make these B-trees fully persistent using an I/O-efficient method for full persistence, inspired by the node-splitting method of Driscoll et al. (JCSS 1989). Interesting in its own right, the method is generic enough to be applied to any external memory pointer-based data structure with maximum in-degree d i n and out-degree O ( B ), where every node occupies a constant number of blocks on disk. For a user-specified parameter π = Ω ( d i n ), we achieve O ( π B + log 2 ⁡ π ) I/O-overhead per access to a field of an ephemeral block and amortized O ( π B + log 2 ⁡ π + d i n π log 2 ⁡ B ) I/O-overhead and O ( 1 / B ) block space-overhead per modification to the ephemeral structure.

TCS Journal 2014 Journal Article

Dynamic 3-sided planar range queries with expected doubly-logarithmic time

• Gerth Stølting Brodal
• Alexis C. Kaporis
• Apostolos N. Papadopoulos
• Spyros Sioutas
• Konstantinos Tsakalidis
• Kostas Tsichlas

The Priority Search Tree is the classic solution for the problem of dynamic 2-dimensional searching for the orthogonal query range of the form [ a, b ] × ( − ∞, c ] (3-sided rectangle). It supports all operations in logarithmic worst case complexity in both main and external memory. In this work we show that the update and query complexities can be improved to expected doubly-logarithmic, when the input coordinates are being continuously drawn from specific probability distributions. We present three pairs of linear space solutions for the problem, i. e. a RAM and a corresponding I/O model variant: (1) First, we improve the update complexity to doubly-logarithmic expected with high probability, under the most general assumption that both the x- and y-coordinates of the input points are continuously being drawn from a distribution whose density function is unknown but fixed. (2) Next, we improve both the query complexity to doubly-logarithmic expected with high probability and the update complexity to doubly-logarithmic amortized expected, by assuming that only the x-coordinates are being drawn from a class of smooth distributions, and that the deleted points are selected uniformly at random among the currently stored points. In fact, the y-coordinates are allowed to be arbitrarily distributed. (3) Finally, we improve both the query and the update complexity to doubly-logarithmic expected with high probability by moreover assuming the y-coordinates to be continuously drawn from a more restricted class of realistic distributions. All data structures are deterministic and their complexity's expectation is with respect to the assumed distributions. They comprise combinations of known data structures and of two new data structures introduced here, namely the Weight Balanced Exponential Tree and the External Modified Priority Search Tree.

SODA Conference 2014 Conference Paper

Optimal Deterministic Shallow Cuttings for 3D Dominance Ranges

• Peyman Afshani
• Konstantinos Tsakalidis

SODA Conference 2012 Conference Paper

Fully persistent B-trees

• Gerth Stølting Brodal
• Konstantinos Tsakalidis
• Spyros Sioutas
• Kostas Tsichlas

We present I/O-efficient fully persistent B-Trees that support range searches at any version in O (log B n + t/B ) I/Os and updates at any version in O (log B n + log 2 B ) amortized I/Os, using space O ( m/B ) disk blocks. By n we denote the number of elements in the accessed version, by m the total number of updates, by t the size of the query's output, and by B the disk block size. The result improves the previous fully persistent B-Trees of Lanka and Mays by a factor of O (log B m ) for the range query complexity and O (log B n ) for the update complexity. To achieve the result, we first present a new B-Tree implementation that supports searches and updates in O (log B n ) I/Os, using O ( n/B ) blocks of space. Moreover, every update makes in the worst case a constant number of modifications to the data structure. We make these B-Trees fully persistent using an I/O-efficient method for full persistence that is inspired by the node-splitting method of Driscoll et al. The method we present is interesting in its own right and can be applied to any external memory pointer based data structure with maximum in-degree d in bounded by a constant and out-degree bounded by O ( B ), where every node occupies a constant number of blocks on disk. The I/O-overhead per modification to the ephemeral structure is O ( d in log 2 B ) amortized I/Os, and the space overhead is O ( d in /B ) amortized blocks. Access to a field of an ephemeral block is supported in O (log 2 d in ) worst case I/Os.