Some Recent Papers of J.I. Munro

First, 5 that capture the tone of my recent work

[1] E. Demaine, A. Lopez-Ortiz and J.I. Munro, "Adaptive Set Intersections, Unions and Differences", to appear in Proc ACM-SIAM SODA 2000 (January 2000).

Motivated by boolean queries in text databases, we consider problems of finding intersections, unions and differences in large collections of sorted sets. The main issue is dealing with algorithms that do well on the specific instance at hand, and taking advantage of any special features how the data values in the individual sets intertwine. We introduce the notion of a succinct proof that an answer is correct. This idea is used to produce search methods within a constant factor of optimal for the specific instance. I feel this approach could have substantial impact on how large complex queries are handled.

[2] A. Brodnik and J.I. Munro, "Membership in Constant Time and Almost Minimum Space S.I.A.M. Journal on Computing, 28,5 (1999) 1628-1640

Suppose one is to store a large subset of the values of a given universe, such as all the 9 digit numbers that are in use as S.I.N.s, assuming no check digits. By conventional means one is inclined to simply store all the values in use directly (say in a hash table) or to have a bit map of all possible values marking each as present or absent. Depending on the fraction of the universe that is actually present, both of these methods have advantages and drawbacks in terms of space requirements. We demonstrate a method that achieves (to within a lower order term) the information theoretic bound on space requirements (based on the size of the universe and the subset). Our method requires only a small constant number of probes per search. The paper includes several examples demonstrating the feasibility of the approach on realistic examples.

[3] D.R. Clark and J.I. Munro, "Efficient Suffix Trees on Secondary Storage", Proc. ACM-SIAM SODA 96, (Jan. 1996), 383-391.

This paper addresses the problem of preprocessing a very large text file so that searches for arbitrary phrases may be performed very quickly. Prior work had discarded the notion of using a (suffix) tree as an index and suggested a (suffix) array of pointers into the text. This was based on the observation that a standard tree representation tripled the size of the index. We describe and implement tree representations for this problem that are an almost negligible part of the cost of the index. We demonstrate extremely efficient algorithms for the text search and for updating the index, particularly when the data is on secondary storage. We believe our method superior to other techniques that have been proposed for full text search and that it will ultimately become widely used.

[4] F.E. Fich, J.I. Munro and P.V. Poblete, "Permuting in Place". S.I.A.M. J. on Computing, 24,2 (1995), 266-278.

Like the preceding two papers, this one addresses the problem of performing a fundamental task quickly using as little space as possible. Here we are to permute the elements of an array according to some arbitrary, but computable, permutation. We demonstrate that this can be done in O(n lg n) time using O(lg n) extra words of memory. Faster, more space efficient techniques are given for some useful special cases such as the situation in which the inverse of the permutation is easily computable. We feel this paper introduces an interesting technique for a very basic problem.

[5] P.V. Poblete, A. Viola and J.I. Munro, "The Diagonal Poisson Transform and its Applications to the Analysis of Hashing Schemes". Random Structures and Algorithms,10 (1997).

In this paper we study hashing with conflicts resolved by linear probing. In its straightforward guise this is an old problem. The twist on the algorithm studied here is that we focus on the replacement heuristic by which an incoming element takes a location and the displaced one is moved on, perhaps displacing another in turn. While the average number of probes is identical to that of the standard one, the variance is dramatically reduced, almost to its minimum possible. The notion of variance reduction as a design goal of an algorithm has come up before in my research. I feel it is a valuable notion in developing more "reliable" probabilistic methods.

Other Papers Appearing in Refereed Journals

[J1] P.V. Poblete, A. Viola, and J.I. Munro "The Analysis of the LCFS Hashing Algorithm with the Help of Maple Mapletech 4,1, 8-13.

[J2] P. Bose, A. Lubiw and J.I. Munro, "Efficient Visibility Queries in Simple Polygons", to appear Computational Geometry: Theory and Applications.

[J3] J.I. Munro and V. Raman, "Fast Stable In-Place Sorting", Algorithmica, 16,2 (1996), 151-160.

[J4] J.I. Munro and V. Raman, "Selection from Read-only Memory and Sorting with Minimum Data Movement." Theoretical Computer Science A, 165 (1996) 311-323.

Other Refereed Conference Publications

[C1] E. Demaine and J.I. Munro "Fast Allocation and Deallocation with an Improved Buddy System" to appear in FST & TCS 19, in Lecture Notes in Computer Science, (Springer-Verlag), Dec. 1999.

[C2] D. Benoit, E. Demaine, J.I. Munro and V. Raman, "Representing Trees of Higher Degree", Proc. WADS 99 in Lecture Notes in Computer Science 1663, (Springer-Verlag), August 1999, pp 169-180.

[C3] A. Brodnik, S. Carlsson, E. Demaine, J.I. Munro and R. Sedgewick " Resizable Arrays in Optimal Time and Space", Proc. WADS 99 in Lecture Notes in Computer Science 1663 (Springer-Verlag), August 1999, pp 37-48.

[C4] J. I. Munro, V. Raman and S. Srinivasa Rao "Space Efficient Suffix Trees" FST & TCS 18, in Lecture Notes in Computer Science, (Springer-Verlag), Dec. 1998.

[C5] A. Brodnik, P. B. Miltersen and J.I. Munro "Transdichotomous Algorithms without Multiplication - Some Upper and Lower Bounds, Proc. WADS 97: Algorithms and Data Structures, Lecture Notes in Computer Science 1272 (Springer) August 1997, pp 426-439.

[C6] J.I. Munro and V. Raman, "Succinct Representation of Balanced Parentheses, Static Trees and Planar Graphs", Proc. 38th Annual IEEE Symp. on Foundations of Computer Science, October 1997, pp 118-126.

[C7] J.I. Munro, "Tables", invited talk at FST & TCS 16, in Lecture Notes in Computer Science 1180, (Springer-Verlag), Dec., 1996, 37-42.

[C8] J.I. Munro and X.R. Ji, "On the Pivot Strategy of Quicksort", Proc. Canadian Conf. on EE & CE, May 1996, 302-305.

[C9] A . Brodnik and J.I. Munro "Neighbours on a Grid", Proc. SWAT 96 in Lecture Notes in Computer Science 1097, Springer-Verlag, July 1996, 309-320.

[C10] P.V. Poblete, T. Papadakis and J.I. Munro "The Binomial Transform and Its Applications to the Analysis of Skip Lists, Proc. ESA 95 in Lecture Notes in Computer Science, 979, Springer-Verlag, Sept. 1995, 554-569.

[C11] A. Brodnik and J.I. Munro, "Membership in Constant Time and Minimal Space", Proc. ESA 94 in Lecture Notes in Computer Science, 855, Springer-Verlag, Sept. 1994, 72-81.

[C12] T. Hagerup, K. Mehlhorn, and J.I. Munro "Optimal Algorithms for Generating Discrete Random Variables with Changing Distributions" Proc. ICALP 93 in Lecture Notes in Computer Science, 700 August 1993.

Non-Refereed Contributions

[N1] J.I. Munro, "Succinct Data Structures" Proc. Workshop on Data Strutcures, Chennai, (December 1999).

[N2] J.I. Munro, "The Perfect Shuffle" Workshop on Data Structures (abstract only) in Schloss Dagstuhl Report (March 1998).

[N3] J.I. Munro, "Theoretical Computer Science", in The Canadian Encyclopedia, revised edition. 1996, (complete rewrite of article in previous editions).

[N4] J.I. Munro, "Constant Time Minimal Space Data Structures". Workshop on Data Structures, (abstract only) in Schloss Dagstuhl Report 136, (February 1996).

[N5] J.I. Munro, "Space Efficient Data Structures". Invited talk at LATIN 95: Theoretical Informatics, (April 1995).