@article {16835,
	title = {Metric space similarity joins},
	journal = {ACM Trans. Database Syst.},
	volume = {33},
	year = {2008},
	month = {2008/06//},
	pages = {7:1{\textendash}7:38 - 7:1{\textendash}7:38},
	abstract = {Similarity join algorithms find pairs of objects that lie within a certain distance ε of each other. Algorithms that are adapted from spatial join techniques are designed primarily for data in a vector space and often employ some form of a multidimensional index. For these algorithms, when the data lies in a metric space, the usual solution is to embed the data in vector space and then make use of a multidimensional index. Such an approach has a number of drawbacks when the data is high dimensional as we must eventually find the most discriminating dimensions, which is not trivial. In addition, although the maximum distance between objects increases with dimension, the ability to discriminate between objects in each dimension does not. These drawbacks are overcome via the introduction of a new method called Quickjoin that does not require a multidimensional index and instead adapts techniques used in distance-based indexing for use in a method that is conceptually similar to the Quicksort algorithm. A formal analysis is provided of the Quickjoin method. Experiments show that the Quickjoin method significantly outperforms two existing techniques.},
	keywords = {distance-based indexing, external memory algorithms, nearest neighbor queries, range queries, Ranking, Similarity join},
	isbn = {0362-5915},
	doi = {10.1145/1366102.1366104},
	url = {http://doi.acm.org/10.1145/1366102.1366104},
	author = {Jacox,Edwin H. and Samet, Hanan}
}
@article {16892,
	title = {Improved search heuristics for the sa-tree},
	journal = {Pattern Recognition Letters},
	volume = {24},
	year = {2003},
	month = {2003/11//},
	pages = {2785 - 2795},
	abstract = {The sa-tree is an interesting metric space indexing structure that is inspired by the Voronoi diagram. In essence, the sa-tree records a portion of the Delaunay graph of the data set, a graph whose vertices are the Voronoi cells, with edges between adjacent cells. An improvement is presented on the original search strategy for the sa-tree. This consists of details on the intuition behind the improvement as well as the original search strategy and a proof of their correctness. Furthermore, it is shown how to adapt an incremental nearest neighbor algorithm to the sa-tree, which allows computing nearest neighbor in a progressive manner. Unlike other adaptations, the resulting algorithm does not take the unnecessary steps to ensure that keys of {\textquotedblleft}node{\textquotedblright} elements are monotonically non-decreasing.},
	keywords = {distance-based indexing, Metric spaces, Nearest neighbor algorithms},
	isbn = {0167-8655},
	doi = {10.1016/S0167-8655(03)00122-3},
	url = {http://www.sciencedirect.com/science/article/pii/S0167865503001223},
	author = {Hjaltason,G{\i}́sli R. and Samet, Hanan}
}
@article {16891,
	title = {Index-driven similarity search in metric spaces (Survey Article)},
	journal = {ACM Trans. Database Syst.},
	volume = {28},
	year = {2003},
	month = {2003/12//},
	pages = {517 - 580},
	abstract = {Similarity search is a very important operation in multimedia databases and other database applications involving complex objects, and involves finding objects in a data set S similar to a query object q, based on some similarity measure. In this article, we focus on methods for similarity search that make the general assumption that similarity is represented with a distance metric d. Existing methods for handling similarity search in this setting typically fall into one of two classes. The first directly indexes the objects based on distances (distance-based indexing), while the second is based on mapping to a vector space (mapping-based approach). The main part of this article is dedicated to a survey of distance-based indexing methods, but we also briefly outline how search occurs in mapping-based methods. We also present a general framework for performing search based on distances, and present algorithms for common types of queries that operate on an arbitrary "search hierarchy." These algorithms can be applied on each of the methods presented, provided a suitable search hierarchy is defined.},
	keywords = {distance-based indexing, Hiearchical metric data structures, nearest neighbor queries, range queries, Ranking, similarity searching},
	isbn = {0362-5915},
	doi = {10.1145/958942.958948},
	url = {http://doi.acm.org/10.1145/958942.958948},
	author = {Hjaltason,Gisli R. and Samet, Hanan}
}
