Metric Data Structures
If there is no structure to the similarity measure then a brute force search requiring the comparison of the query image to every image in the dataset is the best that can be done. If, however, the similarity function satisfies the triangle inequality then it is possible to use the result of each comparison to prune the set of candidates to be examined.
The first article on metric trees, as well as the first use of the term "metric tree", published in the open literature was by Jeffrey Uhlmann in 1991. Other researchers were working independently on similar data structures, and research on metric tree data structures blossomed in the late 1990s and included an examination by Google co-founder Sergey Brin of their use for very large databases. The first textbook on metric data structures was published in 2006.
Read more about this topic: Metric Tree
Famous quotes containing the words data and/or structures:
“To write it, it took three months; to conceive it three minutes; to collect the data in it—all my life.”
—F. Scott Fitzgerald (1896–1940)
“The American who has been confined, in his own country, to the sight of buildings designed after foreign models, is surprised on entering York Minster or St. Peter’s at Rome, by the feeling that these structures are imitations also,—faint copies of an invisible archetype.”
—Ralph Waldo Emerson (1803–1882)