The complicated indoor environment such as obstacles causes the non-line of sight (NLOS) environment. In this paper, we propose a voting matrix based residual weighting (VM-Rwgh) algorithm to mitigate NLOS errors in indoor localization system. The voting matrix is employed to provide initial localization results. The residual weighting is used to improve the localization accuracy. The VM-Rwgh algorithm can overcome the effects of NLOS errors, even when more than half of the measurements contain NLOS errors. Simulation results show that the VM-Rwgh algorithm provides higher location accuracy with relatively lower computational complexity in comparison with other methods.

In this paper, a one-class Naïve Bayesian classifier (One-NB) for detecting toll frauds in a VoIP service is proposed. Since toll frauds occur irregularly and their patterns are too diverse to be generalized as one class, conventional binary-class classification is not effective for toll fraud detection. In addition, conventional novelty detection algorithms have struggled with optimizing their parameters to achieve a stable detection performance. In order to resolve the above limitations, the original Naïve Bayesian classifier is modified to handle the novelty detection problem. In addition, a genetic algorithm (GA) is employed to increase efficiency by selecting significant variables. In order to verify the performance of One-NB, comparative experiments using five well-known novelty detectors and three binary classifiers are conducted over real call data records (CDRs) provided by a Korean VoIP service company. The experimental results show that One-NB detects toll frauds more accurately than other novelty detectors and binary classifiers when the toll frauds rates are relatively low. In addition, The performance of One-NB is found to be more stable than the benchmark methods since no parameter optimization is required for One-NB.

Estimation of distribution algorithms (EDAs), since they were introduced, have been successfully used to solve discrete optimization problems and hence proven to be an effective methodology for discrete optimization. To enhance the applicability of EDAs, researchers started to integrate EDAs with discretization methods such that the EDAs designed for discrete variables can be made capable of solving continuous optimization problems. In order to further our understandings of the collaboration between EDAs and discretization methods, in this paper, we propose a quality measure of discretization methods for EDAs. We then utilize the proposed quality measure to analyze three discretization methods: fixed-width histogram (FWH), fixed-height histogram (FHH), and greedy random split (GRS). Analytical measurements are obtained for FHH and FWH, and sampling measurements are conducted for FHH, FWH, and GRS. Furthermore, we integrate Bayesian optimization algorithm (BOA), a representative EDA, with the three discretization methods to conduct experiments and to observe the performance difference. A good agreement is reached between the discretization quality measurements and the numerical optimization results. The empirical results show that the proposed quality measure can be considered as an indicator of the suitability for a discretization method to work with EDAs.

A suffix tree is widely adopted for indexing genome sequences. While supporting highly efficient search, the suffix tree has a few shortcomings such as very large size and very long construction time. In this paper, we propose a very fast parallel algorithm to construct a disk-based suffix tree for human genome sequences. Our algorithm constructs a suffix array for part of the suffixes in the human genome sequence and then converts it into a suffix tree very quickly. It outperformed the previous algorithms by Loh et al. and Barsky et al. by up to 2.09 and 3.04 times, respectively.

We proposes a new adaptive spectral masking method of algebraic vector quantization (AVQ) for non-sparse signals in the modified discreet cosine transform (MDCT) domain. This paper also proposes switching the adaptive spectral masking on and off depending on whether or not the target signal is non-sparse. The switching decision is based on the results of MDCT-domain sparseness analysis. When the target signal is categorized as non-sparse, the masking level of the target MDCT coefficients is adaptively controlled using spectral envelope information. The performance of the proposed method, as a part of ITU-T G.711.1 Annex D, is evaluated in comparison with conventional AVQ. Subjective listening test results showed that the proposed method improves sound quality by more than 0.1 points on a five-point scale on average for speech, music, and mixed content, which indicates significant improvement.

The authors have evaluated a method of expanding the bit depth of image signals called SGRAD, which requires fewer calculations, while degrading the sharpness of images less. Where noise is superimposed on image signals, the conventional method for obtaining high bit depth sometimes incorrectly detects the contours of images, making it unable to sufficiently correct the gradation. Requiring many line memories is also an issue with the conventional method when applying the process to vertical gradation. As a solution to this particular issue, SGRAD improves the method of detecting contours with transiting gradation to effectively correct the gradation of image signals which noise is superimposed on. In addition, the use of a prediction algorithm for detecting gradation reduces the scale of the circuit with less correction of the vertical gradation.

Toward the actualization of an automatic navigation system for fetoscopic tracheal occlusion (FETO) surgery, this paper proposes a 3D ultrasound (US) calibration-based approach that can locate the fetal facial surface, oral cavity, and airways by a registration between a 3D fetal model and 3D US images. The proposed approach consists of an offline process and online process. The offline process first reconstructs the 3D fetal model with the anatomies of the oral cavity and airways. Then, a point-based 3D US calibration system based on real-time 3D US images, an electromagnetic (EM) tracking device, and a novel cones' phantom, computes the matrix that transforms the 3D US image space into the world coordinate system. In the online process, by scanning the mother's body with a 3D US probe, 3D US images containing the fetus are obtained. The fetal facial surface extracted from the 3D US images is registered to the 3D fetal model using an ICP-based (iterative closest point) algorithm and the calibration matrices, so that the fetal facial surface as well as the oral cavity and airways are located. The results indicate that the 3D US calibration system achieves an FRE (fiducial registration error) of 1.49±0.44mm and a TRE (target registration error) of 1.81±0.56mm by using 24 fiducial points from two US volumes. A mean TRE of 1.55±0.46 mm is also achieved for measuring location accuracy of the 3D fetal facial surface extracted from 3D US images by 14 target markers, and mean location errors of 2.51±0.47 mm and 3.04±0.59 mm are achieved for indirectly measuring location accuracy of the pharynx and the entrance of the trachea, respectively, which satisfy the requirement of the FETO surgery.

Analysis of the trust network proves beneficial to the users in Online Social Networks (OSNs) for decision-making. Since the construction of trust propagation paths connecting unfamiliar users is the preceding work of trust inference, it is vital to find appropriate trust propagation paths. Most of existing trust network discovery algorithms apply the classical exhausted searching approaches with low efficiency and/or just take into account the factors relating to trust without regard to the role of distrust relationships. To solve the issues, we first analyze the trust discounting operators with structure balance theory and validate the distribution characteristics of balanced transitive triads. Then, Maximum Indirect Referral Belief Search (MIRBS) and Minimum Indirect Functional Uncertainty Search (MIFUS) strategies are proposed and followed by the Optimal Trust Inference Path Search (OTIPS) algorithms accordingly on the basis of the bidirectional versions of Dijkstra's algorithm. The comparative experiments of path search, trust inference and edge sign prediction are performed on the Epinions data set. The experimental results show that the proposed algorithm can find the trust inference path with better efficiency and the found paths have better applicability to trust inference.

Proof-of-concept cyclic analog-to-digital converters (ADCs) have been designed and fabricated in 90-nm CMOS technology. The measurement results of an experimental prototype demonstrate the effectiveness of the proposed switched-capacitor (SC) architecture to realize a non-binary ADC based on β expansion. Different from the conventional binary ADC, a simple 1-bit/step structure for an SC multiplying digital-to-analog converter (MDAC) is proposed to present residue amplification by β (1 < β < 2). The redundancy of non-binary ADCs with radix β tolerates the non-linear conversion errors caused by the offsets of comparators, the mismatches of capacitors, and the finite DC gains of amplifiers, which are used in the MDAC. We also employed a radix value estimation algorithm to obtain an effective value of β for non-binary encoding; it can be realized by merely adding a simple conversion sequence and digital circuits. As a result, the power penalty of a high-gain wideband amplifier and the required accuracy of the circuit elements for a high-resolution ADC were largely relaxed so that the circuit design was greatly simplified. The implemented ADC achieves a measured peak signal-to-noise-and-distortion-ratio (SNDR) of 60.44dB, even with an op-amp with a poor DC gain (< 50dB) while dissipating 780µW in analog circuits at 1.4V and occupying an active area of 0.25 × 0.26mm2.

The rapid variation of wireless channels and feedback delay make the available channel state information (CSI) outdated in dynamic wireless multi-hop networks, which significantly degrades the accuracy of cross-layer resource allocation. To deal with this problem, a cross-layer resource allocation scheme is proposed for wireless multi-hop networks by taking the outdated CSI into account and basing compensation on the results of channel prediction. The cross-layer resource allocation is formulated as a network utility maximization problem, which jointly considers congestion control, channel allocation, power control, scheduling and routing with the compensated CSI. Based on a dual decomposition approach, the problem is solved in a distributed manner. Simulation results show that the proposed algorithm can reasonably allocate the resources, and significantly improve the throughput and energy efficiency in the network.

This paper investigates a signal detection method with a RAKE combiner for the case wherein the receiving signals use the same spreading code. In the case where multiple user interference with the same spreading code (MUI-SC) occurs, blind channel estimation is difficult and as far as we know has not been investigated. To tackle the issue of MUI-SC, we propose two blind channel estimation methods based on the multimodulus algorithm (MMA), i.e., MMA-IQ and MMA-I methods. When a one dimensional modulation scheme, such as differential binary phase-shift keying (DBPSK), is used, the output of the MMA-IQ channel estimation method can, under MUI-SC, have two states. The first state is that the channel estimate corresponds to a channel response for one of the received signals, and the second state is that the channel estimate corresponds to combined channel responses for two of the received signals. This is because the MMA-IQ uses two degrees of freedom (both axes in the IQ-plane), however one DBPSK signal uses only one degree of freedom. In the case of the second state, it is possible to detect two signals/packets at once. However, in the MMA-IQ, the receiver has to recognize the state of the channel estimate before the signal detection, thus we also propose a state recognition method. In the MMA-I channel estimation method, only the I-axis is used thus the channel estimate always corresponds the case with one signal. Numerical results show that the average number of detected packets of the MMA-IQ is more than that of the MMA-I in high signal-to-noise power ratio case. In addition, several aspects of the MMA-I and MMA-IQ based RAKE signal detection methods are shown.

In this paper, we consider the problem of partitioning a given collection of node sets into k collections such that the average size of collections is the largest, where the size of a collection is defined as the cardinarity of the union of the subsets contained in the collection. More concretely, we give an upper bound on the performance ratio of an approximation algorithm proposed by Abrams et al., which is known to have a performance ratio of at least 1-1/e≅0.6321 where e is Napier's constant. The proposed upper bound is 1-(2-d+1√2)d+1/2 for any d≥1 provided that k=o(n) which approaches to 0.75 as d increases.

In a convex drawing of a plane graph, all edges are drawn as straight-line segments without any edge-intersection and all facial cycles are drawn as convex polygons. In a convex grid drawing, all vertices are put on grid points. A plane graph G has a convex drawing if and only if G is internally triconnected, and an internally triconnected plane graph G has a convex grid drawing on an (n-1)×(n-1) grid if either G is triconnected or the triconnected component decomposition tree T(G) of G has two or three leaves, where n is the number of vertices in G. An internally triconnected plane graph G has a convex grid drawing on a 2n×2n grid if T(G) has exactly four leaves. In this paper, we show that an internally triconnected plane graph G has a convex grid drawing on a 6n×n2 grid if T(G) has exactly five leaves. We also present an algorithm to find such a drawing in linear time. This is the first algorithm that finds a convex grid drawing of such a plane graph G in a grid of polynomial size.

The Discrete Memory Machine (DMM) and the Unified Memory Machine (UMM) are theoretical parallel computing models that capture the essence of the shared memory and the global memory of GPUs. It is assumed that warps (or groups of threads) on the DMM and the UMM work synchronously in a round-robin manner. However, warps work asynchronously in real GPUs, in the sense that they are randomly (or arbitrarily) dispatched for execution. The first contribution of this paper is to introduce asynchronous versions of these models in which warps are arbitrarily dispatched. In addition, we assume that threads can execute the “syncthreads” instruction for barrier synchronization. Since the barrier synchronization operation may be costly, we should evaluate and minimize the number of barrier synchronization operations executed by parallel algorithms. The second contribution of this paper is to show a parallel algorithm to the sum of n numbers in optimal computing time and few barrier synchronization steps. Our parallel algorithm computes the sum of n numbers in O(n/w+llog n) time units and O(log l/log w+log log w) barrier synchronization steps using wl threads on the asynchronous UMM with width w and latency l. Since the computation of the sum takes at least Ω(n/w+llog n) time units, this algorithm is time optimal. Finally, we show that the prefix-sums of n numbers can also be computed in O(n/w+llog n) time units and O(log l/log w+log log w) barrier synchronization steps using wl threads.

Suppose that each arc in a digraph D = (V,A) has two costs of non-negative integers, called a spine cost and a leaf cost. A caterpillar is a directed tree consisting of a single directed path (of spine arcs) and leaf vertices each of which is incident to the directed path by exactly one incoming arc (leaf arc). For a given terminal set K ⊆ V, we study the problem of finding a caterpillar in D such that it contains all terminals in K and its total cost is minimized, where the cost of each arc in the caterpillar depends on whether it is used as a spine arc or a leaf arc. In this paper, we first show that the problem is NP-hard for any fixed constant number of terminals with |K| ≥ 3, while it is solvable in polynomial time for at most two terminals. We also give an inapproximability result for any fixed constant number of terminals with |K| ≥ 3. Finally, we give a linear-time algorithm to solve the problem for digraphs with bounded treewidth, where the treewidth for a digraph D is defined as the one for the underlying graph of D. Our algorithm runs in linear time even if |K| = O(|V|), and the hidden constant factor of the running time is just a single exponential of the treewidth.

Attenuated and delayed versions of the pulse signal overlap in multipath propagation. Previous algorithms can resolve them only if signal sampling is ideal, but fail to resolve two counterparts with non-ideal sampling. In this paper, we propose a novel method which can resolve the general types of non-ideally sampled pulse signals in the time domain via Taylor Series Expansion (TSE) and estimate multipath signals' precise time delays and amplitudes. In combination with the CLEAN algorithm, the overlapped pulse signal parameters are estimated one by one through an iteration method. Simulation results verify the effectiveness of the proposed method.

By the motivation to discover patterns in massive structured data in the form of graphs and trees, we study a special case of the k-subtree enumeration problem with a tree of n nodes as an input graph, which is originally introduced by (Ferreira, Grossi, and Rizzi, ESA'11, 275-286, 2011) for general graphs. Based on reverse search technique (Avis and Fukuda, Discrete Appl. Math., vol.65, pp.21-46, 1996), we present the first constant delay enumeration algorithm that lists all k-subtrees of an input rooted tree in O(1) worst-case time per subtree. This result improves on the straightforward application of Ferreira et al.'s algorithm with O(k) amortized time per subtree when an input is restricted to tree. Finally, we discuss an application of our algorithm to a modification of the graph motif problem for trees.

This paper reports on the image compression tolerability and high implementability of a novel proposed watermarking method that uses a morphological wavelet transform based on max-plus algebra. This algorithm is suitable for embedded low-power processors in mobile devices. For objective and unified evaluation of the capability of the proposed watermarking algorithm, we focus attention on a watermarking contest presented by the IHC, which belongs to the IEICE and investigate the image quality and tolerance against JPEG compression attack. During experiments for this contest, six benchmark images processed by the proposed watermarking is done to reduce the file size of original images to 1/10, 1/20, or less, and the error rate of embedding data is reduced to 0%. Thus, the embedded data can be completely extracted. The PSNR value is up to 54.66dB in these experiments. Furthermore, when the smallest image size is attained 0.49MB and the PSNR value become about 52dB, the proposed algorithm maintains very high quality with an error rate of 0%. Additionally, the processing time of the proposed watermarking can realize about 416.4 and 4.6 times faster than that of DCT and HWT on the ARM processor, respectively. As a result, the proposed watermarking method achieves effective processing capability for mobile processors.

This paper studies the complexity of computing discrete logarithms over algebraic tori. We show that the order certified version of the discrete logarithm problem over general finite fields (OCDL, in symbols) reduces to the discrete logarithm problem over algebraic tori (TDL, in symbols) with respect to the polynomial-time Turing reducibility. This reduction means that if the prime factorization can be computed in polynomial time, then TDL is equivalent to the discrete logarithm problem over general finite fields with respect to the Turing reducibility.

A new artificial fish swarm algorithm (AFSA) for solving the multiple knapsack problem (MKP) is introduced in this paper. In the proposed AFSA, artificial fish (AF) individuals are only allowed to search the region near constraint boundaries of the problem to be solved. For this purpose, several behaviors to be performed by AF individuals, including escaping behavior, randomly moving behavior, preying behavior and following behavior, were specially designed. Exhaustive experiments were implemented in order to investigate the proposed AFSA's performance. The results demonstrated the proposed AFSA has the ability of finding high-quality solutions with very fast speed, as compared with some other versions of AFSA based on different constraint-handling methods. This study is also meaningful for solving other constrained problems.