8031191
Dynamic dictionary matching and compressed suffix trees
Recent breakthrough in compressed indexing data structures has reduced the space for indexing a text (or a collection of texts) of length <i>n</i> from <i>O</i>(<i>n</i> log <i>n</i>) bits to <i>O</i>(<i>n</i>) bits, while allowing very efficient pattern matching [10, 13]. Yet the compressed nature of such indices also makes them difficult to update dynamically. This paper presents the first <i>O</i>(<i>n</i>)-bit representation of a suffix tree for a dynamic collection of texts whose total length is <i>n</i>, which supports insertion and deletion of a text <i>T</i> in <i>O</i>(|<i>T</i> | log<sup>2</sup> <i>n</i>) time, as well as all suffix tree traversal operations, including forward and backward suffix links. This work can be regarded as a generalization of the compressed representation of static texts. Our new suffix tree representation serves as a core part in a compact solution for the dynamic dictionary matching problem, i.e., providing an <i>O</i>(<i>d</i>)-bit data structure for a dynamic collection of patterns of total length <i>d</i> that can support the dictionary matching query efficiently. When compared with the <i>O</i>(<i>d</i> log <i>d</i>)-bit suffix tree based solution of Amir <i>et al.</i>, the compact solution increases the query time by roughly a factor of log <i>d</i> only. In the study of the above results, we also derive the first <i>O</i>(<i>n</i>)-bit representation for maintaining <i>n</i> pairs of balanced parentheses in <i>O</i>(log <i>n</i>/log log <i>n</i>) time per operation, matching the time complexity of the previous <i>O</i>(<i>n</i> log <i>n</i>)-bit solution.
15069863
Non-migratory online deadline scheduling on multiprocessors
In this paper we consider multiprocessor scheduling with hard deadlines and investigate the cost of eliminating migration in the online setting. Let I be any set of jobs that can be completed by some migratory offline schedule on m processors. We show that I can also be completed by a non-migratory online schedule using m speed-5.828 processors (i.e., processors of 5.828 times faster). This result supplements the previous results that I can also be completed by a non-migratory offline schedule using 6m unit-speed processors [8] or a migratory online schedule using m speed-2 processors [13]. Our result is based on a simple conservative scheduling algorithm called PARK which commits a processor to a job only when the processor has zero commitment before its deadline. A careful analysis of PARK further shows that the processor speed can be reduced arbitrarily close to 1 by exploiting more processors (say, using 16m speed-1.8 processors). PARK also finds application in overloaded systems; it gives the first online non-migratory algorithm that can exploit moderately faster processors to match the performance of any migratory offline algorithm.
17611435
Extra unit-speed machines are almost as powerful as speedy machines for competitive flow time scheduling
We study online scheduling of jobs to minimize the flow time and stretch on parallel machines. We consider algorithms that are given extra resources so as to compensate the lack of future information. Recent results show that a modest increase in machine speed can provide very competitive performance; in particular, using O(1) times faster machines, the algorithm SRPT (shortest remaining processing time) is 1-competitive for both flow time [23] and stretch [12], and HDF (highest density first) is O(1)-competitive for weighted flow time [6]. Using extra unit-speed machines instead of faster machines is more challenging. This paper gives a non-trivial relationship between the extra-speed and extra-machine analysis. It shows that competitive results via faster machines can be transformed to similar results via extra machines, and hence giving the first algorithms that, using O(1) times unit-speed machines, are 1-competitive for flow time and stretch and O(1)-competitive for weighted flow time, respectively.
34112863
Compressed Indexes for Approximate String Matching
We revisit the problem of indexing a string S[1..n] to support searching all substrings in S that match a given pattern P[1..m] with at most k errors. Previous solutions either require an index of size exponential in k or need Ω(mk) time for searching. Motivated by the indexing of DNA sequences, we investigate space efficient indexes that occupy only O(n) space. For k = 1, we give an index to support matching in O(m + occ + logn loglogn) time. The previously best solution achieving this time complexity requires an index of size O(n logn). This new index can be used to improve existing indexes for k ≥2 errors. Among others, it can support matching with k=2 errors in O(m logn loglogn + occ) time.
3557483
Streaming encryption for a secure wavelength and time domain hopped optical network
We describe a working implementation of a streaming encryption system for optical networks. The 10 Gbps data stream is encrypted on the physical level in both the wavelength and time domains. Security is obtained by applying a strong pseudo-random hopping pattern to both. The AES algorithm in counter mode is used to control the switches that implement the hopping permutations. Because of the high throughput requirements, aggressive parallelizing and pipelining techniques are used to achieve data rates of 10 Gbps. The core logic of the system was implemented on the Virtex2-XC2V1000 FPGA. Using four FPGA boards and four serializer and deserializer chips, a secure switch of 4 users over 4 wavelengths can be realized, resulting in a total throughput of 10 Gbps. This system is important as a platform for further research in the area of secure optical networks.
1880699
A distance measure for bounding probabilistic belief change
We propose a distance measure between two probability distributions, which allows one to bound the amount of belief change that occurs when moving from one distribution to another. We contrast the proposed measure with some well known measures, including KL-divergence, showing how they fail to be the basis for bounding belief change as is done using the proposed measure. We then present two practical applications of the proposed distance measure: sensitivity analysis in belief networks and probabilistic belief revision. We show how the distance measure can be easily computed in these applications, and then use it to bound global belief changes that result from either the perturbation of local conditional beliefs or the accommodation of soft evidence. Finally, we show that two well known techniques in sensitivity analysis and belief revision correspond to the minimization of our proposed distance measure and, hence, can be shown to be optimal from that viewpoint.
3053066
Sensitivity Analysis in Bayesian Networks: From Single to Multiple Parameters
Previous work on sensitivity analysis in Bayesian networks has focused on single parameters, where the goal is to understand the sensitivity of queries to single parameter changes, and to identify single parameter changes that would enforce a certain query constraint. In this paper, we expand the work to multiple parameters which may be in the CPT of a single variable, or the CPTs of multiple variables. Not only do we identify the solution space of multiple parameter changes that would be needed to enforce a query constraint, but we also show how to find the optimal solution, that is, the one which disturbs the current probability distribution the least (with respect to a specific measure of disturbance). We characterize the computational complexity of our new techniques and discuss their applications to developing and debugging Bayesian networks, and to the problem of reasoning about the value (reliability) of new information.
9263402
Artificial convolution neural network for medical image pattern recognition
Abstract We have developed several training methods in conjunction with a convolution neural network for general medical image pattern recognition. An unconventional method of using rotation and shift invariance is also proposed to enhance the neural net performance. The structure of the artificial neural network is a simplified network structure of the neocognitron. Two-dimensional local connection as a group is the fundamental architecture for the signal propagation in the convolution neural network. Weighting coefficients of convolution kernels are formed by the neural network through backpropagated training for this artificial neural net. In addition, radiologists' reading procedure was modelled in order to instruct the artificial neural network to recognize the predefined image patterns and those of interest to experts. Our training techniques involve (a) radiologists' rating for each suspected image area, (b) backpropagation of generalized distribution, (c) trainer imposed functions, (d) shift and rotation invariance of diagnosis interpretation, and (e) consistency of clinical input data using appropriate background reduction functions. We have tested these methods for detecting lung nodules on chest radiographs and microcalcications on mammograms. The performance studies have shown the potential use of this technique in a clinical environment. We also used a profile double-matching technique for initial nodule search and used a wavelet high pass filtering technique to enhance subtle clustered microcalcifications. We set searching parameters at a highly sensitive level to identify all potential disease areas. The artificial convolution neural network acts as a final detection classifier to determine whether a disease pattern is shown on the suspected image area.
11373384
Joint Call Admission Control for Next Generation Wireless Network
Next generation wireless network (NGWN) will be heterogeneous in nature where different radio access technologies (RATs) such as UMTS, WiMax, WLAN, etc, coexist. This coexistence necessitates joint radio resource management (JRRM). This paper focuses on joint call admission control (JCAC) for NGWN. Factors that determine a user's preference for a particular RAT are discussed. We propose a JCAC algorithm which considers the user's preference in making admission decision. A specific case where the user prefers to be served by the RAT which has the least service cost is modeled and evaluated using Markov decision process. The results obtained shows that overall service cost in heterogeneous network can be significantly reduced by using the proposed joint call admission control