Abstract
We introduce the SP-tree that is a variant of a multidimensional index structure, with the object of offering efficient sequential disk access. The SP-tree is based on the index clustering technique called the segment-page clustering (SP-clustering). Most relevant index pages are widely scattered on a disk due to dynamic page allocation, and thus many random disk accesses are required during the query processing. The SP-clustering avoids the scattering by storing the relevant nodes contiguously in a segment that contains a sequence of contiguous disk pages and improves the query performance by offering sequential disk access within a segment. Experimental results demonstrate that the SP-clustering improves the query performance up to several times compared with the traditional ones with respect to the total elapsed time.
This research was supported by Basic Science Research Program through the National Research Foundation of Kore (NRF) funded by the Ministry of Education (NRF-2014R1A1A2059306).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Henrich, A.: The LSDh-tree: an access structure for feature vectors. In: Proceedings of the International Conference on Data Engineering, pp. 362–369 (1998)
Henrich, A., Six, H.-W., Widmayer, P.: The LSD-tree: spatial access to multidimensional point and non-point objects. In: Proceedings of the ICDE, pp. 44–53 (1989)
Litwin, W., Lomet, D.B.: The bounded disorder access method. In: Proceedings of the IEEE International Conference on Data Engineering, pp. 38–48 (1986)
Lomet, D.B.: A simple bounded disorder file organization with good performance. ACM Trans. Database Syst. 13(4), 525–551 (1988)
O’Neil, P.E.: The SB-tree: an index-sequential structure for high-performance sequential access. Acta Informatica 29, 241–265 (1992)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Cha, GH. (2017). The SP-tree: A Clustered Index Structure for Efficient Sequential Access. In: Park, J., Pan, Y., Yi, G., Loia, V. (eds) Advances in Computer Science and Ubiquitous Computing. UCAWSN CUTE CSA 2016 2016 2016. Lecture Notes in Electrical Engineering, vol 421. Springer, Singapore. https://doi.org/10.1007/978-981-10-3023-9_16
Download citation
DOI: https://doi.org/10.1007/978-981-10-3023-9_16
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-10-3022-2
Online ISBN: 978-981-10-3023-9
eBook Packages: EngineeringEngineering (R0)