Denial Constraints (DCs) are a flexible formalism to express many types of data rules, making them a widely adopted tool for many applications. This flexibility led to the development of numerous algorithms to automatically discover DCs directly from data. However, few studies have been conducted on the quality of the discovered DCs. We experimentally quantify the lack of quality in the results obtained by state-of-the-art algorithms, showing how the proportion of discovered DCs that are false is rarely below 95%. We hypothesize that the common source of these erroneous DCs stems from the adoption of the current DC validity definition. We use a statistical approach to explain the mechanism leading to these results, and propose a redefinition of DC validity properties to avoid the acceptance of false DCs. We validate this redefinition experimentally, showing that it exclusively accepts true constraints of the data, and is reliable enough to discover DCs missed by domain experts. Additionally, we provide curated sets of golden DCs for each dataset used in our study, those generated by domain experts and those discovered using our approach.

Transmission lines are crucial components of the electric power system and are exposed to several conditions that can disrupt the transmission of electrical power. In this scenario, a protection system must detect and classify a fault, for example, to enable the quick repair and restoration of a faulty line. This paper presents a method for fault type classification with two main characteristics: (1) independence of the sampling rate of the protection system; and (2) capacity to classify failures for different transmission lines than the one used to train the algorithm (generalization competence). Initially, the first post-fault cycle of the three-phase current signal is used to get the groundDetection feature, which aims to indicate the action or not of the ground in the failure. Next, maximum and minimum values are obtained from a pre-fault cycle of the current waveform to normalize the post-fault cycle by the MinMax technique, separately for each phase and individually for each example. Lastly, we get energy-based attributes together with maximum and minimum values from these normalized cycles for each phase to create the feature vector along with the groundDetection attribute. The extracted features are then used as input to the Random Forest algorithm to predict the fault type. The results demonstrate average accuracy higher than 99% for diversified simulated events for both characteristics previously mentioned. Our method also manifested the capacity to classify real fault events even being trained with synthetic examples with an accuracy of 96%.

Exploratory data analysis is the primary technique used by data scientists to extract knowledge from new data sets. This type of workload is composed of trial-and-error hypothesis-driven queries with a human in the loop. To keep up with the data scientist's productivity, the system must be capable of answering queries in interactive times. Given that these queries are highly selective multidimensional queries, multidimensional indexes are necessary to ensure low latency. However, creating the appropriate indexes is not a given due to the highly exploratory and interactive nature of such human-in-the-loop scenarios.In this paper, we identify four main objectives that are desirable for exploratory data analysis workloads: (1) low overhead over the initial queries, (2) low query variance (i.e., high robustness), (3) predictable index convergence, and (4) low total workload time. Given that not all of them can be achieved at the same time, we present three novel incremental multidimensional indexing techniques that represent three sample points on a Pareto front for this multi-objective optimization problem. (a) The Adaptive KD-Tree is designed to achieve the lowest total workload time at the expense of a higher indexing penalty for the initial queries, lack of robustness, and unpredictable convergence. (b) The Progressive KD-Tree has predictable convergence and a user-defined indexing cost for the initial queries. However, total workload time can be higher than with Adaptive KD-Trees, and per-query time still varies. (c) The Greedy Progressive KD-Tree aims at full robustness at the expense of only improving the per-query cost after full index convergence.Our extensive experimental evaluation using both synthetic and real-life data sets and workloads shows that (a) the Adaptive KD-Tree reduces total workload time by up to a factor 2 compared to the state-of-the-art, (b) the Progressive KD-Tree achieves predictable convergence with up to one order of magnitude lower initial query cost, and (c) the Greedy Progressive KDTree exhibits the lowest query variance up to three orders of magnitude lower than the state-of-the-art.

Array Database Management Systems (Array databases) support query processing over multi-dimensional data. Data storage is implemented with non-linear structures to mitigate the shortcomings of the relational model when dealing with raw binary data, such as images, time series, and others. Due to data-hungry nature of multi-dimensional data applications, array databases must ideally provide a linear speedup when using a multi-processing system. When dealing with Non-Uniform Memory Access (NUMA) machines, array databases may require massive data movement across the nodes resulting in a severe performance impact, depending on the user operation. In this paper, we analyze the performance impact of the NUMA architecture in the SAVIME and SciDB array databases running five different well-known static thread pinning strategies. Our experiments showed a maximum speedup of these different strategies by 2.49x for SAVIME and up to 1.40x for SciDB. We also observed that these static strategies only yield 48% from the potential speedup (and 26% of the energy reduction), opening a new research topic.

The detection of constraint-based errors is a critical task in many data cleaning solutions. Previous works perform the task either using traditional data management systems or using specialized systems that speed up error detection. Unfortunately, both approaches may fail to execute in a reasonable time or even exhaust the available memory in the attempt. To address the main drawbacks of previous approaches, we present the FAst Constraint-based Error DeTector (FACET) to detect violations of denial constraints (DCs). FACET uses column sketch information to organize a pipeline of special operators for DC predicates and it implements these operators using a set of efficient algorithms and data structures that adapt to different data characteristics and predicate structures. We evaluate our system on a diverse array of datasets and constraints, showing its robustness and performance gains compared to different types of DBMSs and to a specialized system.

In big data environments, measuring performance interference while sharing resources is complex and not well covered by current benchmarks and tools. Different applications can compete for the same resources (e.g., persistent storage) until they become overloaded without notice either by the benchmark or the big data system. We unveil the case when RocksDB (a big data management system) shares disk flashes among multiple tenants and how YCSB and db_bench (two state-of-the-art big data benchmarks) fail to catch performance interference. In this paper, we define a methodology to measure the problem of performance interference over time and show how RocksDB quickly degrades throughput until it turns almost inoperative while sharing the persistent storage with other tenants.

Research on data dependencies has experienced a revival as dependency violations can reveal errors in data. Several data cleaning systems use a DBMS to detect such violations. While DBMSs are efficient for some kinds of data dependencies (e.g., unique constraints), they are likely to fall short of satisfactory performance for more complex ones, such as order dependencies.

We propose a stochastic framework to evaluate the impact of missing data on the performance of predictive models. The framework allows full control of important aspects of the data set structure. These include the number and type of the input variables, the correlation between the input variables and their general predictive power, and sample size. The missing process is generated from a multivariate Bernoulli distribution, which allows us to simulate missing patterns corresponding to the MCAR, MAR and MNAR mechanisms. Although the framework may be applied to virtually all types of predictive models, in this article, we focus on the logistic regression model and choose the accuracy as the predictive measure. The simulation results show that the effects of missing data disappear for large sample sizes, as expected. On the other hand, as the number of input variables increases, the accuracy decreases mainly for binary inputs.

Big Data technologies and tools have being used for the past decade to solve several scientific and industry problems, with Hadoop/YARN becoming the “de facto” standard for these applications, although other technologies run on top of it. As any other distributed application, those big data technologies rely heavily on the network infrastructure to read and move data from hundreds or thousands of cluster nodes. Although these technologies are based on reliable and efficient distributed algorithms, there are scenarios and conditions that can generate bottlenecks and inefficiencies, i.e., when a high number of concurrent users creates data access contention. In this paper, we propose a novel network topology called Multi-Layer-Mesh and a path switching algorithm based on SDN, that can increase the performance of a big data cluster while reducing the amount of utilized resources (network equipment), in turn reducing the energy and cooling consumption. A thorough simulation-based evaluation of our algorithms shows an average improvement in performance of 31.77% and an average decrease in resource utilization of 36.03% compared to a traditional Spine-Leaf topology, in the selected test scenarios.

The rapid growth of "big-data" intensified the problem of data movement when processing data analytics: Large amounts of data need to move through the memory up to the CPU before any computation takes place. To tackle this costly problem, Processing-in-Memory (PIM) inverts the traditional data processing by pushing computation to memory with an impact on performance and energy efficiency. In this paper, we present an experimental study on processing database SIMD operators in PIM compared to current x86 processor (i.e., using AVX512 instructions). We discuss the execution time gap between those architectures. However, this is the first experimental study, in the database community, to discuss the trade-offs of execution time and energy consumption between PIM and x86 in the main query execution systems: materialized, vectorized, and pipelined. We also discuss the results of a hybrid query scheduling when interleaving the execution of the SIMD operators between PIM and x86 processing hardware. In our results, the hybrid query plan reduced the execution time by 45%. It also drastically reduced energy consumption by more than 2x compared to hardware-specific query plans.

Maintaining data consistency is known to be hard. Recent approaches have relied on integrity constraints to deal with the problem - correct and complete constraints naturally work towards data consistency. State-of-the-art data cleaning frameworks have used the formalism known as denial constraint (DC) to handle a wide range of real-world constraints. Each DC expresses a relationship between predicates that indicate which combinations of attribute values are inconsistent. The design of DCs, however, must keep pace with the complexity of data and applications. The alternative to designing DCs by hand is automatically discovering DCs from data, which is computationally expensive due to the large search space of DCs. To tackle this challenging task, we present a novel algorithm to efficiently discover DCs: DCFinder. The algorithm combines data structures called position list indexes with techniques based on predicate selectivity to efficiently validate DC candidates. Because the available data often contain errors, DCFinder is especially designed to discovering approximate DCs, i.e., DCs that may partially hold. Our experimental evaluation uses real and synthetic datasets and shows that DCFinder outperforms all the existing approximate DC discovery algorithms.

Workload-aware physical data access structures are crucial to achieve short response time with (exploratory) data analysis tasks as commonly required for Big Data and Data Science applications. Recently proposed techniques such as automatic index advisers (for a priori known static workloads) and query-driven adaptive incremental indexing (for a priori unknown dynamic workloads) form the state-of-the-art to build single-dimensional indexes for single-attribute query predicates. However, similar techniques for more demanding multi-attribute query predicates, which are vital for any data analysis task, have not been proposed, yet. In this paper, we present our on-going work on a new set of workload-adaptive indexing techniques that focus on creating multidimensional indexes. We present our proof-of-concept, the Cracking KD-Tree, an adaptive indexing approach that generates a KD-Tree based on multidimensional range query predicates. It works by incrementally creating partial multidimensional indexes as a by-product of query processing. The indexes are produced only on those parts of the data that are accessed, and their creation cost is effectively distributed across a stream of queries. Experimental results show that the Cracking KD-Tree is three times faster than creating a full KD-Tree, one order of magnitude faster than executing full scans and two orders of magnitude faster than using uni-dimensional full or adaptive indexes on multiple columns.

The recent Hybrid Memory Cube (HMC) is a smart memory which includes functional units inside one logic layer of the 3D stacked memory design. In order to execute instructions inside the Hybrid Memory Cube (HMC), the processor needs to send instructions to be executed near data, keeping most of the pipeline complexity inside the processor. Thus, control-flow and data-flow dependencies are all managed inside the processor, in such way that only update instructions are supported by the HMC. In order to solve data-flow dependencies inside the memory, previous work proposed HMC Instruction Vector Extensions (HIVE), which embeds a high number of functional units with a interlock register bank. In this work we propose HMC Instruction Prediction Extensions (HIPE), that supports predicated execution inside the memory, in order to transform control-flow dependencies into data-flow dependencies. Our mechanism focus on removing the high latency iteration between the processor and the smart memory during the execution of branches that depends on data processed inside the memory. In this paper we evaluate a balanced design of HIVE comparing to x86 and HMC executions. After we show the HIPE mechanism results when executing a database workload, which is a strong candidate to use smart memories. We show interesting trade-offs of performance when comparing our mechanism to previous work.

Big Data platforms are convoluted distributed systems which commonly comprise skill- and labour-intensive solution development to treat inherent Big Data application challenges. Several tools have been proposed to help developers and engineers to overcome the involved complexities in coordinating the execution of plenty processes/threads on multiple machines. However, no work so far has been able to combine both an accurate representation of Big Data jobs and realistic modeling of the behaviour of Big Data platforms at scale, including networking elements and data and job placement. In this paper, we propose BigDataNetSim, the first simulator which models accurately all the main components of the data movements in Big Data platforms (e.g., HDFS, YARN/MapReduce, network topologies, switching/routing protocols) in a large scale system. BigDataNetSim can serve as a valuable tool for engineering Big Data solutions, which includes set-up of systems, prototyping of jobs, and improvement of components/algorithms for Big Data platforms. We also demonstrate that BigDataNetSim can simulate a real Hadoop cluster with a high degree of accuracy in terms of data and job placements, being able to scale up to very large systems.

peer reviewed

The Brazilian government is maintaining several digital inclusion projects, providing computers and Internet connection to developing regions around the country. However, these projects can only succeed if they are constantly assessed; namely, the projects infrastructure deployment must be closely monitored and evaluated. In this paper, we introduce a system called SIMMC, which is currently monitoring and evaluating more than 4,500 computing devices from Brazilian digital inclusion projects. This system is innovative because, in addition to being used by the government for managing and expanding its projects, the collected data is also publicly available on a web page, allowing the citizens to follow the projects' deployment. We describe the SIMMC architecture, reporting some techniques used to optimize its data analysis processes, and describe how the information acquired and presented by the system has been used to enable public administration overhaul and improve efficiency on the project management, as well as its strategic use for security, theft, and defrauding.

In the parallel execution of queries in Non-Uniform Memory Access (NUMA), the operating system maps database processes/threads (i.e., workers) to the available cores across the NUMA nodes. However, this mapping results in poor cache activity with many minor page faults and slower query response time when workers and data are allocated in different NUMA nodes. The system needs to move large volumes of data around the NUMA nodes to catch up with the running workers. Our hypothesis is that we mitigate the data movement to boost cache hits and response time if we only hand out to the system the local optimum number of cores instead of all the available ones. In this paper we present a PetriNet mechanism that represents the load of the database workers for dynamically computing and allocating the local optimum number of CPU cores to tackle such load. Preliminary results show that data movement diminishes with the local optimum number of CPU cores.

Nowadays, applications that predominantly perform lookups over large databases are becoming more popular with column-stores as the database system architecture of choice. For these applications, Hybrid Memory Cubes (HMCs) can provide bandwidth of up to 320 GB/s and represents the best choice to keep the throughput for these ever increasing databases. However, even with the high available memory bandwidth and processing power, in order to achieve the peak performance, data movements through the memory hierarchy consumes an unnecessary amount of time and energy. In order to accelerate database operations, and reduce the energy consumption of the system, this paper presents the Reconfigurable Vector Unit (RVU) that enables massive and adaptive in-memory processing, extending the native HMC instructions and also increasing its effectiveness. RVU enables the programmer to reconfigure it to perform as a large vector unit or multiple small vectors units to better adjust for the application needs during different computation phases. Due to its adaptability, RVU is capable of achieving performance increase of 27 χ on average and reduce the DRAM energy consumption in 29% when compared to an x86 processor with 16 cores. Compared with the state-of-the-art mechanism capable of performing large vector operations with fixed size, inside the HMC, RVU performed up to 12% better in terms of performance and improve in 53% the energy consumption.

In this paper we focus on the aggregate query model implemented over NoSQL document-stores for read-mostly data bases. We discuss that the aggregate query model can be a good fit for read-mostly databases if the following design requirements are met: on-line time range queries, aggregates with predefined filters, frequent schema evolution and no ad-hoc. In our model, we present a composite object schema implementation over NoSQL document-stores, in which data associations are nested in a document under the same search key. We present the design choices to obtain a model adapted to our needs. Our schema is inspired by the star schema of Data Warehouses to reduce accessing data associations in many different documents and computing aggregates within the same composite. We present performance results of our empirical study over a 300 million records database that serves in production for the Ministry of Communications of Brazil. Results show the performance gains and penalties of our star composite schema when compared to the traditional multidimensional schema.

Building scalable web applications on top of NoSQL data stores is becoming common practice. Many of these data stores can easily be accessed programmatically, and do not enforce a schema. Software engineers can design the data model on the go, a flexibility that is crucial in agile software development. The typical tasks of database schema management are now handled within the application code, usually involving object mapper libraries. However, today's Integrated Development Environments (IDEs) lack the proper tool support when it comes to managing the combined evolution of the application code and of the schema. Yet simple refactorings such as renaming an attribute at the source code level can cause irretrievable data loss or runtime errors once the application is serving in production. In this demo, we present ControVol, a framework for controlled schema evolution in application development against NoSQL data stores. ControVol is integrated into the IDE and statically type checks object mapper class declarations against the schema evolution history, as recorded by the code repository. ControVol is capable of warning of common yet risky cases of mismatched data and schema. ControVol is further able to suggest quick fixes by which developers can have these issues automatically resolved.

MapReduce query processing systems translate a query statement into a query plan, consisting of a set of MapReduce jobs to be executed in distributed machines. During query translation, these query systems uniformly allocate computing resources to each job by delegating the same tuning to the entire query plan. However, jobs may implement their own collection of operators, which lead to different usage of computing resources. In this paper we propose an adaptive tuning mechanism that enables setting specific resources to each job within a query plan. Our adaptive mechanism relies on a data structure that maps jobs to tuning codes by analyzing source code and log files. This adaptive mechanism allows delegating specific resources to the query plan at runtime as the data structure hosts specific pre-computed tuning codes.

Over the last decade, large amounts of concurrent transactions have been generated from different sources, such as, Internet-based systems, mobile applications, smart-homes and cars. High-throughput transaction processing is becoming commonplace, however there is no testing technique for validating non functional aspects of DBMS under transaction flooding workloads. In this paper we propose a database state machine to represent the states of DBMS when processing concurrent transactions. The state transitions are forced by increasing concurrency of the testing workload. Preliminary results show the effectiveness of our approach to drive the system among different performance states and to find related defects.

Nowadays the large-scale systems are common-place in any kind of applications. The popularity of the web created a new environment in which the applications need to be highly scalable due to the data tsunami generated by a huge load of requests (i.e., connections and business operations). In this context, the main question is to validate how far the web applications can deal with the load generated by the clients. Load testing is a technique to analyze the behavior of the system under test upon normal and heavy load conditions. In this work we present a peer-to-peer load testing approach to isolate bottleneck problems related to centralized testing drivers and to scale up the load. Our approach was tested in a DBMS as study case and presents satisfactory results.

Testing distributed systems is challenging. Peer-to-peer (P2P) systems are composed of a high number of concurrent nodes distributed across the network. The nodes are also highly volatile (i.e., free to join and leave the system at any time). In this kind of system, a great deal of control should be carried out by the test harness, including: volatility of nodes, test case deployment and coordination. In this demonstration we present the PeerUnit framework for testing P2P systems. The original characteristic of this framework is the individual control of nodes, allowing test cases to precisely control their volatility during execution. We validated this framework through implementation and experimentation on two popular open-source P2P systems.

Developing peer-to-peer (P2P) systems is hard because they must be deployed on a high number of nodes, which can be autonomous, refusing to answer to some requests or even unexpectedly leaving the system. Such volatility of nodes is a common behavior in P2P system and can be interpreted as fault during tests.In this paper, we propose a framework for testing P2P systems. This framework is based on the individual control of nodes, allowing test cases to precisely control the volatility of nodes during execution.We validated this framework through implementation and experimentation on an open-source P2P system.

Peer-to-peer (P2P) is becoming a key technology for software development, but still lacks integrated solutions to build trust in the final software, in terms of correctness and security. Testing such systems is difficult because of the high numbers of nodes which can be volatile. In this paper, we present a framework for testing volatility of P2P systems. The framework is based on the individual control of peers, allowing test cases to precisely control the volatility of peers during execution. We validated our framework through implementation and experimentation on two open-source P2P systems. Through experimentation, we analyze the behavior of both systems on different conditions of volatility and show how the framework is able to detect implementation problems.