Search

The 4th epiDAMIK@SIGKDD workshop is a forum to discuss new insights into how data mining can play a bigger role in epidemiology and public health research. While the integration of data science methods into epidemiology has significant potential, it remains under studied. We aim to raise the profile of this emerging research area of data-driven and computational epidemiology, and create a venue for presenting state-of-the-art and in-progress results-in particular, results that would otherwise be difficult to present at a major data mining conference, including lessons learnt in the 'trenches'. The current COVID-19 pandemic has only showcased the urgency and importance of this area. Our target audience consists of data mining and machine learning researchers from both academia and industry who are interested in epidemiological and public-health applications of their work, and practitioners from the areas of mathematical epidemiology and public health.

The rapid development of Big Data coupled with slowing down of Moore’s law has made the memory performance a bottleneck in the von Neumann architecture. Machine learning has the potential to provide opportunities to address the memory performance issues, specifically through data access prediction. While recent works focusing on the prediction of memory accesses have used recurrent neural networks (RNN), there is a lack of a framework utilizing such prediction in a prefetcher. This paper introduces the RNN Augmented Offset Prefetcher (RAOP) framework, which consists of two parts: an RNN-based predictor and an offset prefetching module. By leveraging the RNN predicted access as a temporal reference, RAOP improves prefetching performance by executing offset prefetching for both the current address and the RNN predicted address. We implement the RNN in the predictor with a compressed long short-term memory (LSTM) model and demonstrate the effect of augmenting an RNN predictor to a simple next-line prefetcher in the prefetching module results in 3.22x, 4.2x, and 15.6% improvement in prefetch accuracy, coverage, and speedup. We further implement a best-offset prefetcher (BOP) in RAOP and compare it to several state-of-the-art prefetchers. Results show that RAOP achieves a mean 4.05% speedup by prefetching in last level cache, outperforming state-of-the-art prefetchers. By augmenting an RNN predictor to BOP, RAOP results in 6.5x, 9.2x, and 12.8% improvement in prefetch accuracy, coverage, and speedup.

Spectral-domain CNNs have been shown to be more efficient than traditional spatial CNNs in terms of reducing computation complexity. However they come with a 'kernel explosion' problem that, even after compression (pruning), imposes a high memory burden and off-chip bandwidth requirement for kernel access. This creates a performance gap between the potential acceleration offered by compression and actual FPGA implementation performance, especially for low-latency CNN inference. In this paper, we develop a principled approach to overcoming this performance gap and designing a low-latency, low-bandwidth, spectral sparse CNN accelerator on FPGAs. First, we analyze the bandwidth-storage tradeoff of sparse convolutional layers and locate communication bottlenecks. We then develop a dataflow for flexibly optimizing data reuse in different layers to minimize off-chip communication. Finally, we propose a novel scheduling algorithm to optimally schedule the on-chip memory access of multiple sparse kernels and minimize read conflicts. On a state-of-the-art FPGA platform, our design reduces data transfers by 42% with DSP utilization up to 90% and achieves inference latency of 9 ms for VGG16, compared to the baseline state-of-the-art latency of 68 ms.

Q-Table based Reinforcement Learning (QRL) is a class of widely used algorithms in AI that work by successively improving the estimates of Q-values - quality of state-action pairs, stored in a table. They significantly outperform Neural Network based techniques when the state space is tractable. Fast learning for AI applications in several domains (such as robotics), with tractable `mid-sized' Q-tables, still necessitates performing a large number of rapid updates. State-of-the-art FPGA implementations of QRL do not scale well with the increasing Q-Table state space. Thus, they are not efficient for such applications. In this work, we develop a novel FPGA based design of QRL and SARSA (State Action Reward State Action), scalable to large state spaces and thereby facilitating a large class of AI applications. Our architecture provides higher throughput while using significantly fewer on-chip resources. It is capable of supporting a variety of action selection policies that covers Q-Learning and variations of bandit algorithms and can be easily extended for multi-agent Q learning. Our pipelined implementation fully handles the dependencies between consecutive updates allowing it to process one sample every clock cycle. We evaluate our architecture for Q-Learning and SARSA algorithms and show that our designs achieve a high throughput of up to 180 million samples per second.

Accurate prediction of crime incidents can assist the police in better planning of prevention strategies and scheduling deployment. The problem is often studied as a spatio-temporal regression problem approached by dividing the area of interest into a grid of uniform cells, and performing regression on timeseries of each cell. We propose that changing the method of division of the area can significantly improve crime prediction. We demonstrate this using a heterogeneous division of the area obtained by our partitioning algorithm that takes into account the density of crime. We further show that existing measures do not provide a fair comparison of two methods that partition the area in two different ways. To address this severe drawback in crime prediction evaluation, we propose a novel measure which is based on optimal allocation of resources relying on the prediction and then checking the actual number of crimes that would have been avoided by the allocation. Essentially, our measure answers the question of which model would have assisted in preventing most number of actual crimes if allocation were to be done using the predicted crimes. We also prove that a greedy algorithm results in the optimal allocation resources, thus making our evaluation computationally lightweight. Experiments on real-world datasets demonstrate that heterogeneous division of the area results in improved crime prediction while drastically decreasing the number of models to be trained compared to uniform grid division.

Graph sampling is an important tool to obtain small and manageable subgraphs from large real-world graphs. Prior research has shown that Induced Edge Sampling (IES) outperforms other sampling methods in terms of the quality of subgraph obtained. Even though fast sampling is crucial for several workflows, there has been little work on parallel sampling algorithms in the past. In this paper, we present parIES - a framework for parallel Induced Edge Sampling on shared-memory parallel machines. parIES, equipped with optimized load balancing and synchronization avoiding strategies, can sample both static and streaming dynamic graphs, while achieving high scalability and parallel efficiency. We develop a lightweight concurrent hash table coupled with a space-efficient dynamic graph data structure to overcome the challenges and memory constraints of sampling streaming dynamic graphs. We evaluate parIES on a 16-core (32 threads) Intel server using 7 large synthetic and real-world networks. From a static graph, parIES can sample a subgraph with > 1.4B edges in

Accurate crime forecasting can allow law enforcement to more effectively plan their resource allocation such as patrol routes and placements. We study the effectiveness of traditional regression approaches in forecasting crime occurrences in Portland, Oregon. We divide the area of interest into equally spaced cells and investigate the spatial autocorrelation between the crime occurrence rates of neighboring cells. We also attempt to use neighboring cells' information in the regression models along with the cell's own time series to enhance the forecast results. Our results show that regression is a promising method that outperforms a moving window averaging method, especially when the future horizon to be predicted increases. However, addition of neighborhood cells decreased the quality of predictions, suggesting that spatial correlation in crime is more complex than geographical neighborhood. We also explore a possibility of connection of criminal activities and popularity of crime incidents in Portland on the Web, and discuss future directions we will take to improve crime prediction.

Often in marketing, political campaigns and social media, two competing products or opinions propagate over a social network. Studying social influence in such competing cascades scenarios enables building effective strategies for maximizing the propagation of one process by targeting the most "influential" nodes in the network. The majority of prior work however, focuses on unsigned networks where individuals adopt the opinion of their neighbors with certain probability. In real life, relationships between individuals can be positive (e.g., friend of relationship) or negative (e.g. connection between "foes"). According to social theory, people tend to have similar opinions to their friends but opposite of their foes. In this work, we study the problem of competing cascades on signed networks, which has been relatively unexplored. Particularly, we study the progressive propagation of two competing cascades in a signed network under the Independent Cascade Model, and provide an approximate analytical solution to compute the probability of infection of a node at any given time. We leverage our analytical solution to the problem of competing cascades in signed networks to develop a heuristic for the influence maximization problem. Unlike prior work, we allow the seed-set to be initialized with populations of both cascades with the end goal of maximizing the spread of one cascade. We validate our approach on several large-scale real-world and synthetic networks. Our experiments demonstrate that our influence maximization heuristic significantly outperforms state-of-the-art methods, particularly when the network is dominated by distrust relationships.

Many real life networks have an underlying bipartite structure based on which similarity between two nodes or data instances can be defined. For example, in the case of a document corpus, the similarity between a pair of documents can be assumed to arise from the words that co-occur in them, and this document-word co-occurrence relationship can be modeled as a bipartite graph. A document similarity graph can be obtained by taking a one-mode projection of the bipartite graph, which is a popular technique for studying similar networks which arise from bipartite structure. A graph-based clustering algorithm can then be applied to this projection graph to obtain clusters of documents. In this paper we study the use of one-mode projection of the document-word bipartite graph and the subsequent application of a modularity optimization algorithm to cluster the documents. In particular, we propose an alternative and faster algorithm, which works in two-steps: first, finding the documents that are easy to cluster, and then, assigning the remaining documents to the existing or new clusters. We show that the algorithms based on one-mode projections perform significantly better than traditional clustering approaches. In addition, our method has similar or better clustering performance than the most popular algorithm for modularity optimization, while also running four times faster.