This isn’t about the history stored on your computer, this is about the browsing habits observed in real time by eg: ad agencies who get lots of information about where you have been because their ads run everywhere.

Because you visit the same domains across sessions. Throw in some less common domains like HN (i.e. top 1000 instead of top 100 website), and you're trivial to reidentify. (This is what "reidentification" is referring to in the quoted part of the paper in TFA)

Also even if say you and I visit the same exact 100 sites. Order, time on site, sub pages visited, and time of day I use the sites, all can mater. Ad network can also leak out data as you may see a different set of ads than me.