OpenRaiser/Intern-Atlas huggingface dataset:
A Survey of Security and Privacy Issues in V2X Communication Systems
Venue: arXiv cs.CR 2022
Year: 2022

Vehicle-to-Everything (V2X) communication is receiving growing attention from industry and academia as multiple pilot projects explore its capabilities and feasibility. With about 50\% of global road vehicle exports coming from the European Union (EU), and within the context of EU legislation around security and data protection, V2X initiatives must consider security and privacy aspects across the system stack, in addition to road safety. Contrary to this principle, our survey of relevant standards, research outputs, and EU pilot projects indicates otherwise; we identify multiple security and privacy related shortcomings and inconsistencies across the standards. We conduct a root cause analysis of the reasons and difficulties associated with these gaps, and categorize the identified security and privacy issues relative to these root causes. As a result, our comprehensive analysis sheds lights on a number of areas that require improvements in the standards, which are not explicitly identified in related work. Our analysis fills gaps left by other related surveys, which are focused on specific technical areas but not necessarily point out underlying root issues in standard specifications. We bring forward recommendations to address these gaps for the overall improvement of security and safety in vehicular communication.
TRUST: An Accurate and End-to-End Table structure Recognizer Using Splitting-based Transformers
Venue: arXiv cs.CV 2022
Year: 2022

Table structure recognition is a crucial part of document image analysis domain. Its difficulty lies in the need to parse the physical coordinates and logical indices of each cell at the same time. However, the existing methods are difficult to achieve both these goals, especially when the table splitting lines are blurred or tilted. In this paper, we propose an accurate and end-to-end transformer-based table structure recognition method, referred to as TRUST. Transformers are suitable for table structure recognition because of their global computations, perfect memory, and parallel computation. By introducing novel Transformer-based Query-based Splitting Module and Vertex-based Merging Module, the table structure recognition problem is decoupled into two joint optimization sub-tasks: multi-oriented table row/column splitting and table grid merging. The Query-based Splitting Module learns strong context information from long dependencies via Transformer networks, accurately predicts the multi-oriented table row/column separators, and obtains the basic grids of the table accordingly. The Vertex-based Merging Module is capable of aggregating local contextual information between adjacent basic grids, providing the ability to merge basic girds that belong to the same spanning cell accurately. We conduct experiments on several popular benchmarks including PubTabNet and SynthTable, our method achieves new state-of-the-art results. In particular, TRUST runs at 10 FPS on PubTabNet, surpassing the previous methods by a large margin.
Deep Reinforcement Learning for Uplink Multi-Carrier Non-Orthogonal Multiple Access Resource Allocation Using Buffer State Information
Venue: arXiv cs.NI 2022
Year: 2022

For orthogonal multiple access (OMA) systems, the number of served user equipments (UEs) is limited to the number of available orthogonal resources. On the other hand, non-orthogonal multiple access (NOMA) schemes allow multiple UEs to use the same orthogonal resource. This extra degree of freedom introduces new challenges for resource allocation. Buffer state information (BSI), like the size and age of packets waiting for transmission, can be used to improve scheduling in OMA systems. In this paper, we investigate the impact of BSI on the performance of a centralized scheduler in an uplink multi-carrier NOMA scenario with UEs having various data rate and latency requirements. To handle the large combinatorial space of allocating UEs to the resources, we propose a novel scheduler based on actor-critic reinforcement learning incorporating BSI. Training and evaluation are carried out using Nokia's "wireless suite". We propose various novel techniques to both stabilize and speed up training. The proposed scheduler outperforms benchmark schedulers.
The Lothbrok approach for SPARQL Query Optimization over Decentralized Knowledge Graphs
Venue: arXiv cs.DB 2022
Year: 2022

While the Web of Data in principle offers access to a wide range of interlinked data, the architecture of the Semantic Web today relies mostly on the data providers to maintain access to their data through SPARQL endpoints. Several studies, however, have shown that such endpoints often experience downtime, meaning that the data they maintain becomes inaccessible. While decentralized systems based on Peer-to-Peer (P2P) technology have previously shown to increase the availability of knowledge graphs, even when a large proportion of the nodes fail, processing queries in such a setup can be an expensive task since data necessary to answer a single query might be distributed over multiple nodes. In this paper, we therefore propose an approach to optimizing SPARQL queries over decentralized knowledge graphs, called Lothbrok. While there are potentially many aspects to consider when optimizing such queries, we focus on three aspects: cardinality estimation, locality awareness, and data fragmentation. We empirically show that Lothbrok is able to achieve significantly faster query processing performance compared to the state of the art when processing challenging queries as well as when the network is under high load.
Reversible Computations of One-Way Counter Automata
Venue: arXiv cs.FL 2022
Year: 2022

Deterministic one-way time-bounded multi-counter automata are studied with respect to their ability to perform reversible computations, which means that the automata are also backward deterministic and, thus, are able to uniquely step the computation back and forth. We study the computational capacity of such devices and obtain separation results between irreversible and reversible k-counter automata for superpolynomial time. For exponential time we obtain moreover an infinite and tight hierarchy with respect to the number of counters. This hierarchy is shown with Kolmogorov complexity and incompressibility arguments. In this way, on passing we can prove this hierarchy also for ordinary counter automata. This improves the known hierarchy for ordinary counter automata in the sense that here we consider a weaker acceptance condition. Then, it turns out that k+1 reversible counters are not better than k ordinary counters and vice versa. Finally, almost all usually studied decidability questions turn out to be undecidable and not even semidecidable for reversible multi-counter automata, if at least two counters are provided.
Combinatorial Algorithms for Subsequence Matching: A Survey
Venue: arXiv cs.FL 2022
Year: 2022

In this paper we provide an overview of a series of recent results regarding algorithms for searching for subsequences in words or for the analysis of the sets of subsequences occurring in a word.
Energy Efficient Design in IRS-Assisted UAV Data Collection System under Malicious Jamming
Venue: arXiv cs.IT 2022
Year: 2022

In this paper, we study an unmanned aerial vehicle (UAV) enabled data collection system, where an intelligent reflecting surface (IRS) is deployed to assist in the communication from a cluster of Internet-of-Things (IoT) devices to a UAV in the presence of a jammer. We aim to improve the energy efficiency (EE) via the joint design of UAV trajectory, IRS passive beamforming, device power allocation, and communication scheduling. However, the formulated non-linear fractional programming problem is challenging to solve due to its non-convexity and coupled variables. To overcome the difficulty, we propose an alternating optimization based algorithm to solve it sub-optimally by leveraging Dinkelbach's algorithm, successive convex approximation (SCA) technique, and block coordinate descent (BCD) method. Extensive simulation results show that the proposed design can significantly improve the anti-jamming performance. In particular, for the remote jammer case, the proposed design can largely shorten the flight path and thus decrease the energy consumption via the signal enhancement; while for the local jammer case, which is deemed highly challenging in conventional systems without IRS since the retreating away strategy becomes ineffective, our proposed design even achieves a higher performance gain owing to the efficient jamming signal mitigation.
Ant Colony Optimization for Mining Gradual Patterns
Venue: arXiv cs.DB 2022
Year: 2022

Gradual pattern extraction is a field in (KDD) Knowledge Discovery in Databases that maps correlations between attributes of a data set as gradual dependencies. A gradual dependency may take a form of "the more Attribute K , the less Attribute L". In this paper, we propose an ant colony optimization technique that uses a probabilistic approach to learn and extract frequent gradual patterns. Through computational experiments on real-world data sets, we compared the performance of our ant-based algorithm to an existing gradual item set extraction algorithm and we found out that our algorithm outperforms the later especially when dealing with large data sets.
Reducing the Complexity of the Sensor-Target Coverage Problem Through Point and Set Classification
Venue: arXiv cs.CG 2022
Year: 2022

The problem of covering random points in a plane with sets of a given shape has several practical applications in communications and operations research. One especially prominent application is the coverage of randomly-located points of interest by randomly-located sensors in a wireless sensor network. In this article we consider the situation of a large area containing randomly placed points (representing points of interest), as well a number of randomly-placed disks of equal radius in the same region (representing individual sensors' coverage areas). The problem of finding the smallest possible set of disks that cover the given points is known to be NP-complete. We show that the computational complexity may be reduced by classifying the disks into several definite classes that can be characterized as necessary, excludable, or indeterminate. The problem may then be reduced to considering only the indeterminate sets and the points that they cover. In addition, indeterminate sets and the points that they cover may be divided into disjoint ``islands'' that can be solved separately. Hence the actual complexity is determined by the number of points and sets in the largest island. We run a number of simulations to show how the proportion of sets and points of various types depend on two basic scale-invariant parameters related to point and set density. We show that enormous reductions in complexity can be achieved even in situations where point and set density is relatively high.
Data Analysis in Social Networks for Agribusiness -- A Systematic Mapping Study
Venue: arXiv cs.SI 2022
Year: 2022

The ability of companies to react to changes imposed by the market is related to information acquisition and knowledge generation. Big data technologies, crowdsourcing, and Online Social Network (OSN) are used for knowledge generation. These technologies assumed a significant position in agribusiness. This work investigates how social network analysis can promote agribusiness to provide a basis for future applications and evaluations. We adopted a hybrid systematic mapping to conduct the investigation. Two hundred twenty-three works that propose solutions for agribusiness were found and categorized. Results showed the most used techniques, OSNs, and revealed an increase in the number of studies in this area. The information obtained indicates how social media monitoring can complement traditional methods for decision-making on the management and regulation of agricultural systems. However, agribusiness still lacks more studies using data analysis tools on social networks. Based on our results, we discuss some challenges and research directions.
A case study of the profit-maximizing multi-vehicle pickup and delivery selection problem for the road networks with the integratable nodes
Venue: arXiv cs.DM 2022
Year: 2022

This paper is a study of an application-based model in profit-maximizing multi-vehicle pickup and delivery selection problem (PPDSP). The graph-theoretic model proposed by existing studies of PPDSP is based on transport requests to define the corresponding nodes (i.e., each request corresponds to a pickup node and a delivery node). In practice, however, there are probably multiple requests coming from or going to an identical location. Considering the road networks with the integratable nodes as above, we define a new model based on the integrated nodes for the corresponding PPDSP and propose a novel mixed-integer formulation. In comparative experiments with the existing formulation, as the number of integratable nodes increases, our method has a clear advantage in terms of the number of variables as well as the number of constraints required in the generated instances, and the accuracy of the optimized solution obtained within a given time.
Hierarchical Local-Global Transformer for Temporal Sentence Grounding
Venue: arXiv cs.MM 2022
Year: 2022

This paper studies the multimedia problem of temporal sentence grounding (TSG), which aims to accurately determine the specific video segment in an untrimmed video according to a given sentence query. Traditional TSG methods mainly follow the top-down or bottom-up framework and are not end-to-end. They severely rely on time-consuming post-processing to refine the grounding results. Recently, some transformer-based approaches are proposed to efficiently and effectively model the fine-grained semantic alignment between video and query. Although these methods achieve significant performance to some extent, they equally take frames of the video and words of the query as transformer input for correlating, failing to capture their different levels of granularity with distinct semantics. To address this issue, in this paper, we propose a novel Hierarchical Local-Global Transformer (HLGT) to leverage this hierarchy information and model the interactions between different levels of granularity and different modalities for learning more fine-grained multi-modal representations. Specifically, we first split the video and query into individual clips and phrases to learn their local context (adjacent dependency) and global correlation (long-range dependency) via a temporal transformer. Then, a global-local transformer is introduced to learn the interactions between the local-level and global-level semantics for better multi-modal reasoning. Besides, we develop a new cross-modal cycle-consistency loss to enforce interaction between two modalities and encourage the semantic alignment between them. Finally, we design a brand-new cross-modal parallel transformer decoder to integrate the encoded visual and textual features for final grounding. Extensive experiments on three challenging datasets show that our proposed HLGT achieves a new state-of-the-art performance.
GRILLBot: An Assistant for Real-World Tasks with Neural Semantic Parsing and Graph-Based Representations
Venue: arXiv cs.CL 2022
Year: 2022

GRILLBot is the winning system in the 2022 Alexa Prize TaskBot Challenge, moving towards the next generation of multimodal task assistants. It is a voice assistant to guide users through complex real-world tasks in the domains of cooking and home improvement. These are long-running and complex tasks that require flexible adjustment and adaptation. The demo highlights the core aspects, including a novel Neural Decision Parser for contextualized semantic parsing, a new "TaskGraph" state representation that supports conditional execution, knowledge-grounded chit-chat, and automatic enrichment of tasks with images and videos.
Protecting Critical Inter-Domain Communication through Flyover Reservations
Venue: arXiv cs.NI 2022
Year: 2022

To protect against naturally occurring or adversely induced congestion in the Internet, we propose the concept of flyover reservations, a fundamentally new approach for addressing the availability demands of critical low-volume applications. In contrast to path-based reservation systems, flyovers are fine-grained "hop-based" bandwidth reservations on the level of individual autonomous systems. We demonstrate the scalability of this approach experimentally through simulations on large graphs. Moreover, we introduce Helia, a protocol for secure flyover reservation setup and data transmission. We evaluate Helia's performance based on an implementation in DPDK, demonstrating authentication and forwarding of reservation traffic at 160 Gbps. Our security analysis shows that Helia can resist a large variety of powerful attacks against reservation admission and traffic forwarding. Despite its simplicity, Helia outperforms current state-of-the-art reservation systems in many key metrics.
An Anonymous Overlay Routing Protocol for Uplink-Intensive Applications
Venue: arXiv cs.NI 2022
Year: 2022

Sender anonymity in network communication is an important problem, widely addressed in the literature. Mixnets, combined with onion routing, represent certainly the most concrete and effective approach achieving the above goal. In general, the drawback of these approaches is that anonymity has a price in terms of traffic overhead and latency. On the Internet, to achieve scalability and not to require relevant infrastructure and network-protocol changes, only P2P overlay protocols can be adopted. Among these, the most representative proposal is certainly Tarzan, which is designed to obtain strong anonymity still preserving low-latency applications. In recent years, we are witnessing a change in Internet traffic. Due to IoT, cloud storage, WSN, M2M, uplink traffic is more and more increasing. An interesting question is whether this new traffic configuration may enable new strategies to improve the effectiveness of Tarzan-like approaches. In this paper, we investigate this problem, by proposing \textit{C-Tarzan}, an anonymous overlay P2P routing protocol. Through a deep experimental analysis, we show that C-Tarzan outperforms Tarzan in the case of uplink-intensive applications.
Membership Inference Attacks by Exploiting Loss Trajectory
Venue: arXiv cs.CR 2022
Year: 2022

Machine learning models are vulnerable to membership inference attacks in which an adversary aims to predict whether or not a particular sample was contained in the target model's training dataset. Existing attack methods have commonly exploited the output information (mostly, losses) solely from the given target model. As a result, in practical scenarios where both the member and non-member samples yield similarly small losses, these methods are naturally unable to differentiate between them. To address this limitation, in this paper, we propose a new attack method, called \system, which can exploit the membership information from the whole training process of the target model for improving the attack performance. To mount the attack in the common black-box setting, we leverage knowledge distillation, and represent the membership information by the losses evaluated on a sequence of intermediate models at different distillation epochs, namely \emph{distilled loss trajectory}, together with the loss from the given target model. Experimental results over different datasets and model architectures demonstrate the great advantage of our attack in terms of different metrics. For example, on CINIC-10, our attack achieves at least 6$\times$ higher true-positive rate at a low false-positive rate of 0.1\% than existing methods. Further analysis demonstrates the general effectiveness of our attack in more strict scenarios.
Reconstruction of a Single String from a Part of its Composition Multiset
Venue: arXiv cs.IT 2022
Year: 2022

Motivated by applications in polymer-based data storage, we study the problem of reconstructing a string from part of its composition multiset. We give a full description of the structure of the strings that cannot be uniquely reconstructed (up to reversal) from their multiset of all of their prefix-suffix compositions. Leveraging this description, we prove that for all $n\ge 6$, there exists a string of length $n$ that cannot be uniquely reconstructed up to reversal. Moreover, for all $n\ge 6$, we explicitly construct the set consisting of all length $n$ strings that can be uniquely reconstructed up to reversal. As a by product, we obtain that any binary string can be constructed using Dyck strings and Catalan-Bertrand strings. For any given string $\bm{s}$, we provide a method to explicitly construct the set of all strings with the same prefix-suffix composition multiset as $\bm{s}$, as well as a formula for the size of this set. As an application, we construct a composition code of maximal size. Furthermore, we construct two classes of composition codes which can respectively correct composition missing errors and mass reducing substitution errors. In addition, we raise two new problems: reconstructing a string from its composition multiset when at most a constant number of substring compositions are lost; reconstructing a string when only given its compositions of substrings of length at most $r$. For each of these setups, we give suitable codes under some conditions.
Connecticut Redistricting Analysis
Venue: arXiv cs.CY 2022
Year: 2022

Connecticut passed their new state House of Representatives district plan on November 18, 2021 and passed their new state Senate district plan on November 23, 2021. Each passed unanimously in their 9-person bipartisan Reapportionment Commission; however, the process has been criticized for legislators controlling the process and for the negotiations that serve to protect incumbents. This paper investigates the extent of incumbent protection in the new Assembly maps while also providing summary data on the new districts. The impact of new districts on incumbents is analyzed through the location of district borders, an ensemble analysis (using MCMC methods) to determine if the protection of incumbents constitutes a statistical outlier, and by investigating changes to competitive districts.
What is missing in deep music generation? A study of repetition and structure in popular music
Venue: arXiv cs.SD 2022
Year: 2022

Structure is one of the most essential aspects of music, and music structure is commonly indicated through repetition. However, the nature of repetition and structure in music is still not well understood, especially in the context of music generation, and much remains to be explored with Music Information Retrieval (MIR) techniques. Analyses of two popular music datasets (Chinese and American) illustrate important music construction principles: (1) structure exists at multiple hierarchical levels, (2) songs use repetition and limited vocabulary so that individual songs do not follow general statistics of song collections, (3) structure interacts with rhythm, melody, harmony, and predictability, and (4) over the course of a song, repetition is not random, but follows a general trend as revealed by cross-entropy. These and other findings offer challenges as well as opportunities for deep-learning music generation and suggest new formal music criteria and evaluation methods. Music from recent music generation systems is analyzed and compared to human-composed music in our datasets, often revealing striking differences from a structural perspective.