The week's pick
Reseach Article
Evaluating Various Quality Factors for Splitting Nodes in Tree-Structured Spatial Indices
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 180 - Number 29 |
| Year of Publication: 2018 |
| Authors: Esam Al-Nsour, Azzam Sleit, Mohammad Alshraideh |
10.5120/ijca2018916709
|
Esam Al-Nsour, Azzam Sleit, Mohammad Alshraideh . Evaluating Various Quality Factors for Splitting Nodes in Tree-Structured Spatial Indices. International Journal of Computer Applications. 180, 29 ( Mar 2018), 49-55. DOI=10.5120/ijca2018916709
Abstract
The massive increase of multi-dimensional (spatial) data collected, either in size or veracity, has demanded better spatial index techniques able to handle efficient storing and fast retrieval of spatial objects. No matter how big the data are, eventually it will reside on physical storage media arranged as a series of logical blocks with prefixed sizes resembling nodes in tree-structured spatial indices. Good node splitting strategy is essential since it affects; the final shape of the index, the overlap area between nodes, and the overall index performance. Better node splitting process results will be obtained if multiple splitting strategies (quality factors) were combined to govern the split decision, and it will eliminate the need for dynamic or static tree packing. Three widely used quality factors; minimizing total overlap area, even distribution of objects, and squared nodes’ margins, along with a fourth factor named the “preferred-axis” were merged in one combined value to govern the split decision. Provided results, for the index creation tests and different sized window queries performance, indicate the superiority of the combined quality factors strategy in comparison of other unilateral usage of quality factors. Provided results showed that combined quality-factors strategy had outperformed different two strategies found in the literature in both index creation tests and index performance tests. The obtained results were achieved without the need for any dynamic or static tree packing.
References
- Zou Z, Wang Y, Cao K, Qu T, Wang Z. Semantic overlay network for large-scale spatial information indexing. Computers & geosciences. 2013 Aug 31;57:208-17
- A Sleit, M Al-Akhras, I Juma, M Ali, Applying ordinal association rules for cleansing data with missing values, Journal of American Science 5 (3), 52-62, 2009
- W Almobaideen, D Al-Khateeb, A Sleit, M Qatawneh, K Qadadeh, Improved stability based partially disjoint AOMDV, Int'l J. of Communications, Network and System Sciences 6 (5), 244-250, 2011.
- A Sleit, H Saadeh, I Al-Dhamari, A Tareef, An enhanced sub image matching algorithm for binary images, RECENT ADVANCES in APPLIED MATHEMATICS, 565-569, 2010.
- A Sleit, W AlMobaideen, AH Baarah, AH Abusitta, An efficient pattern matching algorithm, Journal of Applied Sciences 7 (18), 2691-2695, 2007
- W Almobaideen, R Al-Soub, A Sleit, MSDM: Maximally spatial disjoint multipath routing protocol for manet, Communications and Network 5 (04), 316, 2013
- Sahr, K. and White, D., 1998. Discrete global grid systems. Computing Science and Statistics, pp.269-278.
- Samet, H., 1984. The quadtree and related hierarchical data structures. ACM Computing Surveys (CSUR), 16(2), pp.187-260.
- Morton, G. M. (1966), A computer Oriented Geodetic Data Base; and a New Technique in File Sequencing, Technical Report, Ottawa, Canada: IBM Ltd.
- Manolopoulos Y, Nanopoulos A, Papadopoulos A, Theodoridis Y. R-trees: Theory& Applications. Springer Sci.&Business Media; 2010Sep8.
- Guttman, A. R-Trees, a Dynamic Index Structure for Spatial Searching. Proceedings of ACM SIGMOD Conference 1984; 47-57.
- Sleit A, Al-Nsour E. Corner-based splitting: An improved node splitting algorithm for R-tree. Journal of Information Science. 2014 Apr; 40(2):222-36.
- Beckmann N, Kriegel HP, Schneider R, Seeger B. The R*-tree: an efficient and robust access method for points and rectangles. In: Acm Sigmod Record, 1990 May 1 (Vol. 19, No. 2, pp. 322-331). ACM.
- Al-Nsour, E., Sleit, A., and Alshraideh, M., 2017, December. R-tree node-splitting algorithm using combined quality factors and weights (CSCI), 2017 International Conference on (in press). IEEE.
- Al-Sayyed, R.M., Al-Nsour, E.Y. and Al-Omari, L.M., 2016. Extending Auditing Models to Correspond with Clients’ Needs in Cloud Environments. International Journal of Communications, Network and System Sciences, 9(09), p.347.
Index Terms
Keywords