×

ISB-tree: A new indexing scheme with efficient expected behaviour. (English) Zbl 1215.68085

Summary: We present the interpolation search B-tree (ISB-tree), a new cache-aware indexing scheme that supports update operations (insertions and deletions) in \(O(1)\) worst-case block transfers and search operations in \(O(\log _{\text{B}} \log n)\) expected block transfers, where B represents the disk block size and \(n\) denotes the number of stored elements. The expected search bound holds with high probability for a large class of (unknown) input distributions. The worst-case search bound of our indexing scheme is \(O(\log _{\text{B}} n)\) block transfers. Our update and expected search bounds constitute a considerable improvement over the \(O(\log _{\text{B}} n)\) worst-case block transfer bounds for search and update operations achieved by the B-tree and its numerous variants. This is also verified by an accompanying experimental study.

MSC:

68P05 Data structures

Software:

LEDA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P.K. Agarwal, L. Arge, G. Brodal, J.S. Vitter, I/O-efficient dynamic point location in monotone planar subdivisions, in: Proc. 10th ACM-SIAM Symp. on Discrete Algorithms - SODA’99, 1999, pp. 11-20.; P.K. Agarwal, L. Arge, G. Brodal, J.S. Vitter, I/O-efficient dynamic point location in monotone planar subdivisions, in: Proc. 10th ACM-SIAM Symp. on Discrete Algorithms - SODA’99, 1999, pp. 11-20. · Zbl 0938.68144
[2] Aggarwal, A.; Vitter, J. S., The input/output complexity of sorting and related problems, Commun. ACM, 31, 9, 1116-1127 (1988)
[3] Andersson, A.; Mattson, C., Dynamic interpolation search in \(o(\log \log n)\) time, (Proc. ICALP’93. Proc. ICALP’93, Lecture Notes in Comput. Sci., vol. 700 (1993), Springer-Verlag), 15-27
[4] L. Arge, J.S. Vitter, Optimal dynamic interval management in external memory, in: Proc. 37th IEEE Symp. on Foundations of Computer Science - FOCS’96, 1996, pp. 560-569.; L. Arge, J.S. Vitter, Optimal dynamic interval management in external memory, in: Proc. 37th IEEE Symp. on Foundations of Computer Science - FOCS’96, 1996, pp. 560-569.
[5] Baeza-Yates, R. A., Bounded disorder: The effects of the index, Theoret. Comput. Sci., 168, 21-38 (1996) · Zbl 0874.68233
[6] Bayer, R.; McCreight, E., Organization of large ordered indexes, Acta Inform., 1, 173-189 (1972) · Zbl 0226.68008
[7] N. Beckmann, H. Krigel, R. Schneider, B. Seeger, The R*-tree: An efficient and robust access method for points and rectangles, SIGMOD, 1990.; N. Beckmann, H. Krigel, R. Schneider, B. Seeger, The R*-tree: An efficient and robust access method for points and rectangles, SIGMOD, 1990.
[8] Comer, D., The ubiquitous B-tree, ACM Comput. Surveys, 11, 2, 121-137 (1979) · Zbl 0419.68034
[9] Dietz, P.; Raman, R., A constant update time finger search tree, Inform. Process. Lett., 52, 147-154 (1994) · Zbl 0938.68586
[10] Fagin, R.; Nievergelt, J.; Pippinger, N.; Strong, H. R., Extendible hashing-A fast access method for dynamic files, ACM Trans. Database Syst., 4, 3, 315-344 (1979)
[11] Ferragina, P.; Grossi, R., The string B-tree: A new data structure for string search in external memory and its applications, J. ACM, 46, 2, 236-280 (1999) · Zbl 1065.68518
[12] Fox, E.; Chen, Q.; Daoud, A., Practical minimal perfect hash functions for large databases, Commun. ACM, 35, 5, 105-121 (1992)
[13] M. Frigo, C.E. Leiserson, H. Prokop, S. Ramachandran, Cache-oblivious algorithms, in: Proc. 40th IEEE Symp. on Foundations of Computer Science - FOCS’99, 1999, pp. 285-297.; M. Frigo, C.E. Leiserson, H. Prokop, S. Ramachandran, Cache-oblivious algorithms, in: Proc. 40th IEEE Symp. on Foundations of Computer Science - FOCS’99, 1999, pp. 285-297. · Zbl 1295.68236
[14] Kaporis, A.; Makris, C.; Sioutas, S.; Tsakalidis, A.; Tsichlas, K.; Zaroliagis, C., Improved bounds for finger search on a RAM, (Algorithms - ESA 2003. Algorithms - ESA 2003, Lecture Notes in Comput. Sci., vol. 2832 (2003), Springer-Verlag), 325-336, Full version in: Algorithmica, forthcoming · Zbl 1266.68098
[15] Kaporis, A.; Makris, C.; Mavritsakis, G.; Sioutas, S.; Tsakalidis, A.; Tsichlas, K.; Zaroliagis, C., ISB-tree: A new indexing scheme with efficient expected behaviour, (Algorithms and Computation - ISAAC 2005. Algorithms and Computation - ISAAC 2005, Lecture Notes in Comput. Sci., vol. 3827 (2005), Springer-Verlag), 318-327 · Zbl 1173.68453
[16] Knuth, D. E., Sorting and searching, (The Art of Computer Programming, vol. 3 (1973), Addison-Wesley) · Zbl 0883.68015
[17] Knuth, D. E., Deletions that preserve randomness, IEEE Trans. Softw. Eng., 3, 351-359 (1977) · Zbl 0355.68036
[18] Lehman, P.; Bing Yao, S., Efficient locking for concurrent operations on B-trees, ACM Trans. Database Syst., 6, 4, 650-670 (1981) · Zbl 0465.68061
[19] Levcopoulos, C.; Overmars, M. H., Balanced search tree with \(O(1)\) worst-case update time, Acta Inform., 26, 269-277 (1988) · Zbl 0662.68016
[20] W. Litwin, Linear hashing: A new tool for files and tables addressing, Proc. of the 6th Internat. Conf. on Very Large Databases, 1980, pp. 212-223.; W. Litwin, Linear hashing: A new tool for files and tables addressing, Proc. of the 6th Internat. Conf. on Very Large Databases, 1980, pp. 212-223.
[21] Litwin, W.; Lomet, D., A new method for fast data searches with keys, IEEE Software, 4, 2, 16-24 (1987)
[22] Lomet, D., A simple bounded disorder file organization with good performance, ACM Trans. Database Syst., 13, 4, 525-551 (1988) · Zbl 0665.68010
[23] Manolopoulos, Y.; Theodoridis, Y.; Tsotras, V., Advanced Database Indexing (2000), Kluwer Academic Publishers · Zbl 0943.68049
[24] Mehlhorn, K.; Näher, S., LEDA: A Platform for Combinatorial and Geometric Computing (1999), Cambridge University Press · Zbl 0976.68156
[25] Mehlhorn, K.; Tsakalidis, A., Dynamic interpolation search, J. ACM, 40, 3, 621-634 (1993) · Zbl 0785.68019
[26] O’Neil, P. E., The SB-tree. An index-sequential structure for high-performance sequential access, Acta Inform., 29, 3, 241-265 (1992) · Zbl 0758.68026
[27] Overmars, M.; van Leeuwen, J., Worst case optimal insertion and deletion methods for decomposable searching problems, Inform. Process. Lett., 12, 4, 168-173 (1981) · Zbl 0459.68026
[28] R. Raman, Eliminating amortization, on data structures with guaranteed response time, PhD Thesis, Department of Computer Science, University of Rochester, New York, 1992; Technical Report TR-439, 1992.; R. Raman, Eliminating amortization, on data structures with guaranteed response time, PhD Thesis, Department of Computer Science, University of Rochester, New York, 1992; Technical Report TR-439, 1992.
[29] Rao, J.; Ross, K., Cache conscious indexing for decision-support in main memory, (Atkinson, M.; etal., Proc. International Conference on Very Large Databases, vol. 25 (1999), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 78-89
[30] J. Rao, K. Ross, Making B+-trees cache conscious in main memory, in: Proc. ACM SIGMOD International Conference on Management of Data, 2000, pp. 475-486.; J. Rao, K. Ross, Making B+-trees cache conscious in main memory, in: Proc. ACM SIGMOD International Conference on Management of Data, 2000, pp. 475-486.
[31] Saltzberg, B.; Tsotras, V., Comparison of access methods for time-evolving data, ACM Comput. Surveys, 31, 158-221 (1999)
[32] B. Seeger, P.A. Larson, Multi-disk B-trees, in: Proc. SIGMOD Conference 1991, pp. 436-445.; B. Seeger, P.A. Larson, Multi-disk B-trees, in: Proc. SIGMOD Conference 1991, pp. 436-445.
[33] Srinivasan, V.; Carey, M. J., Performance of B+ tree concurrency algorithms, VLDB J., 2, 4, 361-406 (1993)
[34] Theodoridis, Y., The R-tree Portal (2003), [Tiger1] and [Tiger2] data sets in:
[35] Vitter, J. S., External memory algorithms and data structures: Dealing with massive data, ACM Comput. Surveys, 33, 2, 209-271 (2001)
[36] Vitter, J. S.; Shriver, E. A.M., Optimal algorithms for parallel memory I: Two-level memories, Algorithmica, 12, 2-3, 110-147 (1994) · Zbl 0917.68085
[37] Willard, D. E., Searching unindexed and nonuniformly generated files in \(\log \log N\) time, SIAM J. Comput., 14, 4, 1013-1029 (1985) · Zbl 0575.68061
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.