Metric tree

This article is about the data structure. For the type of metric space, see Real tree.

A metric tree is any tree data structure specialized to index data in metric spaces. Metric trees exploit properties of metric spaces such as the triangle inequality to make accesses to the data more efficient. Examples include the M-tree, vp-trees, cover trees, MVP trees, and BK-trees.[1]

Most algorithms and data structures for searching a dataset are based on the classical binary search algorithm, and generalizations such as the k-d tree or range tree work by interleaving the binary search algorithm over the separate coordinates and treating each spatial coordinate as an independent search constraint. These data structures are well-suited for range query problems asking for every point that satisfies and .

A limitation of these multidimensional search structures is that they are only defined for searching over objects that can be treated as vectors. They aren't applicable for the more general case in which the algorithm is given only a collection of objects and a function for measuring the distance or similarity between two objects. If, for example, someone were to create a function that returns a value indicating how similar one image is to another, a natural algorithmic problem would be to take a dataset of images and find the ones that are similar according to the function to a given query image.

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 [citation needed]. 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.[2] Other researchers were working independently on similar data structures. In particular, Peter Yianilos claimed to have independently discovered the same method, which he called a vantage point tree (VP-tree).[3] The 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.[4] The first textbook on metric data structures was published in 2006.[1]

Open source implementations

References

  1. ^ a b Samet, Hanan (2006). Foundations of multidimensional and metric data structures. Morgan Kaufmann. ISBN 978-0-12-369446-1.
  2. ^ Uhlmann, Jeffrey (1991). "Satisfying General Proximity/Similarity Queries with Metric Trees". Information Processing Letters. 40 (4): 175–179. doi:10.1016/0020-0190(91)90074-r.
  3. ^ Yianilos, Peter N. (1993). "Data structures and algorithms for nearest neighbor search in general metric spaces". Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms. Society for Industrial and Applied Mathematics Philadelphia, PA, USA. pp. 311–321. pny93. Retrieved 2019-03-07.
  4. ^ Brin, Sergey (1995). "Near Neighbor Search in Large Metric Spaces" (PDF). 21st International Conference on Very Large Data Bases (VLDB).
  5. ^ "Tracker Component Library". Matlab Repository. Retrieved January 5, 2019.

Read other articles:

Shaw-Han Liem

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada Desember 2023. I Am Robot and ProudI am Robot and Proud tampil pada Februari 2009.Informasi latar belakangNama lahirShaw-Han LiemLahirToronto, Ontario, KanadaAsalToronto, Ontario, KanadaGenreIndietronikaTahun aktif2001–sekarangLabelDarla, & RecordsSitus webwww...

 

Confine tra il Brasile e la Guyana

Confine tra il Brasile e la GuyanaDati generaliStati Brasile Guyana Lunghezza1605 km Dati storiciIstituito nel1904 Attuale dal1926 Manuale Il confine tra il Brasile e la Guyana è un confine internazionale continuo 1605 km[1] che separa il Brasile dalla Guyana, due paesi del Sud America. Indice 1 Tracciato 2 Storia 3 Popolazioni e movimenti migratori 4 Punti di attraversamento 5 Note 6 Voci correlate 7 Altri progetti Tracciato Triplice confine Brasile / Venezuela / Guya...

 

Andries Hoogerwerf

Macan Jawa yang sekarang telah punah yang difoto oleh Andries Hoogerwerf pada 1938Andries Hoogerwerf (29 Agustus 1906 – 5 Februari 1977) adalah seorang atlet trek dan lapangan, naturalis, ornitologis dan konservasionis asal Velanda. Ia menjalani sebagian besar masa kerjanya di Hindia Belanda dan Nugini Belanda.[1] Publikasi 1938 – De avifauna van Batavia en omstreken. Leiden. 1949 – Bijdrage tot de oölogie van Java. Netherlands. 1949 – De avifauna van de Planten...

The O'Rahilly

Irish republican (1875–1916) Michael Joseph O'RahillyMícheál Seosamh Ó RathailleMichael Joseph O'Rahilly (The O'Rahilly) c. 1913-1916Born(1875-04-22)22 April 1875Ballylongford, County Kerry, IrelandDied29 April 1916(1916-04-29) (aged 41)Dublin, IrelandResting placeGlasnevin CemeteryNationalityIrishOther namesThe O'Rahilly, Ua RathghailleEducationClongowes Wood CollegeOrganization(s)Irish VolunteersGaelic LeagueSpouse(s)Nancy O'Rahilly (m. 1899)ChildrenBobbyRichardAodogánNiallM...

 

Daftar Bupati Timor Tengah Utara

Bupati Timor Tengah UtaraLambang Timor Tengah UtaraPetahanaJuandi Davidsejak 26 Februari 2021Masa jabatan5 tahunDibentuk1958Pejabat pertamaPetrus Canisius Tarcisius SalassaSitus webhttps://ttukab.go.id Berikut daftar Bupati Timor Tengah Utara dari masa ke masa: No. Potret Nama(Masa Hidup) Mulai Menjabat Selesai Menjabat Prd. Jabatan Sebelumnya Wakil Bupati Ket. M.E.Ngefak 1 Januari 1957 20 Desember 1958 Sekretaris Daerah Timor dan Kepulauan SK Gubernur Nusa Tenggara No.494/UP.3/3/41 M.E....

 

Constance of France, Princess of Antioch

Princess consort of Antioch ConstanceNuptial of Bohemond and ConstancePrincess consort of AntiochTenure1106–1111Countess consort of TroyesTenure1093/95 – 1104Born1078Died14 September 1126 (aged 47–48)SpouseHugh I, Count of TroyesBohemond I of AntiochIssueManasses of TroyesBohemond II of AntiochJohn of AntiochHouseCapetFatherPhilip I of FranceMotherBertha of Holland Constance of France (1078 – 14 September 1125) was Countess of Troyes from her first marriage and Princess of An...

أنديرس بنغتسون

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (مارس 2019) أنديرس بنغتسون (بالسويدية: Anders Bengtsson)‏  معلومات شخصية الميلاد سنة 1968 (العمر 55–56 سنة)  مواطنة السويد  مناصب عضو البرلمان السويدي   عضو خلال الفترة1 أ...

 

Northeastern University – London

University in London, England Northeastern University - LondonTypeUndergraduate, postgraduateEstablishedIncorporated 2010; announced 2011; offering tuition from September 2012Endowment£2.5 million (2014/15)[1]Officer in chargeRob Farquharson (COO)FounderA. C. GraylingStudents500Undergraduates300 studentsLocationLondon, United Kingdom51°31′15″N 0°7′19″W / 51.52083°N 0.12194°W / 51.52083; -0.12194OwnershipNortheastern UniversityWebsitenulondon.ac.uk...

 

SS-Junkerschule

Questa voce o sezione sull'argomento nazismo non cita le fonti necessarie o quelle presenti sono insufficienti. Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento. SS-JunkerschuleAllg. Abzeichen Schule Bad Tölz Descrizione generaleNazione Germania Servizio Schutzstaffel TipoScuola militare RuoloFormazione di ufficiali e sottufficiali delle SS Battaglie/guerreSeconda gu...

Mexique aux Jeux olympiques d'été de 2008

Cet article est une ébauche concernant les Jeux olympiques et le Mexique. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Mexique aux Jeux olympiques d'été de 2008 Code CIO MEX Lieu Pékin Participation 21e Athlètes 85 dans 23 sports Porte-drapeau Paola Espinosa MédaillesRang : 36 Or2 Arg.0 Bron.2 Total4 Mexique aux Jeux olympiques d'été Mexique aux Jeux olympiques d'été de 2004 Mexique aux Jeux ol...

 

2020年夏季奧林匹克運動會波蘭代表團

2020年夏季奥林匹克运动会波兰代表團波兰国旗IOC編碼POLNOC波蘭奧林匹克委員會網站olimpijski.pl（英文）（波兰文）2020年夏季奥林匹克运动会（東京）2021年7月23日至8月8日（受2019冠状病毒病疫情影响推迟，但仍保留原定名称）運動員206參賽項目24个大项旗手开幕式：帕维尔·科热尼奥夫斯基（游泳）和马娅·沃什乔夫斯卡（自行车）[1]闭幕式：卡罗利娜·纳亚（皮划艇）&#...

 

中華民國國軍中的中共間諜列表

 本表是動態列表，或許永遠不會完結。歡迎您參考可靠來源來查漏補缺。 潛伏於中華民國國軍中的中共間諜列表收錄根據公開資料來源，曾潛伏於中華民國國軍、被中國共產黨聲稱或承認，或者遭中華民國政府調查審判，為中華人民共和國和中國人民解放軍進行間諜行為的人物。以下列表以現今可查知時間為準，正確的間諜活動或洩漏機密時間可能早於或晚於以下所歸�...

Night Music (Joe Jackson album)

1994 studio album by Joe JacksonNight MusicStudio album by Joe JacksonReleased3 October 1994[1]GenreRock, pop, classical musicLength47:39LabelVirginProducerJoe Jackson and Ed RoyensdalJoe Jackson chronology Laughter & Lust(1991) Night Music(1994) Joe Jackson - Greatest Hits(1997) Professional ratingsReview scoresSourceRatingAllmusic[2] Night Music is the 12th studio album by Joe Jackson, released in 1994 on Virgin Records. The album did not chart.[3] Soon ...

 

Foxley Wood, Purley

This article is about the nature reserve in London. For the nature reserve in Norfolk, see Foxley Wood. Foxley Wood is an 11.36 hectare Local Nature Reserve and Site of Borough Importance for Nature Conservation, Grade 1, in Purley in the London Borough of Croydon. It is owned and managed by Croydon Council.[1][2][3] The site was purchased by Coulsdon and Purley Urban District Council under the Green Belt Act in the 1930s.[4] Some of the woodland on the site is...

 

St. Benedict's Catholic Church (Honaunau, Hawaii)

Historic Place in Hawaii County, Hawaii United States historic placeSt. Benedict's Catholic ChurchU.S. National Register of Historic PlacesHawai`i Register of Historic Places Saint Benedict's Catholic ChurchLocationHonaunau, HawaiiCoordinates19°26′6.252″N 155°53′17.952″W / 19.43507000°N 155.88832000°W / 19.43507000; -155.88832000Built1899ArchitectVelghe, Fr. John BerchmansArchitectural styleGothicNRHP reference No.79000753[1]HRHP ...

Palazzo Buonaparte

Facciata Palazzo Buonaparte è un edificio storico di San Miniato, provincia di Pisa, situato tra via Maioli e piazza XX Settembre. Storia e descrizione L'edificio, come ricorda una targa posta sulla facciata, apparteneva al canonico Filippo Buonaparte, che il 29 giugno 1797 fu visitato dal parente corso Napoleone, generale dell'esercito francese in cerca delle sue origini nobiliari in Toscana e in particolare proprio a San Miniato. Il palazzo ha oggi un fronte severo, arricchito da un porta...

 

Streptococcus pyogenes

Streptococcus pyogenes PenyakitSindrom TS dan Limfangitis Pewarnaan GramGram-positif TaksonomiKerajaanBacillatiFilumBacillotaKelasBacilliOrdoLactobacillalesFamiliStreptococcaceaeGenusStreptococcusSpesiesStreptococcus pyogenes Rosenbach Streptococcus pyogenes ialah bakteri Gram-positif bentuk bundar yang tumbuh dalam rantai panjang[1] dan merupakan penyebab infeksi Streptococcus Grup A. Streptococcus pyogenes menampakkan antigen grup A di dinding selnya dan beta-hemolisis saat dikultur...

 

圣佩德罗-达乌尼昂

圣佩德罗-达乌尼昂São Pedro da União市镇圣佩德罗-达乌尼昂在巴西的位置坐标：21°07′37″S 46°36′54″W / 21.1269°S 46.615°W / -21.1269; -46.615国家巴西州米纳斯吉拉斯州面积 • 总计258.511 平方公里（99.812 平方英里）海拔932 公尺（3,058 英尺）人口 • 總計5,291人 • 密度20.5人/平方公里（53人/平方英里） 圣佩德罗-达乌尼昂（葡�...

Puteal Scribonianum

The Puteal Scribonianum on a 62 BC denarius The Puteal Scribonianum (Scribonian Puteal) or Puteal Libonis (Puteal of Libo) was a structure in the Forum Romanum in Ancient Rome.[1] A puteal was a classical wellhead, round or sometimes square, placed atop a well opening to keep people from falling in. The Scribonian Puteal was dedicated or restored by a member of the Libo family, perhaps the praetor of 204 BC, or the tribune of the people in 149 BC. The praetor's tribunal was convened n...

 

Djurgårdens IF Handikappfotbollförening

Djurgårdens IF Handikappfotboll Klubbens färgerHemortStockholm,  SverigeAktivJanuari 1997-VerksamhetHandikappfotbollSmeknamnDjurgår'nFörkortningDIF Djurgårdens IF handikappfotboll startade sin verksamhet i januari 1997 och ingår i alliansförening i Djurgårdens IF. Föreningen håller till vid sommartid på Hjorthagens IP och vid vintertid på Spånga IP. [1] Referenser ^ ”Djurgårdens IF Handikappfotbollsförening”. Djurgårdens IF Handikappfotbollsförening. 22 januari 2013....