@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 {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}
}
@conference {17880,
	title = {Optimizing retrieval and processing of multi-dimensional scientific datasets},
	booktitle = {Parallel and Distributed Processing Symposium, 2000. IPDPS 2000. Proceedings. 14th International},
	year = {2000},
	month = {2000///},
	pages = {405 - 410},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {We have developed the Active Data Repository (ADR), an infrastructure that integrates storage, retrieval, and processing of large multi-dimensional scientific datasets on distributed memory parallel machines with multiple disks attached to each node. In earlier work, we proposed three strategies for processing range queries within the ADR framework. Our experimental results show that the relative performance of the strategies changes under varying application characteristics and machine configurations. In this work we investigate approaches to guide and automate the selection of the best strategy for a given application and machine configuration. We describe analytical models to predict the relative performance of the strategies where input data elements are uniformly distributed in the attribute space of the output dataset, restricting the output dataset to be a regular d-dimensional array},
	keywords = {active data repository, Area measurement, Computer science, Data analysis, distributed memory parallel machines, Educational institutions, Information retrieval, Information Storage and Retrieval, infrastructure, Microscopy, Microwave integrated circuits, multi-dimensional scientific datasets retrieval, PARALLEL PROCESSING, Pathology, range queries, regular d-dimensional array, Satellites, Tomography},
	isbn = {0-7695-0574-0},
	doi = {10.1109/IPDPS.2000.846013},
	author = {Chang,Chialin and Kurc, T. and Sussman, Alan and Saltz, J.}
}
