SOLD: A node-Splitting algorithm for R-tree based on Objects’ Locations Distribution

Abstract

Spatial data indexing methods are of extreme importance as they massively build up as a result of the explosive growth in capturing data with spatial features. No matter how much the data size is, eventually it will reside on disk pages. Disk pages have to be properly indexed to preserve spatial properties of objects, optimise disk space usage and improve objects’ retrieval performance. One of the most popular spatial data indexes is the R-tree which is a height balanced tree data structure, where leaf nodes resemble disk pages and contain pointers to objects’ locations. A single tree node can host up to a maximum number of objects, where any more insertion makes it an overflown node and it has to be split. Better splits lead to better index performance and more utilisation of disk space. In this work, we introduce a new way of finding the most proper split for an overflown node in the R-tree index. The proposed work scans – in a linear cost – the overflown node’s objects once to identify the distribution of objects’ locations (minimum bounding rectangles (MBRs)) in relative to its node’s bounding rectangle (node’s MBR). It uses objects’ locations to calculate – for each main axis – the split quality factors: expected overlap between resulting nodes, objects distribution evenness among resulting nodes and the perimeter of resulting nodes. The axis with better combined quality factors values is selected as the split axis. The Splitting based on Objects’ Locations Distribution (SOLD) algorithm was implemented and tested against two other splitting algorithms, experiments using synthetic and real data files showed good results and it outperformed both algorithms in index creation tests and data retrieval tests.

Keywords

Multidimensional indexes node splitting R-tree spatial database spatial indexing

Get full access to this article

View all access options for this article.

References

Yang

Spatial network big data: challenges, approaches, and opportunities. PhD Thesis, University of Minnesota, Minneapolis, MN, 2015.

Almobaideen

Al-Khateeb

Sleit

et al . Improved stability based partially disjoint AOMDV. Int J Comm Netw Syst Sci2013; 6(5): 244–250.

Ooi

Sacks-Davis

Han

Indexing in spatial databases. Unpublished/Technical Papers, 1993, http://www.comp.nus.edu.sg/~ooibc/spatialsurvey.pdf.

Patel

Garg

Comparison of advance tree data structures. Int J Comput Appl2012; 41(2): 11–21.

Sleit

Dalhoum

Al-Dhamari

et al . Efficient enhancement on cellular automata for data mining. In: Proceedings of the 13th WSEAS international conference on Systems, Rodos, 22–24 July 2009, pp. 616–620. Stevens Point, WI: World Scientific and Engineering Academy and Society (WSEAS).

Al-Badarneh

Al-Alaj

A. A

spatial index structure using dynamic recursive space partitioning. In: 2011 international conference on innovations in information technology (IIT), Abu Dhabi, United Arab Emirates, 25–27 April 2011, pp. 255–260. New York: IEEE.

Al-Badarneh

Al-Alaj

Mahafzah

BA.

Multi Small Index (MSI): a spatial indexing structure. J Inform Sci2013; 39(5): 643–660.

Zou

Wang

Cao

et al . Semantic overlay network for large-scale spatial information indexing. Comput Geosci2013; 57: 208–217.

Eldawy

Mokbel

MF.

SpatialHadoop: a MapReduce framework for spatial data. In: 2015 IEEE 31st international conference on data engineering (ICDE), Seoul, South Korea, 13–17 April 2015, pp. 1352–1363. New York: IEEE.

10.

Dragicevic

Castro

et al . Geospatial big data handling theory and methods: a review and research challenges. ISPRS J Photogramm2016; 115: 119–133.

11.

Sleit

Saadeh

Al-Dhamari

et al . An enhanced sub image matching algorithm for binary images. In: American conference on applied mathematics, Cambridge, MA, 27–29 January 2010, pp. 565–569. Stevens Point, WI: World Scientific and Engineering Academy and Society (WSEAS).

12.

Sleit

AlMobaideen

Baarah

et al . An efficient pattern matching algorithm. J Appl Sci2007; 7(18): 269–265.

13.

Manolopoulos

Nanopoulos

Papadopoulos

et al . R-trees: theory and applications. London: Springer Science & Business Media, 2010.

14.

Guttman

R-trees: a dynamic index structure for spatial searching. In: Proceedings of ACM SIGMOD conference, Boston, MA, 18–21 June 1984, pp. 47–57. New York: ACM.

15.

Papadias

Sellis

Theodoridis

et al . Topological relations in the world of minimum bounding rectangles: a study with R-trees. In: SIGMOD ‘95 proceedings of the 1995 ACM SIGMOD international conference on management of data, San Jose, CA, 22–25 May 1995. New York: ACM.

16.

Teng

Subramanya

SR.

Node splitting algorithms in tree-structured high-dimensional indexes for similarity search. In: Proceedings of the 2002 ACM symposium on applied computing, Madrid, 11–14 March 2002, pp. 766–770. New York: ACM.

17.

Beckmann

Kriegel

Schneider

et al . The R*-tree: an efficient and robust access method for points and rectangles. SIGMOD Rec1990; 19(2): 322–331.

18.

Berchtold

Keim

Kriegel

H-P.

The X-tree: an index structure for high-dimensional data. In: Proceedings of the 22nd international conference on very large data bases, Mumbai, India, 3–6 September 1996, pp. 28–39. San Francisco, CA: Morgan Kaufmann.

19.

Ang

Tan

TC.

New linear node splitting algorithm for R-trees. In: International symposium on advances in spatial databases, Berlin, 15–18 July 1997, pp. 337–349. Berlin: Springer.

20.

Sellis

Roussopoulos

Faloutsos

The R+-tree: a dynamic index for multidimensional objects. In: Proceedings of 13th international conference on very large data bases, Brighton, 1–4 September 1987.

21.

Kamel

Faloutsos

Hilbert R-tree: an improved R-tree using fractals. In: Proceedings of the 20th international conference on very large data bases, Santiago de Chile, 12–15 September 1994. San Francisco, CA: Morgan Kaufmann.

22.

Liu

Fang

Han

C. A

new R-tree node splitting algorithm using MBR partition policy. In: 2009 17th international conference on geoinformatics, Fairfax, VA, 12–14 August 2009, pp. 1–6. New York: IEEE.

23.

Al-Badarneh

Yaseen

Hmeidi

A new enhancement to the R-tree node splitting. J Inform Sci2010; 36(1): 3–18.

24.

Wang

Chen

A new solution of node splitting to the R Tree algorithm. In: 2010 international conference on intelligent control and information processing (ICICIP), Dalian, China, 13–15 August 2010, pp. 611–614. New York: IEEE.

25.

Korotkov

A new double sorting-based node splitting algorithm for R-tree. Program Comput Soft+2012; 38(3): 109–118.

26.

Sleit

Al-Nsour

Corner-based splitting: an improved node splitting algorithm for R-tree. J Inform Sci2014; 40(2): 222–236.

27.

Arafat

Global center point splitting: new linear node splitting algorithm for R-trees. An-Najah Univ J Res (N Sc)2016; 30(1): 112–126.

28.

Theodoridis

Sellis

A model for the prediction of R-tree performance. In: Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, Montreal, QC, Canada, 4–6 June 1996, pp. 161–171. New York: ACM.