We introduce an improved method to split overflowed nodes of R-tree spatial index called the Corner Based Splitting (CBS) algorithm. Good splits produce an efficient R-tree which has minimal height, overlap and coverage in each node. The CBS algorithm selects the splitting axis that produces the most even split according to the number of objects, using the distance from each object centre to the nearest node’s MBR corner. Experiments performed using both synthetic and real data files showed obvious performance improvement. The improvement percentage over the Quad algorithm reached 23%, while the improvement percentage over the NR algorithm reached 37%.
GuttmanA. R-Trees, a dynamic index structure for spatial searching. In: Proceedings of ACM SIGMOD conference, 1984, pp. 47–57.
2.
PapadiasDSellisTTheodoridisYEgenhoferM. Topological relations in the world of minimum bounding rectangles: A study with R-trees. In: ACM SIGMOD, 1995.
3.
FuY.TengJSubramanyaS. Node splitting algorithms in tree-structured high-dimensional indexes for similarity search. In: Proceedings of the 2002 ACM symposium on applied computing (SAC ’02). New York: ACM, 2002, pp. 766–770.
4.
SleitA.On using B+ tree for efficient processing for the boundary neighborhood problem. WSEAS Transactions on Systems2008; 11(11): 711–720.
5.
SleitAAbu DalhoumAQatawnehMAl-ShariefMAl-JabalyMKarajehO. image clustering using color, texture and shape features. KSII Transactions on Internet and Information Systems2013; 5(1): 211–227.
6.
IbrahimAFotouhiFSayedF. The SB+-Tree: an efficient index structure for joining spatial relations. International Journal of Geographic Information Science1997; 11(2): 163–182.
7.
IbrahimAFotouhiFAl-BadarnehA. efficient processing of direction operations in spatial databases. In: Proceedings of IASTED’98: international conference of computer systems and applications, March1998.
8.
SellisTRoussopoulosNFaloutsosC. The R+-tree: A dynamic index for multidimensional objects. In: Proceedings of the VLDB conference, 1987, pp. 507–518.
9.
BeckmannNKriegelHSchneiderRSeegerB. The R*-tree: An efficient and robust method for points and rectangles. In: Proceedings of the ACM SIGMOD conference, 1990, pp. 322–331.
10.
AngCTanT. New linear node splitting algorithm for R-trees. In: Proceedings of the international symposium on advances in spatial databases conference, 1997, pp. 339–349.
11.
Al-BadarnehAYaseenQHmeidiI. A new enhancement to the R-tree node splitting. Journal of Information Science2010; 36(1): 3–18.
12.
TheodoridisYSellisT. A model for the prediction of R-tree performance. In: Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on principles of database systems (PODS ‘96). New York: ACM, 1996, pp. 161–171.
