Search

The inference and training stages of Graph Neural Networks (GNNs) are often dominated by the time required to compute a long sequence of matrix multiplications between the sparse graph adjacency matrix and its embedding. To accelerate these stages, we first propose the Compressed Binary Matrix (CBM) storage format to succinctly represent the binary adjacency matrix of an unweighted graph. Then, we show how to generalize this representation to normalized adjacency matrices of unweighted graphs which arise in the context of GNNs. Finally, we develop efficient matrix multiplication kernels based on this compressed representation. The matrix multiplication kernels proposed in this work never require more scalar operations than classic sparse matrix multiplication algorithms. Experimental evaluation shows that the matrix multiplication strategies proposed outperform the current state-of-the-art implementations provided by Intel MKL, achieving speedups close to 5$\times$. Furthermore, our optimized matrix-multiplication strategies accelerated the inference time of a GNN by up to $3\times$.

Let G = (V, E) be a directed and weighted graph with vertex set V of size n and edge set E of size m, such that each edge (u, v) \in E has a real-valued weight w(u, c). An arborescence in G is a subgraph T = (V, E') such that for a vertex u \in V, the root, there is a unique path in T from u to any other vertex v \in V. The weight of T is the sum of the weights of its edges. In this paper, given G, we are interested in finding an arborescence in G with minimum weight, i.e., an optimal arborescence. Furthermore, when G is subject to changes, namely edge insertions and deletions, we are interested in efficiently maintaining a dynamic arborescence in G. This is a well known problem with applications in several domains such as network design optimization and in phylogenetic inference. In this paper we revisit algorithmic ideas proposed by several authors for this problem, we provide detailed pseudo-code as well as implementation details, and we present experimental results on large scale-free networks and on phylogenetic inference. Our implementation is publicly available at \url{https://gitlab.com/espadas/optimal-arborescences}.

We consider the problem of computing a sequence of range minimum queries. We assume a sequence of commands that contains values and queries. Our goal is to quickly determine the minimum value that exists between the current position and a previous position $i$. Range minimum queries are used as a sub-routine of several algorithms, namely related to string processing. We propose a data structure that can process these commands sequences. We obtain efficient results for several variations of the problem, in particular we obtain $O(1)$ time per command for the offline version and $O(\alpha(n))$ amortized time for the online version, where $\alpha(n)$ is the inverse Ackermann function and $n$ the number of values in the sequence. This data structure also has very small space requirements, namely $O(\ell)$ where $\ell$ is the maximum number active $i$ positions. We implemented our data structure and show that it is competitive against existing alternatives. We obtain comparable command processing time, in the nano second range, and much smaller space requirements., Comment: 29 pages, 3 figures, 3 tables, 6 algorithms

We consider the problem of identifying tandem scattered subsequences within a string. Our algorithm identifies a longest subsequence which occurs twice without overlap in a string. This algorithm is based on the Hunt-Szymanski algorithm, therefore its performance improves if the string is not self similar. This occurs naturally on strings over large alphabets. Our algorithm relies on new results for data structures that support dynamic longest increasing sub-sequences. In the process we also obtain improved algorithms for the decremental string comparison problem., Comment: The work reported in this article was supported by national funds through Funda\c{c}\~ao para a Ci\^encia e Tecnologia (FCT) with reference UIDB/50021/2020 and through project NGPHYLO PTDC/CCI-BIO/29676/2017. Funded in part by European Union's Horizon 2020 research and innovation programme under the Marie Sk{\l}odowska-Curie Actions grant agreement No 690941

We consider the complexity properties of modern puzzle games, Hexiom, Cut the Rope and Back to Bed. The complexity of games plays an important role in the type of experience they provide to players. Back to Bed is shown to be PSPACE-Hard and the first two are shown to be NP-Hard. These results give further insight into the structure of these games and the resulting constructions may be useful in further complexity studies., Comment: The work reported in this article was supported by national funds through Funda\c{c}\~ao para a Ci\^encia e Tecnologia (FCT) through projects NGPHYLO PTDC/CCI-BIO/29676/2017 and UID/CEC/50021/2019. Funded in part by European Union Horizon 2020 research and innovation programme under the Marie Sk{\l}odowska-Curie Actions grant agreement No 690941

Parity check matrices (PCMs) are used to define linear error correcting codes and ensure reliable information transmission over noisy channels. The set of codewords of such a code is the null space of this binary matrix. We consider the problem of minimizing the number of one-entries in parity-check matrices. In the maximum-likelihood (ML) decoding method, the number of ones in PCMs is directly related to the time required to decode messages. We propose a simple matrix row manipulation heuristic which alters the PCM, but not the code itself. We apply simulated annealing and greedy local searches to obtain PCMs with a small number of one entries quickly, i.e. in a couple of minutes or hours when using mainstream hardware. The resulting matrices provide faster ML decoding procedures, especially for large codes., Comment: This work was supported by Funda\c{c}\~ao para a Ci\^encia e Tecnologia (FCT) ref. UID/CEC/50021/2019; European Union's Horizon 2020, Marie Sk{\l}odowska-Curie Actions grant agreement No 690941; The DAAD-CRUP Luso-German bilateral cooperation 2017-2018 research project MONO-EMC; The DFG (project-ID: RU 1524/2-3). Jos{\'e} Rui Figueira acknowledges FCT grant SFRH/BSAB/139892/2018

We consider the problem of updating the information about multiple longest common sub-sequences. This kind of sub-sequences is used to highlight information that is shared across several information sequences, therefore it is extensively used namely in bioinformatics and computational genomics. In this paper we propose a way to maintain this information when the underlying sequences are subject to modifications, namely when letters are added and removed from the extremes of the sequence. Experimentally our data structure obtains significant improvements over the state of the art., Comment: The work reported in this article was supported by national funds through Funda\c{c}\~ao para a Ci\^encia e Tecnologia (FCT) through projects NGPHYLO PTDC/CCI-BIO/29676/2017 and UID/CEC/50021/2019. Funded in part by European Union Horizon 2020 research and innovation programme under the Marie Sk{\l}odowska-Curie Actions grant agreement No 690941

Lempel-Ziv is an easy-to-compute member of a wide family of so-called macro schemes; it restricts pointers to go in one direction only. Optimal bidirectional macro schemes are NP-complete to find, but they may provide much better compression on highly repetitive sequences. We consider the problem of approximating optimal bidirectional macro schemes. We describe a simulated annealing algorithm that usually converges quickly. Moreover, in some cases, we obtain bidirectional macro schemes that are provably a 2-approximation of the optimal. We test our algorithm on a number of artificial repetitive texts and verify that it is efficient in practice and outperforms Lempel-Ziv, sometimes by a wide margin., Comment: This research has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie Actions H2020-MSCA-RISE-2015 BIRDS GA No. 690941

We address the problem of representing dynamic graphs using $k^2$-trees. The $k^2$-tree data structure is one of the succinct data structures proposed for representing static graphs, and binary relations in general. It relies on compact representations of bit vectors. Hence, by relying on compact representations of dynamic bit vectors, we can also represent dynamic graphs. In this paper we follow instead the ideas by Munro {\em et al.}, and we present an alternative implementation for representing dynamic graphs using $k^2$-trees. Our experimental results show that this new implementation is competitive in practice., Comment: This research has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie Actions H2020-MSCA-RISE-2015 BIRDS GA No. 690941

Given an indeterminate string pattern $p$ and an indeterminate string text $t$, the problem of order-preserving pattern matching with character uncertainties ($\mu$OPPM) is to find all substrings of $t$ that satisfy one of the possible orderings defined by $p$. When the text and pattern are determinate strings, we are in the presence of the well-studied exact order-preserving pattern matching (OPPM) problem with diverse applications on time series analysis. Despite its relevance, the exact OPPM problem suffers from two major drawbacks: 1) the inability to deal with indetermination in the text, thus preventing the analysis of noisy time series; and 2) the inability to deal with indetermination in the pattern, thus imposing the strict satisfaction of the orders among all pattern positions. This paper provides the first polynomial algorithm to answer the $\mu$OPPM problem when indetermination is observed on the pattern or text. Given two strings with length $m$ and $O(r)$ uncertain characters per string position, we show that the $\mu$OPPM problem can be solved in $O(mr\lg r)$ time when one string is indeterminate and $r\in\mathbb{N}^+$. Mappings into satisfiability problems are provided when indetermination is observed on both the pattern and the text, and results concerning the general problem complexity are presented as well, with $\mu$OPPM problem proved to be NP-hard in general.

We consider the problem of uniformly generating a spanning tree, of a connected undirected graph. This process is useful to compute statistics, namely for phylogenetic trees. We describe a Markov chain for producing these trees. For cycle graphs we prove that this approach significantly outperforms existing algorithms. For general graphs we obtain no analytical bounds, but experimental results show that the chain still converges quickly. This yields an efficient algorithm, also due to the use of proper fast data structures. To bound the mixing time of the chain we describe a coupling, which we analyse for cycle graphs and simulate for other graphs., Comment: This research has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie Actions H2020-MSCA-RISE-2015 BIRDS GA No. 690941. Prototype implementation at https://github.com/LuisRusso-INESC-ID/LinkCutSpanningTrees

The article describes the structural and algorithmic relations between Cartesian trees and Lyndon Trees. This leads to a uniform presentation of the Lyndon table of a word corresponding to the Next Nearest Smaller table of a sequence of numbers. It shows how to efficiently compute runs, that is, maximal periodicities occurring in a word.

WiFi's popularity has led to crowded scenarios composed of many Access Points (AP) and clients, often operating on overlapping channels, producing interference that gravely degrades performance. This misallocation of resources is often the result of multiple WLANs ownership, that is, networks are frequently setup automatically without considering neighbouring APs. In this work we overview the effect of Overlapping BSS (OBSS) from the perspective of the MAC layer, taking special interest on describing the advantages of eliminating collisions with Carrier Sense Multiple Access with Enhanced Collision Avoidance (CSMA/ECA). We propose a single Access Point (AP) and several multi-AP scenarios, including the residential building example proposed for testing the upcoming IEEE 802.11ax amendment. Results using the first NS-3 implementation of CSMA/ECA reveal the advantage of CSMA/ECA's deterministic backoff contention technique, confirming its suitability for very crowded scenarios., Comment: Submitted to Elsevier's COMNET journal

The ability to perform traffic differentiation is a promising feature of the current Medium Access Control (MAC) in Wireless Local Area Networks (WLANs). The Enhanced Distributed Channel Access (EDCA) protocol for WLANs proposes up to four Access Categories (AC) that can be mapped to different traffic priorities. High priority ACs are allowed to transmit more often than low priority ACs, providing a way of prioritising delay sensitive traffic like voice calls or video streaming. Further, EDCA also considers the intricacies related to the management of multiple queues, virtual collisions and traffic differentiation. Nevertheless, EDCA falls short in efficiency when performing in dense WLAN scenarios. Its collision-prone contention mechanism degrades the overall throughput to the point of starving low priority ACs, and produce priority inversions at high number of contenders. Carrier Sense Multiple Access with Enhanced Collision Avoidance (CSMA/ECA) is a compatible MAC protocol for WLANs which is also capable of providing traffic differentiation. Contrary to EDCA, CSMA/ECA uses a contention mechanism with a deterministic backoff technique which is capable of constructing collision-free schedules for many nodes with multiple active ACs, extending the network capacity without starving low priority ACs, as experienced in EDCA. This work analyses traffic differentiation with CSMA/ECA by describing the mechanisms used to construct collision-free schedules with multiple queues. Additionally, evaluates the performance under different traffic conditions and a growing number of contenders. (arXiv's abstract field is not large enough for the paper's abstract, please download the paper for the complete abstract.), Comment: This work has been submitted to the Computer Communications (COMCOM) journal. A revision is ongoing

We study the dynamic optimality conjecture, which predicts that splay trees are a form of universally efficient binary search tree, for any access sequence. We reduce this claim to a regular access bound, which seems plausible and might be easier to prove. This approach may be useful to establish dynamic optimality., Comment: This research has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie Actions H2020-MSCA-RISE-2015 BIRDS GA No. 690941

Collisions are a main cause of throughput degradation in WLANs. The current contention mechanism used in IEEE 802.11 networks is called Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA). It uses a Binary Exponential Backoff (BEB) technique to randomise each contender attempt of transmitting, effectively reducing the collision probability. Nevertheless, CSMA/CA relies on a random backoff that while effective and fully decentralised, in principle is unable to completely eliminate collisions, therefore degrading the network throughput as more contenders attempt to share the channel. To overcome these situations, Carrier Sense Multiple Access with Enhanced Collision Avoidance (CSMA/ECA) is able to create a collision-free schedule in a fully decentralised manner using a deterministic backoff after successful transmissions. Hysteresis and Fair Share are two extensions of CSMA/ECA to support a large number of contenders in a collision-free schedule. CSMA/ECA offers better throughput than CSMA/CA and short-term throughput fairness. This work describes CSMA/ECA and its extensions. Additionally, it provides the first evaluation results of CSMA/ECA with non-saturated traffic, channel errors, and its performance when coexisting with CSMA/CA nodes. Furthermore, it describes the effects of imperfect clocks over CSMA/ECA and present a mechanism to leverage the impact of channel errors and the addition/withdrawal of nodes over collision-free schedules. Finally, experimental results on throughput and lost frames from a CSMA/ECA implementation using commercial hardware and open-source firmware are presented., Comment: This work has been submitted to the IEEE/ACM Transactions on Networking journal

Collisions are a main cause of throughput degradation in Wireless LANs. The current contention mechanism for these networks is based on a random backoff strategy to avoid collisions with other transmitters. Even though it can reduce the probability of collisions, the random backoff prevents users from achieving Collision-Free schedules, where the channel would be used more efficiently. Modifying the contention mechanism by waiting for a deterministic timer after successful transmissions, users would be able to construct a Collision-Free schedule among successful contenders. This work shows the experimental results of a Collision-Free MAC (CF-MAC) protocol for WLANs using commercial hardware and open firmware for wireless network cards which is able to support many users. Testbed results show that the proposed CF-MAC protocol leads to a better distribution of the available bandwidth among users, higher throughput and lower losses than the unmodified WLANs clients using a legacy firmware., Comment: This paper was submitted to the IEEE International Conference on Communications 2015 and it is waiting for approval

During the past month we have been trying to understand both the behavior of CSMA/ECA and how our simulator works. In this report I try to asses some of those doubts and provide a groundwork for discussion of past and new ideas for further develop the MAC protocol., Comment: Technical Report

In this paper a candidate protocol to replace the prevalent CSMA/CA medium access control in Wireless Local Area Networks is presented. The proposed protocol can achieve higher throughput than CSMA/CA, while maintaining fairness, and without additional implementation complexity. Under certain circumstances, it is able to reach and maintain collision-free operation, even when the number of contenders is variable and potentially large. It is backward compatible, allowing for new and legacy stations to coexist without degrading one another's performance, a property that can make the adoption process by future versions of the standard smooth and inexpensive., Comment: This paper has been accepted in the Second IEEE ICC Workshop 2013 on Telecommunication Standards: From Research to Standards

CSMA/ECA is a contention protocol that makes it possible to construct a collision-free schedule by using a deterministic backoff after successful transmissions. In this paper, we further enhance the CSMA/ECA protocol with two properties that allows to fairly accommodate a large number of contenders in a collision-free schedule. The first property, called hysteresis, instructs the contenders not to reset their contention window after successful transmissions. Thanks to hysteresis, the protocol sustains a high throughput regardless of the number of contenders. The second property, called fair-share, preserves fairness when different nodes use different contention windows. We present simulations results that evidence how these properties account for performance gains that go even further beyond CSMA/CA.

Wireless Sensor Networks (WSNs) are composed of nodes that gather metrics like temperature, pollution or pressure from events generated by external entities. Localization in WSNs is paramount, given that the collected metrics must be related to the place of occurrence. This document presents an alternative way towards localization in randomly deployed WSNs based on the composability of localization protocols. Results show a totally distributed localization procedure that achieves a higher number of located nodes than the conventional, individual execution of localization protocols while maintaining the same low levels of battery consumption., Comment: To be presented at the 9th International Wireless Communications & Mobile Computing Conference (IWCMC 2013), July 1-5, Cagliari - Italy. This work has been partially supported by the Spanish Government, through the project CISNETS (Plan Nacional I+D+i, TEC2012-32354)

This short report intends to provide an overview of the procedure and statistics of establishing a TCP/IP link between two USRP-E110. The testings are performed using an example GNURadio code and the networking protocol stack provided by the Linux operating system embedded in the USRP-E110.

Spectrum sensing is one of the key topics towards the implementation of future wireless services like SuperWiFi. This new wireless proposal aims at using the freed spectrum resulting from the analog-to-digital transition of TV channels for wireless data transmission (UHF TV White Spaces). The benefits range from better building penetration to longer distances when compared to the set of IEEE 802.11 standards. Nevertheless, the effective use of the available spectrum is subject to strict regulation that prohibits unlicensed users to interfere with incumbents (like wireless microphones). Cognitive Radios (CR) and dynamic spectrum allocation are suggested to cope with this problem. These techniques consist on frequency sweeps of the TV-UHF band to detect White Spaces that could be used for SuperWiFi transmissions. In this paper we develop and implement algorithms from GNURadio in the Ettus USRP-E110 to build a standalone White Spaces detector that can be consulted from a centralized location via IP networks., Comment: 5th International Workshop on Multiple Access Communications, 11/2012, Dublin, Ireland, (2012)

We present a new algorithm to calculate exact hypervolumes. Given a set of $d$-dimensional points, it computes the hypervolume of the dominated space. Determining this value is an important subroutine of Multiobjective Evolutionary Algorithms (MOEAs). We analyze the "Quick Hypervolume" (QHV) algorithm theoretically and experimentally. The theoretical results are a significant contribution to the current state of the art. Moreover the experimental performance is also very competitive, compared with existing exact hypervolume algorithms. A full description of the algorithm is currently submitted to IEEE Transactions on Evolutionary Computation.

We consider various data-analysis queries on two-dimensional points. We give new space/time tradeoffs over previous work on geometric queries such as dominance and rectangle visibility, and on semigroup and group queries such as sum, average, variance, minimum and maximum. We also introduce new solutions to queries less frequently considered in the literature such as two-dimensional quantiles, majorities, successor/predecessor, mode, and various top-$k$ queries, considering static and dynamic scenarios., Comment: 20 pages, 2 figures, submitting