OpenRaiser/Intern-Atlas huggingface dataset:
Computational Model for Parsing Expression Grammars
Venue: arXiv cs.FL 2024
Year: 2024

We present a computational model for Parsing Expression Grammars (PEGs). The predecessor of PEGs top-down parsing languages (TDPLs) were discovered by A. Birman and J. Ullman in the 1960-s, B. Ford showed in 2004 that both formalisms recognize the same class named Parsing Expression Languages (PELs). A. Birman and J. Ullman established such important properties like TDPLs generate any DCFL and some non-context-free languages like $a^nb^nc^n$, a linear-time parsing algorithm was constructed as well. But since this parsing algorithm was impractical in the 60-s TDPLs were abandoned and then upgraded by B. Ford to PEGs, so the parsing algorithm was improved (from the practical point of view) as well. Now PEGs are actively used in compilers (eg., Python replaced LL(1)-parser with a PEG one) so as for text processing as well. In this paper, we present a computational model for PEG, obtain structural properties of PELs, namely proof that PELs contain Boolean closure of regular closure of DCFLs and PELs are closed over left concatenation with regular closure of DCFLs. We present an extension of the PELs class based on the extension of our computational model. Our model is an upgrade of deterministic pushdown automata (DPDA) such that during the pop of a symbol it is allowed to return the head to the position of the push of the symbol. We provide a linear-time simulation algorithm for the 2-way version of this model, which is similar to the famous S. Cook linear-time simulation algorithm of 2-way DPDA.
Efficient Graph Similarity Computation with Alignment Regularization
Venue: arXiv cs.LG 2024
Year: 2024

We consider the graph similarity computation (GSC) task based on graph edit distance (GED) estimation. State-of-the-art methods treat GSC as a learning-based prediction task using Graph Neural Networks (GNNs). To capture fine-grained interactions between pair-wise graphs, these methods mostly contain a node-level matching module in the end-to-end learning pipeline, which causes high computational costs in both the training and inference stages. We show that the expensive node-to-node matching module is not necessary for GSC, and high-quality learning can be attained with a simple yet powerful regularization technique, which we call the Alignment Regularization (AReg). In the training stage, the AReg term imposes a node-graph correspondence constraint on the GNN encoder. In the inference stage, the graph-level representations learned by the GNN encoder are directly used to compute the similarity score without using AReg again to speed up inference. We further propose a multi-scale GED discriminator to enhance the expressive ability of the learned representations. Extensive experiments on real-world datasets demonstrate the effectiveness, efficiency and transferability of our approach.
Skip and Skip: Segmenting Medical Images with Prompts
Venue: arXiv cs.CV 2024
Year: 2024

Most medical image lesion segmentation methods rely on hand-crafted accurate annotations of the original image for supervised learning. Recently, a series of weakly supervised or unsupervised methods have been proposed to reduce the dependence on pixel-level annotations. However, these methods are essentially based on pixel-level annotation, ignoring the image-level diagnostic results of the current massive medical images. In this paper, we propose a dual U-shaped two-stage framework that utilizes image-level labels to prompt the segmentation. In the first stage, we pre-train a classification network with image-level labels, which is used to obtain the hierarchical pyramid features and guide the learning of downstream branches. In the second stage, we feed the hierarchical features obtained from the classification branch into the downstream branch through short-skip and long-skip and get the lesion masks under the supervised learning of pixel-level labels. Experiments show that our framework achieves better results than networks simply using pixel-level annotations.
Colorful Priority $k$-Supplier
Venue: arXiv cs.DS 2024
Year: 2024

In the Priority $k$-Supplier problem the input consists of a metric space $(F \cup C, d)$ over set of facilities $F$ and a set of clients $C$, an integer $k > 0$, and a non-negative radius $r_v$ for each client $v \in C$. The goal is to select $k$ facilities $S \subseteq F$ to minimize $\max_{v \in C} \frac{d(v,S)}{r_v}$ where $d(v,S)$ is the distance of $v$ to the closes facility in $S$. This problem generalizes the well-studied $k$-Center and $k$-Supplier problems, and admits a $3$-approximation [Plesník, 1987, Bajpai et al., 2022. In this paper we consider two outlier versions. The Priority $k$-Supplier with Outliers problem [Bajpai et al., 2022] allows a specified number of outliers to be uncovered, and the Priority Colorful $k$-Supplier problem is a further generalization where clients are partitioned into $c$ colors and each color class allows a specified number of outliers. These problems are partly motivated by recent interest in fairness in clustering and other optimization problems involving algorithmic decision making. We build upon the work of [Bajpai et al., 2022] and improve their $9$-approximation Priority $k$-Supplier with Outliers problem to a $1+3\sqrt{3}\approx 6.196$-approximation. For the Priority Colorful $k$-Supplier problem, we present the first set of approximation algorithms. For the general case with $c$ colors, we achieve a $17$-pseudo-approximation using $k+2c-1$ centers. For the setting of $c=2$, we obtain a $7$-approximation in random polynomial time, and a $2+\sqrt{5}\approx 4.236$-pseudo-approximation using $k+1$ centers.
A Study on Shared Objects in Sui Smart Contracts
Venue: arXiv cs.DC 2024
Year: 2024

In many smart contract architectures, every contract or object is mutably shared by default. The Sui smart contract platform bears the unique feature of distinguishing between shared and owned objects. While transactions operating on shared objects require consensus to sequence reads and writes, those involving only owned objects are independent and may bypass consensus; thus, the latter are less prone to this throughput bottleneck. However, it may not always be possible or desirable to avoid using shared objects. This article aims at identifying and investigating decentralized applications that require shared objects. Utilizing the Sui Rust SDK to query programmable transaction blocks, we analyze the frequency of transactions involving shared objects, shared resource contention levels, and most "popular" applications that contain shared objects. The presented results are reproducible and show the extensive usage of shared objects in Sui, low contention levels, and moderate dependency among shared objects in atomic transactions. This novel study of shared object use cases in a relatively new smart contract platform is important for improving the efficiency of such object-based architectures. This work is relevant for smart contract platform designers and smart contract developers.
Real-Time Hand Gesture Recognition: Integrating Skeleton-Based Data Fusion and Multi-Stream CNN
Venue: arXiv cs.CV 2024
Year: 2024

Hand Gesture Recognition (HGR) enables intuitive human-computer interactions in various real-world contexts. However, existing frameworks often struggle to meet the real-time requirements essential for practical HGR applications. This study introduces a robust, skeleton-based framework for dynamic HGR that simplifies the recognition of dynamic hand gestures into a static image classification task, effectively reducing both hardware and computational demands. Our framework utilizes a data-level fusion technique to encode 3D skeleton data from dynamic gestures into static RGB spatiotemporal images. It incorporates a specialized end-to-end Ensemble Tuner (e2eET) Multi-Stream CNN architecture that optimizes the semantic connections between data representations while minimizing computational needs. Tested across five benchmark datasets (SHREC'17, DHG-14/28, FPHA, LMDHG, and CNR), the framework showed competitive performance with the state-of-the-art. Its capability to support real-time HGR applications was also demonstrated through deployment on standard consumer PC hardware, showcasing low latency and minimal resource usage in real-world settings. The successful deployment of this framework underscores its potential to enhance real-time applications in fields such as virtual/augmented reality, ambient intelligence, and assistive technologies, providing a scalable and efficient solution for dynamic gesture recognition.
MedOdyssey: A Medical Domain Benchmark for Long Context Evaluation Up to 200K Tokens
Venue: arXiv cs.CL 2024
Year: 2024

Numerous advanced Large Language Models (LLMs) now support context lengths up to 128K, and some extend to 200K. Some benchmarks in the generic domain have also followed up on evaluating long-context capabilities. In the medical domain, tasks are distinctive due to the unique contexts and need for domain expertise, necessitating further evaluation. However, despite the frequent presence of long texts in medical scenarios, evaluation benchmarks of long-context capabilities for LLMs in this field are still rare. In this paper, we propose MedOdyssey, the first medical long-context benchmark with seven length levels ranging from 4K to 200K tokens. MedOdyssey consists of two primary components: the medical-context "needles in a haystack" task and a series of tasks specific to medical applications, together comprising 10 datasets. The first component includes challenges such as counter-intuitive reasoning and novel (unknown) facts injection to mitigate knowledge leakage and data contamination of LLMs. The second component confronts the challenge of requiring professional medical expertise. Especially, we design the ``Maximum Identical Context'' principle to improve fairness by guaranteeing that different LLMs observe as many identical contexts as possible. Our experiment evaluates advanced proprietary and open-source LLMs tailored for processing long contexts and presents detailed performance analyses. This highlights that LLMs still face challenges and need for further research in this area. Our code and data are released in the repository: \url{https://github.com/JOHNNY-fans/MedOdyssey.}
New Upper Bounds for Noisy Permutation Channels
Venue: arXiv cs.IT 2024
Year: 2024

The noisy permutation channel is a useful abstraction introduced by Makur for point-to-point communication networks and biological storage. While the asymptotic capacity results exist for this model, the characterization of the second-order asymptotics is not available. Therefore, we analyze the converse bounds for the noisy permutation channel in the finite blocklength regime. To do this, we present a modified minimax meta-converse for noisy permutation channels by symbol relaxation. To derive the second-order asymptotics of the converse bound, we propose a way to use divergence covering in analysis. It enables the observation of the second-order asymptotics and the strong converse via Berry-Esseen type bounds. These two conclusions hold for noisy permutation channels with strictly positive matrices (entry-wise). In addition, we obtain computable bounds for the noisy permutation channel with the binary symmetric channel (BSC), including the original computable converse bound based on the modified minimax meta-converse, the asymptotic expansion derived from our subset covering technique, and the ε-capacity result. We find that a smaller crossover probability provides a higher upper bound for a fixed finite blocklength, although the ε-capacity is agnostic to the BSC parameter. Finally, numerical results show that the normal approximation shows remarkable precision, and our new converse bound is stronger than previous bounds.
Effects of non-uniform number of actions by Hawkes process on spatial cooperation
Venue: arXiv cs.MA 2024
Year: 2024

The emergence of cooperative behavior, despite natural selection favoring rational self-interest, presents a significant evolutionary puzzle. Evolutionary game theory elucidates why cooperative behavior can be advantageous for survival. However, the impact of non-uniformity in the frequency of actions, particularly when actions are altered in the short term, has received little scholarly attention. To demonstrate the relationship between the non-uniformity in the frequency of actions and the evolution of cooperation, we conducted multi-agent simulations of evolutionary games. In our model, each agent performs actions in a chain-reaction, resulting in a non-uniform distribution of the number of actions. To achieve a variety of non-uniform action frequency, we introduced two types of chain-reaction rules: one where an agent's actions trigger subsequent actions, and another where an agent's actions depend on the actions of others. Our results revealed that cooperation evolves more effectively in scenarios with even slight non-uniformity in action frequency compared to completely uniform cases. In addition, scenarios where agents' actions are primarily triggered by their own previous actions more effectively support cooperation, whereas those triggered by others' actions are less effective. This implies that a few highly active individuals contribute positively to cooperation, while the tendency to follow others' actions can hinder it.
Online detection and infographic explanation of spam reviews with data drift adaptation
Venue: arXiv cs.LG 2024
Year: 2024

Spam reviews are a pervasive problem on online platforms due to its significant impact on reputation. However, research into spam detection in data streams is scarce. Another concern lies in their need for transparency. Consequently, this paper addresses those problems by proposing an online solution for identifying and explaining spam reviews, incorporating data drift adaptation. It integrates (i) incremental profiling, (ii) data drift detection & adaptation, and (iii) identification of spam reviews employing Machine Learning. The explainable mechanism displays a visual and textual prediction explanation in a dashboard. The best results obtained reached up to 87 % spam F-measure.
Tempora-Fusion: Time-Lock Puzzle with Efficient Verifiable Homomorphic Linear Combination
Venue: arXiv cs.CR 2024
Year: 2024

To securely transmit sensitive information into the future, Time-Lock Puzzles (TLPs) have been developed. Their applications include scheduled payments, timed commitments, e-voting, and sealed-bid auctions. Homomorphic TLP is a key variant of TLP that enables computation on puzzles from different clients. This allows a solver/server to tackle only a single puzzle encoding the computation's result. However, existing homomorphic TLPs lack support for verifying the correctness of the computation results. We address this limitation by introducing Tempora-Fusion, a TLP that allows a server to perform homomorphic linear combinations of puzzles from different clients while ensuring verification of computation correctness. This scheme avoids asymmetric-key cryptography for verification, thus paving the way for efficient implementations. We discuss our scheme's application in various domains, such as federated learning, scheduled payments in online banking, and e-voting.
KnobTree: Intelligent Database Parameter Configuration via Explainable Reinforcement Learning
Venue: arXiv cs.AI 2024
Year: 2024

Databases are fundamental to contemporary information systems, yet traditional rule-based configuration methods struggle to manage the complexity of real-world applications with hundreds of tunable parameters. Deep reinforcement learning (DRL), which combines perception and decision-making, presents a potential solution for intelligent database configuration tuning. However, due to black-box property of RL-based method, the generated database tuning strategies still face the urgent problem of lack explainability. Besides, the redundant parameters in large scale database always make the strategy learning become unstable. This paper proposes KnobTree, an interpertable framework designed for the optimization of database parameter configuration. In this framework, an interpertable database tuning algorithm based on RL-based differentatial tree is proposed, which building a transparent tree-based model to generate explainable database tuning strategies. To address the problem of large-scale parameters, We also introduce a explainable method for parameter importance assessment, by utilizing Shapley Values to identify parameters that have significant impacts on database performance. Experiments conducted on MySQL and Gbase8s databases have verified exceptional transparency and interpretability of the KnobTree model. The good property makes generated strategies can offer practical guidance to algorithm designers and database administrators. Moreover, our approach also slightly outperforms the existing RL-based tuning algorithms in aspects such as throughput, latency, and processing time.
Balancing The Perception of Cheating Detection, Privacy and Fairness: A Mixed-Methods Study of Visual Data Obfuscation in Remote Proctoring
Venue: arXiv cs.HC 2024
Year: 2024

Remote proctoring technology, a cheating-preventive measure, often raises privacy and fairness concerns that may affect test-takers' experiences and the validity of test results. Our study explores how selectively obfuscating information in video recordings can protect test-takers' privacy while ensuring effective and fair cheating detection. Interviews with experts (N=9) identified four key video regions indicative of potential cheating behaviors: the test-taker's face, body, background and the presence of individuals in the background. Experts recommended specific obfuscation methods for each region based on privacy significance and cheating behavior frequency, ranging from conventional blurring to advanced methods like replacement with deepfake, 3D avatars and silhouetting. We then conducted a vignette experiment with potential test-takers (N=259, non-experts) to evaluate their perceptions of cheating detection, visual privacy and fairness, using descriptions and examples of still images for each expert-recommended combination of video regions and obfuscation methods. Our results indicate that the effectiveness of obfuscation methods varies by region. Tailoring remote proctoring with region-specific advanced obfuscation methods can improve the perceptions of privacy and fairness compared to the conventional methods, though it may decrease perceived information sufficiency for detecting cheating. However, non-experts preferred conventional blurring for videos they were more willing to share, highlighting a gap between the perceived effectiveness of the advanced obfuscation methods and their practical acceptance. This study contributes to the field of user-centered privacy by suggesting promising directions to address current remote proctoring challenges and guiding future research.
Modeling and Analysis of Application Interference on Dragonfly+
Venue: arXiv cs.NI 2024
Year: 2024

Dragonfly class of networks are considered as promising interconnects for next-generation supercomputers. While Dragonfly+ networks offer more path diversity than the original Dragonfly design, they are still prone to performance variability due to their hierarchical architecture and resource sharing design. Event-driven network simulators are indispensable tools for navigating complex system design. In this study, we quantitatively evaluate a variety of application communication interactions on a 3,456-node Dragonfly+ system by using the CODES toolkit. This study looks at the impact of communication interference from a user's perspective. Specifically, for a given application submitted by a user, we examine how this application will behave with the existing workload running in the system under different job placement policies. Our simulation study considers hundreds of experiment configurations including four target applications with representative communication patterns under a variety of network traffic conditions. Our study shows that intra-job interference can cause severe performance degradation for communication-intensive applications. Inter-job interference can generally be reduced for applications with one-to-one or one-to-many communication patterns through job isolation. Application with one-to-all communication pattern is resilient to network interference.
Voxel-Based Point Cloud Localization for Smart Spaces Management
Venue: arXiv cs.RO 2024
Year: 2024

This paper proposes a voxel-based approach for creating a digital twin of an urban environment that is capable of efficiently managing smart spaces. The paper explains the registration and localization procedure of the point cloud dataset, which uses the KISS ICP for scan point cloud combination and the RANSAC method for the initial alignment of the combined point cloud. The mobile mapping point cloud using Riegl VMX-250 serves as the reference map, and Velodyne scans are used for localization purposes. The point-to-plane iterative closest-point method is then employed to refine the alignment. The paper evaluates the efficacy of the proposed method by calculating the errors between the estimated and ground truth positions. The results indicate that the voxel-based approach is capable of accurately estimating the position of the sensor platform, which are applicable for various use cases. A specific use case in the context is smart parking space management, which is described and initial visualization results are shown.
Investigating the impact of 2D gesture representation on co-speech gesture generation
Venue: arXiv cs.AI 2024
Year: 2024

Co-speech gestures play a crucial role in the interactions between humans and embodied conversational agents (ECA). Recent deep learning methods enable the generation of realistic, natural co-speech gestures synchronized with speech, but such approaches require large amounts of training data. "In-the-wild" datasets, which compile videos from sources such as YouTube through human pose detection models, offer a solution by providing 2D skeleton sequences that are paired with speech. Concurrently, innovative lifting models have emerged, capable of transforming these 2D pose sequences into their 3D counterparts, leading to large and diverse datasets of 3D gestures. However, the derived 3D pose estimation is essentially a pseudo-ground truth, with the actual ground truth being the 2D motion data. This distinction raises questions about the impact of gesture representation dimensionality on the quality of generated motions, a topic that, to our knowledge, remains largely unexplored. In this work, we evaluate the impact of the dimensionality of the training data, 2D or 3D joint coordinates, on the performance of a multimodal speech-to-gesture deep generative model. We use a lifting model to convert 2D-generated sequences of body pose to 3D. Then, we compare the sequence of gestures generated directly in 3D to the gestures generated in 2D and lifted to 3D as post-processing.