OpenRaiser/Intern-Atlas huggingface dataset:
Topic-based Community Search over Spatial-Social Networks (Technical Report)
Venue: arXiv cs.DB 2021
Year: 2021

Recently, the community search problem has attracted significant attention, due to its wide spectrum of real-world applications such as event organization, friend recommendation, advertisement in e-commence, and so on. Given a query vertex, the community search problem finds dense subgraph that contains the query vertex. In social networks, users have multiple check-in locations, influence score, and profile information (keywords). Most previous studies that solve the CS problem over social networks usually neglect such information in a community. In this paper, we propose a novel problem, named community search over spatial-social networks (TCS-SSN), which retrieves community with high social influence, small traveling time, and covering certain keywords. In order to tackle the TCS-SSN problem over the spatial-social networks, we design effective pruning techniques to reduce the problem search space. We also propose an effective indexing mechanism, namely social-spatial index, to facilitate the community query, and develop an efficient query answering algorithm via index traversal. We verify the efficiency and effectiveness of our pruning techniques, indexing mechanism, and query processing algorithm through extensive experiments on real-world and synthetic data sets under various parameter settings.
Human Trajectory Forecasting in Crowds: A Deep Learning Perspective
Venue: arXiv cs.CV 2021
Year: 2021

Since the past few decades, human trajectory forecasting has been a field of active research owing to its numerous real-world applications: evacuation situation analysis, deployment of intelligent transport systems, traffic operations, to name a few. Early works handcrafted this representation based on domain knowledge. However, social interactions in crowded environments are not only diverse but often subtle. Recently, deep learning methods have outperformed their handcrafted counterparts, as they learned about human-human interactions in a more generic data-driven fashion. In this work, we present an in-depth analysis of existing deep learning-based methods for modelling social interactions. We propose two knowledge-based data-driven methods to effectively capture these social interactions. To objectively compare the performance of these interaction-based forecasting models, we develop a large scale interaction-centric benchmark TrajNet++, a significant yet missing component in the field of human trajectory forecasting. We propose novel performance metrics that evaluate the ability of a model to output socially acceptable trajectories. Experiments on TrajNet++ validate the need for our proposed metrics, and our method outperforms competitive baselines on both real-world and synthetic datasets.
The Vectorial Lambda Calculus Revisited
Venue: arXiv cs.LO 2021
Year: 2021

We revisit the Vectorial Lambda Calculus, a typed version of Lineal. Vectorial (as well as Lineal) has been originally designed for quantum computing, as an extension to System F where linear combinations of lambda terms are also terms and linear combinations of types are also types. In its first presentation, Vectorial only provides a weakened version of the Subject Reduction property. We prove that our revised Vectorial Lambda Calculus supports the standard version of said property, answering a long standing issue. In addition we also introduce the concept of weight of types and terms, and prove a relation between the weight of terms and of its types.
TripMD: Driving patterns investigation via Motif Analysis
Venue: arXiv cs.AI 2021
Year: 2021

Processing driving data and investigating driving behavior has been receiving an increasing interest in the last decades, with applications ranging from car insurance pricing to policy making. A common strategy to analyze driving behavior is to study the maneuvers being performance by the driver. In this paper, we propose TripMD, a system that extracts the most relevant driving patterns from sensor recordings (such as acceleration) and provides a visualization that allows for an easy investigation. Additionally, we test our system using the UAH-DriveSet dataset, a publicly available naturalistic driving dataset. We show that (1) our system can extract a rich number of driving patterns from a single driver that are meaningful to understand driving behaviors and (2) our system can be used to identify the driving behavior of an unknown driver from a set of drivers whose behavior we know.
Open-Pub: A Transparent yet Privacy-Preserving Academic Publication System based on Blockchain
Venue: arXiv cs.CR 2021
Year: 2021

Academic publications of latest research results are crucial to advance the development of all disciplines. However, there are several severe disadvantages in current academic publication systems. The first is the misconduct during the publication process due to the opaque paper review process. An anonymous reviewer may give biased comments to a paper without being noticed because the comments are seldom published for evaluation. Second, access to research papers is restricted to only subscribers, and even the authors cannot access their own papers. To address the above problems, we propose Open-Pub, a decentralized, transparent yet privacy-preserving academic publication scheme using the blockchain technology. In Open-Pub, we first design a threshold identity-based group signature (TIBGS) that protects identities of signers using verifiable secret sharing. Then we develop a strong double-blind mechanism to protect the identities of authors and reviewers. With this strong double-blind mechanism, authors can choose to submit papers anonymously, and validators distribute papers anonymously to reviewers on the blockchain according to their research interests. This process is publicly recorded and traceable on the blockchain so as to realize transparent peer preview. To evaluate its efficiency, we implement Open-Pub based on Ethereum and conduct comprehensive experiments to evaluate its performance, including computation cost and processing delay. The experiment results show that Open-Pub is highly efficient in computation and processing anonymous transactions.
A Nearest Neighbor Characterization of Lebesgue Points in Metric Measure Spaces
Venue: arXiv cs.LG 2021
Year: 2021

The property of almost every point being a Lebesgue point has proven to be crucial for the consistency of several classification algorithms based on nearest neighbors. We characterize Lebesgue points in terms of a 1-Nearest Neighbor regression algorithm for pointwise estimation, fleshing out the role played by tie-breaking rules in the corresponding convergence problem. We then give an application of our results, proving the convergence of the risk of a large class of 1-Nearest Neighbor classification algorithms in general metric spaces where almost every point is a Lebesgue point.
Semi-Supervised Learning with Meta-Gradient
Venue: arXiv cs.LG 2021
Year: 2021

In this work, we propose a simple yet effective meta-learning algorithm in semi-supervised learning. We notice that most existing consistency-based approaches suffer from overfitting and limited model generalization ability, especially when training with only a small number of labeled data. To alleviate this issue, we propose a learn-to-generalize regularization term by utilizing the label information and optimize the problem in a meta-learning fashion. Specifically, we seek the pseudo labels of the unlabeled data so that the model can generalize well on the labeled data, which is formulated as a nested optimization problem. We address this problem using the meta-gradient that bridges between the pseudo label and the regularization term. In addition, we introduce a simple first-order approximation to avoid computing higher-order derivatives and provide theoretic convergence analysis. Extensive evaluations on the SVHN, CIFAR, and ImageNet datasets demonstrate that the proposed algorithm performs favorably against state-of-the-art methods.
Threshold ECDSA with an Offline Recovery Party
Venue: arXiv cs.CR 2021
Year: 2021

A $(t,n)-$ threshold signature scheme enables distributed signing among $n$ players such that any subgroup of size $t$ can sign, whereas any group with fewer players cannot. Our goal is to produce signatures that are compatible with an existing centralized signature scheme: the key generation and signature algorithm are replaced by a communication protocol between the parties, but the verification algorithm remains identical to that of a signature issued using the centralized algorithm. Starting from the threshold schemes for the ECDSA signature due to R. Gennaro and S. Goldfeder, we present the first protocol that supports multiparty signatures with an offline participant during the Key Generation Phase, without relying on a trusted third party. Following well-established approaches, we prove our scheme secure against adaptive malicious adversaries.
Reversible Data Hiding in Encrypted Images Based on Bit-plane Compression of Prediction Error
Venue: arXiv cs.MM 2021
Year: 2021

As a technology that can prevent the information from being disclosed, the reversible data hiding in encrypted images (RDHEI) acts as an important role in privacy protection and information security. To make use of the image redundancy and further improve the embedding performance, a high-capacity RDHEI method based on bit-plane compression of prediction error is proposed in this paper. Firstly, the whole prediction error is calculated and divided into blocks of the same size. Then, the content owner rearranges the bit-plane of prediction error by block and compresses the bitstream with the joint encoding algorithm to reserve room. Finally, the image is encrypted and the information can be embedded into the reserved room. On the receiver side, the information extraction and the image recovery are performed separably. Experimental results show that the proposed method brings higher embedding capacity than state-of-the-art RDHEI works.
Mobility driven Cloud-Fog-Edge Framework for Location-aware Services: A Comprehensive Review
Venue: arXiv cs.DC 2021
Year: 2021

With the pervasiveness of IoT devices, smart-phones and improvement of location-tracking technologies huge volume of heterogeneous geo-tagged (location specific) data is generated which facilitates several location-aware services. The analytics with this spatio-temporal (having location and time dimensions) datasets provide varied important services such as, smart transportation, emergency services (health-care, national defence or urban planning). While cloud paradigm is suitable for the capability of storage and computation, the major bottleneck is network connectivity loss. In time-critical application, where real-time response is required for emergency service-provisioning, such connectivity issues increases the latency and thus affects the overall quality of system (QoS). To overcome the issue, fog/ edge topology has emerged, where partial computation is carried out in the edge of the network to reduce the delay in communication. Such fog/ edge based system complements the cloud technology and extends the features of the system. This chapter discusses cloud-fog-edge based hierarchical collaborative framework, where several components are deployed to improve the QoS. On the other side. mobility is another critical factor to enhance the efficacy of such location-aware service provisioning. Therefore, this chapter discusses the concerns and challenges associated with mobility-driven cloud-fog-edge based framework to provide several location-aware services to the end-users efficiently.
Visual analytics of COVID-19 dissemination in São Paulo state, Brazil
Venue: arXiv cs.HC 2021
Year: 2021

Visual analytics techniques are useful tools to support decision-making and cope with increasing data, which is particularly important when monitoring natural or artificial phenomena. When monitoring disease progression, visual analytics approaches help decision-makers choose to understand or even prevent dissemination paths. In this paper, we propose a new visual analytics tool for monitoring COVID-19 dissemination. We use k-nearest neighbors of cities to mimic neighboring cities and analyze COVID-19 dissemination based on the comparison of a city under consideration and its neighborhood. Moreover, such analysis is performed based on periods, which facilitates the assessment of isolation policies. We validate our tool by analyzing the progression of COVID-19 in neighboring cities of São Paulo state, Brazil.
TEAM: Trilateration for Exploration and Mapping with Robotic Networks
Venue: arXiv cs.RO 2021
Year: 2021

Motivated by lunar exploration, we consider deploying a network of mobile robots to explore an unknown environment while acting as a cooperative positioning system. Robots measure and communicate position-related data in order to perform localization in the absence of infrastructure-based solutions (e.g. stationary beacons or GPS). We present Trilateration for Exploration and Mapping (TEAM), a novel algorithm for low-complexity localization and mapping with robotic networks. TEAM is designed to leverage the capability of commercially-available ultra-wideband (UWB) radios on board the robots to provide range estimates with centimeter accuracy and perform anchorless localization in a shared, stationary frame. It is well-suited for feature-deprived environments, where feature-based localization approaches suffer. We provide experimental results in varied Gazebo simulation environments as well as on a testbed of Turtlebot3 Burgers with Pozyx UWB radios. We compare TEAM to the popular Rao-Blackwellized Particle Filter for Simultaneous Localization and Mapping (SLAM). We demonstrate that TEAM requires an order of magnitude less computational complexity and reduces the necessary sample rate of LiDAR measurements by an order of magnitude. These advantages do not require sacrificing performance, as TEAM reduces the maximum localization error by 50% and achieves up to a 28% increase in map accuracy in feature-deprived environments and comparable map accuracy in other settings.
Accelerating Multigrid-based Hierarchical Scientific Data Refactoring on GPUs
Venue: arXiv cs.DC 2021
Year: 2021

Rapid growth in scientific data and a widening gap between computational speed and I/O bandwidth make it increasingly infeasible to store and share all data produced by scientific simulations. Instead, we need methods for reducing data volumes: ideally, methods that can scale data volumes adaptively so as to enable negotiation of performance and fidelity tradeoffs in different situations. Multigrid-based hierarchical data representations hold promise as a solution to this problem, allowing for flexible conversion between different fidelities so that, for example, data can be created at high fidelity and then transferred or stored at lower fidelity via logically simple and mathematically sound operations. However, the effective use of such representations has been hindered until now by the relatively high costs of creating, accessing, reducing, and otherwise operating on such representations. We describe here highly optimized data refactoring kernels for GPU accelerators that enable efficient creation and manipulation of data in multigrid-based hierarchical forms. We demonstrate that our optimized design can achieve up to 250 TB/s aggregated data refactoring throughput -- 83% of theoretical peak -- on 1024 nodes of the Summit supercomputer. We showcase our optimized design by applying it to a large-scale scientific visualization workflow and the MGARD lossy compression software.
Continual Adaptation for Deep Stereo
Venue: arXiv cs.CV 2021
Year: 2021

Depth estimation from stereo images is carried out with unmatched results by convolutional neural networks trained end-to-end to regress dense disparities. Like for most tasks, this is possible if large amounts of labelled samples are available for training, possibly covering the whole data distribution encountered at deployment time. Being such an assumption systematically unmet in real applications, the capacity of adapting to any unseen setting becomes of paramount importance. Purposely, we propose a continual adaptation paradigm for deep stereo networks designed to deal with challenging and ever-changing environments. We design a lightweight and modular architecture, Modularly ADaptive Network (MADNet), and formulate Modular ADaptation algorithms (MAD, MAD++) which permit efficient optimization of independent sub-portions of the entire network. In our paradigm, the learning signals needed to continuously adapt models online can be sourced from self-supervision via right-to-left image warping or from traditional stereo algorithms. With both sources, no other data than the input images being gathered at deployment time are needed. Thus, our network architecture and adaptation algorithms realize the first real-time self-adaptive deep stereo system and pave the way for a new paradigm that can facilitate practical deployment of end-to-end architectures for dense disparity regression.
Multi-Emitter MAP-Elites: Improving quality, diversity and convergence speed with heterogeneous sets of emitters
Venue: arXiv cs.NE 2021
Year: 2021

Quality-Diversity (QD) optimisation is a new family of learning algorithms that aims at generating collections of diverse and high-performing solutions. Among those algorithms, the recently introduced Covariance Matrix Adaptation MAP-Elites (CMA-ME) algorithm proposes the concept of emitters, which uses a predefined heuristic to drive the algorithm's exploration. This algorithm was shown to outperform MAP-Elites, a popular QD algorithm that has demonstrated promising results in numerous applications. In this paper, we introduce Multi-Emitter MAP-Elites (ME-MAP-Elites), an algorithm that directly extends CMA-ME and improves its quality, diversity and data efficiency. It leverages the diversity of a heterogeneous set of emitters, in which each emitter type improves the optimisation process in different ways. A bandit algorithm dynamically finds the best selection of emitters depending on the current situation. We evaluate the performance of ME-MAP-Elites on six tasks, ranging from standard optimisation problems (in 100 dimensions) to complex locomotion tasks in robotics. Our comparisons against CMA-ME and MAP-Elites show that ME-MAP-Elites is faster at providing collections of solutions that are significantly more diverse and higher performing. Moreover, in cases where no fruitful synergy can be found between the different emitters, ME-MAP-Elites is equivalent to the best of the compared algorithms.
Reverse Annealing for Nonnegative/Binary Matrix Factorization
Venue: arXiv cs.LG 2021
Year: 2021

It was recently shown that quantum annealing can be used as an effective, fast subroutine in certain types of matrix factorization algorithms. The quantum annealing algorithm performed best for quick, approximate answers, but performance rapidly plateaued. In this paper, we utilize reverse annealing instead of forward annealing in the quantum annealing subroutine for nonnegative/binary matrix factorization problems. After an initial global search with forward annealing, reverse annealing performs a series of local searches that refine existing solutions. The combination of forward and reverse annealing significantly improves performance compared to forward annealing alone for all but the shortest run times.
Conditional Lower Bound for Inclusion-Based Points-to Analysis
Venue: arXiv cs.PL 2021
Year: 2021

Inclusion-based (i.e., Andersen-style) points-to analysis is a fundamental static analysis problem. The seminal work of Andersen gave a worst-case cubic $O(n^3)$ time points-to analysis algorithm for C, where $n$ is proportional to the number of program variables. An algorithm is truly subcubic if it runs in $O(n^{3-δ})$ time for some $δ> 0$. Despite decades of extensive effort on improving points-to analysis, the cubic bound remains unbeaten. The best combinatorial analysis algorithms have a "slightly subcubic" $O(n^3 / \text{log } n)$ complexity. It is an interesting open problem whether points-to analysis can be solved in truly subcubic time. In this paper, we prove that a truly subcubic $O(n^{3-δ})$ time combinatorial algorithm for inclusion-based points-to analysis is unlikely: a truly subcubic combinatorial points-to analysis algorithm implies a truly subcubic combinatorial algorithm for Boolean Matrix Multiplication (BMM). BMM is a well-studied problem, and no truly subcubic combinatorial BMM algorithm has been known. The fastest combinatorial BMM algorithms run in time $O(n^3/ \text{log}^4 n)$. Our result includes a simplified proof of the BMM-hardness of Dyck-reachability. The reduction is interesting in its own right. First, it is slightly stronger than the existing BMM-hardness results because our reduction only requires one type of parenthesis in Dyck-reachability ($D_1$-reachability). Second, we formally attribute the "cubic bottleneck" to the need to solve $D_1$-reachability, which captures the semantics of pointer references/dereferences. This new perspective enables a more general reduction that applies to programs with arbitrary pointer statements types. Last, our reduction based on $D_1$-reachability shows that demand-driven points-to analysis is as hard as the exhaustive counterpart.
Hardware Implementation of Deep Network Accelerators Towards Healthcare and Biomedical Applications
Venue: arXiv cs.AR 2021
Year: 2021

The advent of dedicated Deep Learning (DL) accelerators and neuromorphic processors has brought on new opportunities for applying both Deep and Spiking Neural Network (SNN) algorithms to healthcare and biomedical applications at the edge. This can facilitate the advancement of medical Internet of Things (IoT) systems and Point of Care (PoC) devices. In this paper, we provide a tutorial describing how various technologies including emerging memristive devices, Field Programmable Gate Arrays (FPGAs), and Complementary Metal Oxide Semiconductor (CMOS) can be used to develop efficient DL accelerators to solve a wide variety of diagnostic, pattern recognition, and signal processing problems in healthcare. Furthermore, we explore how spiking neuromorphic processors can complement their DL counterparts for processing biomedical signals. The tutorial is augmented with case studies of the vast literature on neural network and neuromorphic hardware as applied to the healthcare domain. We benchmark various hardware platforms by performing a sensor fusion signal processing task combining electromyography (EMG) signals with computer vision. Comparisons are made between dedicated neuromorphic processors and embedded AI accelerators in terms of inference latency and energy. Finally, we provide our analysis of the field and share a perspective on the advantages, disadvantages, challenges, and opportunities that various accelerators and neuromorphic processors introduce to healthcare and biomedical domains.