@techreport{TR-IC-10-27,
   number = {IC-10-27},
   author  = {Jurandy Almeida and Ricardo da S. Torres and Neucimar J.
                   Leite},
   title  = {{BP-tree:  An  Efficient  Index  for Similarity Search in
                   High-Dimensional Metric Spaces}},
   month = {August},
   year = {2010},
   institution = {Institute of Computing, University of Campinas},
   note = {In English, 8 pages.
    \par\selectlanguage{english}\textbf{Abstract}
       Similarity  search  in  high-dimensional metric spaces is a key
       operation  in  many applications, such as multimedia databases,
       image  retrieval,  object  recognition,  and  others.  The high
       dimensionality of the data requires special index structures to
       facilitate the search. Most of existing indexes are constructed
       by  partitioning  the  data  set using distance-based criteria.
       However,  those methods either produce disjoint partitions, but
       ignore  the  distribution  properties  of  the data; or produce
       non-disjoint   groups,   which   greatly   affect   the  search 
       performance.  In  this paper, we study the performance of a new
       index  structure,  called  Ball-and-Plane tree (BP-tree), which
       overcomes  the  above  disadvantages. BP-tree is constructed by
       recursively  dividing  the  data  set  into  compact  clusters. 
       Distinctive from other techniques, it integrates the advantages
       of both disjoint and non-disjoint paradigms in order to achieve
       a  structure  of  tight  and low overlapping clusters, yielding
       significantly  improved  performance.  Results obtained from an
       extensive  experimental  evaluation  with  real-world data sets
       show  that  BP-tree  consistently  outperforms state-of-the-art
       solutions.
  }
}