Event streaming is an increasingly critical infrastructure service used in many industries and there is growing demand for cloud-native solutions. Confluent Cloud provides a massive scale event streaming platform built on top of Apache Kafka with tens of thousands of clusters running in 70+ regions across AWS, Google Cloud, and Azure. This paper introduces Kora , the cloud-native platform for Apache Kafka at the core of Confluent Cloud. We describe Kora's design that enables it to meet its cloud-native goals, such as reliability, elasticity, and cost efficiency. We discuss Kora's abstractions which allow users to think in terms of their workload requirements and not the underlying infrastructure, and we discuss how Kora is designed to provide consistent, predictable performance across cloud environments with diverse capabilities.

The k -means method is one of the most widely used clustering algorithms, drawing its popularity from its speed in practice. Recently, however, it was shown to have exponential worst-case running time. In order to close the gap between practical performance and theoretical analysis, the k -means method has been studied in the model of smoothed analysis. But even the smoothed analyses so far are unsatisfactory as the bounds are still super-polynomial in the number n of data points. In this article, we settle the smoothed running time of the k -means method. We show that the smoothed number of iterations is bounded by a polynomial in n and 1/ σ , where σ is the standard deviation of the Gaussian perturbations. This means that if an arbitrary input data set is randomly perturbed, then the k -means method will run in expected polynomial time on that input set.

The k-means method is one of the most widely used clustering algorithms, drawing its popularity from its speed in practice. Recently, however, it was shown to have exponential worst-case running time. In order to close the gap between practical performance and theoretical analysis, the k-means method has been studied in the model of smoothed analysis. But even the smoothed analyses so far are unsatisfactory as the bounds are still super-polynomial in the number n of data points. In this paper, we settle the smoothed running time of the k-means method. We show that the smoothed number of iterations is bounded by a polynomial in n and 1/sigma, where sigma is the standard deviation of the Gaussian perturbations. This means that if an arbitrary input data set is randomly perturbed, then the k-means method will run in expected polynomial time on that input set.

We show a worst-case lower bound and a smoothed upper bound on the number of iterations performed by the Iterative Closest Point (ICP) algorithm. First proposed by Besl and McKay, the algorithm is widely used in computational geometry, where it is known for its simplicity and its observed speed. The theoretical study of ICP was initiated by Ezra, Sharir, and Efrat, who showed that the worst-case running time to align two sets of n points in $\mathbb{R}^d$ is between $\Omega(n\log n)$ and $O(n^2d)^d$. We substantially tighten this gap by improving the lower bound to $\Omega(n/d)^{d+1}$. To help reconcile this bound with the algorithm's observed speed, we also show that the smoothed complexity of ICP is polynomial, independent of the dimensionality of the data. Using similar methods, we improve the best known smoothed upper bound for the popular k-means method to $n^{O(k)}$, once again independent of the dimension.

The k-means method is an old but popular clustering algorithm known for its observed speed and its simplicity. Until recently, however, no meaningful theoretical bounds were known on its running time. In this paper, we demonstrate that the worst-case running time of k-means is superpolynomial by improving the best known lower bound from Ω(n) iterations to 2Ω(√n).

We show a worst-case lower bound and a smoothed upper bound on the number of iterations performed by the iterative closest point (ICP) algorithm. First proposed by Besl and McKay, the algorithm is widely used in computational geometry where it is known for its simplicity and its observed speed. The theoretical study of ICP was initiated by Ezra, Sharir and Efrat, who bounded its worst-case running time between Omega(n log n) and O(n2d)d. We substantially tighten this gap by improving the lower bound to Omega(n/d)d+1. To help reconcile this bound with the algorithm's observed speed, we also show the smoothed complexity of ICP is polynomial, independent of the dimensionality of the data. Using similar methods, we improve the best known smoothed upper bound for the popular k-means method to nO(k)once again independent of the dimension