Ben Wegbreit
Abstract
Context trees provide a convenient way of storing data which is to be viewed as a hierarchy of contexts. This note presents an algorithm which improves on previous context tree retrieval algorithms. It is based on the observation that in typical uses context changes are infrequent relative to retrievals, so that data can be cached to speed up retrieval. A retrieval is started from the position of the previous retrieval and auxiliary structures are built up to make the search rapid. Algorithms for addition and deletion of data and for garbage collection are outlined.
- 1 Deutscb, L.P. An interactive program verifier. Ph.D. Th., Computer Sci. Dep., U. of California, Berkeley, May 1973.Google Scholar
- 2 Rulifson, J.F., Dirksen, J.A., and Waldinger, R.T. QA4--a language for writing problem solving programs. Proc. IFIP Cong. 71, Ljubljana, North-Holland Pub. Co., Amsterdam, 1971.Google Scholar
- 3 Sussman, G.J., and McDermott, D. Why conniving is better than planning. AFIPS Conf. Proc., Vol. 41, Part II, 1972 FJCC, AFIPS Press, Montvale, N.J., pp. 1171-1179.Google Scholar
- 4 Wegbreit, B. Retrieval from context trees. Inf. Proc. Left. 3, 4 (March 1975), 119-120.Google ScholarCross Ref
Recommendations
Deletion Without Rebalancing in Binary Search Trees
We address the vexing issue of deletions in balanced trees. Rebalancing after a deletion is generally more complicated than rebalancing after an insertion. Textbooks neglect deletion rebalancing, and many B-tree--based database systems do not do it. We ...
Individual sequence prediction using memory-efficient context trees
Context trees are a popular and effective tool for tasks such as compression, sequential prediction, and language modeling. We present an algebraic perspective of context trees for the task of individual sequence prediction. Our approach stems from a ...
Exploration of query context for information retrieval
WWW '07: Proceedings of the 16th international conference on World Wide WebA number of existing information retrieval systems propose the notion of query context to combine the knowledge of query and user into retrieval to reveal the most exact description of user's information needs. In this paper we interpret query context ...
Comments