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)
“It is clear that all verbal structures with meaning are verbal imitations of that elusive psychological and physiological process known as thought, a process stumbling through emotional entanglements, sudden irrational convictions, involuntary gleams of insight, rationalized prejudices, and blocks of panic and inertia, finally to reach a completely incommunicable intuition.”
—Northrop Frye (b. 1912)