OpenRaiser/Intern-Atlas huggingface dataset:
Enumerating models of DNF faster: breaking the dependency on the formula size
Venue: arXiv cs.CC 2024
Year: 2024

In this article, we study the problem of enumerating the models of DNF formulas. The aim is to provide enumeration algorithms with a delay that depends polynomially on the size of each model and not on the size of the formula, which can be exponentially larger. We succeed for two subclasses of DNF formulas: we provide a constant delay algorithm for $k$-DNF with fixed $k$ by an appropriate amortization method and we give a quadratic delay algorithm for monotone formulas. We then focus on the \emph{average delay} of enumeration algorithms and show how to obtain a sublinear delay in the formula size.
Incentivizing Exploration with Selective Data Disclosure
Venue: arXiv cs.GT 2024
Year: 2024

We propose and design recommendation systems that incentivize efficient exploration. Agents arrive sequentially, choose actions and receive rewards, drawn from fixed but unknown action-specific distributions. The recommendation system presents each agent with actions and rewards from a subsequence of past agents, chosen ex ante. Thus, the agents engage in sequential social learning, moderated by these subsequences. We asymptotically attain optimal regret rate for exploration, using a flexible frequentist behavioral model and mitigating rationality and commitment assumptions inherent in prior work. We suggest three components of effective recommendation systems: independent focus groups, group aggregators, and interlaced information structures.
Efficient Attention: Attention with Linear Complexities
Venue: arXiv cs.CV 2024
Year: 2024

Dot-product attention has wide applications in computer vision and natural language processing. However, its memory and computational costs grow quadratically with the input size. Such growth prohibits its application on high-resolution inputs. To remedy this drawback, this paper proposes a novel efficient attention mechanism equivalent to dot-product attention but with substantially less memory and computational costs. Its resource efficiency allows more widespread and flexible integration of attention modules into a network, which leads to better accuracies. Empirical evaluations demonstrated the effectiveness of its advantages. Efficient attention modules brought significant performance boosts to object detectors and instance segmenters on MS-COCO 2017. Further, the resource efficiency democratizes attention to complex models, where high costs prohibit the use of dot-product attention. As an exemplar, a model with efficient attention achieved state-of-the-art accuracies for stereo depth estimation on the Scene Flow dataset. Code is available at https://github.com/cmsflash/efficient-attention.
Beyond Uniform Reverse Sampling: A Hybrid Sampling Technique for Misinformation Prevention
Venue: arXiv cs.SI 2024
Year: 2024

Online misinformation has been considered as one of the top global risks as it may cause serious consequences such as economic damages and public panic. The misinformation prevention problem aims at generating a positive cascade with appropriate seed nodes in order to compete against the misinformation. In this paper, we study the misinformation prevention problem under the prominent independent cascade model. Due to the #P-hardness in computing influence, the core problem is to design effective sampling methods to estimate the function value. The main contribution of this paper is a novel sampling method. Different from the classic reverse sampling technique which treats all nodes equally and samples the node uniformly, the proposed method proceeds with a hybrid sampling process which is able to attach high weights to the users who are prone to be affected by the misinformation. Consequently, the new sampling method is more powerful in generating effective samples used for computing seed nodes for the positive cascade. Based on the new hybrid sample technique, we design an algorithm offering a $(1-1/e-ε)$-approximation. We experimentally evaluate the proposed method on extensive datasets and show that it significantly outperforms the state-of-the-art solutions.
Benchmarking Time Series Databases with IoTDB-Benchmark for IoT Scenarios
Venue: arXiv cs.DB 2024
Year: 2024

With the wide application of time series databases (TSDBs) in big data fields like cluster monitoring and industrial IoT, there have been developed a number of TSDBs for time series data management. Different TSDBs have test reports comparing themselves with other databases to show their advantages, but the comparisons are typically based on their own tools without using a common well-recognized test framework. To the best of our knowledge, there is no mature TSDB benchmark either. With the goal of establishing a standard of evaluating TSDB systems, we present the IoTDB-Benchmark framework, specifically designed for TSDB and IoT application scenarios. We pay close attention to some special data ingestion scenarios and summarize 10 basic queries types. We use this benchmark to compare four TSDB systems: InfluxDB, OpenTSDB, KairosDB and TimescaleDB. Our benchmark framework/tool not only measures performance metrics but also takes system resource consumption into consideration.
Geometric interpretation of the general POE model for a serial-link robot via conversion into D-H parameterization
Venue: arXiv cs.RO 2024
Year: 2024

While Product of Exponentials (POE) formula has been gaining increasing popularity in modeling the kinematics of a serial-link robot, the Denavit-Hartenberg (D-H) notation is still the most widely used due to its intuitive and concise geometric interpretation of the robot. This paper has developed an analytical solution to automatically convert a POE model into a D-H model for a robot with revolute, prismatic, and helical joints, which are the complete set of three basic one degree of freedom lower pair joints for constructing a serial-link robot. The conversion algorithm developed can be used in applications such as calibration where it is necessary to convert the D-H model to the POE model for identification and then back to the D-H model for compensation. The equivalence of the two models proved in this paper also benefits the analysis of the identifiability of the kinematic parameters. It is found that the maximum number of identifiable parameters in a general POE model is 5h+4r +2t +n+6 where h, r, t, and n stand for the number of helical, revolute, prismatic, and general joints, respectively. It is also suggested that the identifiability of the base frame and the tool frame in the D-H model is restricted rather than the arbitrary six parameters as assumed previously.
PVNet: A LRCN Architecture for Spatio-Temporal Photovoltaic PowerForecasting from Numerical Weather Prediction
Venue: arXiv cs.LG 2024
Year: 2024

Photovoltaic (PV) power generation has emerged as one of the lead renewable energy sources. Yet, its production is characterized by high uncertainty, being dependent on weather conditions like solar irradiance and temperature. Predicting PV production, even in the 24-hour forecast, remains a challenge and leads energy providers to left idling - often carbon emitting - plants. In this paper, we introduce a Long-Term Recurrent Convolutional Network using Numerical Weather Predictions (NWP) to predict, in turn, PV production in the 24-hour and 48-hour forecast horizons. This network architecture fully leverages both temporal and spatial weather data, sampled over the whole geographical area of interest. We train our model on an NWP dataset from the National Oceanic and Atmospheric Administration (NOAA) to predict spatially aggregated PV production in Germany. We compare its performance to the persistence model and state-of-the-art methods.
The First 50 Years of Software Reliability Engineering: A History of SRE with First Person Accounts
Venue: arXiv cs.SE 2024
Year: 2024

Software Reliability has just passed the 50-year milestone as a technical discipline along with Software Engineering. This paper traces the roots of Software Reliability Engineering (SRE) from its pre-software history to the beginnings of the field with the first software reliability model in 1967 through its maturation in the 1980s to the current challenges in proving application reliability on smartphones and in other areas. This history began as a thesis proposal for a History of Science research program and includes multiple previously unpublished interviews with founders of the field. The project evolved to also provide a survey of the development of SRE from notable prior histories and from citations of new work in the field including reliability applications to Agile Methods. This history concludes at the modern-day providing bookends in the theory, models, literature, and practice of Software Reliability Engineering from 1968 to 2018 and pointing towards new opportunities to deepen and broaden the field.
Factoring Perfect Reconstruction Filter Banks into Causal Lifting Matrices: A Diophantine Approach
Venue: arXiv cs.IT 2024
Year: 2024

The elementary theory of bivariate linear Diophantine equations over polynomial rings is used to construct causal lifting factorizations (elementary matrix decompositions) for causal two-channel FIR perfect reconstruction transfer matrices and wavelet transforms. The Diophantine approach generates causal factorizations satisfying certain polynomial degree-reducing inequalities, enabling a new factorization strategy called the Causal Complementation Algorithm. This provides a causal (i.e., polynomial, hence realizable) alternative to the noncausal lifting scheme developed by Daubechies and Sweldens using the Extended Euclidean Algorithm for Laurent polynomials. The new approach replaces the Euclidean Algorithm with Gaussian elimination employing a slight generalization of polynomial division that ensures existence and uniqueness of quotients whose remainders satisfy user-specified divisibility constraints. The Causal Complementation Algorithm is shown to be more general than the causal version of the Euclidean Algorithm approach by generating additional causal lifting factorizations beyond those obtainable using the polynomial Euclidean Algorithm.
Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number
Venue: arXiv cs.DS 2024
Year: 2024

We investigate the locality number, a recently introduced structural parameter for strings (with applications in pattern matching with variables), and its connection to two important graph-parameters, cutwidth and pathwidth. These connections allow us to show that computing the locality number is NP-hard, but fixed-parameter tractable, if parameterised by the locality number or by the alphabet size, which has been formulated as open problems in the literature. Moreover, the locality number can be approximated with ratio O(sqrt(log(opt)) log(n)). An important aspect of our work -- that is relevant in its own right and of independent interest -- is that we identify connections between the string parameter of the locality number on the one hand, and the famous graph parameters of cutwidth and pathwidth, on the other hand. These two parameters have been jointly investigated in the literature and are arguably among the most central graph parameters that are based on "linearisations" of graphs. In this way, we also identify a direct approximation preserving reduction from cutwidth to pathwidth, which shows that any polynomial f(opt,|V|)-approximation algorithm for pathwidth yields a polynomial 2f(2 opt,h)-approximation algorithm for cutwidth on multigraphs (where h is the number of edges). In particular, this translates known approximation ratios for pathwidth into new approximation ratios for cutwidth, namely O(sqrt(log(opt)) log(h)) and O(sqrt(log(opt)) opt) for (multi) graphs with h edges.
Regular Expressions with Backreferences: Polynomial-Time Matching Techniques
Venue: arXiv cs.FL 2024
Year: 2024

Regular expressions with backreferences (regex, for short), as supported by most modern libraries for regular expression matching, have an NP-complete matching problem. We define a complexity parameter of regex, called active variable degree, such that regex with this parameter bounded by a constant can be matched in polynomial-time. Moreover, we formulate a novel type of determinism for regex (on an automaton-theoretic level), which yields the class of memory-deterministic regex that can be matched in time O(|w|p(|r|)) for a polynomial p (where r is the regex and w the word). Natural extensions of these concepts lead to properties of regex that are intractable to check.
Multi-camera calibration with pattern rigs, including for non-overlapping cameras: CALICO
Venue: arXiv cs.CV 2024
Year: 2024

This paper describes CALICO, a method for multi-camera calibration suitable for challenging contexts: stationary and mobile multi-camera systems, cameras without overlapping fields of view, and non-synchronized cameras. Recent approaches are roughly divided into infrastructure- and pattern-based. Infrastructure-based approaches use the scene's features to calibrate, while pattern-based approaches use calibration patterns. Infrastructure-based approaches are not suitable for stationary camera systems, and pattern-based approaches may constrain camera placement because shared fields of view or extremely large patterns are required. CALICO is a pattern-based approach, where the multi-calibration problem is formulated using rigidity constraints between patterns and cameras. We use a {\it pattern rig}: several patterns rigidly attached to each other or some structure. We express the calibration problem as that of algebraic and reprojection error minimization problems. Simulated and real experiments demonstrate the method in a variety of settings. CALICO compared favorably to Kalibr. Mean reconstruction accuracy error was $\le 0.71$ mm for real camera rigs, and $\le 1.11$ for simulated camera rigs. Code and data releases are available at \cite{tabb_amy_2019_3520866} and \url{https://github.com/amy-tabb/calico}.
Quadrotor Manipulation System: Development of a Robust Contact Force Estimation and Impedance Control Scheme Based on DOb and FTRLS
Venue: arXiv cs.RO 2024
Year: 2024

The research on aerial manipulation systems has been increased rapidly in recent years. These systems are very attractive for a wide range of applications due to their unique features. However, dynamics, control and manipulation tasks of such systems are quite challenging because they are naturally unstable, have very fast dynamics, have strong nonlinearities, are very susceptible to parameters variations due to carrying a payload besides the external disturbances, and have complex inverse kinematics. In addition, the manipulation tasks require estimating (applying) a certain force of (at) the end-effector as well as the accurate positioning of it. Thus, in this article, a robust force estimation and impedance control scheme is proposed to address these issues. The robustness is achieved based on the Disturbance Observer (DOb) technique. Then, a tracking and performance low computational linear controller is used. For teleoperation purpose, the contact force needs to be identified. However, the current developed techniques for force estimation have limitations because they are based on ignoring some dynamics and/or requiring of an indicator of the environment contact. Unlike these techniques, we propose a technique based on linearization capabilities of DOb and a Fast Tracking Recursive Least Squares (FTRLS) algorithm. The complex inverse kinematics problem of such a system is solved by a Jacobin based algorithm. The stability analysis of the proposed scheme is presented. The algorithm is tested to achieve tracking of task space reference trajectories besides the impedance control. The efficiency of the proposed technique is enlightened via numerical simulation.
A Text Classification Framework for Simple and Effective Early Depression Detection Over Social Media Streams
Venue: arXiv cs.CY 2024
Year: 2024

With the rise of the Internet, there is a growing need to build intelligent systems that are capable of efficiently dealing with early risk detection (ERD) problems on social media, such as early depression detection, early rumor detection or identification of sexual predators. These systems, nowadays mostly based on machine learning techniques, must be able to deal with data streams since users provide their data over time. In addition, these systems must be able to decide when the processed data is sufficient to actually classify users. Moreover, since ERD tasks involve risky decisions by which people's lives could be affected, such systems must also be able to justify their decisions. However, most standard and state-of-the-art supervised machine learning models are not well suited to deal with this scenario. This is due to the fact that they either act as black boxes or do not support incremental classification/learning. In this paper we introduce SS3, a novel supervised learning model for text classification that naturally supports these aspects. SS3 was designed to be used as a general framework to deal with ERD problems. We evaluated our model on the CLEF's eRisk2017 pilot task on early depression detection. Most of the 30 contributions submitted to this competition used state-of-the-art methods. Experimental results show that our classifier was able to outperform these models and standard classifiers, despite being less computationally expensive and having the ability to explain its rationale.
DISN: Deep Implicit Surface Network for High-quality Single-view 3D Reconstruction
Venue: arXiv cs.CV 2024
Year: 2024

Reconstructing 3D shapes from single-view images has been a long-standing research problem. In this paper, we present DISN, a Deep Implicit Surface Network which can generate a high-quality detail-rich 3D mesh from an 2D image by predicting the underlying signed distance fields. In addition to utilizing global image features, DISN predicts the projected location for each 3D point on the 2D image, and extracts local features from the image feature maps. Combining global and local features significantly improves the accuracy of the signed distance field prediction, especially for the detail-rich areas. To the best of our knowledge, DISN is the first method that constantly captures details such as holes and thin structures present in 3D shapes from single-view images. DISN achieves the state-of-the-art single-view reconstruction performance on a variety of shape categories reconstructed from both synthetic and real images. Code is available at https://github.com/xharlie/DISN The supplementary can be found at https://xharlie.github.io/images/neurips_2019_supp.pdf
Intelligent Reflecting Surface vs. Decode-and-Forward: How Large Surfaces Are Needed to Beat Relaying?
Venue: arXiv cs.IT 2024
Year: 2024

The rate and energy efficiency of wireless channels can be improved by deploying software-controlled metasurfaces to reflect signals from the source to the destination, especially when the direct path is weak. While previous works mainly optimized the reflections, this letter compares the new technology with classic decode-and-forward (DF) relaying. The main observation is that very high rates and/or large metasurfaces are needed to outperform DF relaying, both in terms of minimizing the total transmit power and maximizing the energy efficiency, which also includes the dissipation in the transceiver hardware.
Synthesis of Computable Regular Functions of Infinite Words
Venue: arXiv cs.FL 2024
Year: 2024

Regular functions from infinite words to infinite words can be equivalently specified by MSO-transducers, streaming $ω$-string transducers as well as deterministic two-way transducers with look-ahead. In their one-way restriction, the latter transducers define the class of rational functions. Even though regular functions are robustly characterised by several finite-state devices, even the subclass of rational functions may contain functions which are not computable (by a Turing machine with infinite input). This paper proposes a decision procedure for the following synthesis problem: given a regular function $f$ (equivalently specified by one of the aforementioned transducer model), is $f$ computable and if it is, synthesize a Turing machine computing it. For regular functions, we show that computability is equivalent to continuity, and therefore the problem boils down to deciding continuity. We establish a generic characterisation of continuity for functions preserving regular languages under inverse image (such as regular functions). We exploit this characterisation to show the decidability of continuity (and hence computability) of rational and regular functions. For rational functions, we show that this can be done in $\mathsf{NLogSpace}$ (it was already known to be in $\mathsf{PTime}$ by Prieur). In a similar fashion, we also effectively characterise uniform continuity of regular functions, and relate it to the notion of uniform computability, which offers stronger efficiency guarantees.
Quantifying the Vulnerabilities of the Online Public Square to Adversarial Manipulation Tactics
Venue: arXiv cs.CY 2024
Year: 2024

Social media, seen by some as the modern public square, is vulnerable to manipulation. By controlling inauthentic accounts impersonating humans, malicious actors can amplify disinformation within target communities. The consequences of such operations are difficult to evaluate due to the challenges posed by collecting data and carrying out ethical experiments that would influence online communities. Here we use a social media model that simulates information diffusion in an empirical network to quantify the impacts of several adversarial manipulation tactics on the quality of content. We find that the presence of influential accounts, a hallmark of social media, exacerbates the vulnerabilities of online communities to manipulation. Among the explored tactics that bad actors can employ, infiltrating a community is the most likely to make low-quality content go viral. Such harm can be further compounded by inauthentic agents flooding the network with low-quality, yet appealing content, but is mitigated when bad actors focus on specific targets, such as influential or vulnerable individuals. These insights suggest countermeasures that platforms could employ to increase the resilience of social media users to manipulation.
2FA Sketch: Two-Factor Armor Sketch for Accurate and Efficient Heavy Hitter Detection in Data Streams
Venue: arXiv cs.NI 2024
Year: 2024

Detecting heavy hitters, which are flows exceeding a specified threshold, is crucial for network measurement, but it faces challenges due to increasing throughput and memory constraints. Existing sketch-based solutions, particularly those using Comparative Counter Voting, have limitations in efficiently identifying heavy hitters. This paper introduces the Two-Factor Armor (2FA) Sketch, a novel data structure designed to enhance heavy hitter detection in data streams. 2FA Sketch implements dual-layer protection through an improved $\mathtt{Arbitration}$ strategy for in-bucket competition and a cross-bucket conflict $\mathtt{Avoidance}$ hashing scheme. By theoretically deriving an optimal $λ$ parameter and redesigning $vote^+_{new}$ as a conflict indicator, it optimizes the Comparative Counter Voting strategy. Experimental results show that 2FA Sketch outperforms the standard Elastic Sketch, reducing error rates by 2.5 to 19.7 times and increasing processing speed by 1.03 times.