Search

Network traffic monitoring uses empirical entropy to detect anomalous events such as various types of attacks. However, the exact computation of the entropy in high-speed networks is a difficult process due to the limited memory resources available in the data plane hardware. In this paper, we present a method and hardware accelerator to approximate the empirical entropy of a large data set with high throughput and sublinear memory requirements. Our method uses streaming algorithms that exploit the fine-grained parallelism of existing hardware platforms for data plane processing, such as field-programmable gate arrays (FPGAs). The method uses sketches to compute the cardinality of the stream and the frequencies of the top-K elements on line, and then it estimates the contribution to the entropy of the rest of the stream assuming a simple uniform distribution for these elements. Implemented on a Xilinx UltraScale+ ZCU102 FPGA, the accelerator implements the method using only on-chip memory, with less than 50% resource usage. Tested on real network traces of up to 120 million packets and more than 5 million flows, the accelerator estimates the empirical entropy with less than 1.5% mean relative error and $21~\mu \text{s}$ latency, and supports a minimum throughput of 204 gigabits per second.

Extracting discriminative k-mers is an important and challenging problem in DNA sequence analysis with applications in metagenomics and motif discovery. Despite the availability of multiple computational tools designed for this purpose, most discriminative k-mer discovery methods suffer from long execution times and high memory usage when processing large datasets. This paper presents a novel approach for discriminative k-mer discovery in DNA sequences, which leverages streaming and sketch algorithms to reduce space complexity and expose data parallelism, enabling the use of parallel platforms for accelerating the execution of computationally-intensive operations. To assess the performance of our method, we designed and implemented two versions of the algorithm that leverage parallelization at different levels: (i) a software version tailored for multithreading and vector instructions in commodity CPUs, and (ii) a custom architecture implemented on a Field-Programmable Gate Array (FPGA) accelerator that exploits fine-grain parallelism and deep pipelining on reconfigurable logic. Experimental results show that, when mining discriminative k-mers from a set of well-known ChIP-seq sequences, our parallel software implementation executes at least 15% faster than exact-counting tools, and requires at least five times less memory when processing large datasets. More importantly, we designed a custom FPGA-based accelerator for our algorithm on a Xilinx KCU1500 board, which achieves speedups above 78x with the largest datasets, compared to our parallel software implementation. The accelerator uses less than 3% of the logic resources available on the on-board XCKU115 Kintex-7 Ultrascale FPGA, and between 12% and 70% of the memory resources, depending on the size of the dataset.

Background The visualization and analysis of brain data such as white matter diffusion tractography and magnetic resonance imaging (MRI) volumes is commonly used by neuro-specialist and researchers to help the understanding of brain structure, functionality and connectivity. As mobile devices are widely used among users and their technology shows a continuous improvement in performance, different types of applications have been designed to help users in different work areas. Results We present, ABrainVis, an Android mobile tool that allows users to visualize different types of brain images, such as white matter diffusion tractographies, represented as fibers in 3D, segmented fiber bundles, MRI 3D images as rendered volumes and slices, and meshes. The tool enables users to choose and combine different types of brain imaging data to provide visual anatomical context for specific visualization needs. ABrainVis provides high performance over a wide range of Android devices, including tablets and cell phones using medium and large tractography datasets. Interesting visualizations including brain tumors and arteries, along with fiber, are given as examples of case studies using ABrainVis. Conclusions The functionality, flexibility and performance of ABrainVis tool introduce an improvement in user experience enabling neurophysicians and neuroscientists fast visualization of large tractography datasets, as well as the ability to incorporate other brain imaging data such as MRI volumes and meshes, adding anatomical contextual information.

The study of the superficial white matter and its description is essential for the understanding of human brain function and the study of pathogenesis. However, the study of these fibers is still an incomplete task due to the high inter-subject variability and the size of this kind of fibers. In this work, a superficial white matter bundle identification based on fiber clustering was performed using probabilistic tractography on 100 subjects from the The Human Connectome Project (HCP) data, aligned with a non-linear registration. The method starts with an intra-subject clustering, followed by a segmentation of fibers connecting the precentral (PrC) and postcentral (PoC) regions, based on a ROI atlas. Due to the high amount of fibers, they were randomly separated into groups. An inter-subject clustering was applied on the fibers of each group, and then two clustering levels were applied to select the most reproducible bundles. Seven bundles per hemisphere were obtained, connecting the PrC and PoC regions. These were compared with bundles from previous atlases, showing in general more coverage and some bundles not found in previous atlases.

Estimating the empirical entropy of the elements in a dataset is an important task in data analysis. In particular, empirical entropy can be effectively used to detect anomalies in network traffic. However, computing the empirical entropy of a large dataset is computationally expensive and requires a large amount of memory. This is particularly important in high-speed network traffic analysis, where computing the entropy of a data flow in real time requires using hardware accelerators with restricted on-chip memory and arithmetic resources. In this work, we propose a method to estimate the entropy using a streaming algorithm with sublinear space requirements. Our approach uses a sketch to estimate the frequency of the elements in the stream, and a priority queue to store the top-k most frequent elements. We show that our method can provide a good approximation of the entropy of the dataset, and present the design of a hardware accelerator that can compute the entropy of the stream with a throughput of one packet per clock cycle. Implemented on a Xilinx Zynq UltraScale + MPSoC ZCU102 FPGA, our accelerator can operate at line rates above 181 Gbps, consuming 511 mW and using less than 24% of the resources available on the device.

This work presents an effective multiple subject clustering method using whole-brain tractography datasets. The method is able to obtain fiber clusters that are representative of the population. The proposed approach first applies a fast intra-subject clustering algorithm on each subject obtaining the cluster centroids for all subjects. Second, it compresses the collection of centroids to a latent space through the encoder of a trained autoencoder. Finally, it uses a modified HDBSCAN with adjusted parameters on the encoded centroids of all subjects to obtain the final inter-subject clusters. The results shows that the proposed method outperforms other clustering strategies, and it is able to retrieve known fascicles in a reasonable execution time, achieving a precision over 87% and F1 score above 86% on a collection of 20 simulated subjects.

Clustering is an essential operation in many data analysis applications. In particular, bioinformatics and genome analysis use clustering to group similar components in sequence data, in order to find important patterns such as DNA motifs. In this paper, we present an algorithm that clusters DNA data using locality-sensitive hashing with MinHash to group similar subsequences in large Chip-seq datasets. Tested on a standard mESC dataset, the algorithm builds clusters that contain subsequences with high-score matches to known DNA motifs. We also describe the architecture and implementation of a hardware accelerator on a Xilinx Kintex-7 XC7K325T FPGA, that exploits the parallelism of the algorithm to cluster data with a throughput of one k-mer per clock cycle at 350MHz. The accelerator achieves a speedup of 91 compared to a parallel software implementation of the algorithm on a 24-core server.

We propose a new automatic algorithm for the tractography-based parcellation of the cortical surface. The method is based on segmented bundles of the superficial white matter (SWM), calculated for each subject, using a multi-subject SWM bundle atlas. The scheme uses a fast intersection algorithm to define cortical regions connected by each bundle and then it defines a graph representation to model the overlapping of the regions to derive the final parcellation. The algorithm was tested on one subject, and resulting parameters were applied to other 4 subjects. Results show a good correspondence between subjects.

We present an optimized algorithm that performs automatic classification of white matter fibers based on a multi-subject bundle atlas. We implemented a parallel algorithm that improves upon its previous version in both execution time and memory usage. Our new version uses the local memory of each processor, which leads to a reduction in execution time. Hence, it allows the analysis of bigger subject and/or atlas datasets. As a result, the segmentation of a subject of 4,145,000 fibers is reduced from about 14 minutes in the previous version to about 6 minutes, yielding an acceleration of 2.34. In addition, the new algorithm reduces the memory consumption of the previous version by a factor of 0.79., Comment: This research has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Sk{\l}odowska-Curie Actions H2020-MSCA-RISE-2015 BIRDS GA No. 690941, CONICYT PFCHA/ DOCTORADO NACIONAL/2016-21160342, CONICYT FONDECYT 1161427, CONICYT PIA/Anillo de Investigaci\'on en Ciencia y Tecnolog\'ia ACT172121, CONICYT BASAL FB0008 and from CONICYT Basal FB0001

Automated methods that can identify white matter bundles from large tractography datasets have several applications in neuroscience research. In these applications, clustering algorithms have shown to play an important role in the analysis and visualization of white matter structure, generating useful data which can be the basis for further studies. This work proposes FFClust, an efficient fiber clustering method for large tractography datasets containing millions of fibers. Resulting clusters describe the whole set of main white matter fascicles present on an individual brain. The method aims to identify compact and homogeneous clusters, which enables several applications. In individuals, the clusters can be used to study the local connectivity in pathological brains, while at population level, the processing and analysis of reproducible bundles, and other post-processing algorithms can be carried out to study the brain connectivity and create new white matter bundle atlases. The proposed method was evaluated in terms of quality and execution time performance versus the state-of-the-art clustering techniques used in the area. Results show that FFClust is effective in the creation of compact clusters, with a low intra-cluster distance, while keeping a good quality Davies–Bouldin index, which is a metric that quantifies the quality of clustering approaches. Furthermore, it is about 8.6 times faster than the most efficient state-of-the-art method for one million fibers dataset. In addition, we show that FFClust is able to correctly identify atlas bundles connecting different brain regions, as an example of application and the utility of compact clusters.

We present a custom hardware architecture for fast heavy hitter detection in large data streams. The architecture probabilistically estimates the frequency of each element in the data stream using the Countmin-CU sketch with the H3 family of hash functions. The sketch is stored in on-chip memory, and the architecture exploits the parallelism available in the data by simultaneously processing each row of the sketch. The hash functions map each element to a set of counters on the sketch, and the sketch increments the counters that hold the minimum value, which corresponds to the estimated frequency of the element. The hash functions and sorting network are implemented in hardware as fully pipelined circuits, in order to maximize their operating clock frequency. We show a prototype of the architecture running on a Xilinx Kintex-7 XC7K325T FPGA operating with a 300MHz clock, which can process a stream of 3,982,496 32-bit elements and detect the heavy hitters with an 4x16,384-element sketch in 13.27ms, achieving a speedup of 768 compared to a modern desktop computer.

Many proteins work together with others in groups called complexes in order to achieve a specific function. Discovering protein complexes is important for understanding biological processes and predict protein functions in living organisms. Large-scale and throughput techniques have made possible to compile protein-protein interaction networks (PPI networks), which have been used in several computational approaches for detecting protein complexes. Those predictions might guide future biologic experimental research. Some approaches are topology-based, where highly connected proteins are predicted to be complexes; some propose different clustering algorithms using partitioning, overlaps among clusters for networks modeled with unweighted or weighted graphs; and others use density of clusters and information based on protein functionality. However, some schemes still require much processing time or the quality of their results can be improved. Furthermore, most of the results obtained with computational tools are not accompanied by an analysis of false positives. We propose an effective and efficient mining algorithm for discovering highly connected subgraphs, which is our base for defining protein complexes. Our representation is based on transforming the PPI network into a directed acyclic graph that reduces the number of represented edges and the search space for discovering subgraphs. Our approach considers weighted and unweighted PPI networks. We compare our best alternative using PPI networks from Saccharomyces cerevisiae (yeast) and Homo sapiens (human) with state-of-the-art approaches in terms of clustering, biological metrics and execution times, as well as three gold standards for yeast and two for human. Furthermore, we analyze false positive predicted complexes searching the PDBe (Protein Data Bank in Europe) database in order to identify matching protein complexes that have been purified and structurally characterized. Our analysis shows that more than 50 yeast protein complexes and more than 300 human protein complexes found to be false positives according to our prediction method, i.e., not described in the gold standard complex databases, in fact contain protein complexes that have been characterized structurally and documented in PDBe. We also found that some of these protein complexes have recently been classified as part of a Periodic Table of Protein Complexes. The latest version of our software is publicly available at http://doi.org/10.6084/m9.figshare.5297314.v1.

BACKGROUND/SUMMARY OF THE PROBLEM The long examination times in MRI create the need to reduce access time and implement an efficientmodel to reduce patient turnaround time to a minimum [1]. A commonly encountered cause of delay is the screening process, an essential and indispensable step to ensure patient safety and delivery of high-quality care [2,3]. Traditionally, the MRI screening process is completed with a paper questionnaire, which is then scanned into the electronic medical record (EMR) or uploaded to the PACS for documentation purposes. The MRI screening process is commonly completed after patient arrival for an MRI appointment. If a patient reports a positive pertinent history during MRI screening (eg, placement of a medical device or presence of foreign bodies), further investigation is required, for example, obtaining specific information about the make and model of an implanted device before “clearing” the patient [2-6]. This process has several challenges. First,many patients are unaware of the specifics of their implanted device or may not be aware of the need or may simply forget to bring device-specific documentation to their MRI

Listing relevant patterns from graphs is becoming increasingly challenging as Web and social graphs are growing in size at a great rate. This scenario requires to process information more efficiently, including the need of processing data that cannot fit in main memory. Typical approaches for processing data using limited main memory include the streaming and external memory models. This paper addresses the problem of listing dense sub graphs from Web and social graphs using little memory. We propose an external memory algorithm based on K-way merge-sort for clustering and reordering input graphs. We also propose mining heuristics that work well with different stream orders such as URL, BFS, and cluster-based. Our experimental evaluation shows that on Web graphs, in comparison with the in-memory algorithm, the streaming mining heuristic is able to find between 70 and 96% of edges participating in dense sub graphs, uses only between 17 and 25% of the memory, and running times are between 34 and 65%. We further consider an application that uses these dense sub graphs for compressing Web graphs with a representation that enables querying the collection of sub graphs for pattern recovery and basic statistics without decompression.

Mining and analyzing graphs are challenging tasks, especially with today's fast-growing graphs such as Web and social networks. In the case of Web and social networks an effective approach have been using compressed representations that enable basic navigation over the compressed structure. In this paper, we first present a parallel algorithm for reducing the number of edges of Web graphs adding virtual nodes over a cluster using BSP (Bulk Synchronous Processing) model. Applying another compression technique on edge-reduced Web graphs we achieve the best state-of-the-art space/time tradeoff for accessing out/in-neighbors. Second, we present a scalable parallel algorithm over BSP for extracting dense subgraphs and represent them with compact data structures. Our algorithm uses summarized information for implementing dynamic load balance avoiding idle time on processors. We show that our algorithms are scalable and keep compression efficiency.

Mining and analyzing large web and social networks are challenging tasks in terms of storage and information access. In order to address this problem, several works have proposed compressing large graphs allowing neighbor access over their compressed representations. In this paper, we propose a novel compressed structure aiming to reduce storage and support efficient navigation over web and social graph compressed representations. Our approach uses clustering and mining for finding dense subgraphs and represents them using compact data structures. We perform experiments using a wide range of web and social networks and compare our results with the best known techniques. Our results show that we improve the state of the art space/time tradeoffs for supporting neighbor queries. Our compressed structure also enables mining queries based on dense subgraphs, such as cliques and bicliques.

We propose a strategy to perform query processing on P2P similarity search systems based on peers and super-peers. We show that by approximating global but resumed information about the indexed data in each peer, the average amount of computation and communication performed to solve range queries can be significantly reduced as compared to alternative state of the art strategies based on local indexing at peer level. We illustrate our technique by using an indexing method based on compact clustering.

In this paper we propose a distributed meta-index using a peer-to-peer protocol to allow spatio-temporal queries of moving objects on a large set of distributed database servers. We present distribution and fault tolerance strategies of a meta-index that combines partial trace of object movements with aggregated data about the number of objects in the database servers. The degrees of distribution and fault tolerance were compared by using discrete-event simulators with demanding spatio temporal workloads. The results show that the distributed meta-index using Chord provides good performance, scalability and fault tolerance.

Distributed moving object database servers are a feasible solution to the scalability problem of centralized database systems. In this paper we propose a distributed indexing method, using the Distributed Hash Table (DHT) paradigm, devised to efficiently support complex spatio temporal queries. We assume a setting in which there is a large number of database servers that keep track of events associated with a highly dynamic system of moving objects deployed in a spatial area. We present a technique for properly keeping the index up to date and efficiently processing range and top-k queries for moving object databases. We evaluated our system using event-driven simulators with demanding spatio temporal workloads and the results show good performance in terms of response time and network traffic.