Clustering

We have seen index structures that manifest as trees, hash tables, and graphs. In this chapter, we will introduce a fourth way of organizing data points: clusters. It is perhaps the most natural and the simplest of the four methods, but also the least theoretically-justified. We will see why that is as we describe the details of clustering-based algorithms to top-k retrieval.