Personalized PageRank (PPR) is a typical similarity metric between nodes in a graph, and node searches based on PPR are widely used. In many applications, graphs change dynamically, and in such cases, it is desirable to perform ad hoc searches based on PPR. An ad hoc search involves performing searches by varying the search parameters or graphs. However, as the size of a graph increases, the computation cost of performing an ad hoc search can become excessive. In this paper, we propose a method called Castanet that offers fast ad hoc searches of PPR. The proposed method features (1) iterative estimation of the upper and lower bounds of PPR scores, and (2) dynamic pruning of nodes that are not needed to obtain a search result. Experiments confirm that the proposed method does offer faster ad hoc PPR searches than existing methods.

In this paper, a Boolean algebra approach is proposed to encode various acceptability semantics for abstract argumentation frameworks, where each semantics can be equivalently encoded into several Boolean constraint models based on Boolean matrices and a family of Boolean operations between them. Then, we show that these models can be easily translated into logic programs, and can be solved by a constraint solver over Boolean variables. In addition, we propose some querying strategies to accelerate the calculation of the grounded, stable and complete extensions. Finally, we describe an experimental study on the performance of our encodings according to different semantics and querying strategies.

Given a graph G=(V, E), where V and E are vertex and edge sets of G, and a subset VNT of vertices called a non-terminal set, the minimum spanning tree with a non-terminal set VNT, denoted by MSTNT, is a connected and acyclic spanning subgraph of G that contains all vertices of V with the minimum weight where each vertex in a non-terminal set is not a leaf. On general graphs, the problem of finding an MSTNT of G is NP-hard. We show that if G is an outerplanar graph then finding an MSTNT of G is linearly solvable with respect to the number of vertices.

We propose a cache-aware method to accelerate texture-based volume rendering on a graphics processing unit (GPU) that is compatible with the compute unified device architecture. The proposed method extends a previous method such that it can maximize the average rendering performance while rotating the viewing direction around a volume. To realize this, the proposed method performs in-place rotation of volume data, which rearranges the order of voxels to allow consecutive threads (warps) to refer to voxels with the minimum access strides. Experiments indicate that the proposed method replaces the worst texture cache (TC) hit rate of 42% with the best TC hit rate of 93% for a 10243-voxel volume. Thus, the average frame rate increases by a factor of 1.6 in the proposed method compared with that in the previous method. Although the overhead of in-place rotation slightly decreases the frame rate from 2.0 frames per second (fps) to 1.9 fps, this slowdown occurs only with a few viewing directions.

The differential fault analysis of SOSEMNAUK was presented in Africacrypt in 2011. In this paper, we improve previous work with algebraic techniques which can result in a considerable reduction not only in the number of fault injections but also in time complexity. First, we propose an enhanced method to determine the fault position with a success rate up to 99% based on the single-word fault model. Then, instead of following the design of SOSEMANUK at word levels, we view SOSEMANUK at bit levels during the fault analysis and calculate most components of SOSEMANUK as bit-oriented. We show how to build algebraic equations for SOSEMANUK and how to represent the injected faults in bit-level. Finally, an SAT solver is exploited to solve the combined equations to recover the secret inner state. The results of simulations on a PC show that the full 384 bits initial inner state of SOSEMANUK can be recovered with only 15 fault injections in 3.97h.

Given an undirected graph G, an edge dominating set is a subset F of edges such that each edge not in F is adjacent to some edge in F, and computing the minimum size of an edge dominating set is known to be NP-hard. Since the size of any edge dominating set is at least half of the maximum size µ(G) of a matching in G, we study the problem of testing whether a given graph G has an edge dominating set of size ⌈µ(G)/2⌉ or not. In this paper, we prove that the problem is NP-complete, whereas we design an O*(2.0801µ(G)/2)-time and polynomial-space algorithm to the problem.

In this paper we study a recently proposed variant of the facility location problem, called the r-gathering problem. Given an integer r, a set C of customers, a set F of facilities, and a connecting cost co(c, f) for each pair of c ∈ C and f ∈ F, an r-gathering of customers C to facilities F is an assignment A of C to open facilities F' ⊆ F such that at least r customers are assigned to each open facility. We give an algorithm to find an r-gathering with the minimum cost, where the cost is maxc ∈ C{co(c, A(c))}, when all C and F are on the real line.

An efficient means of learning tree-structural features from tree-structured data would enable us to construct effective mining methods for tree-structured data. Here, a pattern representing rich tree-structural features common to tree-structured data and a polynomial time algorithm for learning important tree patterns are necessary for mining knowledge from tree-structured data. As such a tree pattern, we introduce a term tree pattern t such that any edge label of t belongs to a finite alphabet Λ, any internal vertex of t has ordered children and t has a new kind of structured variable, called a height-constrained variable. A height-constrained variable has a pair of integers (i, j) as constraints, and it can be replaced with a tree whose trunk length is at least i and whose height is at most j. This replacement is called height-constrained replacement. A sequence of consecutive height-constrained variables is called a variable-chain. In this paper, we present polynomial time algorithms for solving the membership problem and the minimal language (MINL) problem for term tree patternshaving no variable-chain. The membership problem for term tree patternsis to decide whether or not a given tree can be obtained from a given term tree pattern by applying height-constrained replacements to all height-constrained variables in the term tree pattern. The MINL problem for term tree patternsis to find a term tree pattern t such that the language generated by t is minimal among languages, generated by term tree patterns, which contain all given tree-structured data. Finally, we show that the class, i.e., the set of all term tree patternshaving no variable-chain, is polynomial time inductively inferable from positive data if |Λ| ≥ 2.

This letter presents a method for solving several linear equations in max-plus algebra. The essential part of these equations is reduced to constraint satisfaction problems compatible with mixed integer programming. This method is flexible, compared with optimization methods, and suitable for scheduling of certain discrete event systems.

Periodic interference frequently affects the measurement of small signals and causes problems in clinical diagnostics. Adaptive filters can be used as potential tools for cancelling such interference. However, when the interference has a frequency fluctuation, the ideal adaptive-filter coefficients for cancelling the interference also fluctuate. When the adaptation property of the algorithm is slow compared with the frequency fluctuation, the interference-cancelling performance is degraded. However, if the adaptation is too quick, the performance is degraded owing to the target signal. To overcome this problem, we propose an adaptive filter that suppresses the fluctuation of the ideal coefficients by utilizing a $rac{pi}{2}$ phase-delay device. This method assumes a frequency response that characterizes the transmission path from the interference source to the main input signal to be sufficiently smooth. In the numerical examples, the proposed method exhibits good performance in the presence of a frequency fluctuation when the forgetting factor is large. Moreover, we show that the proposed method reduces the calculation cost.

A 12-bit 1.25MS/s cyclic analog-to-digital converter (ADC) is designed and fabricated in 90nm CMOS technology, and only occupies an active area as small as 0.037mm2. The proposed ADC is composed of a non-binary AD convertion stage, and a on-chip non-binary-to-binary digital block includes a built-in radix-value self-estimation scheme. Therefore, althouh a non-binary convertion architechture is adopted, the proposed ADC is the same as other stand-alone binary ADCs. The redundancy of non-binary 1-bit/step architecture relaxes the accuracy requirement on analog components of ADC. As a result, the implementation of analog circuits such as amplifier and comparator becomes simple, and high-density Metal-Oxide-Metal (MOM) capacitors can be used to achieve a small chip area. Furthermore, the novel radix-value self-estimation technique can be realized by only simple logic circuits without any extra analog input, so that the total active area of ADC is dramatically reduced. The prototype ADC achieves a measured peak signal-to-noise-and-distortion-ratio (SNDR) of 62.3dB using a poor DC gain amplifier as low as 45dB and MOM capacitors without any careful layout techniques to improve the capacitor matching. The proposed ADC dissipated 490µW in analog circuits at 1.4V power supply and 1.25Msps (20MHz clocking). The measured DNL is +0.94/-0.71LSB and INL is +1.9/-1.2LSB at 30kHz sinusoidal input.

In this letter, we propose an algorithm for the 2-dimensional (2D) direction of arrival (DOA) estimation of noncircular coherently distributed (CD) sources using the centrosymmetric array. For a centrosymmetric array, we prove that the angular signal distributed weight (ASDW) vector of the CD source has a symmetric structure. To estimate azimuth and elevation angle, we perform a 2D searching based on generalized ESPRIT algorithm. The significant superiority of the proposed algorithm is that, the 2D central directions of CD sources can be found independently of deterministic angular distributed function (DADF). Simulations results verify the efficacy of the proposed algorithm.

Massive MIMO transmission, whose number of antennas is much larger than the number of user terminals, has been attracted much attention as one of key technologies in next-generation mobile communication system because it enables improvement in service area and interference mitigation by simple signal processing. Multi-beam massive MIMO has proposed that utilizes the beam selection with high power in analog part and blind algorithm such as constant modulus algorithm (CMA) which does not need channel state information (CSI) is applied in digital part. Proposed configuration obtains high transmission efficiency. We have evaluated QPSK signals because the CMA basically focuses on the constant amplitude modulation. In this paper, in order to achieve the further higher transmission rate, the amplitude and phase compensation scheme is proposed when using the CMA with amplitude and phase modulation scheme such as QAM. The effectiveness of proposed method is verified by the computer simulation.

It is necessary to estimate channel state information coherently to equalize the received signal in wireless communication systems. The pilot symbol, known at the receiver, aided channel estimator degrades the transmission efficiency because it requires the signal spaces and the energy for the transmission. In this paper, we assume a fixed wireless communication system in line of sight slowly varying channel and propose a new blind channel estimation method without help from the pilot symbol for Orthogonal Frequency Division Multiplexing systems. The proposed estimator makes use of the Expectation-Maximization algorithm and the correlation property among the channel frequency responses by considering the assumed channel environment. By computer simulations, we show that the proposed estimator can asymptotically achieve bit error rate performance by using the ideal channel estimation.

The sparse representation models have been widely applied in image super-resolution. The certain optimization problem is supposed and can be solved by the iterative shrinkage algorithm. During iteration, the update of dictionaries and similar patches is necessary to obtain prior knowledge to better solve such ill-conditioned problem as image super-resolution. However, both the processes of iteration and update often spend a lot of time, which will be a bottleneck in practice. To solve it, in this paper, we present the concept of image quality difference based on generalized Gaussian distribution feature which has the same trend with the variation of Peak Signal to Noise Ratio (PSNR), and we update dictionaries or similar patches from the termination strategy according to the adaptive threshold of the image quality difference. Based on this point, we present two sparse representation algorithms for image super-resolution, one achieves the further improvement in image quality and the other decreases running time on the basis of image quality assurance. Experimental results also show that our quantitative results on several test datasets are in line with exceptions.

It is expected that a large number of different objects, such as sensor devices and consumer electronics, will be connected to future networks. For such networks, we propose a name resolution method for directly specifying a condition on a set of attribute-value pairs of real-world information without needing prior knowledge of the uniquely assigned name of a target object, e.g., a URL. For name resolution, we need an algorithm to find the target object(s) satisfying a query condition on multiple attributes. To address the problem that multi-attribute searching algorithms may not work well when the number of attributes (i.e., dimensions) d increases, which is related to the curse of dimensionality, we also propose a probabilistic searching algorithm to reduce searching time at the expense of a small probability of false positives. With this algorithm, we choose permutation pattern(s) of d attributes to use the first K (K « d) ones to search objects so that they contain relevant attributes with a high probability. We argue that our algorithm can identify the target objects at a false positive rate less than 10-6 and a few percentages of tree-searching cost compared with a naive d-dimensional searching under a certain condition.

Attacks against computer networks are evolving rapidly. Conventional intrusion detection system based on pattern matching and static signatures have a significant limitation since the signature database should be updated frequently. The unsupervised learning algorithm can overcome this limitation. Ant Clustering Algorithm (ACA) is a popular unsupervised learning algorithm to classify data into different categories. However, ACA needs to be complemented with other algorithms for the classification process. In this paper, we present a fuzzy anomaly detection system that works in two phases. In the first phase, the training phase, we propose ACA to determine clusters. In the second phase, the classification phase, we exploit a fuzzy approach by the combination of two distance-based methods to detect anomalies in new monitored data. We validate our hybrid approach using the KDD Cup'99 dataset. The results indicate that, compared to several traditional and new techniques, the proposed hybrid approach achieves higher detection rate and lower false positive rate.

In 1999, Boneh and Durfee introduced the small inverse problem, which solves the bivariate modular equation x(N+y)≡1(mod e. Absolute values of solutions for x and y are bounded above by X=Nδ and Y=Nβ, respectively. They solved the problem for β=1/2 in the context of small secret exponent attacks on RSA and proposed a polynomial time algorithm that works when δ<(7-2√7)/6≈0.284. In the same work, the bound was further improved to δ<1-1/≈2≈0.292. Thus far, the small inverse problem has also been analyzed for an arbitrary β. Generalizations of Boneh and Durfee's lattices to obtain the stronger bound yielded the bound δ<1-≈β. However, the algorithm works only when β≥1/4. When 0<β<1/4, there have been several works where the authors claimed their results are the best. In this paper, we revisit the problem for an arbitrary β. At first, we summarize the previous results for 0<β<1/4. We reveal that there are some results that are not valid and show that Weger's algorithms provide the best bounds. Next, we propose an improved algorithm to solve the problem for 0<β<1/4. Our algorithm works when δ<1-2(≈β(3+4β)-β)/3. Our algorithm construction is based on the combinations of Boneh and Durfee's two forms of lattices and it is more natural compared with previous works. For the cryptographic application, we introduce small secret exponent attacks on Multi-Prime RSA with small prime differences.

In this paper, we propose a novel placement algorithm for mixed-grained reconfigurable architectures (MGRAs). MGRA consists of coarse-grained and fine-grained clusters, in order to implement a combined digital systems of high-speed data paths with multi-bit operands and random logic circuits for state machines and bit-wise operations. For accelerating simulated annealing based FPGA placement algorithm, range limiter has been proposed to control the distance of two blocks to be interchanged. However, it is not applicable to MGRAs due to the heterogeneous structure of MGRAs. Proposed range limiter using connection bounding box effectively keeps the size of range limiter to encourage moves across fine-grain blocks in non-adjacent clusters. From experimental results, the proposed method achieved 47.8% reduction of cost in the best case compared with conventional methods.

A Reed-Solomon (RS) decoder is designed based on the pipelined recursive Euclidean algorithm in the key equation solution. While the Euclidean algorithm uses less Galois multipliers than the modified Euclidean (ME) and reformulated inversionless Berlekamp-Massey (RiBM) algorithms, division between two elements in Galois field is required. By implementing the division with a multi-cycle Galois inverter and a serial Galois multiplier, the proposed key equation solver architecture achieves lower complexity than the conventional ME and RiBM based architectures. The proposed RS (255,239) decoder reduces the hardware complexity by 25.9% with 6.5% increase in decoding latency.