Tables. (English) Zbl 1541.68118
Chandru, V. (ed.) et al., Foundations of software technology and theoretical computer science. 16th conference, Hyderabad, India, December 18–20, 1996. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1180, 37-42 (1996).
Summary: In representing a subset of a large finite set, or an index for text search, one is faced with the need for both time and space efficiency. In this paper, we look at some approaches that have been applied to these problems to represent objects in near minimum space and still permit queries to be performed in constant time. It is hoped that this paper will draw attention to techniques for representing large (mostly static) structures.
For the entire collection see [Zbl 0856.00047].
For the entire collection see [Zbl 0856.00047].
MSC:
| 68P05 | Data structures |
Software:
PATRICIAReferences:
| [1] | A. Brodnik and J. I. Munro, Membership in Constant Time and Minimum Space, Proc. Algorithms — ESA ’94, LNCS 855 (1994) 72-81. |
| [2] | D. R. Clark, Compact Pat Trees, manuscript, University of Waterloo (1996). |
| [3] | D. R. Clark and J. I. Munro, Succinct Representation of Trees, in preparation, University of Waterloo (1996). |
| [4] | R. W. Floyd, Algorithm 245: Treesort 3, Communications of the ACM, 7 (1964) 701. |
| [5] | G. H. Gonnet, R. A. Baeza-Yates and T. Snider, Lexicographic Indices for Text: Inverted Files vs. Pat Trees, Tech. Rpt. OED-91-01, Centre for the New OED, University of Waterloo (1991). |
| [6] | G. Jacobson, Space Efficient Static Trees and Graphs, Proc. 30th IEEE Symp. on Foundations of Computer Science, (1989) 549-554. |
| [7] | G. Jacobson, Succinct Data Structures, Tech. Rpt. CMU-CS-89-112, Carnegie Mellon University (1989). |
| [8] | C. C. Lee, D. T. Lee and C. K. Wong, Generating Binary Trees of Bounded Height, Acta Informatica, 23 (1986) 529-544. · Zbl 0575.68067 |
| [9] | U. Manber and G. Myers, Suffix Arrays: A New Method for On-Line String Searches, SIAM Journal on Computing, 22(5) (1993) 935-948. · Zbl 0784.68027 |
| [10] | D. R. Morrison, Patricia — Practical Algorithm to Retrieve Information Coded in Alphnumeric, Journal of the ACM, 15(4) (1968) 514-534. |
| [11] | J. I. Munro, An Implicit Data Structure Supporting Insertion, Deletion, and Search in O(log \(^2\) n) Time, J. Computer and System Sciences, 33, (1986) 66-74. · Zbl 0625.68044 |
| [12] | J. I. Munro and H. Suwanda, Implicit Data Structures for Fast Search and Update, J. Computer and System Sciences, 21, (1980) 236-250. · Zbl 0446.68045 |
| [13] | R. C. Read, The Coding of Various Kinds of Unlabelled Trees, In R. C. Read (ed.) Graph Theory and Computing, Academic Press, (1972) 153-182. · Zbl 0247.05104 |
| [14] | R. Schaffer and R. Sedgewick, The Analysis of Heapsort, Journal of Algorithms, 15(1), (1993) 76-100. · Zbl 0789.68072 |
| [15] | P. Weiner, Linear Pattern Match Algorithms, Proc. 14th IEEE Symp. on Switching and Automata Theory, (1973) 1-11. |
| [16] | J. W. J. Williams, Algorithm 232, Heapsort, Communications of the ACM, 7 (1964) 347-348. |
| [17] | S. Zaks, Lexicographic Generation of Ordered Trees, Theoretical Computer Science, 10(1), (1980) 63-82. · Zbl 0422.05026 |
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.
