Cell probe lower bounds for succinct data structures

ABSTRACT

In this paper, we consider several static data structure problems in the deterministic cell probe model. We develop a new technique for proving lower bounds for succinct data structures, where the redundancy in the storage can be small compared to the information-theoretic minimum. In fact, we succeed in matching (up to constant factors) the lower order terms of the existing data structures with the lower order terms provided by our lower bound. Using this technique, we obtain (i) the first lower bound for the problem of searching and retrieval of a substring in text; (ii) a cell probe lower bound for the problem of representing permutation π with queries π(i) and π⁻¹(i) that matches the lower order term of the existing data structures, and (iii) a lower bound for representing binary matrices that is also matches upper bounds for some set of parameters. The nature of all these problems is that we are to implement two operations that are in a reciprocal relation to each other (search and retrieval, computing forward and inverse element, operations on rows and columns of a matrix). As far as we know, this paper is the first to provide an insight into such problems.

REFERENCES

• 1: Miklós Ajtai. A lower bound for finding predecessors in yao's cell probe model. Combinatorica, 8(3):235--247, 1988.
• 2: Jérémy Barbay, Alexander Golynski, J. Ian Munro, and S. Srinivasa Rao. Adaptive searching in succinctly encoded binary relations and tree-structured documents. In Combinatorial Pattern Matching, pages 24--35, 2006.
• 3: Jérémy Barbay , Meng He , J. Ian Munro , S. Srinivasa Rao, Succinct indexes for strings, binary relations and multi-labeled trees, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.680-689, January 07-09, 2007, New Orleans, Louisiana
• 4: 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]
• 5: Erik D. Demaine , Alejandro López-Ortiz, A linear lower bound on index size for text retrieval, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.289-294, January 07-09, 2001, Washington, D.C., United States
• 6: Erik D. Demaine , Alejandro López-Ortiz, A linear lower bound on index size for text retrieval, Journal of Algorithms, v.48 n.1, p.2-15, August 2003 [doi>10.1016/S0196-6774(03)00043-9]
• 7: M. Farach, Optimal suffix tree construction with large alphabets, Proceedings of the 38th Annual Symposium on Foundations of Computer Science, p.137, October 19-22, 1997
• 8: Arash Farzan , J. Ian Munro, Succinct Representations of Arbitrary Graphs, Proceedings of the 16th annual European symposium on Algorithms, September 15-17, 2008, Karlsruhe, Germany [doi>10.1007/978-3-540-87744-8_33]
• 9: P. Ferragina , G. Manzini, Opportunistic data structures with applications, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.390, November 12-14, 2000
• 10: Paolo Ferragina , Giovanni Manzini, An experimental study of an opportunistic index, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.269-278, January 07-09, 2001, Washington, D.C., United States
• 11: Paolo Ferragina, Giovanni Manzini, Veli Mäkinen, and Gonzalo Navarro. An alphabet-friendly FM-index. In Proceedings of the 11th Symposium on String Processing and Information Retrieval, pages 150--160, 2004.
• 12: Anna Gál and Peter Bro Miltersen. The cell probe complexity of succinct data structures. In International Colloquium on Automata, Languages and Programming, pages 332--344, 2003.
• 13: R. Gennaro , L. Trevisan, Lower bounds on the efficiency of generic cryptographic constructions, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.305, November 12-14, 2000
• 14: Robert Giegerich and Stefan Kurtz. From ukkonen to mccreight and weiner: A unifying view of linear-time suffix tree construction. Algorithmica, 19(3):331--353, 1997.
• 15: Alexander Golynski. Upper and Lower Bounds for Text Indexing Data Structures. PhD thesis, University of Waterloo, http://www.cs.uwaterloo.ca/~imunro/Golynski.pdf, 2007.
• 16: Alexander Golynski , J. Ian Munro , S. Srinivasa Rao, Rank/select operations on large alphabets: a tool for text indexing, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.368-373, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109599]
• 17: Roberto Grossi , Ankur Gupta , Jeffrey Scott Vitter, High-order entropy-compressed text indexes, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 18: Roberto Grossi , Jeffrey Scott Vitter, Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.397-406, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335351]
• 19: Roberto Grossi , Jeffrey Scott Vitter, Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching, SIAM Journal on Computing, v.35 n.2, p.378-407, 2005 [doi>10.1137/S0097539702402354]
• 20: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 21: M. E. Hellman. A cryptanalytic time-memory trade-off. IEEE Transactions on Information Theory, 26:401--405, 1980.
• 22: Juha Kärkkäinen and Peter Sanders. Simple linear work suffix array construction. In International Colloquium on Automata, Languages and Programming, pages 943--955, 2003.
• 23: Ming Li , Paul Vitányi, An introduction to Kolmogorov complexity and its applications (2nd ed.), Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 24: Udi Manber , Gene Myers, Suffix arrays: a new method for on-line string searches, SIAM Journal on Computing, v.22 n.5, p.935-948, Oct. 1993 [doi>10.1137/0222058]
• 25: Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976 [doi>10.1145/321941.321946]
• 26: Peter Bro Miltersen, Lower bounds for union-split-find related problems on random access machines, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.625-634, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195415]
• 27: Peter Bro Miltersen , Noam Nisan , Shmuel Safra , Avi Wigderson, On data structures and asymmetric communication complexity, Journal of Computer and System Sciences, v.57 n.1, p.37-49, Aug. 1998 [doi>10.1006/jcss.1998.1577]
• 28: M. L. Minsky and S. A. Papert. Perceptrons. Cambridge, MA: MIT Press, 1969.
• 29: J. Ian Munro, Rajeev Raman, Venkatesh Raman, and S. Srinivasa Rao. Succinct representations of permutations. In International Colloquium on Automata, Languages and Programming, pages 345--356, 2003.
• 30: Gonzalo Navarro , Veli Mäkinen, Compressed full-text indexes, ACM Computing Surveys (CSUR), v.39 n.1, p.2-es, 2007 [doi>10.1145/1216370.1216372]
• 31: Mihai Pǎtraşcu. Personal communication.
• 32: Mihai Pătraşcu , Mikkel Thorup, Time-space trade-offs for predecessor search, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132551]
• 33: Kunihiko Sadakane, Compressed Text Databases with Efficient Query Algorithms Based on the Compressed Suffix Array, Proceedings of the 11th International Conference on Algorithms and Computation, p.410-421, December 18-20, 2000
• 34: Kunihiko Sadakane, Succinct representations of lcp information and improvements in the compressed suffix arrays, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.225-232, January 06-08, 2002, San Francisco, California
• 35: Pranab Sen. Lower bounds for predecessor searching in the cell probe model. In IEEE Conference on Computational Complexity, pages 73--83, 2003.
• 36: Esko Ukkonen. On-line construction of suffix trees. Algorithmica, 14(3):249--260, 1995.
• 37: Peter Weiner, Linear pattern matching algorithms, Proceedings of the 14th Annual Symposium on Switching and Automata Theory (swat 1973), p.1-11, October 15-17, 1973 [doi>10.1109/SWAT.1973.13]
• 38: 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]
• 39: A. C.-C. Yao, Coherent functions and program checkers, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.84-94, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100226]

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.0 General