OpenRaiser/Intern-Atlas huggingface dataset:
GriT-DBSCAN: A Spatial Clustering Algorithm for Very Large Databases
Venue: arXiv cs.DB 2022
Year: 2022

DBSCAN is a fundamental spatial clustering algorithm with numerous practical applications. However, a bottleneck of the algorithm is in the worst case, the run time complexity is $O(n^2)$. To address this limitation, we propose a new grid-based algorithm for exact DBSCAN in Euclidean space called GriT-DBSCAN, which is based on the following two techniques. First, we introduce a grid tree to organize the non-empty grids for the purpose of efficient non-empty neighboring grids queries. Second, by utilising the spatial relationships among points, we propose a technique that iteratively prunes unnecessary distance calculations when determining whether the minimum distance between two sets is less than or equal to a certain threshold. We theoretically prove that the complexity of GriT-DBSCAN is linear to the data set size. In addition, we obtain two variants of GriT-DBSCAN by incorporating heuristics, or by combining the second technique with an existing algorithm. Experiments are conducted on both synthetic and real-world data sets to evaluate the efficiency of GriT-DBSCAN and its variants. The results of our analyses show that our algorithms outperform existing algorithms.
Stability of Decentralized Queueing Networks Beyond Complete Bipartite Cases
Venue: arXiv cs.GT 2022
Year: 2022

Gaitonde and Tardos recently studied a model of queueing networks where queues compete for servers and re-send returned packets in future rounds. They quantify the amount of additional processing power that guarantees a decentralized system's stability, both when the queues adapt their strategies from round to round using no-regret learning algorithms, and when they are patient and evaluate the utility of a strategy over long periods of time. In this paper, we generalize Gaitonde and Tardos's model and consider scenarios where not all servers can serve all queues (i.e., the underlying graph is an incomplete bipartite graphs) and, further, when packets need to go through more than one layer of servers before their completions (i.e., when the underlying graph is a DAG). For the bipartite case, we obtain bounds comparable to those by Gaitonde and Tardos, with the factor slightly worse in the patient queueing model. For the more general multi-layer systems, we show that straightforward generalizations of the utility function and servers' priority rules in Gaitonde and Tardos's model may lead to unbounded gaps between centralized and decentralized systems when the queues use no regret strategies. We define a new utility and a service priority rule that are aware of the queue lengths, and show that these suffice to restore the bounded gap between centralized and decentralized systems observed in bipartite graphs.
Vision Transformer Visualization: What Neurons Tell and How Neurons Behave?
Venue: arXiv cs.CV 2022
Year: 2022

Recently vision transformers (ViT) have been applied successfully for various tasks in computer vision. However, important questions such as why they work or how they behave still remain largely unknown. In this paper, we propose an effective visualization technique, to assist us in exposing the information carried in neurons and feature embeddings across the ViT's layers. Our approach departs from the computational process of ViTs with a focus on visualizing the local and global information in input images and the latent feature embeddings at multiple levels. Visualizations at the input and embeddings at level 0 reveal interesting findings such as providing support as to why ViTs are rather generally robust to image occlusions and patch shuffling; or unlike CNNs, level 0 embeddings already carry rich semantic details. Next, we develop a rigorous framework to perform effective visualizations across layers, exposing the effects of ViTs filters and grouping/clustering behaviors to object patches. Finally, we provide comprehensive experiments on real datasets to qualitatively and quantitatively demonstrate the merit of our proposed methods as well as our findings. https://github.com/byM1902/ViT_visualization
A Location-Based Global Authorization Method for Underwater Security
Venue: arXiv cs.CR 2022
Year: 2022

National or international maritime authorities are used to handle requests for licenses for all kinds of marine activities. These licenses constitute authorizations limited in time and space, but there is no technical security service to check for the authorization of a wide range of marine assets. We have noted secure AIS solutions suitable for more or less constantly internet-connected assets such as ships with satellite connections. The additional constraints posed by underwater autonomous assets, namely less power and connectivity, can be mitigated by using symmetric cryptography. We propose a security service that allows the automatized check of asset authorization status based on large symmetric keys. Key generation can take place at a central authority according to the time and space limitations of a license, i.e. timestamped and geocoded. Our solution harnesses the exceptionally large key size of the RC5 cipher and the standardized encoding of geocells in the Open Location Code system. While we developed and described our solution for offshore underwater use, aerial and terrestrial environments could also make use of it if they are similarly bandwidth constrained or want to rely on quantum-resistant and computationally economic symmetric methods.
s-Club Cluster Vertex Deletion on Interval and Well-Partitioned Chordal Graphs
Venue: arXiv cs.DS 2022
Year: 2022

In this paper, we study the computational complexity of \textsc{$s$-Club Cluster Vertex Deletion}. Given a graph, \textsc{$s$-Club Cluster Vertex Deletion ($s$-CVD)} aims to delete the minimum number of vertices from the graph so that each connected component of the resulting graph has a diameter at most $s$. When $s=1$, the corresponding problem is popularly known as \sloppy \textsc{Cluster Vertex Deletion (CVD)}. We provide a faster algorithm for \textsc{$s$-CVD} on \emph{interval graphs}. For each $s\geq 1$, we give an $O(n(n+m))$-time algorithm for \textsc{$s$-CVD} on interval graphs with $n$ vertices and $m$ edges. In the case of $s=1$, our algorithm is a slight improvement over the $O(n^3)$-time algorithm of Cao \etal (Theor. Comput. Sci., 2018) and for $s \geq 2$, it significantly improves the state-of-the-art running time $\left(O\left(n^4\right)\right)$. We also give a polynomial-time algorithm to solve \textsc{CVD} on \emph{well-partitioned chordal graphs}, a graph class introduced by Ahn \etal (\textsc{WG 2020}) as a tool for narrowing down complexity gaps for problems that are hard on chordal graphs, and easy on split graphs. Our algorithm relies on a characterisation of the optimal solution and on solving polynomially many instances of the \textsc{Weighted Bipartite Vertex Cover}. This generalises a result of Cao \etal (Theor. Comput. Sci., 2018) on split graphs. We also show that for any even integer $s\geq 2$, \textsc{$s$-CVD} is NP-hard on well-partitioned chordal graphs.
Mechanical features based object recognition
Venue: arXiv cs.RO 2022
Year: 2022

Current robotic haptic object recognition relies on statistical measures derived from movement dependent interaction signals such as force, vibration or position. Mechanical properties that can be identified from these signals are intrinsic object properties that may yield a more robust object representation. Therefore, this paper proposes an object recognition framework using multiple representative mechanical properties: the coefficient of restitution, stiffness, viscosity and friction coefficient. These mechanical properties are identified in real-time using a dual Kalman filter, then used to classify objects. The proposed framework was tested with a robot identifying 20 objects through haptic exploration. The results demonstrate the technique's effectiveness and efficiency, and that all four mechanical properties are required for best recognition yielding a rate of 98.18 $\pm$ 0.424 %. Clustering with Gaussian mixture models further shows that using these mechanical properties results in superior recognition as compared to using statistical parameters of the interaction signals.
Zero-Rate Thresholds and New Capacity Bounds for List-Decoding and List-Recovery
Venue: arXiv cs.IT 2022
Year: 2022

In this work we consider the list-decodability and list-recoverability of arbitrary $q$-ary codes, for all integer values of $q\geq 2$. A code is called $(p,L)_q$-list-decodable if every radius $pn$ Hamming ball contains less than $L$ codewords; $(p,\ell,L)_q$-list-recoverability is a generalization where we place radius $pn$ Hamming balls on every point of a combinatorial rectangle with side length $\ell$ and again stipulate that there be less than $L$ codewords. Our main contribution is to precisely calculate the maximum value of $p$ for which there exist infinite families of positive rate $(p,\ell,L)_q$-list-recoverable codes, the quantity we call the zero-rate threshold. Denoting this value by $p_*$, we in fact show that codes correcting a $p_*+\varepsilon$ fraction of errors must have size $O_{\varepsilon}(1)$, i.e., independent of $n$. Such a result is typically referred to as a ``Plotkin bound.'' To complement this, a standard random code with expurgation construction shows that there exist positive rate codes correcting a $p_*-\varepsilon$ fraction of errors. We also follow a classical proof template (typically attributed to Elias and Bassalygo) to derive from the zero-rate threshold other tradeoffs between rate and decoding radius for list-decoding and list-recovery. Technically, proving the Plotkin bound boils down to demonstrating the Schur convexity of a certain function defined on the $q$-simplex as well as the convexity of a univariate function derived from it. We remark that an earlier argument claimed similar results for $q$-ary list-decoding; however, we point out that this earlier proof is flawed.
Lightweight Alpha Matting Network Using Distillation-Based Channel Pruning
Venue: arXiv cs.CV 2022
Year: 2022

Recently, alpha matting has received a lot of attention because of its usefulness in mobile applications such as selfies. Therefore, there has been a demand for a lightweight alpha matting model due to the limited computational resources of commercial portable devices. To this end, we suggest a distillation-based channel pruning method for the alpha matting networks. In the pruning step, we remove channels of a student network having fewer impacts on mimicking the knowledge of a teacher network. Then, the pruned lightweight student network is trained by the same distillation loss. A lightweight alpha matting model from the proposed method outperforms existing lightweight methods. To show superiority of our algorithm, we provide various quantitative and qualitative experiments with in-depth analyses. Furthermore, we demonstrate the versatility of the proposed distillation-based channel pruning method by applying it to semantic segmentation.
Towards Immersive Collaborative Sensemaking
Venue: arXiv cs.HC 2022
Year: 2022

When collaborating face-to-face, people commonly use the surfaces and spaces around them to perform sensemaking tasks, such as spatially organising documents, notes or images. However, when people collaborate remotely using desktop interfaces they no longer feel like they are sharing the same space. This limitation may be overcome through collaboration in immersive environments, which simulate the physical in-person experience. In this paper, we report on a between-groups study comparing collaborations on image organisation tasks, in an immersive Virtual Reality (VR) environment to more conventional desktop conferencing. Collecting data from 40 subjects in groups of four, we measured task performance, user behaviours, collaboration engagement and awareness. Overall, the VR and desktop interface resulted in similar speed, accuracy and social presence rating, but we observed more conversations and interaction with objects, and more equal contributions to the interaction from participants within groups in VR. We also identified differences in coordination and collaborative awareness behaviours between VR and desktop platforms. We report on a set of systematic measures for assessing VR collaborative experience and a new analysis tool that we have developed to capture user behaviours in collaborative setting. Finally, we provide design considerations and directions for future work.
A Formal-Methods Approach to Provide Evidence in Automated-Driving Safety Cases
Venue: arXiv cs.SE 2022
Year: 2022

The safety of automated driving systems must be justified by convincing arguments and supported by compelling evidence to persuade certification agencies, regulatory entities, and the general public to allow the systems on public roads. This persuasion is typically facilitated by compiling the arguments and the compelling evidence into a safety case. Reviews and testing, two common approaches to ensure correctness of automotive systems cannot explore the typically infinite set of possible behaviours. In contrast, formal methods are exhaustive methods that can provide mathematical proofs of correctness of models, and they can be used to prove that formalizations of functional safety requirements are fulfilled by formal models of system components. This paper shows how formal methods can provide evidence for the correct break-down of the functional safety requirements onto the components that are part of feedback loops, and how this evidence fits into the argument of the safety case. If a proof is obtained, the formal models are used as requirements on the components. This structure of the safety argumentation can be used to alleviate the need for reviews and tests to ensure that the break-down is correct, thereby saving effort both in data collection and verification time.
Flame-state monitoring based on very low number of visible or infrared images via few-shot learning
Venue: arXiv cs.CV 2022
Year: 2022

The current success of machine learning on image-based combustion monitoring is based on massive data, which is costly even impossible for industrial applications. To address this conflict, we introduce few-shot learning in order to achieve combustion monitoring and classification for the first time. Two algorithms, Siamese Network coupled with k Nearest Neighbors (SN-kNN) and Prototypical Network (PN), were tested. Rather than utilizing solely visible images as discussed in previous studies, we also used Infrared (IR) images. We analyzed the training process, test performance and inference speed of two algorithms on both image formats, and also used t-SNE to visualize learned features. The results demonstrated that both SN-kNN and PN were capable to distinguish flame states from learning with merely 20 images per flame state. The worst performance, which was realized by PN on IR images, still possessed precision, accuracy, recall, and F1-score above 0.95. We showed that visible images demonstrated more substantial differences between classes and presented more consistent patterns inside the class, which made the training speed and model performance better compared to IR images. In contrast, the relatively low quality of IR images made it difficult for PN to extract distinguishable prototypes, which caused relatively weak performance. With the entrire training set supporting classification, SN-kNN performed well with IR images. On the other hand, benefitting from the architecture design, PN has a much faster speed in training and inference than SN-kNN. The presented work analyzed the characteristics of both algorithms and image formats for the first time, thus providing guidance for their future utilization in combustion monitoring tasks.
Bringing NURC/SP to Digital Life: the Role of Open-source Automatic Speech Recognition Models
Venue: arXiv cs.CL 2022
Year: 2022

The NURC Project that started in 1969 to study the cultured linguistic urban norm spoken in five Brazilian capitals, was responsible for compiling a large corpus for each capital. The digitized NURC/SP comprises 375 inquiries in 334 hours of recordings taken in São Paulo capital. Although 47 inquiries have transcripts, there was no alignment between the audio-transcription, and 328 inquiries were not transcribed. This article presents an evaluation and error analysis of three automatic speech recognition models trained with spontaneous speech in Portuguese and one model trained with prepared speech. The evaluation allowed us to choose the best model, using WER and CER metrics, in a manually aligned sample of NURC/SP, to automatically transcribe 284 hours.
One Graph to Rule them All: Using NLP and Graph Neural Networks to analyse Tolkien's Legendarium
Venue: arXiv cs.CL 2022
Year: 2022

Natural Language Processing and Machine Learning have considerably advanced Computational Literary Studies. Similarly, the construction of co-occurrence networks of literary characters, and their analysis using methods from social network analysis and network science, have provided insights into the micro- and macro-level structure of literary texts. Combining these perspectives, in this work we study character networks extracted from a text corpus of J.R.R. Tolkien's Legendarium. We show that this perspective helps us to analyse and visualise the narrative style that characterises Tolkien's works. Addressing character classification, embedding and co-occurrence prediction, we further investigate the advantages of state-of-the-art Graph Neural Networks over a popular word embedding method. Our results highlight the large potential of graph learning in Computational Literary Studies.
SealClub: Computer-aided Paper Document Authentication
Venue: arXiv cs.CR 2022
Year: 2022

Digital authentication is a mature field, offering a range of solutions with rigorous mathematical guarantees. Nevertheless, paper documents, where cryptographic techniques are not directly applicable, are still widely utilized due to usability and legal reasons. We propose a novel approach to authenticating paper documents using smartphones by taking short videos of them. Our solution combines cryptographic and image comparison techniques to detect and highlight subtle semantic-changing attacks on rich documents, containing text and graphics, that could go unnoticed by humans. We rigorously analyze our approach, proving that it is secure against strong adversaries capable of compromising different system components. We also measure its accuracy empirically on a set of 128 videos of paper documents, half containing subtle forgeries. Our algorithm finds all forgeries accurately (no false alarms) after analyzing 5.13 frames on average (corresponding to 1.28 seconds of video). Highlighted regions are large enough to be visible to users, but small enough to precisely locate forgeries. Thus, our approach provides a promising way for users to authenticate paper documents using conventional smartphones under realistic conditions.
A Serverless Publish/Subscribe System
Venue: arXiv cs.DC 2022
Year: 2022

Operating a scalable and reliable server application, such as publish/subscribe (pub/sub) systems, requires tremendous development efforts and resources. The emerging serverless paradigm simplifies the development and deployment of highly available applications by delegating most operational concerns to the cloud providers. The serverless paradigm describes a programming model where the developers break the application downs into smaller microservices that run on the cloud in response to events. This paper proposes designing a serverless pub/sub system based on the IBM Bluemix cloud platform. Our pub/sub system performs topic-based, content-based, and function-based matchings. The function-based matching is a novel matching approach where the subscribers can define a highly customizable subscription function that the broker applies to the publications in the cloud. The evaluations of the designed system verify the practicality of the designed system. However, the vendor-specific constraints of the IBM Bluemix resources are a bottleneck to the scalability of the broker.
Post-Training Quantization for Energy Efficient Realization of Deep Neural Networks
Venue: arXiv cs.LG 2022
Year: 2022

The biggest challenge for the deployment of Deep Neural Networks (DNNs) close to the generated data on edge devices is their size, i.e., memory footprint and computational complexity. Both are significantly reduced with quantization. With the resulting lower word-length, the energy efficiency of DNNs increases proportionally. However, lower word-length typically causes accuracy degradation. To counteract this effect, the quantized DNN is retrained. Unfortunately, training costs up to 5000x more energy than the inference of the quantized DNN. To address this issue, we propose a post-training quantization flow without the need for retraining. For this, we investigated different quantization options. Furthermore, our analysis systematically assesses the impact of reduced word-lengths of weights and activations revealing a clear trend for the choice of word-length. Both aspects have not been systematically investigated so far. Our results are independent of the depth of the DNNs and apply to uniform quantization, allowing fast quantization of a given pre-trained DNN. We excel state-of-the-art for 6 bit by 2.2% Top-1 accuracy for ImageNet. Without retraining, our quantization to 8 bit surpasses floating-point accuracy.
Codes, Patterns and Shapes of Contemporary Online Antisemitism and Conspiracy Narratives -- an Annotation Guide and Labeled German-Language Dataset in the Context of COVID-19
Venue: arXiv cs.CL 2022
Year: 2022

Over the course of the COVID-19 pandemic, existing conspiracy theories were refreshed and new ones were created, often interwoven with antisemitic narratives, stereotypes and codes. The sheer volume of antisemitic and conspiracy theory content on the Internet makes data-driven algorithmic approaches essential for anti-discrimination organizations and researchers alike. However, the manifestation and dissemination of these two interrelated phenomena is still quite under-researched in scholarly empirical research of large text corpora. Algorithmic approaches for the detection and classification of specific contents usually require labeled datasets, annotated based on conceptually sound guidelines. While there is a growing number of datasets for the more general phenomenon of hate speech, the development of corpora and annotation guidelines for antisemitic and conspiracy content is still in its infancy, especially for languages other than English. We contribute to closing this gap by developing an annotation guide for antisemitic and conspiracy theory online content in the context of the COVID-19 pandemic. We provide working definitions, including specific forms of antisemitism such as encoded and post-Holocaust antisemitism. We use these to annotate a German-language dataset consisting of ~3,700 Telegram messages sent between 03/2020 and 12/2021.