ABSTRACT
Although the hierarchical structures show marked benefits in searching at lower dimensions, as the dimensionality increases, the performance suffers. For high dimensions (roughly, greater than 8), almost all the nodes are accessed and the overhead of searching becomes so high that a linear scan of the database performs better. In this chapter, we analyze the search in high dimensions and understand this phenomenon called the “curse of dimensionality”.
