Dynamic indexability and lower bounds for dynamic one-dimensional range query indexes

ABSTRACT

The B-tree is a fundamental external index structure that is widely used for answering one-dimensional range reporting queries. Given a set of N keys, a range query can be answered in O(log_B NoverM + KoverB) I/Os, where B is the disk block size, K the output size, and M the size of the main memory buffer. When keys are inserted or deleted, the B-tree is updated in O(log_B N) I/Os, if we require the resulting changes to be committed to disk right away. Otherwise, the memory buffer can be used to buffer the recent updates, and changes can be written to disk in batches, which significantly lowers the amortized update cost. A systematic way of batching up updates is to use the logarithmic method, combined with fractional cascading, resulting in a dynamic B-tree that supports insertions in O(1overB log NoverM) I/Os and queries in O(log NoverM + KoverB) I/Os. Such bounds have also been matched by several known dynamic B-tree variants in the database literature. Note that, however, the query cost of these dynamic B-trees is substantially worse than the O(log_B NoverM + KoverB) bound of the static B-tree by a factor of ?(log B).

In this paper, we prove that for any dynamic one dimensional range query index structure with query cost O(q + KoverB) and amortized insertion cost O(u/B), the tradeoff q · log(u/q) = ©(log B) must hold if q = O(log B). For most reasonable values of the parameters, we have NoverM = B^O(1), in which case our query-insertion tradeoff implies that the bounds mentioned above are already optimal. We also prove a lower bound of u · log q = ©(log B), which is relevant for larger values of q. Our lower bounds hold in a dynamic version of the indexability model, which is of independent interests. Dynamic indexability is a clean yet powerful model for studying dynamic indexing problems, and can potentially lead to more interesting complexity results.

REFERENCES

• 1: Stephen Alstrup , Gerth Brodal , Theis Rauhe, Optimal static range reporting in one dimension, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.476-482, July 2001, Hersonissos, Greece [doi>10.1145/380752.380842]
• 2: L. Arge. The buffer tree: A technique for designing batched external data structures. Algorithmica, 37(1):1--24, 2003. See also WADS'95.
• 3: Lars Arge , Vasilis Samoladas , Jeffrey Scott Vitter, On two-dimensional indexability and optimal range search indexing, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.346-357, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.304010]
• 4: Lars Arge , Vasilis Samoladas , Ke Yi, Optimal External Memory Planar Point Enclosure, Algorithmica, v.54 n.3, p.337-352, May 2009 [doi>10.1007/s00453-007-9126-2]
• 5: R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, 1:173--189, 1972.
• 6: Paul Beame , Faith E. Fich, Optimal bounds for the predecessor problem and related problems, Journal of Computer and System Sciences, v.65 n.1, p.38-72, August 2002 [doi>10.1006/jcss.2002.1822]
• 7: J. L. Bentley and J. B. Saxe. Decomposable searching problems I: Static-to-dynamic transformation. Journal of Algorithms, 1:301--358, 1980.
• 8: Gerth Stolting Brodal , Rolf Fagerberg, Lower bounds for external memory dictionaries, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 9: Adam L. Buchsbaum , Michael Goldwasser , Suresh Venkatasubramanian , Jeffery R. Westbrook, On external memory graph traversal, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.859-860, January 09-11, 2000, San Francisco, California, United States
• 10: B. Chazelle and L. J. Guibas. Fractional cascading: I. A data structuring technique. Algorithmica, 1:133--162, 1986.
• 11: Joseph M. Hellerstein , Elias Koutsoupias , Daniel P. Miranker , Christos H. Papadimitriou , Vasilis Samoladas, On a model of indexability and its bounds for range queries, Journal of the ACM (JACM), v.49 n.1, p.35-55, January 2002 [doi>10.1145/505241.505244]
• 12: Joseph M. Hellerstein , Elias Koutsoupias , Christos H. Papadimitriou, On the analysis of indexing schemes, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.249-256, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263688]
• 13: H. V. Jagadish , P. P. S. Narayan , S. Seshadri , S. Sudarshan , Rama Kanneganti, Incremental Organization for Data Recording and Warehousing, Proceedings of the 23rd International Conference on Very Large Data Bases, p.16-25, August 25-29, 1997
• 14: Chris Jermaine , Anindya Datta , Edward Omiecinski, A Novel Index Supporting High Volume Data Warehouse Insertion, Proceedings of the 25th International Conference on Very Large Data Bases, p.235-246, September 07-10, 1999
• 15: D. E. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming. Addison-Wesley, Reading, MA, 1973.
• 16: Elias Koutsoupias , D. S. Taylor, Tight bounds for 2-dimensional indexing schemes, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.52-58, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275494]
• 17: Christian Worm Mortensen , Rasmus Pagh , Mihai Pǎtraçcu, On dynamic range reporting in one dimension, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060606]
• 18: Patrick O'Neil , Edward Cheng , Dieter Gawlick , Elizabeth O'Neil, The log-structured merge-tree (LSM-tree), Acta Informatica, v.33 n.4, p.351-385, 1996 [doi>10.1007/s002360050048]
• 19: Vasilis Samoladas , Daniel P. Miranker, A lower bound theorem for indexing schemes and its application to multidimensional range queries, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.44-51, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275493]
• 20: Z. Wei, K. Yi, and Q. Zhang. Dynamic external hashing: The limit of buffering. Manuscript.
• 21: Andrew Chi-Chih Yao, Should Tables Be Sorted?, Journal of the ACM (JACM), v.28 n.3, p.615-628, July 1981 [doi>10.1145/322261.322274]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.3 Tradeoffs among Complexity Measures

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Theory

Keywords:
dynamization, indexability, lower bound, range query