Konstantinos Tsakalidis
	Lecturer, Ph.D.
	Department of Computer Science
	University of Liverpool
	Contact Information
	Post: Office 1.13, Ashton Building
	Ashton Street, Liverpool L69 3BX, UK
	Mail: K.Tsakalidis at liverpool.ac.uk

• Algorithm & Data Structures
• Discrete & Computational Geometry
• Graph Algorithms
• Databases & Big Data
  

Teaching:

• COMP222: Principles of Computer Game Design and Implementation
• Online flipped learning with Canvas

Program Committee Member:

• The 37th Symposium on Computational Geometry (SoCG’21)

Links:

1. My DBLP Profile
2. My Google Scholar Profile
3. My LinkedIn Profile

Publications:

14. Optimal deterministic shallow cuttings for 3-d dominance ranges Shallow cuttings are one of the most fundamental tools in range searching as many problems in the field admit efficient static data structures due to their application. We present the first efficient deterministic algorithms that, given n three-dimensional points, construct optimal-size (single and multiple) shallow cuttings for orthogonal dominance ranges. Specifically, we show how to construct a single shallow cutting in O(nlogn) worst-case time, using O(n) space. We also show that the same complexity suffices to construct simultaneously a logarithmic number of shallow cuttings on the input pointset. Our algorithms are optimal in the comparison and algebraic-comparison models, and constitute an important step forwards as the first improvement over previous deterministic polynomial-time guarantees by Matoušek (Comput Geom 2(3):169–186, 1992) and Agarwal et al. (SIAM J Comput 29(3):912–953, 2000) matching the complexity of the optimal deteministic algorithm for the more general 3-d halfspace ranges by Chan and Tsakalidis (Discrete Comput Geom 56(4):866–881, 2016). Our methods yield worst-case efficient preprocessing algorithms for a series of important orthogonal range searching problems in the pointer machine and the word-RAM models, where such shallow cuttings are utilized to support queries efficiently. Konstantinos Tsakalidis, Peyman Afshani Algorithmica 80(11): 3192-3206 (2018). The preliminary version appeared in the proceedings of SODA 2014: 1389-1398

13. Dynamic planar orthogonal point location in sublogarithmic time We study a longstanding problem in computational geometry: dynamic 2-d orthogonal point location, i.e., vertical ray shooting among n horizontal line segments. We present a data structure achieving O(logn/loglogn) optimal expected query time and O(log1/2+εn) update time (amortized) in the word-RAM model for any constant epsilon>0, under the assumption that the x-coordinates are integers bounded polynomially in n. This substantially improves previous results of Giyora and Kaplan [SODA 2007] and Blelloch [SODA 2008] with O(logn) query and update time, and of Nekrich (2010) with O(logn/loglogn) query time and O(log1+εn) update time. Our result matches the best known upper bound for simpler problems such as dynamic 2-d dominance range searching. We also obtain similar bounds for orthogonal line segment intersection reporting queries, vertical ray stabbing, and vertical stabbing-max, improving previous bounds, respectively, of Blelloch [SODA 2008] and Mortensen [SODA 2003], of Tao (2014), and of Agarwal, Arge, and Yi [SODA 2005] and Nekrich [ISAAC 2011]. Timothy M. Chan, Konstantinos Tsakalidis Proceedings of Symposium on Computational Geometry 2018: 25:1-25:15

12. Orthogonal point location and rectangle stabbing queries in 3-d In this work, we present a collection of new results on two fundamental problems in geometric data structures: orthogonal point location and rectangle stabbing. - Orthogonal point location. We give the first linear-space data structure that supports 3-d point location queries on n disjoint axis-aligned boxes with optimal O(logn) query time in the (arithmetic) pointer machine model. This improves the previous O(log3/2n) bound of Rahul [SODA 2015]. We similarly obtain the first linear-space data structure in the I/O model with optimal query cost, and also the first linear-space data structure in the word RAM model with sub-logarithmic query time. - Rectangle stabbing. We give the first linear-space data structure that supports 3-d 4-sided and 5-sided rectangle stabbing queries in optimal O(logwn+k) time in the word RAM model. We similarly obtain the first optimal data structure for the closely related problem of 2-d top-k rectangle stabbing in the word RAM model, and also improved results for 3-d 6-sided rectangle stabbing. For point location, our solution is simpler than previous methods, and is based on an interesting variant of the van Emde Boas recursion, applied in a round-robin fashion over the dimensions, combined with bit-packing techniques. For rectangle stabbing, our solution is a variant of Alstrup, Brodal, and Rauhe's grid-based recursive technique [FOCS 2000], combined with a number of new ideas. Timothy M. Chan, Yakov Nekrich, Saladi Rahul, Konstantinos Tsakalidis Proceedings of ICALP 2018: 31:1-31:14

11. Fuzzy random walkers with second order bounds: an asymmetric analysis Edge-fuzzy graphs constitute an essential modeling paradigm across a broad spectrum of domains ranging from artificial intelligence to computational neuroscience and social network analysis. Under this model, fundamental graph properties such as edge length and graph diameter become stochastic and as such they are consequently expressed in probabilistic terms. Thus, algorithms for fuzzy graph analysis must rely on non-deterministic design principles. One such principle is Random Walker, which is based on a virtual entity and selects either edges or, like in this case, vertices of a fuzzy graph to visit. This allows the estimation of global graph properties through a long sequence of local decisions, making it a viable strategy candidate for graph processing software relying on native graph databases such as Neo4j. As a concrete example, Chebyshev Walktrap, a heuristic fuzzy community discovery algorithm relying on second order statistics and on the teleportation of the Random Walker, is proposed and its performance, expressed in terms of community coherence and number of vertex visits, is compared to the previously proposed algorithms of Markov Walktrap, Fuzzy Walktrap, and Fuzzy Newman–Girvan. In order to facilitate this comparison, a metric based on the asymmetric metrics of Tversky index and Kullback–Leibler divergence is used. Georgios Drakopoulos, Andreas Kanavos, Konstantinos Tsakalidis Algorithms 10(2): 40 (2017)

10. Dynamic orthogonal range searching on the RAM, revisited We study a longstanding problem in computational geometry: 2-d dynamic orthogonal range reporting. We present a new data structure achieving O(logn/loglogn+k) optimal query time and O(log2/3+o(1)n) update time (amortized) in the word RAM model, where n is the number of data points and k is the output size. This is the first improvement in over 10 years of Mortensen's previous result [SIAM J. Comput., 2006], which has O(log7/8+εn) update time for an arbitrarily small constant epsilon. In the case of 3-sided queries, our update time reduces to O(log1/2+εn), improving Wilkinson's previous bound [ESA 2014] of O(log2/3+εn). Timothy M. Chan, Konstantinos Tsakalidis Proceedings of Symposium on Computational Geometry 2017: 28:1-28:13

9. Optimal deterministic algorithms for 2-d and 3-d shallow cuttings We present optimal deterministic algorithms for constructing shallow cuttings in an arrangement of lines in two dimensions or planes in three dimensions. Our results improve the deterministic polynomial-time algorithm of Matoušek (Comput Geom 2(3):169–186, 1992) and the optimal but randomized algorithm of Ramos (Proceedings of the Fifteenth Annual Symposium on Computational Geometry, SoCG’99, 1999). This leads to efficient derandomization of previous algorithms for numerous well-studied problems in computational geometry, including halfspace range reporting in 2-d and 3-d, k nearest neighbors search in 2-d, (&le k) -levels in 3-d, order-k Voronoi diagrams in 2-d, linear programming with k violations in 2-d, dynamic convex hulls in 3-d, dynamic nearest neighbor search in 2-d, convex layers (onion peeling) in 3-d, ε -nets for halfspace ranges in 3-d, and more. As a side product we also describe an optimal deterministic algorithm for constructing standard (non-shallow) cuttings in two dimensions, which is arguably simpler than the known optimal algorithms by Matoušek (Discrete Comput Geom 6(1):385–406, 1991) and Chazelle (Discrete Comput Geom 9(1):145–158, 1993). Timothy M. Chan, Konstantinos Tsakalidis Invited to Discrete & Computational Geometry 56(4): 866-881 (2016). The preliminary version appeared in the proceedings of Symposium on Computational Geometry 2015: 719-732

8. SMaRT: A novel framework for addressing range queries over nonlinear trajectories A spatiotemporal database is a database that manages both space and time information. Common examples include tracking of moving objects, intelligent transportation systems, cellular communications and meteorology monitoring. A spatiotemporal query determines the objects included in a region at a specified period of time between two date-time instants referred as time window. In the context of this work, we present SMaRT: A novel Spatiotemporal Mysql ReTrieval framework, based on MySQL and PostgreSQL database management system. Moreover, we propose a demo user interface that implements all of its capabilities, in order to help user determine the most efficient spatiotemporal query method on user-defined 2D trajectories. To our knowledge, we are the first to study and compare methods of addressing range queries on nonlinear moving object trajectories, that are represented both in dual and native dimensional space. In particular, it is the first time a theoretically efficient dual approach was implemented for nonlinear trajectories and incorporated into a well-known open-source RDBMS. An experimental evaluation is included that shows the performance and efficiency of our approach. Panagiotis Gerolymatos, Spyros Sioutas, Nikolaos Nodarakis, Alexandros Panaretos, Konstantinos Tsakalidis Journal of Systems and Software 105: 79-90 (2015)

7. Dynamic 3-sided planar range queries with expected doubly-logarithmic time 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. Gerth S. Brodal, Alexis C. Kaporis, Apostolos N. Papadopoulos, Spyros Sioutas, Konstantinos Tsakalidis, Kostas Tsichlas Theor. Comput. Sci. 526: 58-74 (2014). Preliminary versions appeared in the proceedings of ICDT 2010: 34-43 and of ISAAC 2009: 193-202

6. Deterministic rectangle enclosure and offline dominance reporting on the RAM We revisit a classical problem in computational geometry that has been studied since the 1980s: in the rectangle enclosure problem we want to report all k enclosing pairs of n input rectangles in 2D. We present the first deterministic algorithm that takes O(nlogn+k) worst-case time and O(n) space in the word-RAM model. This improves previous deterministic algorithms with O((nlogn+k)loglogn) running time. We achieve the result by derandomizing the algorithm of Chan, Larsen and Pătraşcu [SoCG’11] that attains the same time complexity but in expectation. The 2D rectangle enclosure problem is related to the offline dominance range reporting problem in 4D, and our result leads to the currently fastest deterministic algorithm for offline dominance reporting in any constant dimension d &ge 4. A key tool behind Chan et al.’s previous randomized algorithm is shallow cuttings for 3D dominance ranges. Recently, Afshani and Tsakalidis [SODA’14] obtained a deterministic O(nlogn)-time algorithm to construct such cuttings. We first present an improved deterministic construction algorithm that runs in O(nloglogn) time in the word-RAM; this result is of independent interest. Many additional ideas are then incorporated, including a linear-time algorithm for merging shallow cuttings and an algorithm for an offline tree point location problem. Timothy M. Chan, Konstantinos Tsakalidis, Peyman Afshani Proceedings of ICALP (1) 2014: 77-88

5. Compressed persistent index for efficient rank/select queries We design compressed persistent indices that store a bit vector of size n and support a sequence of k bit-flip update operations, such that rank and select queries at any version can be supported efficiently. In particular, we present partially and fully persistent compressed indices for offline and online updates that support all operations in time polylogarithmic in n and k. This improves upon the space or time complexities of straightforward approaches, when k=O(n/logn), which is common in biological applications. We also prove that any partially persistent index that occupies O((n+k)log(nk)) bits requires ω(1) time to support the rank query at a given version. Wing-Kai Hon, Lap-Kei Lee, Kunihiko Sadakane, Konstantinos Tsakalidis Proceedings of WADS 2013: 402-414

4. An improved algorithm for static 3D dominance reporting in the pointer machine We present an efficient algorithm for the pointer machine model that preprocesses a set of n three-dimensional points in O(nlogn) worst case time to construct an O(n) space data structure that supports three-dimensional dominance reporting queries in O(logn+t) worst case time, when t points are reported. Previous results achieved either O(n2) worst case or O(nlogn) expected preprocessing time. The novelty of our approach is that we employ persistent data structures and exploit geometric observations of previous works, in order to achieve a drastic reduction in the worst case preprocessing time. Christos Makris, Konstantinos Tsakalidis Proceedings of ISAAC 2012: 568-577

3. Fully persistent B-trees We present I/O-efficient fully persistent B-Trees that support range searches at any version in O(logBn+t/B) I/Os and updates at any version in O(logBn+log2B) 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(logBm) for the range query complexity and O(logBn) for the update complexity. To achieve the result, we first present a new B-Tree implementation that supports searches and updates in O(logBn) 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 din 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(dinlog2B) amortized I/Os, and the space overhead is O(din/B) amortized blocks. Access to a field of an ephemeral block is supported in O(log2din) worst case I/Os. Gerth S. Brodal, Spyros Sioutas, Konstantinos Tsakalidis, Kostas Tsichlas Proceedings of SODA 2012: 602-614

2. Dynamic planar range maxima queries We consider the dynamic two-dimensional maxima query problem. Let P be a set of n points in the plane. A point is maximal if it is not dominated by any other point in P. We describe two data structures that support the reporting of the t maximal points that dominate a given query point, and allow for insertions and deletions of points in P. In the pointer machine model we present a linear space data structure with O(logn+t) worst case query time and O(logn) worst case update time. This is the first dynamic data structure for the planar maxima dominance query problem that achieves these bounds in the worst case. The data structure also supports the more general query of reporting the maximal points among the points that lie in a given 3-sided orthogonal range unbounded from above in the same complexity. We can support 4-sided queries in O(log2n+t) worst case time, and O(log2n) worst case update time, using O(nlogn) space, where t is the size of the output. This improves the worst case deletion time of the dynamic rectangular visibility query problem from O(log3n) to O(log2n). We adapt the data structure to the RAM model with word size w, where the coordinates of the points are integers in the range U = {0, …,2w  − 1 }. We present a linear space data structure that supports 3-sided range maxima queries in O(logn/loglogn+t) worst case time and updates in O(logn/loglogn) worst case time. These are the first sublogarithmic worst case bounds for all operations in the RAM model. Gerth S. Brodal, Konstantinos Tsakalidis Proceedings of ICALP (1) 2011: 256-267

1. A new approach on indexing mobile objects on the plane We present a set of time-efficient approaches to index objects moving on the plane to efficiently answer range queries about their future positions. Our algorithms are based on previously described solutions as well as on the employment of efficient access methods. Finally, an experimental evaluation is included that shows the performance, scalability and efficiency of our methods. Christos Makris, Yiannis Manolopoulos, Spyros Sioutas, Konstantinos Tsakalidis, Kostas Tsichlas Data Knowl. Eng. 67(3): 362-380 (2008). The preliminary version appeared in the proceedings of ADBIS 2007: 189-204