NDLI: A new R-tree node splitting algorithm using MBR partition policy

Content Provider	IEEE Xplore Digital Library
Author	Yan Liu Jinyun Fang Chengde Han
Copyright Year	2009
Description	Author affiliation: Institute of Computing Technology, Chinese Academy of Sciences, Graduate University of Chinese Academy of Sciences, Beijing, China (Yan Liu) \|\| Institute of Computing Technology, Chinese Academy of Sciences, Beijing, China (Jinyun Fang; Chengde Han)
Abstract	In this paper we introduced a new R-tree node splitting algorithm. As an indexing technique for multi-dimensional data, R-tree is widely used in geographical information systems, CAD systems and spatial databases. An R-tree consists of nodes which in turn consist of records. Each node in R-tree must contain limited number of records in order that it can be stored within one disk block, thus a node splitting algorithm is used while inserting a new record into a full node. A node splitting algorithm is one of the crucial factors of the query performance of an R-tree since bad splits would result in an inefficient R-tree structure. At first we gave an efficient, linear node splitting algorithm that could construct an R-tree fast, by partitioning the minimum bounding rectangle of the node according to the shape of the node's MBR and the shapes of the MBRs of the node's records. Then we found that this node splitting algorithm would generate uneven nodes sometimes, that is the node to be split might be split into two nodes with one of them containing less records than the minimum number of records required. We then developed an algorithm to balance those uneven splitting results to meet the demands of the R-tree definition. At Last we improved our node splitting algorithm by considering the siblings of the splitting node. The siblings of the splitting node were picked up during the phase of choosing node to insert record and were put together with the splitting node to generate a better result. We performed several experiments to compare our node splitting algorithms with some other node splitting algorithms on both synthetic and real world data. These experiments tested the tree-construction costs and the query performance of the resulting R-trees. The results showed that the tree-constructing cost of our algorithm was lower than others and although the balancing procedure degraded the performance, our algorithm outperformed other node splitting algorithms in queries of the resulting R-trees.
Starting Page	1
Ending Page	6
File Size	238741
Page Count	6
File Format	PDF
ISBN	9781424445622
DOI	10.1109/GEOINFORMATICS.2009.5293260
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2009-08-12
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Computers Costs Shape Multi-dimensional data index R-tree Multimedia databases Spatial databases Partitioning algorithms Information systems GIS Upper bound Node-splitting algorithm Testing Indexing Spatial database
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A new solution of node splitting to the R Tree algorithm

Optimization Reearch of Multi-dimensional Indexing Structure of R*-Tree

A new node-split algorithm in R-tree based on spatial clustering

An improved Spatial index based on the R*Q-tree

Parallel Spatial Index Algorithm Based on Hilbert Partition

Clustered Sorting R-Tree: An Index for Multi-Dimensional Spatial Objects

A new method about spatial data query based on the R*Q-tree

Evolving r-trees for spatial databases.

Location Based Hybrid Indexing Structure - R k-d Tree

A new R-tree node splitting algorithm using MBR partition policy

Similar Documents

A new solution of node splitting to the R Tree algorithm

Optimization Reearch of Multi-dimensional Indexing Structure of R*-Tree

A new node-split algorithm in R-tree based on spatial clustering

An improved Spatial index based on the R*Q-tree

Parallel Spatial Index Algorithm Based on Hilbert Partition

Clustered Sorting R-Tree: An Index for Multi-Dimensional Spatial Objects

A new method about spatial data query based on the R*Q-tree

Evolving r-trees for spatial databases.

Location Based Hybrid Indexing Structure - R k-d Tree

A new R-tree node splitting algorithm using MBR partition policy