Геоақпараттық жүйелердегі R-ағаштары

Кіріспе

Ғарыштық индекстеуде қолданылатын деректер құрылымдары

Деректер құрылымы

R-ағаштар – кеңістіктік қол жеткізу әдістері үшін қолданылатын ағаш тәрізді деректер құрылымдары, яғни географиялық координаттар, тіктөртбұрыштар немесе көпбұрыштар сияқты көп өлшемді ақпаратты индекстеу үшін. R-ағашты 1984 жылы Антонин Гаттман ұсынған және теориялық және қолданбалы салаларда кеңінен қолданылып келеді. R-ағаштың нақты қолданылуының бір мысалы – мейрамханалардың орналасқан жерлері немесе әдеттегі карталар құрамына кіретін көпбұрыштар: көшелер, ғимараттар, көлдердің шекаралары, жағалау сызықтары сияқты кеңістіктік объектілерді сақтау. Содан кейін "Менің қазіргі орнымнан 2 км радиустағы барлық мұражайларды табу", "Менің орнымнан 2 км радиустағы барлық жол сегменттерін алу" (навигациялық жүйеде көрсету үшін) немесе "Жақын маңындағы жанармай құю стансасын табу" (жолдарды ескермей) сияқты сұрақтарға жылдам жауап алуға болады. R-ағаш түрлі қашықтық өлшемдерін, соның ішінде үлкен шеңбер қашықтығын ескере отырып, жақын көршіні іздеуді де жеделдете алады.

R-ағаш идеясы

Деректер құрылымының негізгі идеясы – жақын орналасқан объектілерді топтастыру және оларды ағаштың келесі жоғары деңгейіндегі ең кішкентай қоршау тіктөртбұрышымен көрсету; R ағаштағы "R" тіктөртбұрышты білдіреді. Барлық объектілер осы қоршау тіктөртбұрышының ішінде жатқандықтан, қоршау тіктөртбұрышымен қиыспайтын сұраныс, сонымен қатар, құрамындағы ешбір объектімен қиыспайды. Жапырақ деңгейінде әр тіктөртбұрыш бір объектіні сипаттайды; жоғары деңгейлерде жиынтықтау объектілер санын арттырады. Бұл деректер жиынтығының күрделі шамалауы ретінде де қарастырылуы мүмкін. B ағашына ұқсас, R ағашы да теңгерілген іздеу ағашы (барлық жапырақ түйіндері бірдей тереңдікте болады), деректерді беттерде ұйымдастырады және дискіде сақтау үшін (мәселен, деректер базаларында қолданылатындай) жасалған. Әрбір бетте шекті сандағы жазбалар болуы мүмкін, көбінесе ол белгіленеді. Ол сондай-ақ ең аз толтыруға кепілдік береді (тамыр түйінінен басқа), бірақ ең жақсы өнімділік ең аз толтырумен 30%-40% шегіндегі максималды жазбалар санымен қамтамасыз етілген (B ағаштары 50% беттің толтырылуын кепілдік береді, ал B* ағаштары тіпті 66%). Бұған себеп – B ағаштарында сақталатын сызықтық деректерге қарағанда кеңістіктік деректерге қажетті күрделі теңгерім. Көптеген ағаштардағыдай, іздеу алгоритмдері (мысалы, қиылысу, қамту, ең жақын көршіні іздеу) өте қарапайым. Негізгі идея – шектеу қораптарын пайдаланып, кіші ағаш ішінде іздеу қажет пе, жоқ па, соны анықтау. Осылайша, ағаштағы түйіндердің көпшілігі іздеу кезінде оқылмайды. B ағаштары сияқты, R ағаштары үлкен деректер жиынтығы мен деректер базалары үшін қолайлы, онда түйіндер қажет болған кезде жадқа беттеп беріледі, ал бүкіл ағаш негізгі жадта сақталмайды. Егер деректер жадында (немесе кэште) орналаса алса да, R ағаштары әдетте, бірнеше жүзден астам объектілер болған кезде, барлық объектілерді тікелей тексеруден артық өнімділікті қамтамасыз етеді. Алайда, жад қолдануда, одан да жақсы өнімділік беретін немесе іске асыру оңайырақ болатын баламалар бар. Компьютерлік кластерде R ағашының жадтағы есептеуін сақтау үшін, есептеу түйіндері желімен қосылған кезде, зерттеушілер таратылған ортада R ағашының астында деректерге арналған қолданбаларды іске асыру үшін RDMA (Алыстан тікелей жадқа қол жеткізу) қолданды. Бұл тәсіл үлкен қосымшалар үшін кеңейеді және R ағашы үшін жоғары өнімділік пен төмен күту уақытын қамтамасыз етеді. R ағашының негізгі қиындығы – бір жағынан теңгерілген (жапырақ түйіндері бірдей биіктікте) тиімді ағаш құру, екінші жағынан тіктөртбұрыштар тым көп бос орынды қамтып алмайды және тым көп жамылмайды (іздеу кезінде аздаған кіші ағаштарды өңдеу қажет болсын). Мысалы, тиімді ағаш алу үшін элементтерді енгізудің бастапқы идеясы – әрқашан оның шектеу қорабының ең аз кеңеюін қажет ететін кіші ағашқа енгізу. Бет толғаннан кейін, деректер екі топқа бөлінеді, олардың әрқайсысы ең аз аумақты қамтуы керек. R ағаштары үшін жүргізілетін зерттеулер мен жетілдірулердің көпшілігі ағаштың құрылу тәсілін жақсартуға бағытталған және оларды екі мақсатқа топтастыруға болады: бастапқыда тиімді ағаш құру (көлемді жүктеу деп аталады) және қолданыстағы ағашқа өзгерістер енгізу (қосу және жою). R ағаштары ең нашар жағдайда жақсы өнімділікке кепілдік бермейді, бірақ әдетте нақты әлемдегі деректермен жақсы жұмыс істейді. Теориялық қызығушылық көбірек болса да, R ағашының (көлемді жүктемелі) Басымдық R ағашының нұсқасы ең нашар жағдайда оңтайлы, бірақ күрделілігінің артуына байланысты практикалық қолданбаларда әлі көп көңіл бөлінбейді. Деректер R ағашында ұйымдастырылған кезде, берілген арақашықтықтағы көршілер r және барлық нүктелердің k жақын көршілері (әрбір Lp нормасы үшін) кеңістіктік қосылуды пайдалану арқылы тиімді есептелуі мүмкін. Бұл көптеген алгоритмдер үшін пайдалы, мысалы, жергілікті аномалиялық фактор. DeLi Clu, Density Link Clustering – кластерлік талдау алгоритмі, ол OPTICS кластерін тиімді есептеу үшін ұқсас кеңістіктік қосылу үшін R ағаштық құрылымын қолданады.

The key idea of the data structure is to group nearby objects and represent them with their minimum bounding rectangle in the next higher level of the tree; the "R" in R tree is for rectangle. Since all objects lie within this bounding rectangle, a query that does not intersect the bounding rectangle also cannot intersect any of the contained objects. At the leaf level, each rectangle describes a single object; at higher levels the aggregation includes an increasing number of objects. This can also be seen as an increasingly coarse approximation of the data set. Similar to the B tree, the R tree is also a balanced search tree (so all leaf nodes are at the same depth), organizes the data in pages, and is designed for storage on disk (as used in databases). Each page can contain a maximum number of entries, often denoted as It also guarantees a minimum fill (except for the root node), however best performance has been experienced with a minimum fill of 30%–40% of the maximum number of entries (B trees guarantee 50% page fill, and B* trees even 66%). The reason for this is the more complex balancing required for spatial data as opposed to linear data stored in B trees. As with most trees, the searching algorithms (e. g., intersection, containment, nearest neighbor search) are rather simple. The key idea is to use the bounding boxes to decide whether or not to search inside a subtree. In this way, most of the nodes in the tree are never read during a search. Like B trees, R trees are suitable for large data sets and databases, where nodes can be paged to memory when needed, and the whole tree cannot be kept in main memory. Even if data can be fit in memory (or cached), the R trees in most practical applications will usually provide performance advantages over naive check of all objects when the number of objects is more than few hundred or so. However, for in memory applications, there are similar alternatives that can provide slightly better performance or be simpler to implement in practice. To maintain in memory computing for R tree in a computer cluster where computing nodes are connected by a network, researchers have used RDMA (Remote Direct Memory Access) to implement data intensive applications under R tree in a distributed environment. This approach is scalable for increasingly large applications and achieves high throughput and low latency performance for R tree. The key difficulty of R tree is to build an efficient tree that on one hand is balanced (so the leaf nodes are at the same height) on the other hand the rectangles do not cover too much empty space and do not overlap too much (so that during search, fewer subtrees need to be processed). For example, the original idea for inserting elements to obtain an efficient tree is to always insert into the subtree that requires least enlargement of its bounding box. Once that page is full, the data is split into two sets that should cover the minimal area each. Most of the research and improvements for R trees aims at improving the way the tree is built and can be grouped into two objectives: building an efficient tree from scratch (known as bulk loading) and performing changes on an existing tree (insertion and deletion). R trees do not guarantee good worst case performance, but generally perform well with real world data. While more of theoretical interest, the (bulk loaded) Priority R tree variant of the R tree is worst case optimal, but due to the increased complexity, has not received much attention in practical applications so far. When data is organized in an R tree, the neighbors within a given distance r and the k nearest neighbors (for any Lp Norm) of all points can efficiently be computed using a spatial join. This is beneficial for many algorithms based on such queries, for example the Local Outlier Factor. DeLi Clu, Density Link Clustering is a cluster analysis algorithm that uses the R tree structure for a similar kind of spatial join to efficiently compute an OPTICS clustering.

Деректер кестесі

R ағаштарындағы деректер әр түрлі сандағы жазбаларға ие беттерде ұйымдастырылады (алдын ала белгіленген максималды шегіне дейін және әдетте минималды толтырудан жоғары). Жапырақ емес түйіннің әрбір жазуы екі дерек бөлігін сақтайды: бала түйінін анықтау тәсілі және осы бала түйініндегі барлық жазбалардың шектейтін тіктөртбұрышы. Жапырақ түйіндері әр бала үшін қажетті деректерді сақтайды, көбінесе баланы көрсететін нүкте немесе шектейтін тіктөртбұрыш, сондай-ақ балаға арналған сыртқы идентификатор. Нүктелік деректер үшін жапырақ жазбалары тек нүсқалардың өзі болуы мүмкін. Көпбұрышты деректер үшін (әдетте үлкен көпбұрыштарды сақтауды қажет етеді) жиі кездесетін тәсіл – көпбұрыштың тек MBR (минималды шектейтін тіктөртбұрыш) және ағаштағы бірегей идентификаторын сақтау.