Large Spatial Database Indexing with aX-tree

Authors

  • Grace L. Samson  Department of Informatics, University of Huddersfield, United Kingdom
  • Mistura M. Usman  Department of Computer Science, University of Abuja, Gwagwalada, Federal Capital Territory, Nigeria
  • Aminat A. Showole  Department of Computer Science, University of Abuja, Gwagwalada, Federal Capital Territory, Nigeria
  • Joan Lu  Department of Informatics, University of Huddersfield, United Kingdom
  • Hadeel Jazzaa  School of Computing and Engineering, University of Huddersfield, United Kingdom

Keywords:

Super-Nodes, Bulk-loading, X-tree, Spatial indexing, Sorting, Spatial Data Management, Shape-files, Spatial Coordinate.

Abstract

Spatial databases are optimized for the management of data stored based on their geometric space. Researchers through high degree scalability have proposed several spatial indexing structures towards this effect. Among these indexing structures is the X-tree. The existing X-trees and its variants are designed for dynamic environment, with the capability for handling insertions and deletions. Notwithstanding, the X-tree degrades on retrieval performance as dimensionality increases and brings about poor worst-case performance than sequential scan. We propose a new X-tree packing techniques for static spatial databases which performs better in space utilization through cautious packing. This new improved structure yields two basic advantage: It reduces the space overhead of the index and produces a better response time, because the aX-tree has a higher fan-out and so the tree always ends up shorter. New model for super-node construction and effective method for optimal packing using an improved str bulk-loading technique is proposed. The study reveals that proposed system performs better than many existing spatial indexing structures.

References

  1. Vieira, M. R. and Tsotras, V. J. (2013) Spatio-Temporal Databases: Complex Motion Pattern Queries. Springer
  2. Tian, Y., Ji, Y., and Scholer, J. (2015) “A prototype spatio-temporal database built on top of relational database”. Paper presented at the 14-19. doi:10.1109/ITNG.2015.8
  3.  Samson, G. L., & Lu, J. (2016). PaX-DBSCAN: A PROPOSED ALGORITHM FOR IMPROVED CLUSTERING. In M. R. Pańkowska (Ed.) Studia Ekonomiczne. Zeszyty Naukowe, (269524th ed.). Katowice: Wydawnictwo Uniwersytetu Ekonomicznego w Katowicach. Retrieved from www.sbc.org.pl/Content/269524
  4. Samson, G. L., LU, J., and XU, Q. (2016) Large spatial datasets: Present Challenges, future opportunities. Int'l Conference on Change, Innovation, Informaticsand Disruptive Technology,North America,dec.2016. Availableat: <http://proceedings.sriweb.org/repository/index.php/ICCIIDT/icciidtt_london/paper/view/24>. Date accessed: 28 Dec. 2016.
  5. Samson, G. L., Lu, J., Usman, M. M., & Xu, Q. (2017). Spatial Databases: An Overview. In J. Lu, & Q. Xu (Eds.), Ontologies and Big Data Considerations for Effective Intelligence (pp. 111-149). Hershey, PA: IGI Global. doi:10.4018/978-1-5225-2058-0.ch003. Available at: http://www.igi-global.com/chapter/spatial-databases/177391.
  6. Mauder, M., Emrich, T., Kriegel, H., Renz, M., Trajcevski, G.,and Züfle, A. (2015) “Minimal spatio-temporal database repairs”. Paper presented at the 492-495. doi:10.1145/2525314.2525468
  7. Kamlesh, K. Pandey., Rajat, K. Y., Anshu, D., and Pradeep, K. S. (2015), “A Analysis of Different Type of Advance database System For Data Mining Based on Basic Factor”, International Journal on Recent and Innovation Trends in Computing and Communication (IJRITCC), 3 (2) ISSN: 2321-8169, PP: 456 - 460, DOI: 10.17762/ijritcc2321-8169.150206
  8. Billings, S. (2013) Nonlinear system identification: NARMAX methods in the time, frequency, and spatio-temporal domains (1st ed.). Hoboken: Wiley.
  9. Meng, X., Ding, Z., and Xu, J. (2014). Moving objects management: Models, techniques and applications (2; 2nd 2014; ed.). Dordrecht: Springer Berlin Heidelberg. doi:10.1007/978-3-642-38276-5
  10. Huang, Y., and He, Z. (2015; 2014 ) “Processing continuous K-nearest skyline query with uncertainty in spatio-temporal databases” Journal of Intelligent Information Systems, 45(2), 165-186. doi:10.1007/s10844-014-0344-1
  11. Kang, C., Pugliese, A., Grant, J., & Subrahmanian, V. S. (2014). STUN: Querying spatio-temporal uncertain (social) networks. Social Network Analysis and Mining, 4(1), 1-19. doi:10.1007/s13278-014-0156-x
  12. Moussalli, R., Absalyamov, I., Vieira, M. R., Najjar, W., and Tsotras, V. J. (2015; 2014;) “High performance FPGA and GPU complex pattern matching over spatio-temporal streams”. Geoinformatica, 19(2), 405-434. doi:10.1007/s10707-014-0217-3
  13. Secchi, P., Vantini, S., and Vitelli, V. (2015) “Analysis of spatio-temporal mobile phone data: A case study in the metropolitan area of milan” Statistical Methods & Applications, 24(2), 279-300. doi:10.1007/s10260-014-0294-
  14. Eldawy, A., Mokbel, M. F., Alharthi, S., Alzaidy, A., Tarek, K., and Ghani, S. (2015) SHAHED: “A MapReduce-based system for querying and visualizing spatio-temporal satellite data”. Paper presented at the 1585-1596. doi:10.1109/ICDE.2015.7113427
  15. Eldawy, A., & Mokbel, M. F. (2015, June). The Era of Big Spatial Data: Challenges and Opportunities. In 2015 16th IEEE International Conference on Mobile Data Management (Vol. 2, pp. 7-10). IEEE
  16. Candan, K. S. and Sapino, M. L. (2010). Data management for multimedia retrieval. Cambridge University Press.
  17. Patel, P., and Garg, D. (2012) Comparison of Advance Tree Data Structures.arXiv preprint arXiv:1209.6495.
  18. Ajit, S. and Deepak, G. (2011) "Implementation and Performance Analysis of Exponential Tree Sorting" International Journal of Computer Applications ISBN: 978-93-80752-86-3 24 (3) pp. 34-38.
  19. Samet, H. (2009) “Sorting spatial data by spatial occupancy” GeoSpatial Visual Analytics (pp. 31-43). Springer Netherlands.
  20. Cazals, F., Emiris, I. Z., Chazal, F., Gärtner, B., Lammersen, C., Giesen, J., and Rote, G. (2013). “D2. 1: Handling High-Dimensional Data”. Computational Geometric Learning (CGL) Technical Report No.: CGL-TR-01.
  21. Park, Y., Liu, L., and Yoo, J. (2013) “fast and compact indexing technique for moving objects” Information Reuse and Integration (IRI), 2013 IEEE 14th International Conference on (pp. 562-569). IEEE.
  22. Guting, R. H. (1994) “An introduction to spatial database systems” The VLDB Journal—The International Journal on Very Large Data Bases, 3(4), 357-399.
  23. Manolopoulos, Y., Nanopoulos, A., Papadopoulos, A. N., and Theodoridis, Y. (2010) R-trees: Theory and Applications. Springer Science and Business Media.
  24. Jin, S., Kim, O., & Feng, W. (2013, June). MX-tree: a double hierarchical metric index with overlap reduction. In International Conference on Computational Science and Its Applications (pp. 574-589). Springer Berlin Heidelberg.
  25. Dash, J. Patra, D. & Pradhan C. (2015)”A Proposed Hybrid Spatial Indexing: QX Tree” International Journal of Computer Science and Information Technologies. 6 (2) pp. 1737-1739. ISBN:0975-9646
  26. Berchtold, S., Keim, D. A.., Kriegel, and Hans-Peter (1996). "The X-tree: An Index Structure for High-Dimensional Data". Proceedings of the 22nd VLDB Conference (Mumbai, India): 28–39.
  27. Berchtold, S., Keim, D. A., & Kriegel, H. P. (2001). An index structure for high-dimensional data. Readings in multimedia computing and networking. pp. 451.
  28. Ciaccia, P., Patella, M., and Zezula, P., 1997. M-tree: An E cient Access Method for Similarity Search in Metric Spaces, in VLDB'97, pp. 426-435
  29. Stuller, J., Pokorny, J., Bernhard, T. and Yoshifumi, M. (2000) Current Issues in Databases and Information Systems: East-European Conference on Advances in Databases and Information Systems Held Jointly with International Conference on Database Systems for Advanced Applications, ADBIS-DASFAA 2000 Prague, Czech Republic, September 5-9, 2000 Proceedings
  30. Doja, M. N., Jain, S., and Alam, M. A. (2012) “SAS: Implementation of scaled association rules on spatial multidimensional quantitative dataset” International Journal of Advanced Computer Science and Applications Vol. 3,(9) pp. 30-35
  31. Mamoulis, N. (2012). Spatial data management (1st ed.). Morgan & Claypool Publishers.
  32. Giao, B. C., and Anh, D. T. (2015) “Improving Sort-Tile-Recusive algorithm for R-tree packing in indexing time series” In Computing & Communication Technologies-Research, Innovation, and Vision for the Future (RIVF), 2015 IEEE RIVF International Conference on (pp. 117-122). IEEE.
  33. Leutenegger, S. T., Edgington, J. M. and M. A. Lopez. (1997) "STR: A simple and efficient algorithm," in Proceedings 13th International Conference on Data Engineering, p. 497–506
  34. Preparata F. P. and Shamos M. I. (1985.) Computational Geometry: An Introduction. Springer-Verlag, New York.
  35. Sagan H. (1994). Space-Filling Curves. Nueva York: Springer-Verlag.
  36. Samet, H. (2006) Foundations of Multidimensional and Metric Data Structures: Mor-ganKaufmann
  37. Roussopoulos, N., Kelley, S., & Vincent, F. (1995, June). Nearest neighbor queries. In ACM sigmod record (Vol. 24, No. 2, pp. 71-79). ACM.
  38. Kame I., and Faloutsos C. (1993) On Packing R-trees Proceedings of the second international conference on Information and knowledge management Pages 490-499.
  39. Shan, S., and Wang, G. G. (2010) “Survey of modeling and optimization strategies to solve high-dimensional design problems with computationally-expensive black-box functions” Structural and Multidisciplinary Optimization, 41(2), 219-241.
  40. Lodi, A., Martello, S., and Monaci, M. (2002) "Two-dimensional packing problems: A survey". European Journal of Operational Research (Elsevier)141: 241–252. doi:10.1016/s0377-2217(02)00123-6.
  41. Dolci, C., Salvini, D., Schrattner, M. and Weibel R. (2010) “Spatial Partitioning and Indexing” Geographic Information Technology Training Alliance (GITTA). Available at: < http://www.gitta.info/SpatPartitio/en/text/SpatPartitio.pdf>. accessed: 30 Dec. 2016.
  42. Lee, Y. J., Lee, D. M., Ryu, S. J., & Chung, C. W. (1996, September). Controlled decomposition strategy for complex spatial objects. In International Conference on Database and Expert Systems Applications (pp. 207-223). Springer Berlin Heidelberg.
  43. Assent I., Krieger R., Muller E. and Seidl T. (2007) DUSC: Dimensionality Unbiased Subspace Clustering IEEE International Conference on Data Mining (ICDM 2007), Omaha, Nebraska, USA, pages 409-414
  44. Arya, S., Mount, D. M., Netanyahu, N., Silverman, R., & Wu, A. Y. (1994). An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. In Proc. 5th ACM-SIAM Sympos. Discrete Algorithms (pp. 573-582).

IInternational Journal of Scientific Research in Computer Science, Engineering and Information Technology

Downloads

Published

2018-04-30

Issue

Volume 3, Issue 3, March-April-2018

Section

Research Articles

License

Copyright (c) IJSRCSEIT

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

[1]
Grace L. Samson, Mistura M. Usman, Aminat A. Showole, Joan Lu, Hadeel Jazzaa, " Large Spatial Database Indexing with aX-tree, IInternational Journal of Scientific Research in Computer Science, Engineering and Information Technology(IJSRCSEIT), ISSN : 2456-3307, Volume 3, Issue 3, pp.759-773, March-April-2018.