Secondary indexing in one dimension: beyond b-trees and bitmap indexes

ABSTRACT

Let ∑ be a finite, ordered alphabet, and consider a string x=χ₁χ₂... χ_n ∈ ∑ⁿ. A secondary index for x answers alphabet range queries of the form: Given a range [α_l,α_r] ⊆ ∑, return the set I_[αl,αr] = {i |χ_i ∈ >[α_l,α_r]}. Secondary indexes are heavily used in relational databases and scientific data analysis. It is well-known that the obvious solution, storing a dictionary for the set ∪_i{χ_i} with a position set associated with each character, does not always give optimal query time. In this paper we give the first theoretically optimal data structure for the secondary indexing problem. In the I/O model, the amount of data read when answering a query is within a constant factor of the minimum space needed to represent the set I_[αl,αr], assuming that the size of internal memory is (|∑| lg n)^δ blocks, for some constant δ > 0. The space usage of the data structure is O(nlg |∑|) bits in the worst case, and we further show how to bound the size of the data structure in terms of the 0th order entropy of x. We show how to support updates achieving various time-space trade-offs.

We also consider an approximate version of the basic secondary indexing problem where a query reports a superset of I_[αl,αr] containing each element not in I_[αl,αr] with probability at most ∈, where ∈ > 0 is the false positive probability. For this problem the amount of data that needs to be read by the query algorithm is reduced to O(|I_(αl,αr]| lg(1/∈)) bits.

REFERENCES

• 1: Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
• 2: Tan Apaydin , Guadalupe Canahuate , Hakan Ferhatosmanoglu , Ali Saman Tosun, Approximate encoding for direct access and query processing over compressed bitmaps, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 3: Lars Arge. The buffer tree: A technique for designing batched external data structures. Algorithmica, 37(1):1--24, 2003.
• 4: Lars Arge , Jeffrey Scott Vitter, Optimal External Memory Interval Management, SIAM Journal on Computing, v.32 n.6, p.1488-1508, 2003 [doi>10.1137/S009753970240481X]
• 5: Philip Bille, Anna Pagh, and Rasmus Pagh. Fast evaluation of union-intersection expressions. In Proceedings of the 18th International Symposium on Algorithms And Computation (ISAAC '07), volume 4835 of Lecture Notes in Computer Science, pages 739--750. Springer-Verlag, 2007.
• 6: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 7: 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
• 8: Larry Carter , Robert Floyd , John Gill , George Markowsky , Mark Wegman, Exact and approximate membership testers, Proceedings of the tenth annual ACM symposium on Theory of computing, p.59-65, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804332]
• 9: Chee-Yong Chan , Yannis E. Ioannidis, Bitmap index design and evaluation, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.355-366, June 01-04, 1998, Seattle, Washington, United States
• 10: Chee-Yong Chan , Yannis E. Ioannidis, An efficient bitmap encoding scheme for selection queries, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.215-226, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 11: Mark de Berg , Otfried Cheong , Marc van Kreveld , Mark Overmars, Computational Geometry: Algorithms and Applications, Springer-Verlag TELOS, Santa Clara, CA, 2008
• 12: Peter Elias. Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory, 21(2):194--203, March 1975.
• 13: Goetz Graefe, B-tree indexes for high update rates, ACM SIGMOD Record, v.35 n.1, p.39-44, March 2006 [doi>10.1145/1121995.1122002]
• 14: Patrick O'Neil , Dallan Quass, Improved query performance with variant indexes, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.38-49, May 11-15, 1997, Tucson, Arizona, United States
• 15: Vijayshankar Raman , Lin Qiao , Wei Han , Inderpal Narang , Ying-Lin Chen , Kou-Horng Yang , Fen-Ling Ling, Lazy, adaptive rid-list intersection, and its application to index anding, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247566]
• 16: Rishi Rakesh Sinha , Marianne Winslett, Multi-resolution bitmap indexes for scientific data, ACM Transactions on Database Systems (TODS), v.32 n.3, p.16-es, August 2007 [doi>10.1145/1272743.1272746]
• 17: Rishi Rakesh Sinha , Marianne Winslett , Kesheng Wu , Kurt Stockinger , Arie Shoshani, Adaptive Bitmap Indexes for Space-Constrained Systems, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.1418-1420, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497575]
• 18: Kesheng Wu , Ekow Otoo , Arie Shoshani, On the performance of bitmap indices for high cardinality attributes, Proceedings of the Thirtieth international conference on Very large data bases, p.24-35, August 31-September 03, 2004, Toronto, Canada

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

Additional Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Composite structures**

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing

General Terms:
Algorithms, Theory

Keywords:
b-tree, bitmap index, range query