The Virtual Memory Xinu Project investigates a new model of virtual memory in which dedicated, large-memory machines serve as a backing store (page servers) for virtual memory systems operating on a set of (heterogeneous) clients. The dedicated page server allows sharing of the large physical memory resource and provides fast access to data. This paper gives a brief overview of the Virtual Memory Xinu research project. It outlines the new virtual memory model used, the project’s goals, and prototype design and implementation.

Given a set S of n points in the plane such that each point in S is associated with a non negative weight, we consider the problem of computing the single source longest increasing chains among the points in S. This problem is a generalization of the planar maximal layers problem. In this paper, we present a parallel algorithm that computes the single source longest increasing chains in the plane in O(log^2*n) time using O(n^2/log^3 n) processors in hte CREW PRAM computational model. We also have solved a related problem of computing the all-pairs longest paths in an n-node weighted planar st-graph, in O(log^2 n) time using O(n^2 / log n) CREW PRAM processors. Both of our parallel algorithms are an improvement over the previously best known results.

Each federal organization is fully responsible for its copmuter security program whether the security program is performed by in-house staff or contracted out.  Time constraints, budget constraints, availability or expertise of staff, and the potential knowledge to be gained by the organization from an experienced contractor are among the reasons a federal organization may wish to get external assistance for some of these complex, labor intensive activities.

We give a result that implies an improvement by a factor of log log n in the hypercube bounds for the geometric problems of batched planar point location, trapezoidal decomposition, and polygon triangulation. The improvements are achieved through a better solution to the multisearch problem on a hypercube, a parallel search problem where the elements in the data structure S to be searched are totally ordered, but where it is not possible to compare in constant time any two given queries q and q’. Whereas the previous best solution to this problem took O(log n(log log n)^3) time on an n-processor hypercube, the solution given here takes O(log n (log log n)^2) time on an n-processor hypercube. The hypercube model for which we claim our bounds is the standard one, SIMD, with O(1) memory registers per processor, and with one-port communication. Each registar can store O(log n) bits, so that a processor knows its ID.

We propose a non-transform image compression technique based on approximate pattern matching, that we name Pattern Matching Image Compression (PMIC). The main idea behind it is a lossy extension of the Lempel-Ziv data compression scheme in which one searches for the longest prefix of an uncompressed image that approximately (e.g., D of mismatches are allowed) occurs in the already processed image. This main algorithm is enhanced with several new features such as searching for reverse approximate matching, recognizing substrings in images that are additively shifted versions of each other, introducing a variable and adaptive maximum distortion level D, and so forth. These enhancements are crucial to the overall quality of our scheme. In this paper we present algorithmic as well as experimental results of the Pattern Matching Image Compression. Our scheme turns out to be competitive with JPEG and wavelet compression for graphical and photographical images. A unique feature of the purposed algorithm is that an asymptotic performance of the scheme can be theroretically established. More precisely, under stationary mixing probablilistic model of an image and fixed maximum distortion level D, the compression ratio is asymptotically equal to the so called generalized Renyientropy r0(D). This entropy is in general smaller than the optimal rate distortion function R(D), but there is numerical evidence that these two quantities do not differ too much for small values of D.

This paper compares the conventional stopping criterion of ad-hoc mutation score with the proposed Barnard’s score notation technique based on the Bayesian SPRT to test the software mutation test-case adequacy. A Monte Carlo simulation is used to mimic the mutation analysis as in a software laboratory on the well known Trityp test program for two calculated experimental designs. The results indicate that the Bayesian SPRT through Barnard’s score notation proves at least equally accurate and more cost effective for the goal of a given test-case adequacy.

Networked multimedia applications are a proliferating new feature of the emerging National Information Infrastructure (NII). Such applications employ a variety of information technologies and services to make motion and still pictures, richly formatted text and hypertext, sound and data available to information appliances over networks. The results are new, attractive communications capabilities which are valued by end-users. For maximum user acceptance, the capabilities of information appliances and the communications services that interconnect them must be well matched to specific applications for multimedia features to work well. The Cross-Industry Working Team (XIWT) member companies have delineated a set of core capabilites needed to support effective networked multimedia applications. Using these capabilities as a guide, five NII Class designations or profiles are proposed. The NII Class Profiles are intended to associate information appliance and communications services capabilities with applications requirements. These class designations can serve two purposes: 1) to establish a framework for common understanding and basis for cooperation among information industry stakeholders, and 2) as a guide to inform consumers about product capablilities to assist their purchasing choices. Proposed implementation is through a to-be-developed “Servicemark” program, e.g., NII Class “X” Capable, with an appropriate logo. Industry leadership will provide increased marketing opportunities for all NII stakeholders, and more satisfied consumers.