[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

MBR Compression in Spatial Databases Using Semi-Approximation Scheme

  • Conference paper
Knowledge-Based Intelligent Information and Engineering Systems (KES 2006)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 4251))

  • 1277 Accesses

Abstract

Studies on spatial index, which is used for location-based services in mobile computing or GIS have increased in proportion to the increase in the spatial data. However, these studies were on the indices based on R-tree, and there are a few studies on how to increase the search performance of the spatial data by compressing MBRs. This study was conducted in order to propose a new MBR compression scheme, SA (Semi-approximation), and a SAR-tree that indexes spatial data using R-tree. The basic idea of this paper is the compression of MBRs in a spatial index. Since SA decreases the size of MBR keys, halves QMBR enlargement, and increases node utilization. Therefore, the SAR-tree heightens the overall search performance. The experiments show that the proposed index has increased performance, higher than that of the pre-established schemes on compression of MBRs.

This work was supported by the second Brain Korea 21 Project in 2006.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Guttman, A.: R-trees: A Dynamic Index Structure for Spatial Searching. In: ACM SIGMOD Int. Conf. on Management of Data, pp. 47–57 (1984)

    Google Scholar 

  2. Berchtold, S., Keim, D.A., Kriegel, H.P.: The X-tree: An index structure for high-dimensional data. In: Proc. 22nd Int. Conf. on VLDB, pp. 28–39 (1996)

    Google Scholar 

  3. Katayama, N., Satoh, S.: The SR-tree: An index structure for high-dimensional nearest neighbor queries. In: Proc. ACM SIGMOD Int. Conf. on Management of Data, pp. 380–396 (1997)

    Google Scholar 

  4. Kim, J.D., Moon, S.H., Choi, J.O.: A Spatial Index Using MBR Compression and Hashing Technique for Mobile Map Service. In: Zhou, L.-z., Ooi, B.-C., Meng, X. (eds.) DASFAA 2005. LNCS, vol. 3453, pp. 625–636. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  5. Kim, K.H., Cha, S.K., Kwon, K.J.: Optimizing Multidimensional Index trees for Main Memory Access. In: Int. Conf. on ACM SIGMD, pp. 139–150 (2001)

    Google Scholar 

  6. Sakurai, Y., Yoshikawa, M., Uemura, S., Kojima, H.: Spatial indexing of high-dimensional data based on relative approximation. VLDB J., 93–108 (2002)

    Google Scholar 

  7. Goldstein, J., Ramakrishnan, R., Shaft, U.: Compressing Relations and Indexes. In: Proceedings of IEEE Conference on Data Engineering, pp. 370–379 (1998)

    Google Scholar 

  8. The R-tree Portal, http://www.rtreeportal.org

  9. Schwetman, H.: CSIM19: A Powerful Tool for Building System Models. In: Proceedings of the 2001 Winter Simulation Conference, pp. 250–255 (2001)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, Korea University, Seoul, Korea

    Jongwan Kim, SeokJin Im, Sang-Won Kang & Chong-Sun Hwang

  2. Division of Information and Communication, Cheonan University, Cheonan, Korea

    SeongHoon Lee

Authors
  1. Jongwan Kim
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. SeokJin Im
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Sang-Won Kang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. SeongHoon Lee
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Chong-Sun Hwang
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. School of Design, Engineering and Computing, Bournemouth University, UK

    Bogdan Gabrys

  2. Centre for SMART Systems, School of Environment and Technology, University of Brighton, BN2 4GJ, Brighton, UK

    Robert J. Howlett

  3. School of Electrical and Information Engineering, Knowledge Based Intelligent Engineering Systems Centre, University of South Australia, Mawson Lakes, 5095, SA, Australia

    Lakhmi C. Jain

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Kim, J., Im, S., Kang, SW., Lee, S., Hwang, CS. (2006). MBR Compression in Spatial Databases Using Semi-Approximation Scheme. In: Gabrys, B., Howlett, R.J., Jain, L.C. (eds) Knowledge-Based Intelligent Information and Engineering Systems. KES 2006. Lecture Notes in Computer Science(), vol 4251. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11892960_135

Download citation

  • DOI: https://doi.org/10.1007/11892960_135

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-46535-5

  • Online ISBN: 978-3-540-46536-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics