  The input to the $k$-median for lines problem is a set $L$ of $n$ lines in
$\mathbb{R}^d$, and the goal is to compute a set of $k$ centers (points) in
$\mathbb{R}^d$ that minimizes the sum of squared distances over every line in
$L$ and its nearest center. This is a straightforward generalization of the
$k$-median problem where the input is a set of $n$ points instead of lines.
  We suggest the first PTAS that computes a $(1+\epsilon)$-approximation to
this problem in time $O(n \log n)$ for any constant approximation error
$\epsilon \in (0, 1)$, and constant integers $k, d \geq 1$. This is by proving
that there is always a weighted subset (called coreset) of $dk^{O(k)}\log
(n)/\epsilon^2$ lines in $L$ that approximates the sum of squared distances
from $L$ to any given set of $k$ points.
  Using traditional merge-and-reduce technique, this coreset implies results
for a streaming set (possibly infinite) of lines to $M$ machines in one pass
(e.g. cloud) using memory, update time and communication that is
near-logarithmic in $n$, as well as deletion of any line but using linear
space. These results generalized for other distance functions such as
$k$-median (sum of distances) or ignoring farthest $m$ lines from the given
centers to handle outliers.
  Experimental results on 10 machines on Amazon EC2 cloud show that the
algorithm performs well in practice. Open source code for all the algorithms
and experiments is also provided.
  This thesis is an extension of the following accepted paper: "$k$-Means
Clustering of Lines for Big Data", by Yair Marom & Dan Feldman, Proceedings of
NeurIPS 2019 conference, to appear on December 2019.
