OpenRaiser/Intern-Atlas huggingface dataset:
Fast and Robust Iterative Closest Point
Venue: arXiv cs.CV 2023
Year: 2023

The Iterative Closest Point (ICP) algorithm and its variants are a fundamental technique for rigid registration between two point sets, with wide applications in different areas from robotics to 3D reconstruction. The main drawbacks for ICP are its slow convergence as well as its sensitivity to outliers, missing data, and partial overlaps. Recent work such as Sparse ICP achieves robustness via sparsity optimization at the cost of computational speed. In this paper, we propose a new method for robust registration with fast convergence. First, we show that the classical point-to-point ICP can be treated as a majorization-minimization (MM) algorithm, and propose an Anderson acceleration approach to speed up its convergence. In addition, we introduce a robust error metric based on the Welsch's function, which is minimized efficiently using the MM algorithm with Anderson acceleration. On challenging datasets with noises and partial overlaps, we achieve similar or better accuracy than Sparse ICP while being at least an order of magnitude faster. Finally, we extend the robust formulation to point-to-plane ICP, and solve the resulting problem using a similar Anderson-accelerated MM strategy. Our robust ICP methods improve the registration accuracy on benchmark datasets while being competitive in computational time.
Computational Paths -- An approach in the $LND_{EQ}-TRS_{2}$ system
Venue: arXiv cs.LO 2023
Year: 2023

We use a labelled deduction system ( LND$_{ED-}$TRS ) based on the concept of computational paths (sequences of rewrites) as equalities between two terms of the same type, which allowed us to carry out in homotopic theory an approach using the concept of computational paths. From this, we show that the computational paths can be used to perform the proofs of the $LND_{EQ}-TRS_{2}$ rewriting system.
Multilevel Motion Planning: A Fiber Bundle Formulation
Venue: arXiv cs.RO 2023
Year: 2023

High-dimensional motion planning problems can often be solved significantly faster by using multilevel abstractions. While there are various ways to formally capture multilevel abstractions, we formulate them in terms of fiber bundles. Fiber bundles essentially describe lower-dimensional projections of the state space using local product spaces, which allows us to concisely describe and derive novel algorithms in terms of bundle restrictions and bundle sections. Given such a structure and a corresponding admissible constraint function, we develop highly efficient and asymptotically-optimal sampling-based motion planning methods for high-dimensional state spaces. Those methods exploit the structure of fiber bundles through the use of bundle primitives. Those primitives are used to create novel bundle planners, the rapidly-exploring quotient-space trees (QRRT*), and the quotient-space roadmap planner (QMP*). Both planners are shown to be probabilistically complete and almost-surely asymptotically optimal. To evaluate our bundle planners, we compare them against classical sampling-based planners on benchmarks of four low-dimensional scenarios, and eight high-dimensional scenarios, ranging from 21 to 100 degrees of freedom, including multiple robots and nonholonomic constraints. Our findings show improvements up to 2 to 6 orders of magnitude and underline the efficiency of multilevel motion planners and the benefit of exploiting multilevel abstractions using the terminology of fiber bundles.
Support Aggregate Analytic Window Function over Large Data by Spilling
Venue: arXiv cs.DB 2023
Year: 2023

Analytic function, also called window function, is to query the aggregation of data over a sliding window. For example, a simple query over the online stock platform is to return the average price of a stock of the last three days. These functions are commonly used features in SQL databases. They are supported in most of the commercial databases. With the increasing usage of cloud data infra and machine learning technology, the frequency of queries with analytic window functions rises. Some analytic functions only require const space in memory to store the state, such as SUM, AVG, while others require linear space, such as MIN, MAX. When the window is extremely large, the memory space to store the state may be too large. In this case, we need to spill the state to disk, which is a heavy operation. In this paper, we proposed an algorithm to manipulate the state data in the disk to reduce the disk I/O to make spill available and efficienct. We analyze the complexity of the algorithm with different data distribution.
A class of graphs with large rankwidth
Venue: arXiv cs.DM 2023
Year: 2023

We describe several graphs with arbitrarily large rankwidth (or equivalently with arbitrarily large cliquewidth). Korpelainen, Lozin, and Mayhill [Split permutation graphs, Graphs and Combinatorics, 30(3):633-646, 2014] proved that there exist split graphs with Dilworth number 2 with arbitrarily large rankwidth, but without explicitly constructing them. We provide an explicit construction. Maffray, Penev, and Vušković [Coloring rings, Journal of Graph Theory 96(4):642-683, 2021] proved that graphs that they call rings on $n$ sets can be colored in polynomial time. We show that for every fixed integer $n\geq 3$, there exist rings on $n$ sets with arbitrarily large rankwidth. When $n\geq 5$ and $n$ is odd, this provides a new construction of even-hole-free graphs with arbitrarily large rankwidth.
HITNet: Hierarchical Iterative Tile Refinement Network for Real-time Stereo Matching
Venue: arXiv cs.CV 2023
Year: 2023

This paper presents HITNet, a novel neural network architecture for real-time stereo matching. Contrary to many recent neural network approaches that operate on a full cost volume and rely on 3D convolutions, our approach does not explicitly build a volume and instead relies on a fast multi-resolution initialization step, differentiable 2D geometric propagation and warping mechanisms to infer disparity hypotheses. To achieve a high level of accuracy, our network not only geometrically reasons about disparities but also infers slanted plane hypotheses allowing to more accurately perform geometric warping and upsampling operations. Our architecture is inherently multi-resolution allowing the propagation of information across different levels. Multiple experiments prove the effectiveness of the proposed approach at a fraction of the computation required by state-of-the-art methods. At the time of writing, HITNet ranks 1st-3rd on all the metrics published on the ETH3D website for two view stereo, ranks 1st on most of the metrics among all the end-to-end learning approaches on Middlebury-v3, ranks 1st on the popular KITTI 2012 and 2015 benchmarks among the published methods faster than 100ms.
Natural Strategic Abilities in Voting Protocols
Venue: arXiv cs.MA 2023
Year: 2023

Security properties are often focused on the technological side of the system. One implicitly assumes that the users will behave in the right way to preserve the property at hand. In real life, this cannot be taken for granted. In particular, security mechanisms that are difficult and costly to use are often ignored by the users, and do not really defend the system against possible attacks. Here, we propose a graded notion of security based on the complexity of the user's strategic behavior. More precisely, we suggest that the level to which a security property $φ$ is satisfied can be defined in terms of (a) the complexity of the strategy that the voter needs to execute to make $φ$ true, and (b) the resources that the user must employ on the way. The simpler and cheaper to obtain $φ$, the higher the degree of security. We demonstrate how the idea works in a case study based on an electronic voting scenario. To this end, we model the vVote implementation of the \Pret voting protocol for coercion-resistant and voter-verifiable elections. Then, we identify "natural" strategies for the voter to obtain receipt-freeness, and measure the voter's effort that they require. We also look at how hard it is for the coercer to compromise the election through a randomization attack.
Benchmarking Multivariate Time Series Classification Algorithms
Venue: arXiv cs.LG 2023
Year: 2023

Time Series Classification (TSC) involved building predictive models for a discrete target variable from ordered, real valued, attributes. Over recent years, a new set of TSC algorithms have been developed which have made significant improvement over the previous state of the art. The main focus has been on univariate TSC, i.e. the problem where each case has a single series and a class label. In reality, it is more common to encounter multivariate TSC (MTSC) problems where multiple series are associated with a single label. Despite this, much less consideration has been given to MTSC than the univariate case. The UEA archive of 30 MTSC problems released in 2018 has made comparison of algorithms easier. We review recently proposed bespoke MTSC algorithms based on deep learning, shapelets and bag of words approaches. The simplest approach to MTSC is to ensemble univariate classifiers over the multivariate dimensions. We compare the bespoke algorithms to these dimension independent approaches on the 26 of the 30 MTSC archive problems where the data are all of equal length. We demonstrate that the independent ensemble of HIVE-COTE classifiers is the most accurate, but that, unlike with univariate classification, dynamic time warping is still competitive at MTSC.
COMET: Convolutional Dimension Interaction for Collaborative Filtering
Venue: arXiv cs.IR 2023
Year: 2023

Representation learning-based recommendation models play a dominant role among recommendation techniques. However, most of the existing methods assume both historical interactions and embedding dimensions are independent of each other, and thus regrettably ignore the high-order interaction information among historical interactions and embedding dimensions. In this paper, we propose a novel representation learning-based model called COMET (COnvolutional diMEnsion inTeraction), which simultaneously models the high-order interaction patterns among historical interactions and embedding dimensions. To be specific, COMET stacks the embeddings of historical interactions horizontally at first, which results in two "embedding maps". In this way, internal interactions and dimensional interactions can be exploited by convolutional neural networks (CNN) with kernels of different sizes simultaneously. A fully-connected multi-layer perceptron (MLP) is then applied to obtain two interaction vectors. Lastly, the representations of users and items are enriched by the learnt interaction vectors, which can further be used to produce the final prediction. Extensive experiments and ablation studies on various public implicit feedback datasets clearly demonstrate the effectiveness and rationality of our proposed method.
Aggregate Analytic Window Query over Spatial Data
Venue: arXiv cs.DB 2023
Year: 2023

Analytic window query is a commonly used query in the relational databases. It answers the aggregations of data over a sliding window. For example, to get the average prices of a stock for each day. However, it is not supported in the spatial databases. Because the spatial data are not in a one-dimension space, there is no straightforward way to extend the original analytic window query to spatial databases. But these queries are useful and meaningful. For example, to find the average number of visits for all the POIs in the circle with a fixed radius for each POI as the centre. In this paper, we define the aggregate analytic window query over spatial data and propose algorithms for grid index and tree-index. We also analyze the complexity of the algorithms to prove they are efficient and practical.
On Feature Relevance Uncertainty: A Monte Carlo Dropout Sampling Approach
Venue: arXiv cs.LG 2023
Year: 2023

Understanding decisions made by neural networks is key for the deployment of intelligent systems in real world applications. However, the opaque decision making process of these systems is a disadvantage where interpretability is essential. Many feature-based explanation techniques have been introduced over the last few years in the field of machine learning to better understand decisions made by neural networks and have become an important component to verify their reasoning capabilities. However, existing methods do not allow statements to be made about the uncertainty regarding a feature's relevance for the prediction. In this paper, we introduce Monte Carlo Relevance Propagation (MCRP) for feature relevance uncertainty estimation. A simple but powerful method based on Monte Carlo estimation of the feature relevance distribution to compute feature relevance uncertainty scores that allow a deeper understanding of a neural network's perception and reasoning.
A Time Leap Challenge for SAT Solving
Venue: arXiv cs.AI 2023
Year: 2023

We compare the impact of hardware advancement and algorithm advancement for SAT solving over the last two decades. In particular, we compare 20-year-old SAT-solvers on new computer hardware with modern SAT-solvers on 20-year-old hardware. Our findings show that the progress on the algorithmic side has at least as much impact as the progress on the hardware side.
Efficiency in Digital Economies -- A Primer on Tokenomics
Venue: arXiv cs.CY 2023
Year: 2023

Cryptographic tokens are a new digital paradigm that can facilitate the establishment of economic incentives in digital ecoystems. Tokens can be leveraged for the coordination, optimization and governance of large networks at scale in a decentralized manner. A key aspect is their programmability, that can reward participants relative to their stage of adoption, according to the value they contribute and the risk they bear. Moreover, this can be done in a transparent and verifiable way, which increases trustworthiness in the emerging systems. This work presents an overview of this new phenomenon and to provide multi-disciplinary arguments on why tokenized ecosystems can drive a huge momentum for positive-sum collaboration in the digital age. We illustrate how certain principles and values that arise from the evolutionary process of digital cooperation can lead to a market economy characterized by economic efficiency of both individuals and the tokenized ecosystem as a whole.
Secure Data Hiding for Contact Tracing
Venue: arXiv cs.CR 2023
Year: 2023

Contact tracing is an effective tool in controlling the spread of infectious diseases such as COVID-19. It involves digital monitoring and recording of physical proximity between people over time with a central and trusted authority, so that when one user reports infection, it is possible to identify all other users who have been in close proximity to that person during a relevant time period in the past and alert them. One way to achieve this involves recording on the server the locations, e.g. by reading and reporting the GPS coordinates of a smartphone, of all users over time. Despite its simplicity, privacy concerns have prevented widespread adoption of this method. Technology that would enable the "hiding" of data could go a long way towards alleviating privacy concerns and enable contact tracing at a very large scale. In this article we describe a general method to hide data. By hiding, we mean that instead of disclosing a data value x, we would disclose an "encoded" version of x, namely E(x), where E(x) is easy to compute but very difficult, from a computational point of view, to invert. We propose a general construction of such a function E and show that it guarantees perfect recall, namely, all individuals who have potentially been exposed to infection are alerted, at the price of an infinitesimal number of false alarms, namely, only a negligible number of individuals who have not actually been exposed will be wrongly informed that they have.
A soft robot that adapts to environments through shape change
Venue: arXiv cs.RO 2023
Year: 2023

Many organisms, including various species of spiders and caterpillars, change their shape to switch gaits and adapt to different environments. Recent technological advances, ranging from stretchable circuits to highly deformable soft robots, have begun to make shape-changing robots a possibility. However, it is currently unclear how and when shape change should occur, and what capabilities could be gained, leading to a wide range of unsolved design and control problems. To begin addressing these questions, here we simulate, design, and build a soft robot that utilizes shape change to achieve locomotion over both a flat and inclined surface. Modeling this robot in simulation, we explore its capabilities in two environments and demonstrate the existence of environment-specific shapes and gaits that successfully transfer to the physical hardware. We found that the shape-changing robot traverses these environments better than an equivalent but non-morphing robot, in simulation and reality.
Loghub: A Large Collection of System Log Datasets for AI-driven Log Analytics
Venue: arXiv cs.SE 2023
Year: 2023

Logs have been widely adopted in software system development and maintenance because of the rich runtime information they record. In recent years, the increase of software size and complexity leads to the rapid growth of the volume of logs. To handle these large volumes of logs efficiently and effectively, a line of research focuses on developing intelligent and automated log analysis techniques. However, only a few of these techniques have reached successful deployments in industry due to the lack of public log datasets and open benchmarking upon them. To fill this significant gap and facilitate more research on AI-driven log analytics, we have collected and released loghub, a large collection of system log datasets. In particular, loghub provides 19 real-world log datasets collected from a wide range of software systems, including distributed systems, supercomputers, operating systems, mobile systems, server applications, and standalone software. In this paper, we summarize the statistics of these datasets, introduce some practical usage scenarios of the loghub datasets, and present our benchmarking results on loghub to benefit the researchers and practitioners in this field. Up to the time of this paper writing, the loghub datasets have been downloaded for roughly 90,000 times in total by hundreds of organizations from both industry and academia. The loghub datasets are available at https://github.com/logpai/loghub.
Modular Subset Sum, Dynamic Strings, and Zero-Sum Sets
Venue: arXiv cs.DS 2023
Year: 2023

The modular subset sum problem consists of deciding, given a modulus $m$, a multiset $S$ of $n$ integers in $0..m-1$, and a target integer $t$, whether there exists a subset of $S$ with elements summing to $t \mod m $, and to report such a set if it exists. We give a simple $O(m \log m)$-time with high probability (w.h.p.) algorithm for the modular subset sum problem. This builds on and improves on a previous $O(m \log^7 m)$ w.h.p. algorithm from Axiotis, Backurs, Jin, Tzamos, and Wu (SODA 19). Our method utilizes the ADT of the dynamic strings structure of Gawrychowski et al. (SODA~18). However, as this structure is rather complicated we present a much simpler alternative which we call the Data Dependent Tree. As an application, we consider the computational version of a fundamental theorem in zero-sum Ramsey theory. The Erdős-Ginzburg-Ziv Theorem states that a multiset of $2n - 1$ integers always contains a subset of cardinality exactly $n$ whose values sum to a multiple of $n$. We give an algorithm for finding such a subset in time $O(n \log n)$ w.h.p. which improves on an $O(n^2)$ algorithm due to Del Lungo, Marini, and Mori (Disc. Math. 09).
Beyond Fixed Grid: Learning Geometric Image Representation with a Deformable Grid
Venue: arXiv cs.CV 2023
Year: 2023

In modern computer vision, images are typically represented as a fixed uniform grid with some stride and processed via a deep convolutional neural network. We argue that deforming the grid to better align with the high-frequency image content is a more effective strategy. We introduce \emph{Deformable Grid} DefGrid, a learnable neural network module that predicts location offsets of vertices of a 2-dimensional triangular grid, such that the edges of the deformed grid align with image boundaries. We showcase our DefGrid in a variety of use cases, i.e., by inserting it as a module at various levels of processing. We utilize DefGrid as an end-to-end \emph{learnable geometric downsampling} layer that replaces standard pooling methods for reducing feature resolution when feeding images into a deep CNN. We show significantly improved results at the same grid resolution compared to using CNNs on uniform grids for the task of semantic segmentation. We also utilize DefGrid at the output layers for the task of object mask annotation, and show that reasoning about object boundaries on our predicted polygonal grid leads to more accurate results over existing pixel-wise and curve-based approaches. We finally showcase DefGrid as a standalone module for unsupervised image partitioning, showing superior performance over existing approaches. Project website: http://www.cs.toronto.edu/~jungao/def-grid
A Survey on Reinforcement Learning for Combinatorial Optimization
Venue: arXiv cs.LG 2023
Year: 2023

This paper gives a detailed review of reinforcement learning (RL) in combinatorial optimization, introduces the history of combinatorial optimization starting in the 1950s, and compares it with the RL algorithms of recent years. This paper explicitly looks at a famous combinatorial problem-traveling salesperson problem (TSP). It compares the approach of modern RL algorithms for the TSP with an approach published in the 1970s. By comparing the similarities and variances between these methodologies, the paper demonstrates how RL algorithms are optimized due to the evolution of machine learning techniques and computing power. The paper then briefly introduces the deep learning approach to the TSP named deep RL, which is an extension of the traditional mathematical framework. In deep RL, attention and feature encoding mechanisms are introduced to generate near-optimal solutions. The survey shows that integrating the deep learning mechanism, such as attention with RL, can effectively approximate the TSP. The paper also argues that deep learning could be a generic approach that can be integrated with any traditional RL algorithm to enhance the outcomes of the TSP.
Predicting Relationship Labels and Individual Personality Traits from Telecommunication History in Social Networks using Hawkes Processes
Venue: arXiv cs.CY 2023
Year: 2023

Mobile phones contain a wealth of private information, so we try to keep them secure. We provide large-scale evidence that the psychological profiles of individuals and their relations with their peers can be predicted from seemingly anonymous communication traces -- calling and texting logs that service providers routinely collect. Based on two extensive longitudinal studies containing more than 900 college students, we use point process modeling to describe communication patterns. We automatically predict the peer relationship type and temporal dynamics, and assess user personality based on the modeling. For some personality traits, the results are comparable to the gold-standard performances obtained from survey self-report data. Findings illustrate how information usually residing outside the control of individuals can be used to reconstruct sensitive information.