М ағашы - Википедия - M-tree

М-ағаштар болып табылады ағаштардың құрылымдары ұқсас R-ағаштар және B ағаштары. Ол а метрикалық және сүйенеді үшбұрыш теңсіздігі тиімді диапазон үшін және k-жақын көрші (k-NN) сұраулар.М-ағаштар көптеген жағдайларда жақсы жұмыс істей алғанымен, ағашта үлкен қабаттасулар болуы мүмкін және қабаттасудан қалай жақсы сақтану туралы нақты стратегия жоқ. Сонымен қатар, оны тек үшін қолдануға болады қашықтықтағы функциялар үшбұрыштың теңсіздігін қанағаттандыратын, алайда көптеген ұқсастық функциялары қолданылған ақпаратты іздеу мұны қанағаттандырмаңыз.[1]

Шолу

2D M-Tree пайдалану арқылы бейнеленген ELKI. Осьтік масштабтың арқасында сфералар эллипсоидты болып көрінеді. Әрбір көк сфера (жапырақ) қызыл сферада болады (каталог түйіндері). Жапырақтары қабаттасады, бірақ көп емес.

Кез-келген ағашқа негізделген мәліметтер құрылымындағыдай, M-ағашы түйіндер мен жапырақтардан тұрады. Әр түйінде оны бірегей түрде анықтайтын деректер объектісі және оның балалары орналасқан кіші ағашқа көрсеткіш бар. Әр жапырақта бірнеше деректер нысандары болады. Әр түйін үшін радиус болады шарды қажетті метрикалық кеңістікте анықтайды. Осылайша, әрбір түйін және жапырақ белгілі бір түйінде тұру қашықтықта орналасқан бастап және әрбір түйін және жапырақ ата-аналық түйінмен одан қашықтықты сақтаңыз.

Ағаш құрылысы

Компоненттер

M-ағашында келесі компоненттер мен қосалқы компоненттер бар:

  1. Жапырақты емес түйіндер
    1. Маршруттау объектілерінің жиынтығы NRO.
    2. Түйіннің ата-анасының O сілтегішіб.
  2. Жапырақ түйіндері
    1. N объектілер жиынтығыO.
    2. Түйіннің ата-анасының O сілтегішіб.
  3. Бағыттау нысаны
    1. (Ерекшелігі мәні) O бағыттау нысаныр.
    2. Қамту радиусы r (Oр).
    3. Т ағашын жабуға арналған көрсеткіш (Oр).
    4. O қашықтығыр оның d (O) негізгі объектісіненр, P (Oр))
  4. Нысан
    1. (Объектінің ерекшелігі мәні) Oj.
    2. Объект идентификаторы туралы (Oj).
    3. O қашықтығыj оның d (O) негізгі объектісіненj, P (Oj))

Кірістіру

Негізгі идея алдымен жапырақ түйінін табу N жаңа объект қайда O тиесілі. Егер N толы емес болса, оны бекітіңіз N. Егер N толы, содан кейін бөлу әдісін қолданыңыз N. Алгоритм келесідей:

Алгоритм Кірісті енгізу: түйін N M-Tree MT, Кіру   Шығарылым: жаңа данасы MT барлық жазбаларды түпнұсқада қамтиды MT плюс 
  бағыттау объектілері немесе объектілері егер N жапырақ емес содан кейін  {/ * Жаңа нысанға сәйкес келетін жазбаларды іздеңіз * / рұқсат етіңіз  объектілерді бағыттау маршруттау объектілерінің жиынтығы  осындай        егер  бос емес содан кейін       {/ * Егер бір немесе бірнеше жазба болса, жаңа нысанға жақын жазба іздеңіз * /        }       басқа       {/ * Егер мұндай жазба болмаса, онда * / / * оның радиусының шетінен жаңа объектіге дейінгі ең аз қашықтықтағы объектіні іздеңіз * /           / * Жазбаның жаңа радиустарын жаңартыңыз * /        } / * Келесі деңгейге енгізуді жалғастыру * / қайту кірістіру ();  басқа  {/ * Егер түйіннің сыйымдылығы болса, онда жаңа нысанды енгізіңіз * / егер N толық емес содан кейін       { дүкен () } / * Түйін толық қуатында, содан кейін осы деңгейде жаңа сплит жасау қажет * / басқа       { Сызат() }  }
  • «←» дегенді білдіреді тапсырма. Мысалы, »ең үлкенэлемент«деген мағынаны білдіреді ең үлкен мәніне өзгереді элемент.
  • "қайту«алгоритмді тоқтатады және келесі мәнді шығарады.

Сызат

Егер сплит әдісі ағаштың тамырына жетсе, онда ол екі бағыттауыш нысанын таңдайды N, және барлық нысандарды түпнұсқасында қамтитын екі жаңа түйін жасайды N, және оларды жаңа тамырға сақтаңыз. Егер бөлу әдістері түйінге келсе N бұл ағаштың тамыры емес, әдіс екі жаңа маршруттау нысанын таңдайды N, әрбір бағыттау нысанын қайта ұйымдастырыңыз N екі жаңа түйінде және , және осы жаңа түйіндерді ата-ана түйінде сақтаңыз түпнұсқа N. Бөлу қайталануы керек, егер сақтау үшін жеткіліксіз . Алгоритм келесідей:

Алгоритм Бөлуді енгізу: түйін N M-Tree MT, Кіру   Шығарылым: жаңа данасы MT құрамында жаңа бөлім бар.
  / * Жаңа маршруттау объектілері енді түйіндегі барлық және жаңа маршруттау объектісі болып табылады * / let NN жазбалары   егер N түбір емес содан кейін  {/ * Ата-ана түйіні мен ата-аналық маршруттау нысанын алыңыз * / рұқсат етіңіз  ата-аналық маршруттау объектісі бол N     рұқсат етіңіз  ата-анасының түйіні болыңыз N  } / * Бұл түйінде бөлінетін түйін нысандарының бөлігі болады * / Жаңа түйін жасаңыз N '  / * Бөлінген түйіннен екі маршруттау нысанын алға жылжыту, жаңа маршруттау объектілері болу * * Жаңа объектілерді құру  және .  Жарнамалау () * * Бөлінетін түйіннен қандай нысандар жаңа маршруттау объектілері болатынын таңдаңыз * / Бөлім () / * Әр жаңа маршруттау объектісінде жазбаларды сақтау * / Дүкен жазбалар N және жазбалар N '  егер N ағымдағы түбір содан кейін  {/ * Жаңа түйін жасаңыз және оны жаңа түбір етіп орнатыңыз және жаңа бағыттау объектілерін сақтаңыз * / Жаңа түбір түйінін жасаңыз       Дүкен  және  жылы   }  басқа  {/ * Енді жаңа нысандардың бірін сақтау үшін ата-аналық маршруттау нысанын қолданыңыз * / Жазбаны ауыстырыңыз  кіруімен  жылы       егер  толық емес содан кейін      {/ * Екінші маршруттау нысаны ата-анасында бос сыйымдылығы болған жағдайда ғана сақталады * / Дүкен  жылы       }      басқа      {/ * Егер бос сыйымдылық болмаса, онда деңгейді бөліңіз * / Сызат()      }  }
  • «←» дегенді білдіреді тапсырма. Мысалы, »ең үлкенэлемент«деген мағынаны білдіреді ең үлкен мәніне өзгереді элемент.
  • "қайту«алгоритмді тоқтатады және келесі мәнді шығарады.

Ағаштар туралы сұраулар

Ауқым сұрауы

Диапазондық сұрау - минималды ұқсастық / максималды арақашықтық мәні көрсетілген жерде. Берілген сұраныс нысаны үшін және максималды іздеу қашықтығы, диапазон сұрауы ауқымы(Q, r (Q)) барлық индекстелген нысандарды таңдайды осындай .[2]

Algorithm RangeSearch түбірлік түйіннен басталып, талап етілетін объектілерге апарып тастауға болмайтын барлық жолдарды рекурсивті түрде өтеді.

Алгоритм RangeSearchInput: түйін N M-Tree MT, Q: сұрау нысаны, : іздеу радиусы
Шығу: барлық ДБ нысандары осындай 
{   рұқсат етіңіз  болуы түйіннің негізгі нысаны N;  егер N емес жапырақ содан кейін {     әрқайсысы үшін кіру() жылы N істеу {          егер  содан кейін {             Есептеу ;            егер  содан кейін              RangeSearch(* ptr ()),Q,);           }    }  }  басқа {     әрқайсысы үшін кіру() жылы N істеу {          егер  содан кейін {             Есептеу ;            егер  содан кейін              қосу  нәтижеге;          }    }  }}
  • «←» дегенді білдіреді тапсырма. Мысалы, »ең үлкенэлемент«деген мағынаны білдіреді ең үлкен мәніне өзгереді элемент.
  • "қайту«алгоритмді тоқтатады және келесі мәнді шығарады.
  • - бұл жеке деректер файлында орналасқан объектінің идентификаторы.
  • тармақ болып табылады - жабын ағашы

k-NN сұраулары

K Жақын көрші (k-NN) сұрауы кіріс параметрінің мәні ретінде кіріс жиынтығын қабылдайды. Берілген Q ∈ D нысаны мен k ≥ 1 антетригі үшін k-NN сұранысы NN (Q, k) d қашықтықтағы функцияға сәйкес Q-дан ең аз қашықтықта болатын индекстелген объектілерді таңдайды.[2]

Сондай-ақ қараңыз

Әдебиеттер тізімі

  1. ^ Циачия, Паоло; Пателла, Марко; Зезула, Павел (1997). «М-ағаш - метрикалық кеңістіктегі ұқсастықты іздеудің тиімді әдісі» (PDF). 23-ші VLDB конференциясының материалдары Афина, Греция, 1997 ж. IBM Almaden зерттеу орталығы: өте үлкен мәліметтер қорлары Endowment Inc., 426-435 бб. p426. Алынған 2010-09-07.
  2. ^ а б P. Ciaccia; М. Пателла; Ф. Рабитти; П.Зезула. «Метрикалық кеңістіктерді М ағашымен индекстеу» (PDF). Информатика және техника кафедрасы. Болон университеті. б. 3. Алынған 19 қараша 2013.