Floods are among the most common and devastating natural hazards, imposing immense costs on our society and economy due to their disastrous consequences. Recent progress in weather prediction and spaceborne flood mapping demonstrated the feasibility of anticipating extreme events and reliably detecting their catastrophic effects afterwards. However, these efforts are rarely linked to one another and there is a critical lack of datasets and benchmarks to enable the direct forecasting of flood extent. To resolve this issue, we curate a novel dataset enabling a timely prediction of flood extent. Furthermore, we provide a representative evaluation of state-of-the-art methods, structured into two benchmark tracks for forecasting flood inundation maps i) in general and ii) focused on coastal regions. Altogether, our dataset and benchmark provide a comprehensive platform for evaluating flood forecasts, enabling future solutions for this critical challenge. Data, code & models are shared at https://github.com/Multihuntr/GFF under a CC0 license.

Abstract Group activity recognition in video is a complex task due to the need for a model to recognise the actions of all individuals in the video and their complex interactions. Recent studies propose that optimal performance is achieved by individually tracking each person and subsequently inputting the sequence of poses or cropped images/optical flow into a model. This helps the model to recognise what actions each person is performing before they are merged to arrive at the group action class. However, all previous models rely highly on high-quality tracking and have only been evaluated using ground truth tracking information. In practice, achieving highly reliable tracking information for all individuals in a group activity video is almost impossible. We introduce an innovative deep learning-based group activity recognition approach called Rendered Pose-based Group Activity Recognition System (RePGARS), designed to tolerate unreliable tracking and pose information. Experimental results confirm that RePGARS outperforms all existing group activity recognition algorithms tested, which do not use ground truth detection and tracking information.

Abstract We introduce a novel deep learning-based group activity recognition approach called the Pose Only Group Activity Recognition System (POGARS), designed to use only tracked poses of people to predict the performed group activity. In contrast to existing approaches for group activity recognition, POGARS uses 1D CNNs to learn spatiotemporal dynamics of individuals involved in a group activity and forgo learning features from pixel data. The proposed model uses a spatial and temporal attention mechanism to infer person-wise importance and multi-task learning for simultaneously performing group and individual action classification. Experimental results confirm that POGARS achieves highly competitive results compared to state-of-the-art methods on a widely used public volleyball dataset despite only using tracked pose as input. Further, our experiments show by using pose only as input, POGARS has better generalization capabilities compared to methods that use RGB as input.

Abstract Advances in deep neural networks have led to significant improvement of object detection accuracy. However, object detection in crowded scenarios is a challenging task for neural networks since extremely overlapped objects provide fewer visible cues for a model to learn from. Further complicating the detection of overlapping objects is the fact that most object detectors produce multiple redundant detections for single objects, which are indistinguishable from detections of separate overlapped objects. Most existing works use some variant of non-maximum suppression to prune duplicate candidate bounding boxes based on their confidence scores and the amount of overlap between predicted bounding boxes. These methods are unaware of how much overlap there actually is between the objects in the image, and are therefore inclined to merge detections for highly overlapped objects. In this paper, we propose an overlap aware box selection solution that uses a predicted overlap map to help it decide which highly overlapping bounding boxes are associated with actual overlapping objects and should not be pruned. We show our solution outperforms the state-of-the-art set-NMS bounding box selection algorithm for both the crowdHuman dataset and a sports dataset.

It is of considerable interest to detect somatic mutations in paired tumor and normal sequencing data. A number of callers that are based on statistical or machine learning approaches have been developed to detect somatic small variants. However, they take into consideration only limited information about the reference and potential variant allele in both tumor and normal samples at a candidate somatic site. Also, they differ in how biological and technological noises are addressed. Hence, they are expected to produce divergent outputs. To overcome the drawbacks of existing somatic callers, we develop a deep learning-based tool called DeepSSV, which employs a convolutional neural network (CNN) model to learn increasingly abstract feature representations from the raw data in higher feature layers. DeepSSV creates a spatially oriented representation of read alignments around the candidate somatic sites adapted for the convolutional architecture, which enables it to expand to effectively gather scattered evidence. Moreover, DeepSSV incorporates the mapping information of both reference allele-supporting and variant allele-supporting reads in the tumor and normal samples at a genomic site that are readily available in the pileup format file. Together, the CNN model can process the whole alignment information. Such representational richness allows the model to capture the dependencies in the sequence and identify context-based sequencing artifacts. We fitted the model on ground truth somatic mutations and did benchmarking experiments on simulated and real tumors. The benchmarking results demonstrate that DeepSSV outperforms its state-of-the-art competitors in overall F1 score.

Distributed deep learning systems (DDLS) train deep neural network models by utilizing the distributed resources of a cluster. Developers of DDLS are required to make many decisions to process their particular workloads in their chosen environment efficiently. The advent of GPU-based deep learning, the ever-increasing size of datasets, and deep neural network models, in combination with the bandwidth constraints that exist in cluster environments require developers of DDLS to be innovative in order to train high-quality models quickly. Comparing DDLS side-by-side is difficult due to their extensive feature lists and architectural deviations. We aim to shine some light on the fundamental principles that are at work when training deep neural networks in a cluster of independent machines by analyzing the general properties associated with training deep learning models and how such workloads can be distributed in a cluster to achieve collaborative model training. Thereby we provide an overview of the different techniques that are used by contemporary DDLS and discuss their influence and implications on the training process. To conceptualize and compare DDLS, we group different techniques into categories, thus establishing a taxonomy of distributed deep learning systems.

Observing eye movement is a direct way to analyse human’s attention. Eye movement patterns in normal environment have been widely investigated. In virtual reality (VR) environment, previous studies of eye movement patterns are mainly based on content-unrelated influential factors. Considering this issue, in this paper, a novel content-related factor is studied. One crucial kind of region of interest (ROI), namely vision-penetrable entrance, is chosen to analyse eye movement pattern differences. The results suggest that users show more interest in vision-penetrable entrances than in other regions. Furthermore, this kind of difference is identified as higher average density of fixation. As far as we know, this paper is the first attempt to study specific types of ROI in virtual reality environments. The method utilised in this paper can be applied in other ROI analysis.

Automatically determining three-dimensional human pose from monocular RGB image data is a challenging problem. The two-dimensional nature of the input results in intrinsic ambiguities which make inferring depth particularly difficult. Recently, researchers have demonstrated that the flexible statistical modelling capabilities of deep neural networks are sufficient to make such inferences with reasonable accuracy. However, many of these models use coordinate output techniques which are memory-intensive, not differentiable, and/or do not spatially generalise well. We propose improvements to 3D coordinate prediction which avoid the aforementioned undesirable traits by predicting 2D marginal heatmaps under an augmented soft-argmax scheme. Our resulting model, MargiPose, produces visually coherent heatmaps whilst maintaining differentiability. We are also able to achieve state-of-the-art accuracy on publicly available 3D human pose estimation data.

Many distributed deep learning systems have been published over the past few years, often accompanied by impressive performance claims. In practice these figures are often achieved in high performance computing (HPC) environments with fast InfiniBand network connections. For average deep learning practitioners this is usually an unrealistic scenario, since they cannot afford access to these facilities. Simple re-implementations of algorithms such as EASGD [1] for standard Ethernet environments often fail to replicate the scalability and performance of the original works [2] . In this paper, we explore this particular problem domain and present MPCA SGD, a method for distributed training of deep neural networks that is specifically designed to run in low-budget environments. MPCA SGD tries to make the best possible use of available resources, and can operate well if network bandwidth is constrained. Furthermore, MPCA SGD runs on top of the popular Apache Spark [3] framework. Thus, it can easily be deployed in existing data centers and office environments where Spark is already used. When training large deep learning models in a gigabit Ethernet cluster, MPCA SGD achieves significantly faster convergence rates than many popular alternatives. For example, MPCA SGD can train ResNet-152 [4] up to 5.3x faster than state-of-the-art systems like MXNet [5] , up to 5.3x faster than bulk-synchronous systems like SparkNet [6] and up to 5.3x faster than decentral asynchronous systems like EASGD [1] .

Transforming multi-dimensional data into a one-dimensional sequence using space-filling curves such as the Hilbert curve, the Gray curve, and the Z-curve has been studied extensively. These techniques are not sensitive to data or workload skewness, however, in practice, user-access patterns and data distributions are often very skewed in high dimensional space. It is desirable to produce a one-dimensional sequence which keeps the multi-dimensional grid cells that are queried together close to each other. This generates sequences with higher spatial locality. We propose a workload-based approach to produce one-dimensional ordering from multi-dimensional data in this paper. An extensive experimental evaluation suggests that our approach produces a high quality ordering sequence which outperforms the existing state-of-the-art Hilbert curve by a factor of 4.84, the Gray curve by a factor of 6.66, and the Z-curve by a factor of 7.26 for the number of subsequences used to answer a query; and for IO time, it outperforms the Hilbert curve by a factor of 2.20, the Gray curve by a factor of 2.25, and the Z-curve by 2.38.

We define and study Euclidean and spatial network variants of a new path finding problem: given a set of safe zones, find paths that minimize the distance traveled outside the safe zones. In this problem, the entire space with the exception of the safe zones is unsafe, but passable, and it differs from problems that involve unsafe regions to be strictly avoided. As a result, existing algorithms are not effective solutions to the new problem. To solve the Euclidean variant, we devise a transformation of the continuous data space with safe zones into a discrete graph upon which shortest path algorithms apply. A naïve transformation yields a very large graph that is expensive to search. In contrast, our transformation exploits properties of hyperbolas in the Euclidean space to safely eliminate graph edges, thus improving performance without affecting the shortest path results. To solve the spatial network variant, we propose a different graph-to-graph transformation that identifies critical points that serve the same purpose as do the hyperbolas, thus avoiding the creation of extraneous edges. This transformation can be extended to support a weighted version of the problem, where travel in safe zones has non-zero cost. We conduct extensive experiments using both real and synthetic data. The results show that our approaches outperform baseline approaches by more than an order of magnitude in graph construction time, storage space and query response time.

The need to store vast amounts of trajectory data becomes more problematic as GPS-based tracking devices become increasingly prevalent. There are two commonly used approaches for compressing trajectory data. The first is the line generalisation approach which aims to fit the trajectory using a series of line segments. The second is to store the initial data point and then store the remaining data points as a sequence of successive deltas. The line generalisation approach is only effective when given a large error margin, and existing delta compression algorithms do not permit lossy compression. Consequently there is an uncovered gap in which users expect a good compression ratio by giving away only a small error margin. This paper fills this gap by extending the delta compression approach to allow users to trade a small maximum error margin for large improvements to the compression ratio. In addition, alternative techniques are extensively studied for the following two key components of any delta-based approach: predicting the value of the next data point and encoding leading zeros. We propose a new trajectory compression system called Trajic based on the results of the study. Experimental results show that Trajic produces 1.5 times smaller compressed data than a straight-forward delta compression algorithm for lossless compression and produces 9.4 times smaller compressed data than a state-of-the-art line generalisation algorithm when using a small maximum error bound of 1 meter.

A well-studied query type on moving objects is the continuous range query. An interesting and practical situation is that instead of being continuously evaluated, the query may be evaluated at different degrees of continuity, e.g. every 2 seconds (close to continuous), every 10 minutes or at irregular time intervals (close to snapshot). Furthermore, the range query may be stacked under predicates applied to the returned objects. An example is the count predicate that requires the number of objects in the range to be at least Y. The conjecture is that these two practical considerations can help reduce communication costs. We propose a safe region-based solution that exploits these two practical considerations. An extensive experimental study shows that our solution can reduce communication costs by a factor of 9.5 compared to an existing state-of-the-art system.

In this paper, we study the problem of efficient spatiotemporal indexing of moving objects. In order to reduce the frequency of object location updates, a linear motion model is used to model the near future location of moving objects. A number of existing spatiotemporal indexes have already been proposed for indexing these models. However, these indexes are either designed to offer high query performance or high update performance. Therefore, they are all ill suited to handle situations where both queries and updates arrive at a high rate. In this paper, we propose the SeTPR*-tree which extends the TPR*-tree to more efficiently use a limited-sized RAM buffer for processing queries in batches and rapidly arriving updates. We provide both theoretical and empirical evidence of the effectiveness of the SeTPR*-tree in improving query and update performance. We have conducted extensive experiments using a recognized spatiotemporal benchmark on a solid state drive. The SeTPR*-tree simultaneously outperforms the best tested index optimized for queries by up to a factor of 5.6 for query I/O and outperforms the best tested index for updates by up to a factor of 11.5 for update I/O.

There exists a need for high performance, read-only main-memory database systems for OLAP-style application scenarios. Most of the existing works in this area are centered around the domain of column-store databases, which are particularly well suited to OLAP-style scenarios and have been shown to overcome the memory bottleneck issues that have been found to hinder the more traditional row-store database systems. One of the main database operations these systems are focused on optimizing is the JOIN operation. However, all these existing systems use join algorithms that are designed with the unrealistic assumption that there is unlimited temporary memory available to perform the join. In contrast, we propose a Memory Constrained Join algorithm (MCJoin) which is both high performing and also performs all of its operations within a tight given memory constraint. Extensive experimental results show that MCJoin outperforms a naive memory constrained version of the state-of-the-art Radix-Clustered Hash Join algorithm in all of the situations tested, with margins of up to almost 500%.

There have been intense research interests in moving object indexing in the past decade. However, existing work did not exploit the important property of skewed velocity distributions. In many real world scenarios, objects travel predominantly along only a few directions. Examples include vehicles on road networks, flights, people walking on the streets, etc. The search space for a query is heavily dependent on the velocity distribution of the objects grouped in the nodes of an index tree. Motivated by this observation, we propose the velocity partitioning (VP) technique, which exploits the skew in velocity distribution to speed up query processing using moving object indexes. The VP technique first identifies the "dominant velocity axes (DVAs)" using a combination of principal components analysis (PCA) and k-means clustering. Then, a moving object index (e.g., a TPR-tree) is created based on each DVA, using the DVA as an axis of the underlying coordinate system. An object is maintained in the index whose DVA is closest to the object's current moving direction. Thus, all the objects in an index are moving in a near 1-dimensional space instead of a 2-dimensional space. As a result, the expansion of the search space with time is greatly reduced, from a quadratic function of the maximum speed (of the objects in the search range) to a near linear function of the maximum speed. The VP technique can be applied to a wide range of moving object index structures. We have implemented the VP technique on two representative ones, the TPR*-tree and the B x -tree. Extensive experiments validate that the VP technique consistently improves the performance of those index structures.

We propose and study a new type of facility location selection query, the top-k most influential location selection query. Given a set M of customers and a set F of existing facilities, this query finds k locations from a set C of candidate locations with the largest influence values, where the influence of a candidate location c (c in C) is defined as the number of customers in M who are the reverse nearest neighbors of c. We first present a naive algorithm to process the query. However, the algorithm is computationally expensive and not scalable to large datasets. This motivates us to explore more efficient solutions. We propose two branch and bound algorithms, the Estimation Expanding Pruning (EEP) algorithm and the Bounding Influence Pruning (BIP) algorithm. These algorithms exploit various geometric properties to prune the search space, and thus achieve much better performance than that of the naive algorithm. Specifically, the EEP algorithm estimates the distances to the nearest existing facilities for the customers and the numbers of influenced customers for the candidate locations, and then gradually refines the estimation until the answer set is found, during which distance metric based pruning techniques are used to improve the refinement efficiency. BIP only estimates the numbers of influenced customers for the candidate locations. But it uses the existing facilities to limit the space for searching the influenced customers and achieve a better estimation, which results in an even more efficient algorithm. Extensive experiments conducted on both real and synthetic datasets validate the efficiency of the algorithms.

The increasing popularity of flash memory means more database systems will run on flash memory in the future. One of the most important database operations is the external sort. Hence, this paper is focused on studying the problem of efficient external sorting on flash memory. In contrast to most previous work, we target the situation where previously sorted data have become progressively unsorted due to data updates. Accordingly, we call this ‘partially’ sorted data. We focus on re-sorting partially sorted data by taking advantage of the partial sorted nature of the data to speed up the run generation phase of the traditional external merge sort. We do this by finding ‘naturally occurring’ page runs in the partially sorted data. Our algorithm can perform up to a factor of 1024 less write IO compared with a traditional external merge sort during the run generation phase. We map the problem of finding naturally occurring runs into the shortest distance problem in a directed acyclic graph (DAG). Accordingly, we propose an optimal solution to the problem using the well-known DAG-Shortest-Paths algorithm. However, we found that the optimal solution was too slow for even moderate-sized data sets and accordingly propose a fast heuristic solution that—we experimentally show—finds a high percentage of page runs using a minimum of computational overhead. Experiments using both real and synthetic data sets show that our heuristic algorithm can halve the external sorting time when compared with three likely competing external sorting algorithms.

This paper explores efficient ways to use flash memory to store online analytical processing (OLAP) data. The particular type of queries considered are range queries using the aggregate functions SUM, COUNT and AVG. The asymmetric cost of reads and writes for flash memory gives higher importance to how updates are handled in a flash memory environment. A popular data structure used for answering OLAP range-sum queries is the prefix sum cube. It allows the range-sum query to be answered in constant time. However, updating the prefix sum cube is very expensive. To overcome this, the Δ-tree was proposed by Chun et al. (Dynamic update cube for range-sum queries. Proc. Int. Conf. Very Large Data Bases, San Francisco, CA, USA, 2001, pp. 521–530. Morgan Kaufmann Publisher). The Δ-tree stores all updates to the prefix sum cube in a separate r-tree. This approach worked well for the hard disk where in-place updates are relatively cheap. However, for flash memory where in-place updates are very expensive, the Δ-tree performs very poorly. We take a four-pronged approach to overcome the problem of expensive in-place updates. The first is efficient caching of updates in RAM. The second is writing out whole trees from RAM to flash memory instead of incrementally updating a disk resident tree. The third is we allow users to trade bounded amounts of accuracy for less updates via lossy compression. Finally, we use a quadtree index structure instead of the R-tree. We prove that the quadtree compression problem is NP-complete. A greedy heuristic is proposed to find near optimal solutions in polynomial time. Various experiments were conducted to compare the proposed algorithms against the existing Δ-tree. The results show that our algorithms consistently outperformed Δ-tree by factors of between 10 and 100. This demonstrates the importance of designing flash memory customized algorithms for OLAP range queries. In addition, among our algorithms, the error bound solutions with a small error bound setting significantly outperform the accurate solution in terms of performance for a variety of parameter settings. This indicates that the error bound algorithms offer users an effective trade-off between execution time and accuracy.

Location information is necessarily uncertain when objects are constantly moving. The cost can be high to maintain precise locations at the application server for all the objects while many applications may not need all the costly precision that is technically possible. An interesting question is how to reduce the cost associated with obtaining precise locations while satisfying user requirements. A general technique of maintaining uncertain location information is using a “safe-region” for each object, a region in which the object must be in but it is not known where it exactly is. Location updates are only needed when the object moves out of its safe region, or a user query needs more precise information to answer. This paper uses the same idea for finding an object that is likely to be the nearest neighbor of a query location, a query type termed herein Probabilistic one-of Nearest Neighbor (PoNN) query. An algorithm is described that first tries to answer a given PoNN query with the known safe regions. If this fails, the algorithm selects some objects to ask for their precise locations (called location exposures). An innovative method is used by the algorithm in deciding which objects to expose in order to reduce the total number of exposures. The innovation includes an information gain formulation of the problem and careful probability calculations. The paper details the algorithm and shows an experimental study of the algorithm against more straightforward solutions in a simulated environment.

Embedded devices such as personal digital assistants (PDAs), pocket PCs, palmtops, and handheld PCs are increasingly using flash memory for the permanent storage of databases. Databases achieve their fast data access speeds by using a memory manager that manages data pages in a memory buffer. The buffer manager uses a page replacement policy to evict pages when the memory buffer is full. An eviction of a dirty page will result in a write to flash memory. Unfortunately, writing to flash memory consumes a lot more energy than reading. Much of the previous work in page replacement policies has focused on reducing the number of page reads rather than writes. One of the few existing works to consider the effects of flash memory's hardware constraints for database design is Lee et. al.'s in-page Logging (IPL) approach [Lee and Moon 2007]. They demonstrated IPL significantly outperforms traditional disk-based databases when running on flash memory. However, they do not consider the energy efficiency of their approach in terms of the behavior of the page replacement policy. This article addresses this issue by presenting the Multi-Buffer Manager, which is customized for flash databases that use a logging-based approach for managing updates such as IPL. Extensive experiments show the page replacement policy used plays a pivotal role in the performance of the flash database system. In particular, our Multi-Buffer Manager can reduce energy consumption by up to 40% compared to the state-of-the-art clean first flash-based buffer replacement policy (CFLRU).

This paper explores the effect that changing access patterns has on the performance of database management systems. Changes in access patterns play an important role in determining the efficiency of key performance optimization techniques, such as dynamic clustering, prefetching, and buffer replacement. However, all existing benchmarks or evaluation frameworks produce static access patterns in which objects are always accessed in the same order repeatedly. Hence, we have proposed the Dynamic Evaluation Framework (DEF) that simulates access pattern changes using configurable styles of change. DEF has been designed to be open and fully extensible (e.g., new access pattern change models can be added easily). In this paper, we instantiate DEF into the Dynamic Object Evaluation Framework (DoEF) which is designed for object databases, that is, object-oriented or object-relational databases, such as multimedia databases or most XML databases. The capabilities of DoEF have been evaluated by simulating the execution of four different dynamic clustering algorithms. The results confirm our analysis that flexible conservative reclustering is the key in determining a clustering algorithm’s ability to adapt to changes in access pattern. These results show the effectiveness of DoEF at determining the adaptability of each dynamic clustering algorithm to changes in access pattern in a simulation environment. In a second set of experiments, we have used DoEF to compare the performance of two real-life object stores: Platypus and SHORE. DoEF has helped to reveal the poor swapping performance of Platypus.

Query optimizers in object-relational database management systems typically require users to provide the execution cost models of user-defined functions (UDFs). Despite this need, however, there has been little work done to provide such a model. The existing approaches are static in that they require users to train the model a priori with pregenerated UDF execution cost data. Static approaches can not adapt to changing UDF execution patterns and thus degrade in accuracy when the UDF executions used for generating training data do not reflect the patterns of those performed during operation. This article proposes a new approach based on the recent trend of self-tuning DBMS by which the cost model is maintained dynamically and incrementally as UDFs are being executed online. In the context of UDF cost modeling, our approach faces a number of challenges, that is, it should work with limited memory, work with limited computation time, and adjust to the fluctuations in the execution costs (e.g., caching effect). In this article, we first provide a set of guidelines for developing techniques that meet these challenges, while achieving accurate and fast cost prediction with small overheads. Then, we present two concrete techniques developed under the guidelines. One is an instance-based technique based on the conventionalk-nearest neighbor (KNN) technique which uses a multidimensional index like the R*-tree. The other is a summary-based technique which uses the quadtree to store summary values at multiple resolutions. We have performed extensive performance evaluations comparing these two techniques against existing histogram-based techniques and the KNN technique, using both real and synthetic UDFs/data sets. The results show our techniques provide better performance in most situations considered.