Lecture Notes: Best-first Algorithm

The R-tree is one of the (very) few multi-dimensional indexes that have been incorporated in a commercial database system (e.g., Oracle, DB2, Informix, etc.). Therefore, it is an important research topic to design efficient algorithms for R-trees that can be easily implemented. Such algorithms enhance the power of a commercial system, thus having immediate impacts in practice. In this lecture, we will study a well-known method called best-first (BF) search, which has been applied extensively to solve a large number of problems with R-trees. A crucial feature of the method is that it can be used to design optimal algorithms (we will clarify the notion of optimality later). We will discuss it in the context of nearest neighbor (NN) search. 1 Best-first algorithm Let P be a set of 2d points. The NN problem is to find the point p ∈ P that is the closest to a query point q. For example, assume that P consists of p1,..., p13, as in Figure 1a. Then, the result of the NN query q is p3. Next, we will explain how a BF algorithm [1] uses the R-tree in Figure 1b to answer the query