Approximate duplicate detection in data streams aims to determine whether an item is present within a small subsequence of the data stream. It is a fundamental query problem needed in several network applications, such as web crawling and Radio Frequency Identification (RFID) tag management. Most of the existing algorithms are not space-efficient as they overlook the distributional information of query frequency and membership likelihood. In this paper, we propose CEll Bloom Filter (CEBF) algorithm, a space-efficient data structure designed by adopting a block-wise updating strategy, to solve this problem, and two typical distributions are considered: two typical distributions: (1) uniform query frequency of items, and (2) uniform membership likelihood of items. For an arbitrary sliding window size n and an arbitrary average false positive rate $\epsilon \in (0,1)$, the proposed algorithm needs approximately $O(n{\log }_2(1/\epsilon ))$ bits, which is significantly less than the number of bits used in existing methods. Space lower bound is also derived for these two typical distributions, which demonstrates that the proposed algorithm is near-optimal in terms of space consumption. Experiments are conducted on both synthetic and real datasets, and the experimental results clearly demonstrate that the proposed method is clearly and significantly more effective and promising compared to existing other methods.

Constrained clustering, such as $k$-means with instance-level Must-Link (ML) and Cannot-Link (CL) auxiliary information as the constraints, has been extensively studied recently, due to its broad applications in data science and AI. Despite some heuristic approaches, there has not been any algorithm providing a non-trivial approximation ratio to the constrained $k$-means problem. To address this issue, we propose an algorithm with a provable approximation ratio of $O\mathsf{}\mathrm{(}\log \mathsf{}k\mathrm{)}$ when only ML constraints are considered. We also empirically evaluate the performance of our algorithm on real-world datasets having artificial ML and disjoint CL constraints. The experimental results show that our algorithm outperforms the existing greedy-based heuristic methods in clustering accuracy.

With the prevalence of big-data technology, intricate, nanoscale Multi-Processor System-on-Chips (MP-SoCs) have been used in various safety-critical applications. However, with no extra countermeasures taken, this widespread use of MP-SoCs can lead to an undesirable decrease in their dependability. This study presents a promising approach using a group of Embedded Instruments (EIs) inside a processor core for health monitoring. Multiple health monitoring datasets obtained from the employed EIs are sampled and collated via the implemented experiment and thereafter used for conducting its remaining useful lifetime prognostics. This enables MP-SoCs to undertake preventive self-repair, thus realizing a zero mean downtime system and ensuring improved dependability. In addition, a principal component analysis based algorithm is designed for realizing the EI data fusion. Subsequently, a genetic algorithm based degradation optimization is employed to create a lifetime prediction model with respect to the processor.

Emerging applications widely use field-programmable gate array (FPGA) prototypes as a tool to verify modern very-large-scale integration (VLSI) circuits, imposing many problems, including routing failure caused by the limited number of connections among blocks of FPGAs therein. Such a shortage of connections can be alleviated through time-division multiplexing (TDM), by which multiple signals sharing an identical routing channel can be transmitted. In this context, the routing quality dominantly decides the performance of such systems, proposing the requirement of minimizing the signal delay between FPGA pairs. This paper proposes algorithms for the routing problem in a multi-FPGA system with TDM support, aiming to minimize the maximum TDM ratio. The algorithm consists of two major stages: (1) A method is proposed to set the weight of an edge according to how many times it is shared by the routing requirements and consequently to compute a set of approximate minimum Steiner trees. (2) A ratio assignment method based on the edge-demand framework is devised for assigning ratios to the edges respecting the TDM ratio constraints. Experiments were conducted against the public benchmarks to evaluate our proposed approach as compared with all published works, and the results manifest that our method achieves a better TDM ratio in comparison.