Remote photoplethysmography (rPPG) is a method for non-contact measurement of physiological signals from facial videos, holding great potential in various applications such as healthcare, affective computing, and anti-spoofing. Existing deep learning methods struggle to address two core issues of rPPG simultaneously: understanding the periodic pattern of rPPG among long contexts and addressing large spatiotemporal redundancy in video segments. These represent a trade-off between computational complexity and the ability to capture long-range dependencies. In this paper, we introduce RhythmMamba, a state space model-based method that captures long-range dependencies while maintaining linear complexity. By viewing rPPG as a time series task through the proposed frame stem, the periodic variations in pulse waves are modeled as state transitions. Additionally, we design multi-temporal constraint and frequency domain feed-forward, both aligned with the characteristics of rPPG time series, to improve the learning capacity of Mamba for rPPG signals. Extensive experiments show that RhythmMamba achieves state-of-the-art performance with 319% throughput and 23% peak GPU memory.

With the increasing availability of time-dependent objects on Social internet of Things (SIoT), taking advantage of this data for SIoT-based route planning and recommendation is becoming increasingly imperative. To facilitate IoT-based route planning and recommendation, Trajectory Search by Locations (TSL) has been serving as a fundamental operation for data cleaning based on personalized requirements. However, existing TSL methods regard each trajectory as an indivisible object of time series. Because that the lengths and spatial distributions of trajectories may vary, traditional TRL methods often fail to return high-quality results, especially when the trajectory data is spare. Such limitation is considered to be a major bottleneck for improving the effectiveness of SIoT-based route planning and recommendation. To address the limitation, we propose a parallel mechanism for handling the problem of Trajectory Search by Locations through Parallel split-and-combine (TSL-Psc). The TSL-Psc problem is described as follows. Given a set of trajectories, a query sequence Q consisting of a sequence of timestamped locations, and a spatio-temporal similarity threshold θ, we retrieve a combined trajectory composed of sub-trajectories that (i) has similarity to Q no less than θ and (ii) contains the minimum number of sub-trajectory combinations. The resulting functionality of TSL-Psc targets a broad range of time-sensitive applications regarding SIoT, including traffic analysis, real-time group route planning, and ridesharing. To enable efficient TSL-Psc computation of trajectory data, we develop a three-phase Joint-Split Parallel Search (JSPS) algorithm on the basis of FSPS and GSPS. JSPS consists of pre-checking, split, and combine phases. We develop a spatial-first expansion algorithm and a temporal-first expansion algorithm that are capable of pruning search space in both spatial and temporal domains. Comprehensive experiments conducted on real-world datasets provide valuable insights into the algorithm’s performance, demonstrating that the proposed TSL-Psc problem formulation produces high-quality outcomes while the search algorithms deliver high-standard efficiency and scalability.

Existing lexical substitution (LS) benchmarks were collected by asking human annotators to think of substitutes from memory, resulting in benchmarks with limited coverage and relatively small scales.To overcome this problem, we propose a novel annotation method to construct an LS dataset based on human and machine collaboration.Based on our annotation method, we construct the first Chinese LS dataset CHNLS which consists of 33,695 instances and 144,708 substitutes, covering three text genres (News, Novel, and Wikipedia).Specifically, we first combine four unsupervised LS methods as an ensemble method to generate the candidate substitutes, and then let human annotators judge these candidates or add new ones.This collaborative process combines the diversity of machine-generated substitutes with the expertise of human annotators.Experimental results that the ensemble method outperforms other LS methods.To our best knowledge, this is the first study for the Chinese LS task.

We revisit two fundamental problems in database theory. The join-dependency (JD) testing problem is to determine whether a given JD holds on a relation r . We prove that the problem is NP-hard even if the JD involves only relations each of which has only two attributes. The JD-existence testing problem is to determine if there exists any non-trivial JD satisfied by r . We present an I/O-efficient algorithm in the external memory model, which in fact settles the closely related Loomis–Whitney enumeration problem. As a side product, we solve the triangle enumeration problem with the optimal I/O-complexity, improving a recent result of Pagh and Silvestri in PODS'14.

In dynamic distinct counting, we want to maintain a multi-set S of integers under insertions to answer efficiently the query: how many distinct elements are there in S? In external memory, the problem admits two standard solutions. The first one maintains $S$ in a hash structure, so that the distinct count can be incrementally updated after each insertion using O(1) expected I/Os. A query is answered for free. The second one stores S in a linked list, and thus supports an insertion in O(1/B) amortized I/Os. A query can be answered in O(N/B log_{M/B} (N/B)) I/Os by sorting, where N=|S|, B is the block size, and M is the memory size. In this paper, we show that the above two naive solutions are already optimal within a polylog factor. Specifically, for any Las Vegas structure using N^{O(1)} blocks, if its expected amortized insertion cost is o(1/log B}), then it must incur Omega(N/(B log B)) expected I/Os answering a query in the worst case, under the (realistic) condition that N is a polynomial of B. This means that the problem is repugnant to update buffering: the query cost jumps from 0 dramatically to almost linearity as soon as the insertion cost drops slightly below Omega(1).

This paper aims to understand the I/O-complexity of maintaining a big sample set---whose size exceeds the internal memory's capacity---on a data stream. We study this topic in a new computation model, named the external memory stream (EMS) model, that naturally extends the standard external memory model to stream environments. A suite of EMS-indigenous techniques are presented to prove matching lower and upper bounds for with-replacement (WR) and without-replacement (WoR) sampling on append-only and time-based sliding window streams, respectively. Our results imply that, compared to RAM, the EMS model is perhaps a more suitable computation model for studying stream sampling, because the new model separates different problems by their hardness in ways that could not be observed in RAM.

In this paper, we revisit two fundamental problems in database theory. The first one is called join dependency (JD) testing, where we are given a relation r and a JD, and need to determine whether the JD holds on r. The second problem is called JD existence testing, where we need to determine if there exists any non-trivial JD that holds on r.

Prediction-error expansion (PEE)-based reversible data hiding schemes consist of two steps. First, a sharp prediction-error (PE) histogram is generated by utilizing pixel prediction strategies. Second, secret messages are reversibly embedded into the prediction-errors through expanding and shifting the PE histogram. Previous PEE methods treat the two steps independently while they either focus on pixel prediction to obtain a sharp PE histogram, or aim at histogram modification to enhance the embedding performance for a given PE histogram. This paper propose a pixel prediction method based on the minimum rate criterion for reversible data hiding, which establishes the consistency between the two steps in essence. And correspondingly, a novel optimized histograms modification scheme is presented to approximate the optimal embedding performance on the generated PE sequence. Experiments demonstrate that the proposed method outperforms the previous state-of-art counterparts significantly in terms of both the prediction accuracy and the final embedding performance.

Recently, a recursive code construction (RCC) approaching the rate-distortion bound of reversible data hiding (RDH) was proposed. However, to estimate the rate-distortion bound or execute RCC, one should first estimate the optimal transition probability matrix (OTPM). By previous methods, OTPM can be effectively estimated only for some specific distortion metrics, such as square error distortion or L1-Norm. In this paper, we proposed a unified framework of estimating the OTPM for general distortion metrics, with which we can calculate the rate-distortion bound of RDH for general cases and extend RCC to improve state-of-the-art RDH schemes based on any distortion metrics.

This paper studies the independent range sampling problem. The input is a set P of n points in R. Given an interval q = [x, y] and an integer t ≥ 1, a query returns t elements uniformly sampled (with/without replacement) from P ∩ q. The sampling result must be independent from those returned by the previous queries. The objective is to store P in a structure for answering all queries efficiently.

This paper studies two fundamental problems both of which are defined on a set S of elements drawn from an ordered domain. In the first problem--called approximate K-partitioning--we want to divide S into K disjoint partitions P1, ..., PK such that (i) every element in Pi is smaller than all the elements in Pj for any i, j satisfying 1 ≤ i < j ≤ K, and (ii) the size of each Pi (1 ≤ i ≤ K) falls in a given range [a, b]. In the second problem--called approximate K-splitters---we want to find K - 1 elements s_1, ..., sK-1 from S, such that the size of S ∩ (s_i, s_i-1] falls in a given range [a, b] (define dummy s_0 = - ∞ and s_K = ∞). We present I/O-efficient comparison-based algorithms for solving these problems, and establish their optimality by proving matching lower bounds. Our results reveal that the two problems are separated in terms of I/O complexity when K is small, but have the same hardness when K is large.

Designing an appropriate regularizer is of great importance for accurate optical flow estimation. Recent works exploiting the nonlocal similarity and the sparsity of the motion field have led to promising flow estimation results. In this paper, we propose to unify these two powerful priors. To this end, we propose an effective flow regularization technique based on joint low-rank and sparse matrix recovery. By grouping similar flow patches into clusters, we effectively regularize the motion field by decomposing each set of similar flow patches into a low-rank component and a sparse component. For better enforcing the low-rank property, instead of using the convex nuclear norm, we use the log det(·) function as the surrogate of rank, which can also be efficiently minimized by iterative singular value thresholding. Experimental results on the Middlebury benchmark show that the performance of the proposed nonlocal sparse and low-rank regularization method is higher than (or comparable to) those of previous approaches that harness these same priors, and is competitive to current state-of-the-art methods.

This article studies I/O-efficient algorithms for the triangle listing problem and the triangle counting problem , whose solutions are basic operators in dealing with many other graph problems. In the former problem, given an undirected graph G , the objective is to find all the cliques involving 3 vertices in G . In the latter problem, the objective is to report just the number of such cliques without having to enumerate them. Both problems have been well studied in internal memory, but still remain as difficult challenges when G does not fit in memory, thus making it crucial to minimize the number of disk I/Os performed. Although previous research has attempted to tackle these challenges, the state-of-the-art solutions rely on a set of crippling assumptions to guarantee good performance. Motivated by this, we develop a new algorithm that is provably I/O and CPU efficient at the same time, without making any assumption on the input G at all. The algorithm uses ideas drastically different from all the previous approaches, and outperforms the existing competitors by a factor of over an order of magnitude in our extensive experimentation.

This paper studies I/O-efficient algorithms for settling the classic triangle listing problem, whose solution is a basic operator in dealing with many other graph problems. Specifically, given an undirected graph G, the objective of triangle listing is to find all the cliques involving 3 vertices in G. The problem has been well studied in internal memory, but remains an urgent difficult challenge when G does not fit in memory, rendering any algorithm to entail frequent I/O accesses. Although previous research has attempted to tackle the challenge, the state-of-the-art solutions rely on a set of crippling assumptions to guarantee good performance. Motivated by this, we develop a new algorithm that is provably I/O and CPU efficient at the same time, without making any assumption on the input G at all. The algorithm uses ideas drastically different from all the previous approaches, and outperformed the existing competitors by a factor over an order of magnitude in our extensive experimentation.

This paper presents new results in external memory for finding the skyline (a.k.a. maxima) of N points in d-dimensional space. The state of the art uses for fixed d ≥ 3, and O((N/B)logM/B(N/B)) I/Os for d = 2, where M and B are the sizes (in words) of memory and a disk block, respectively. We give algorithms whose running time depends on the number K of points in the skyline. Specifically, we achieve expected cost for fixed d ≥ 3, and O((N/B)logM/B(K/B)) worst-case cost for d = 2. As a side product, we solve two problems both of independent interest. The first one, the M-skyline problem, aims at reporting M arbitrary skyline points, or the entire skyline if its size is at most M. We settle this problem in O(N/B) expected time in any fixed dimensionality d. The second one, the M-pivot problem, is more fundamental: given a set S of N elements drawn from an ordered domain, it outputs M evenly scattered elements (called pivots) from S, namely, S has asymptotically the same number of elements between each pair of consecutive pivots. We give a deterministic algorithm for solving the problem in O(N/B) I/Os.

In the maximizing range sum (MaxRS) problem, given (i) a setPof 2D points each of which is associated with a positive weight, and (ii) a rectanglerof specific extents, we need to decide where to placerin order to maximize the covered weight ofr- that is, the total weight of the data points covered byr. Algorithms solving the problem exactly entail expensive CPU or I/O cost. In practice, exact answers are often not compulsory in a MaxRS application, where slight imprecision can often be comfortably tolerated, provided that approximate answers can be computed considerably faster. Motivated by this, the present paper studies the (1 - ε)-approximate MaxRS problem, which admits the same inputs as MaxRS, but aims instead to return a rectangle whose covered weight is at least (1-ε)m*, wherem* is the optimal covered weight, and ε can be an arbitrarily small constant between 0 and 1. We present fast algorithms that settle this problem with strong theoretical guarantees.

Recently, code construction approaching the rate-distortion bound of reversible data hiding has been proposed by Lin , in which the coding/decoding process needs the optimal probability distribution of marked-signals as parameters. Therefore, the efficiency and accuracy of estimating the optimal marked-signal distribution will greatly influence the speeds of encoding and decoding. In this paper, we propose a fast algorithm to solve the optimal marked-signal distribution. Furthermore, we modify the method to achieve the optimal distribution directly according to a given distortion constraint or an expected embedding rate, which makes it more practical for applications.

State-of-the-art schemes for reversible data hiding (RDH) usually consist of two steps: first construct a host sequence with a sharp histogram via prediction errors, and then embed messages by modifying the histogram with methods, such as difference expansion and histogram shift. In this paper, we focus on the second stage, and propose a histogram modification method for RDH, which embeds the message by recursively utilizing the decompression and compression processes of an entropy coder. We prove that, for independent identically distributed (i.i.d.) gray-scale host signals, the proposed method asymptotically approaches the rate-distortion bound of RDH as long as perfect compression can be realized, i.e., the entropy coder can approach entropy. Therefore, this method establishes the equivalency between reversible data hiding and lossless data compression. Experiments show that this coding method can be used to improve the performance of previous RDH schemes and the improvements are more significant for larger images.