درخت متریک

درخت متریک یک داده‌ساختار درخت است که به داده‌های شاخص در فضاهای متریک تخصیص داده می‌شود. درخت‌های متریک از ویژگی‌های فضاهای متریک مانند نابرابری مثلثی برای دست‌رسی بهتر به داده‌ها بهره‌برداری می‌کنند. به عنوان مثال می‌توان از M-tree، vp-tree، cover tree، MVP Tree و bk tree نام برد.

جست‌و‌جوی چندبعدی

بیشتر الگوریتم‌ها و داده‌ساختارها برای جست‌وجوی یک مجموعه داده بر پایه‌ی الگوریتم کلاسیک جست‌و‌جوی دودویی هستند و مانند درخت کی‌دی و درخت محدوده با اجرای الگوریتم جست‌و‌جوی دودویی روی مختصات‌های جدا شده کار می‌کنند و روی هر محور خاص، به صورت مستقل جست‌و‌جو می‌کنند. این الگوریتم‌ها برای مسئله‌های بازه‌ای مناسب هستند که برای هر نقطه‌ی $(x,y)$ که شروط ${\mbox{min}}_{x}\leq x\leq {\mbox{max}}_{x}$ و ${\mbox{min}}_{y}\leq y\leq {\mbox{max}}_{y}$ را دارند. یکی از محدودیت‌هایی که این جست‌و‌جوهای چندبعدی دارند، آن است که آن‌ها تنها برای جست‌و‌جو روی شی‌ء‌هایی تعریف شده‌اند که مانند بردار عمل می‌کنند. آن‌ها کاربردی برای حالات کلی‌تر که در آن، الگوریتم مجموعه‌ای از اشیا و یک تابع برای اندازه‌گیری فاصله یا شباهت دو شیء است، ندارند. اگر برای مثال کسی بخواهد تابعی بسازد که مقداری را برگرداند که شباهت یک عکس به عکسی دیگر را نشان دهد، یک مسئله‌ی الگوریتمی طبیعی این می‌تواند باشد که به ازای یک عکس درخواستی بگوید کدام عکس از یک مجموعه از عکس‌ها، به آن شبیه‌تر است.

داده‌ساختارهای متریک

اگر هیچ ساختاری برای اندازه‌گیری شباهت موجود نباشد، آن‌گاه مقایسه‌ی همه‌ی عکس‌ها با عکس درخواستی می‌تواند کار را انجام دهد؛ اما اگر تابع شباهت، شرط نابرابری مثلثی را داشته باشد، آن‌گاه می‌توان نتیجه‌ی هر مقایسه را برای هرس کردن تعدادی از عکس‌ها استفاده کرد.
ولین مقاله در خصوص درخت متریک که در آن از عنوان «درخت متریک» استفاده شد، توسط جفری اولمن در سال ۱۹۹۱ انتشار یافت. بقیه تحقیقات به طور مستقل در حوزهٔ داده‌ساختارهای مشابه انجام شد. به طور خاص پیتر یالینوس ادعای کشف روش مشابهی به طور مستقل کرد و آن را Vantage-point tree نامید. تحقیقات در حوزهٔ درخت متریک در اواخر دهه ۱۹۹۰ شکوفا شد و توسط سرگئی برین یکی از بنیان‌گزاران شرکت گوگل برای استفاده در پایگاه داده‌های بسیار بزرگ مورد سنجش قرار گرفت. اولین دست‌نویس حول داده ساختار درخت متریک در سال ۲۰۰۶ انتشار یافت.

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Metric tree». در دانشنامهٔ ویکی‌پدیای انگلیسی.