Search

Event logs that are recorded by information systems provide a valuable starting point for the analysis of processes in various domains, reaching from healthcare, through logistics, to e-commerce. Specifically, behavioral patterns discovered from an event log enable operational insights, even in scenarios where process execution is rather unstructured and shows a large degree of variability. While such behavioral patterns capture frequently recurring episodes of a process’ behavior, they are not limited to sequential behavior but include notions of concurrency and exclusive choices. Existing algorithms to discover behavioral patterns are context-agnostic, though. They neglect the context in which patterns are observed, which severely limits the granularity at which behavioral regularities are identified. In this paper, we therefore present an approach to discover contextual behavioral patterns. Contextual patterns may be frequent solely in a certain partition of the event log, which enables fine-granular insights into the aspects that influence the conduct of a process. Moreover, we show how to analyze the discovered contextual behavioral patterns in terms of causal relations between context information and the patterns, as well as correlations between the patterns themselves. A complete analysis methodology leveraging all the tools presented in the paper and supplemented by interpretations guidelines is also provided. Finally, experiments with real-world event logs demonstrate the effectiveness of our techniques in obtaining fine-granular process insights. [ABSTRACT FROM AUTHOR]

Increasingly, individuals and companies adopt a cloud service provider as a primary data and IT infrastructure platform. The remote access of the data inevitably brings the issue of trust. Data encryption is necessary to keep sensitive information secure and private on the cloud. Yet adversaries can still learn valuable information regarding encrypted data by observing data access patterns. To solve such problem, Oblivious RAMs (ORAMs) are proposed to completely hide access patterns. However, most ORAM constructions are expensive and not suitable to deploy in a database for supporting query processing over large data. Furthermore, an ORAM processes queries synchronously, hence, does not provide high throughput for concurrent query processing. In this article, we design a practical oblivious query processing framework to enable efficient query processing over a cloud database. In particular, we focus on processing multiple range and $k$ k NN queries asynchronously and concurrently with high throughput. The key idea is to integrate indices into ORAM which leverages a suite of optimization techniques (e.g., oblivious batch processing and caching). The effectiveness and efficiency of our oblivious query processing framework is demonstrated through extensive evaluations over large datasets. Our construction shows an order of magnitude speedup in comparison with other baselines. [ABSTRACT FROM AUTHOR]

Many real-world datasets are given in the stream of entity-identifier pairs, and measuring data distribution on these datasets is fundamental for applications such as privacy protection. In this paper, we study the problem of computing the cumulative distribution for different cardinalities (i.e., the number of distinct entities owning the same identifier). However, previous sketch-based methods cost large memory space especially when there are a large number of identifiers, and sampling-based methods require much time for cardinality estimation. A recent work KHyperLogLog combines both sketch and sampling methods but it is wasteful to separately build a HyperLogLog sketch of large size for identifiers with small cardinalities. To address these challenges, we propose a memory-efficient method EV-HLL, which designs a shared structure to store all sampled identifiers and their entities and utilizes additional sketches to track value updates during the sampling procedure. Meanwhile, EV-HLL provides real-time unbiased estimations according to value changes whenever a new entity-identifier pair arrives. We evaluate the performance of EV-HLL and other state-of-the-arts on real-world available datasets. Experimental results demonstrate that comparing to other methods, EV-HLL effectively reduces their memory usage with the same estimation accuracy and has higher accuracy with the same memory usage. [ABSTRACT FROM AUTHOR]

Time series similarity computation is a fundamental primitive that underpins many time series data analysis tasks. However, many existing time series similarity measures have a high computation cost. While there has been much research effort for reducing the computational cost, such effort is usually specific to one similarity measure. We propose NeuTS (Neural metric learning for Time Series) to accelerate time series similarity computation in a generic fashion. NeuTS computes the similarity of a given time series pair in linear time and generic to handle any existing similarity measures. NeuTS samples a number of seed time series from the given database, and then uses their pair-wise similarities as guidance to approximate the similarity function with a neural metric learning framework. NeuTS features two novel modules to achieve accurate approximation of the similarity function: (1) a local attention memory module that augments existing recurrent neural networks for time series encoding; and (2) a distance-weighted ranking loss that effectively transcribes information from the seed-based guidance. With these two modules, NeuTS can yield high accuracies and fast convergence rates even if the training data is small. Our experiments with five real-life datasets and four similarity measures (Fréchet, Hausdorff, ERP and DTW) show that NeuTS outperforms baselines consistently and significantly. Specifically, it achieves over 80 percent accuracies in most settings, while obtaining 50x-1000x speedup over bruteforce methods and 3x-350x speedup over approximate algorithms for top-k similarity search. [ABSTRACT FROM AUTHOR]

Besides the conventional schema-oriented tasks, data dependencies are recently revisited for data quality applications, such as violation detection, data repairing and record matching. To address the variety and veracity issues of big data, data dependencies have been extended as data quality rules to adapt to various data types, ranging from (1) categorical data with equality relationships to (2) heterogeneous data with similarity relationships, and (3) numerical data with order relationships. In this survey, we briefly review the recent proposals on data dependencies categorized into the aforesaid types of data. In addition to (a) the concepts of these data dependency notations, we investigate (b) the extension relationships between data dependencies, e.g., conditional functional dependencies (CFDs) extend the conventional functional dependencies (FDs). It forms a family tree of extensions, mostly rooted in FDs, helping us understand the expressive power of various data dependencies. Moreover, we summarize (c) the discovery of dependencies from data, since data dependencies are often unlikely to be manually specified in a traditional way, given the huge volume and high variety of big data. We further outline (d) the applications of the extended data dependencies, in particular in data quality practice. It guides users to select proper data dependencies with sufficient expressive power and reasonable discovery cost. Finally, we conclude with several directions of future studies on the emerging data. [ABSTRACT FROM AUTHOR]

Data outsourcing is a cost-effective solution for data owners to tackle issues such as large volumes of data, huge number of users, and intensive computation needed for data analysis. They can simply upload their databases to a cloud and let it perform all management works, including query processing. One problem with this service model is how query issuers can verify the query results they receive are indeed correct. This concern is legitimate because, as a third party, clouds may not be fully trustworthy, and as a large data center, clouds are ideal targets for hackers. There has been significant work on query result verification, but most consider only simple queries where query results can be attained by checking the raw data against the query conditions directly. In this paper, we consider the problem of enabling users to verify the correctness of the results of analytic queries. Unlike simple queries, analytic queries involve ranking functions to score a database, which makes it difficult to build data structures for verification purposes. We propose two approaches, namely one-signature and multi-signature, and show that they work well on three representative types of analytic queries, including top-k, range, and KNN queries, through both analysis and experiments. [ABSTRACT FROM AUTHOR]

Reorganizing bus frequencies to cater for the actual travel demands can significantly save the cost of the public transport system. Many, if not all, previous studies formulate this as a bus frequency optimization problem that tries to minimize passengers’ average waiting time. On the other hand, many investigations have confirmed that the user satisfaction drops faster as the waiting time increases. Consequently, this paper studies the bus frequency optimization problem considering the user satisfaction. Specifically, for the first time to our best knowledge, we study how to schedule the buses such that the total number of passengers who could receive their bus services within the waiting time threshold can be maximized. We propose two variants of the problem, FAST and FASTCO, to cater for different application needs and prove that both are NP-hard. To solve FAST effectively and efficiently, we first present an index-based $(1-1/e)$ (1 - 1 / e) -approximation algorithm. By exploiting the locality property of routes in a bus network, we further propose a partition-based greedy method that achieves a $(1-\rho)(1-1/e)$ (1 - ρ) (1 - 1 / e) approximation ratio. Then we propose a progressive partition-based greedy method to further boost the efficiency while achieving a $(1-\rho)(1-1/e-\varepsilon)$ (1 - ρ) (1 - 1 / e - ɛ) approximation ratio. For the FASTCO problem, two greedy-based heuristic methods are proposed. Experiments on a real city-wide bus dataset in Singapore have been conducted to verify the efficiency, effectiveness, and scalability of our methods in addressing FAST and FASTCO respectively. [ABSTRACT FROM AUTHOR]

Due to recent explosion of data volume and velocity, a new array of lightweight key-value stores have emerged to serve as alternatives to traditional databases. The majority of these storage engines, however, sacrifice their read performance in order to cope with write throughput by avoiding random disk access when writing a record in favor of fast sequential accesses. But, the boundary between sequential versus random access is becoming blurred with the advent of solid-state drives (SSDs). In this work, we propose our new key-value store, LogStore, optimized for hybrid storage architectures. Additionally, introduce a novel cost-based data staging model based on log-structured storage, in which recent changes are first stored on SSDs, and pushed to HDD as it ages, while minimizing the read/write amplification for merging data from SSDs and HDDs. Furthermore, we take a holistic approach in improving both the read and write performance by dynamically optimizing the data layout, such as deferring and reversing the compaction process, and developing an access strategy to leverage the strengths of each available medium in our storage hierarchy. Lastly, in our extensive evaluation, we demonstrate that LogStore achieves up to 6x improvement in throughput/latency over LevelDB, a state-of-the-art key-value store. [ABSTRACT FROM AUTHOR]

Since inaccuracies commonly exist in many applications, data uncertainty has become an important problem in database systems. To deal with data uncertainty, probabilistic databases can be used to store uncertain data, and querying facilities are provided to yield answers with confidence. However, the results from a query or mining process may not be reliable when the uncertainty propagates in the systems. In this paper, we leverage the power of crowdsourcing by designing a set of Human Intelligence Tasks, or HITs in short, to ask a crowd to improve the quality of uncertain data. In particular, we consider crowds consists of workers with diverse accuracy rates when answering the HITs. We design solutions to maximize the data quality with minimal number of HITs. There are two obstacles for this non-trivial optimization, which lead to very high computational cost for selecting the optimal set of HITs. First, members of a crowd may return incorrect answers with different probabilities. Second, the HITs decomposed from uncertain data are often correlated. We have addressed these challenges in this paper by designing an effective approximation algorithm and an efficient heuristic solution, especially for crowds with diverse individual accuracy rates. To further improve the efficiency, we derive tight lower and upper bounds for effective filtering and estimation. Extensive experiments on both a simulated crowd and a real crowdsourcing platform are conducted to evaluate our solutions. [ABSTRACT FROM AUTHOR]

The increasing amount of graph-structured data catalyzes analytics over graph databases using semantic queries. Motivated by the ubiquity of commercial cloud platforms, data owners are willing to store their graph databases remotely. However, data privacy has emerged as a widespread concern since the cloud platforms are not fully trusted. One viable solution is to encrypt sensitive data before outsourcing, which inevitably hinders data retrieval. To enable queries over encrypted data, searchable symmetric encryption (SSE) has been introduced. Yet, the most well-studied class of SSE schemes focuses on retrieving textual files given keywords, which cannot be applied to graph databases directly. This paper extends our preliminary work (FC’17) and proposes GraphShield, a structured encryption scheme for graphs. Beyond shortest distance queries, GraphShield can support other classic graph-based queries (e.g., maximum flow) and more complicated analytics (e.g., PageRank). Technically, we incorporate a suite of (efficient) cryptographic primitives and tailor some extra secure protocols for facilitating graph analytics. Our scheme also allows updates on the encrypted graph with forward privacy guaranteed. We formalize the security model and prove the adaptive security with reasonable leakage. Finally, we implement our scheme on various real-world datasets, and the experiment results demonstrate its practicality and scalability. [ABSTRACT FROM AUTHOR]

Real-life graph datasets extracted from the Web are inevitably full of incompleteness, conflicts, and redundancies, so graph data cleaning shows its necessity. Although rules like data dependencies have been widely studied in relational data repairing, very few works exist to repair graph data. In this article, we introduce a repairing semantics for graphs, called Graph-Repairing Rules (${\sf GRR}$ GRR s). This semantics can capture the incompleteness, conflicts, and redundancies in graphs and indicate how to correct these errors. However, this graph repairing semantics can only repair the graphs strictly isomorphic to the rule patterns, which decreases the utility of the rules. To overcome this shortcoming, we further propose a flexible rule-based graph repairing semantics (called $\delta$ δ -GRR). We study three fundamental problems associated with both ${\sf GRR}$ GRR s and $\delta$ δ -GRRs, consistency, implication, and termination, which show whether a given set of rules make sense. Repairing the graph data using ${\sf GRR}$ GRR s or $\delta$ δ -GRRs involves a problem of finding isomorphic subgraphs of the graph data, which is NP-complete. To efficiently circumvent the complex calculation of subgraph isomorphism, we design a decomposition-and-join strategy to solve this problem. Extensive experiments on real datasets show that our two graph repairing semantics and corresponding repairing algorithms can effectively and efficiently repair real-life graph data. [ABSTRACT FROM AUTHOR]

Quasi-periodic time series (QTS) exists widely in the real world, and it is important to detect the anomalies of QTS. In this paper, we propose an automatic QTS anomaly detection framework (AQADF) consisting of a two-level clustering-based QTS segmentation algorithm (TCQSA) and a hybrid attentional LSTM-CNN model (HALCM). TCQSA first automatically splits the QTS into quasi-periods which are then classified by HALCM into normal periods or anomalies. Notably, TCQSA integrates a hierarchical clustering and the k-means technique, making itself highly universal and noise-resistant. HALCM hybridizes LSTM and CNN to simultaneously extract the overall variation trends and local features of QTS for modeling its fluctuation pattern. Furthermore, we embed a trend attention gate (TAG) into the LSTM, a feature attention mechanism (FAM) and a location attention mechanism (LAM) into the CNN to finely tune the extracted variation trends and local features according to their true importance to achieve a better representation of the fluctuation pattern of the QTS. On four public datasets, HALCM exceeds four state-of-the-art baselines and obtains at least 97.3 percent accuracy, TCQSA outperforms two cutting-edge QTS segmentation algorithms and can be applied to different types of QTSs. Additionally, the effectiveness of the attention mechanisms is quantitatively and qualitatively demonstrated. [ABSTRACT FROM AUTHOR]

Conversational systems have recently attracted significant attention. Both the research community and industry believe that it will exert huge impact on human-computer interaction, and specifically, the IR/RecSys community has begun to explore Conversational Recommendation. In real-life scenarios, such systems are often urgently needed in helping users accomplishing different tasks under various situations. However, existing works still face several shortcomings: (1) Most efforts are largely confined in single task setting. They fall short of hands in handling tasks across domains. (2) Aside from soliciting user preference from dialogue history, a conversational recommender naturally has access to the back-end data structure which should be fully leveraged to yield good recommendations. In this paper, we thus present a Topic-guided Conversational Recommender (TCR) which is specifically designed for the multi-domain setting. It augments the sequence-to-sequence (seq2seq) models with a neural latent topic component to better guide the response generation. To better leverage the dialogue history and the back-end data structure, we adopt a graph convolutional network (GCN) to model the relationships between different recommendation candidates while also capture the match between candidates and the dialogue history. We then seamlessly combine these two parts with the idea of pointer networks. We perform extensive evaluation on a large-scale task-oriented multi-domain dialogue dataset and the results show that our method achieves superior performance as compared to a wide range of baselines. [ABSTRACT FROM AUTHOR]

Flash-based Solid State Drives (SSDs) have proved to be ideal devices that support embedded transaction protocols inside SSDs. Existing embedded transaction protocols in SSDs effectively improve transaction throughput, but still incur high transaction overhead and long recovery time. While it is reasonable to provide a small-capacity non-volatile (NVM-based) disk cache in the SSDs, in this paper, we propose a new embedded transaction protocol called Non-volatile Cache Transaction (NVCTX). NVCTX reduces transaction overhead and provides fast recovery by leveraging the small-capacity NVM-based disk cache from two aspects. First, we store transactional metadata, which is of small amount but is frequently accessed, in the NVM-based disk cache rather than in the flash memory. Second, we introduce two techniques, i.e., a dynamic allocation algorithm and a hybrid storing method, to improve the performance when the capacity of the NVM-based disk cache is very limited. We have implemented NVCTX on a real hardware board called Cosmos+ FPGA platform, and modified ext4 file system and NVMe (Non-Volatile Memory express) driver to be compatible with the transactional interfaces provided by NVCTX. For comparison, we also implement SCC, BPCC, WAL, and X-FTL protocols in the firmware of Cosmos+ FPGA platform. Evaluations using DBMS (Database Management System) and file system workloads show that, compared to four typical transaction protocols (SCC, BPCC, WAL, and X-FTL), NVCTX improves transaction throughput by up to 136.5, 9.4, 131.6 and 29.9 percent, reduces write traffic to flash memory by up to 42.8, 4.1, 62.4, 31.2 percent, lowers garbage collection overhead by up to 93.2, 63, 66.5, 22.1 percent, and shortens recovery time to 1/2574, 1/2559, 1/95 and 1/2 respectively compared with SCC, BPCC, WAL, and X-FTL. [ABSTRACT FROM AUTHOR]

Database and Artificial Intelligence (AI) can benefit from each other. On one hand, AI can make database more intelligent (AI4DB). For example, traditional empirical database optimization techniques (e.g., cost estimation, join order selection, knob tuning, index and view selection) cannot meet the high-performance requirement for large-scale database instances, various applications and diversified users, especially on the cloud. Fortunately, learning-based techniques can alleviate this problem. On the other hand, database techniques can optimize AI models (DB4AI). For example, AI is hard to deploy in real applications, because it requires developers to write complex codes and train complicated models. Database techniques can be used to reduce the complexity of using AI models, accelerate AI algorithms and provide AI capability inside databases. Thus both DB4AI and AI4DB have been extensively studied recently. In this article, we review existing studies on AI4DB and DB4AI. For AI4DB, we review the techniques on learning-based configuration tuning, optimizer, index/view advisor, and security. For DB4AI, we review AI-oriented declarative language, AI-oriented data governance, training acceleration, and inference acceleration. Finally, we provide research challenges and future directions. [ABSTRACT FROM AUTHOR]

Data quality plays a key role in big data management today. With the explosive growth of data from a variety of sources, the quality of data is faced with multiple problems. Motivated by this, we study the multiple data cleaning on incompleteness and inconsistency with currency reasoning and determination in this paper. We introduce a 4-step framework, named ${\sf Imp3C}$ Imp 3 C , for errors detection and quality improvement in incomplete and inconsistent data without timestamps. We achieve an integrated currency determining method to compute the currency orders among tuples, according to currency constraints. Thus, the inconsistent data and missing values are repaired effectively considering the temporal impact. For both effectiveness and efficiency consideration, we carry out inconsistency repair ahead of incompleteness repair. A currency-related consistency distance metric is defined to measure the similarity between dirty tuples and clean ones more accurately. In addition, currency orders are treated as an important feature in the missing imputation training process. The solution algorithms are introduced in detail with case studies. A thorough experiment on three real-life datasets verifies our method ${\sf Imp3C}$ Imp 3 C improves the performance of data repairing with multiple quality problems. ${\sf Imp3C}$ Imp 3 C outperforms the existing advanced methods, especially in the datasets with complex currency orders. [ABSTRACT FROM AUTHOR]

Support for efficient spatial data storage and retrieval has become a vital component in almost all spatial database systems. While GPUs have become a mainstream platform for high-throughput data processing in recent years, exploiting the massively parallel processing power of GPUs is non-trivial. Current approaches that parallelize one query at a time have low work efficiency and cannot make good use of GPU resources. On the other hand, many spatial database systems could receive a large number of queries simultaneously. In this paper, we present a comprehensive framework named G-PICS for parallel processing of concurrent spatial queries on GPUs. G-PICS encapsulates efficient parallel algorithms for constructing a variety of spatial trees with different space partitioning methods. G-PICS also provides highly optimized programs for processing major spatial query types, and such programs can be accessed via an API that could be further extended to implement user-defined algorithms. While support for dynamic data inputs is missing in existing work, G-PICS implements efficient parallel algorithms for bulk updates of data. Furthermore, G-PICS is designed to work in a Multi-GPU environment to support datasets beyond the size of a single GPU’s global memory. Empirical evaluation of G-PICS shows significant performance improvement over the state-of-the-art GPU and parallel CPU-based spatial query processing systems. In particular, G-PICS achieves double-digit speedup over such systems in tree construction (up to 53X) and query processing (up to 80X). [ABSTRACT FROM AUTHOR]

Entity resolution identifies all records in a database that refer to the same entity. In this paper, we propose an unsupervised framework for entity resolution using blocking and graph algorithms. The records are partitioned into blocks with no redundancy for efficiency improvement. For intra-block data processing, we propose a graph-theoretic fusion framework with two components, namely ITER and CliqueRank. Specifically, ITER constructs a weighted bipartite graph between terms and record-record pairs and iteratively propagates the node salience until convergence. Subsequently, CliqueRank constructs a record graph to estimate the likelihood of two records resident in the same clique. The derived likelihood from CliqueRank is fed back to ITER to rectify the edge weight until a joint optimum can be reached. Experimental evaluation was conducted with 4 real datasets. Results show that our unsupervised framework is comparable or even superior to state-of-the-art deep learning approaches. [ABSTRACT FROM AUTHOR]

Real graphs often contain edge and node weights, representing, for instance, penalty, distance or uncertainty. We study the problem of keyword search over weighted node-labeled graphs, in which a query consists of a set of keywords and an answer is a subgraph whose nodes contain the keywords. We evaluate answers using three ranking strategies: optimizing edge weights, optimizing node weights, and a bi-objective combination of both node and edge weights. We prove that optimizing node weights and the bi-objective function are NP-hard. We propose an algorithm that optimizes edge weights and has an approximation ratio of two for the unique node enumeration paradigm. To optimize node weights and the bi-objective function, we propose transformations that distribute node weights onto the edges. We then prove that our transformations allow our algorithm to also optimize node weights and the bi-objective function with the same approximation ratio of two. Notably, the proposed transformations are compatible with existing algorithms that only optimize edge weights. We empirically show that in many natural examples, incorporating node weights (both keyword holders and middle nodes) produces more relevant answers than ranking methods based only on edge weights. Extensive experiments over real-life datasets verify the effectiveness and efficiency of our solution. [ABSTRACT FROM AUTHOR]

Due to their high retrieval efficiency and low storage cost, cross-modal hashing methods have attracted considerable attention. Generally, compared with shallow cross-modal hashing methods, deep cross-modal hashing methods can achieve a more satisfactory performance by integrating feature learning and hash codes optimizing into a same framework. However, most existing deep cross-modal hashing methods either cannot learn a unified hash code for the two correlated data-points of different modalities in a database instance or cannot guide the learning of unified hash codes by the feedback of hashing function learning procedure, to enhance the retrieval accuracy. To address the issues above, in this paper, we propose a novel end-to-end Deep Cross-Modal Hashing with Hashing Functions and Unified Hash Codes Jointly Learning (DCHUC). Specifically, by an iterative optimization algorithm, DCHUC jointly learns unified hash codes for image-text pairs in a database and a pair of hash functions for unseen query image-text pairs. With the iterative optimization algorithm, the learned unified hash codes can be used to guide the hashing function learning procedure; Meanwhile, the learned hashing functions can feedback to guide the unified hash codes optimizing procedure. Extensive experiments on three public datasets demonstrate that the proposed method outperforms the state-of-the-art cross-modal hashing methods. [ABSTRACT FROM AUTHOR]

With the advent of the Internet and Internet-connected devices, modern business applications can experience rapid increases as well as variability in transactional workloads. Database replication has been employed to scale performance and improve availability of relational databases but past approaches have suffered from various issues including limited scalability, performance versus consistency tradeoffs, and requirements for database or application modifications. This paper presents Hihooi, a replication-based middleware system that is able to achieve workload scalability, strong consistency guarantees, and elasticity for existing transactional databases at a low cost. A novel replication algorithm enables Hihooi to propagate database modifications asynchronously to all replicas at high speeds, while ensuring that all replicas are consistent. At the same time, a fine-grained routing algorithm is used to load balance incoming transactions to available replicas in a consistent way. Our thorough experimental evaluation with several well-established benchmarks shows how Hihooi is able to achieve almost linear workload scalability for transactional databases. [ABSTRACT FROM AUTHOR]

Despite exciting progress on cryptography, secure and efficient query processing over outsourced data remains an open challenge. We develop a communication-efficient and information-theoretically secure system, entitled Obscure for aggregation queries with conjunctive or disjunctive predicates, using secret-sharing. Obscure is strongly secure (i.e., secure regardless of the computational-capabilities of an adversary) and prevents the network, as well as, the (adversarial) servers to learn the user’s queries, results, or the database. In addition, Obscure provides additional security features, such as hiding access-patterns (i.e., hiding the identity of the tuple satisfying a query) and hiding query-patterns (i.e., hiding which two queries are identical). Also, Obscure does not require any communication between any two servers that store the secret-shared data before/during/after the query execution. Moreover, our techniques deal with the secret-shared data that is outsourced by a single or multiple database owners, as well as, allows a user, which may not be the database owner, to execute the query over secret-shared data. We further develop (non-mandatory) privacy-preserving result verification algorithms that detect malicious behaviors, and experimentally validate the efficiency of Obscure on large datasets, the size of which prior approaches of secret-sharing or multi-party computation systems have not scaled to. [ABSTRACT FROM AUTHOR]

Cross-database micro-expression recognition (CDMER) is one of recently emerging and interesting problem in micro-expression analysis. CDMER is more challenging than the conventional micro-expression recognition (MER), because the training and testing samples in CDMER come from different micro-expression databases, resulting in inconsistency of the feature distributions between the training and testing sets. In this paper, we contribute to this topic from three aspects. First, we establish a CDMER experimental evaluation protocol aiming to allow the researchers to conveniently work on this topic and evaluate their proposed methods under the same standard. Second, we conduct benchmark experiments by using NINE state-of-the-art domain adaptation (DA) methods and SIX popular spatiotemporal descriptors for investigating CDMER problem from two different perspectives. Third, we propose a novel DA method called region selective transfer regression (RSTR) to deal with the CDMER task. The overall superior performance of RSTR over the state-of-the-art DA methods demonstrates that taking into consideration the facial local region information used in RSTR contributes to developing effective DA methods for dealing with CDMER problem. [ABSTRACT FROM AUTHOR]

Subgraph matching finds all embeddings from a data graph that are identical to a query graph. Recent algorithms work by generating a tree-structured index on the data graph based on the query graph, ordering the vertices path-by-path in the tree, and enumerating the embeddings following the matching order. However, we find such path-based ordering and tree-structured index based enumeration inherently limit the performance due to the lack of consideration on the edges among the vertices across tree paths. To address this problem, we propose an approach that generates the matching order based on a cost model considering both the edges among query vertices and the number of candidates. Furthermore, we create a bigraph index for candidate vertices and their selected neighbors in the data graph, and use this index to perform enumeration along the matching order. Our experiments on both real-world and synthetic datasets show that our method outperforms the state of the art by orders of magnitude. [ABSTRACT FROM AUTHOR]

Hashing techniques are in great demand for a wide range of real-world applications such as image retrieval and network compression. Nevertheless, existing approaches could hardly guarantee a satisfactory performance with the extremely low-bit (e.g., 4-bit) hash codes due to the severe information loss and the shrink of the discrete solution space. In this article, we propose a novel Collaborative Learning strategy that is tailored for generating high-quality low-bit hash codes. The core idea is to jointly distill bit-specific and informative representations for a group of pre-defined code lengths. The learning of short hash codes among the group can benefit from the manifold shared with other long codes, where multiple views from different hash codes provide the supplementary guidance and regularization, making the convergence faster and more stable. To achieve that, an asymmetric hashing framework with two variants of multi-head embedding structures is derived, termed as Multi-head Asymmetric Hashing (MAH), leading to great efficiency of training and querying. Extensive experiments on three benchmark datasets have been conducted to verify the superiority of the proposed MAH, and have shown that the 8-bit hash codes generated by MAH achieve 94.3 percent of the MAP 1. Mean Average Precision (MAP) score on the CIFAR-10 dataset, which significantly surpasses the performance of the 48-bit codes by the state-of-the-arts in image retrieval tasks. [ABSTRACT FROM AUTHOR]

The primitive of verifiable database (VDB) can enable a resource-limited client to securely outsource an encrypted database to an untrusted cloud server and the client could efficiently retrieve and update the data at will. Meanwhile, the client can undoubtedly detect any misbehavior by the server if the database has been tampered with. We argue that most of the existing VDB schemes can only support the updating operation of replacement, rather than other common updating operations such as insertion and deletion. Recently, the first publicly verifiable VDB schemes that supports all updating operations was proposed based on the idea of hierarchical vector commitment. However, one disadvantage of the proposed VDB scheme is that the computation and storage complexity increases linearly when the client continually inserts data records in the same index of the database. As a result, it remains an open problem how to construct an efficient (and publicly verifiable) VDB scheme that can support all updating operations regardless of the manner of insertion. In this paper, we first introduce a new primitive called committed invertible Bloom filter (CIBF) and utilize it to propose a new publicly verifiable VDB scheme that can support all kinds of updating operations. Additionally, the proposed construction is efficient regardless of the manner of updating operations and thus provides an affirmative answer to the above open problem. [ABSTRACT FROM AUTHOR]

Estimating set similarity and detecting highly similar sets are fundamental problems in areas such as databases and machine learning. MinHash is a well-known technique for approximating Jaccard similarity of sets and has been successfully used for many applications. Its two compressed versions, $b$ b -bit MinHash and Odd Sketch, can significantly reduce the memory usage of the MinHash, especially for estimating high similarities (i.e., similarities around 1). Although MinHash can be applied to static sets as well as streaming sets, of which elements are given in a streaming fashion, unfortunately, $b$ b -bit MinHash and Odd Sketch fail to deal with streaming data. To solve this problem, we previously designed a memory-efficient sketch method, MaxLogHash, to accurately estimate Jaccard similarities in streaming sets. Compared with MinHash, our method uses smaller sized registers (each register consists of less than 7 bits) to build a compact sketch for each set. In this paper, we further develop a faster method, MaxLogOPH++. Compared with MaxLogHash, MaxLogOPH++ reduces the time complexity for updating each coming element from $O(k)$ O (k) to $O(1)$ O (1) with a small additional memory. We conduct experiments on a variety of datasets, and experimental results demonstrate the efficiency and effectiveness of our methods. [ABSTRACT FROM AUTHOR]

Nowadays, more individuals and corporations tend to use machine learning as a service (MLaaS) in cloud computing environment. However, when enjoying the pay-as-you-go mode and flexible capacity of cloud computing, it also increases the risk of privacy leakage for sensitive data. In this paper, we aim to efficiently implement privacy-preserving MLaaS, and focus on k-means clustering over outsourced encrypted cloud databases. Previous works mainly utilize partially homomorphic encryptions, which require a great number of interactive protocols with high computation and communication costs, making them not practical in real-world applications. To better solve this problem, we propose a new secure and efficient outsourced k-means clustering (SEOKC) scheme using fully homomorphic encryption with ciphertext packing technique, which achieves parallel computation without extra cost. The proposed scheme preserves privacy in three aspects: (1) database security, (2) privacy of clustering results and (3) hiding of data access patterns. We provide formal security analysis and evaluate the performance of the proposed scheme through extensive experiments. The experiment results show that our scheme needs much less computation cost (more than three orders of magnitude lower) than the state-of-the-art schemes, and is suitable to be applied on large databases. [ABSTRACT FROM AUTHOR]

Data incompleteness is a common data quality problem in databases. Recent work proposes to retrieve missing string values from the World Wide Web for higher imputation recall, but on the other hand, takes the risk of introducing web noises into the imputation results. So far there lacks an effective way to control the quality of web-based data imputation, given the complexity of the quality model and lacking of enough ground truth data. In this article, an EM-based quality model is first built for web-based data imputation which investigates three key factors jointly, i.e., precision of web sources, correlation among web sources, and precision and recall of the employed extractors. However, the accuracy of the EM-based quality model could be harmed when the EM (Expectation Maximization) assumption that “the majority agree on the truth” does not hold in some cases. To solve this problem, we introduce crowd intervention to help improve the quality model. While a straightforward but expensive way is to let the crowd to identify all these undesirable cases and provide the right imputation values for these blanks, a most crowd-economic way is to select a small set of blanks for crowd-based imputation, whose results could help to adjust the EM-based quality model towards a better one. To achieve this, an adaptive blank selection strategy is proposed to select a sequence of blanks for crowd-based imputation. Also, we work on finding a proper time to stop further crowd intervention for the balance of crowd efficiency and quality improvement. Our experiments performed on three real world and one simulated data collections prove that the proposed quality model can effectively help improve the quality of the web-based imputation results by more than 15 percent, while our crowd cost saving strategy saves more than 75 percent crowd cost. [ABSTRACT FROM AUTHOR]

Spurred by the development of cloud computing, there has been considerable recent interest in the Database-as-a-Service (DaaS) paradigm. Users lacking in expertise or computational resources can outsource their data and database management needs to a third-party service provider. Outsourcing, however, raises an important issue of result integrity: how can the client verify with lightweight overhead that the query results returned by the service provider are correct (i.e., the same as the results of query execution locally)? This survey focuses on categorizing and reviewing the progress on the current approaches for result integrity of SQL query evaluation in the DaaS model. The survey also includes some potential future research directions for result integrity verification of the outsourced computations. [ABSTRACT FROM AUTHOR]

Frequent itemsets mining is an active research problem in the domain of data mining and knowledge discovery. With the advances in database technology and an exponential increase in data to be stored, there is a need for efficient approaches that can quickly extract useful information from such large datasets. Frequent Itemsets (FIs) mining is a data mining task to find itemsets in a transactional database which occur together above a certain frequency. Finding these FIs usually requires multiple passes over the databases; therefore, making efficient algorithms crucial for mining FIs. This work presents a graph-based approach for representing a complete transactional database. The proposed graph-based representation enables the storing of all relevant information (for extracting FIs) of the database in one pass. Later, an algorithm that extracts the FIs from the graph-based structure is presented. Experimental results are reported comparing the proposed approach with 17 related FIs mining methods using six benchmark datasets. Results show that the proposed approach performs better than others in terms of time. [ABSTRACT FROM AUTHOR]

Clients of outsourced databases need Query Authentication (QA) guaranteeing the integrity and authenticity of query results returned by potentially compromised providers. Prior work provides QA assurances for a limited class of queries by deploying several software-based cryptographic constructs. The constructs are often designed assuming read-only or infrequently updated databases. For dynamic datasets, the data owner is required to perform all updates on behalf of clients. Hence, for concurrent updates by multiple clients, such as for OLTP workloads, existing QA solutions are inefficient. We present ConcurDB, a concurrent QA scheme that enables simultaneous updates by multiple clients. To realize concurrent QA, we have designed several new mechanisms. First, we identify and use an important relationship between QA and memory checking to decouple query execution and verification. We allow clients to execute transactions concurrently and perform verifications in parallel using an offline memory checking based protocol. Then, to extend QA to a multi-client scenario, we design new protocols that enable clients to securely exchange a small set of authentication data even when using the untrusted provider as a communication hub. Finally, we overcome provider-side replay attacks. Using ConcurDB, we provide and evaluate concurrent QA for the full TPC-C benchmark. For updates, ConcurDB shows a 4x performance increase over existing solutions. [ABSTRACT FROM AUTHOR]

The Earth Mover's Distance (EMD) is a robust similarity measure between two histograms (e.g., probability distributions). It has been extensively used in a wide range of applications, e.g., multimedia, data mining, computer vision, etc. As EMD is a computationally intensive operation, many efficient lower and upper bound functions of EMD have been developed. However, they provide no guarantee on the error. In this work, we study how to compute approximate EMD value with bounded error. First, we develop a parametric dual bound function for EMD, in order to offer sufficient trade-off points for optimization. After that, we propose an approximation framework that leverages on lower and upper bound functions to compute approximate EMD with error guarantee. Then, we present three solutions to solve our problem. Experimental results on real data demonstrate the efficiency and the effectiveness of our proposed solutions. [ABSTRACT FROM AUTHOR]

Group k-nearest neighbor (k GNN) search allows a group of n mobile users to jointly retrieve k points from a location-based service provider (LSP) that minimizes the aggregate distance to them. We identify four protection objectives in the privacy preserving k GNN search: (i) every user's location should be protected from LSP; (ii) the group's query and the query answer should be protected from LSP; (iii) LSP's private database information should be protected from users; (iv) every user's location should be protected from other users in the group. We design two privacy preserving solutions under two types of threat model to the privacy preserving k GNN search in the full user collusion environment, where any n−1 users in the group may collude to infer the location of the remaining user. Our solutions do not rely on heavy pre-computation on LSP like previous works. Though we consider k GNN, the proposed privacy preserving solutions can be easily adopted to any group query as it treats the query answering (i.e., k GNN) as a black box. Theoretical and experimental analysis suggest that our solutions are highly efficient in both communication cost and user computational cost while incurring some reasonable overhead on LSP. [ABSTRACT FROM AUTHOR]

In-memory databases (IMDBs) are gaining increasing popularity in big data applications, where clients commit updates intensively. Specifically, it is necessary for IMDBs to have efficient snapshot performance to support certain special applications (e.g., consistent checkpoint, HTAP). Formally, the in-memory consistent snapshot problem refers to taking an in-memory consistent time-in-point snapshot with the constraints that 1) clients can read the latest data items and 2) any data item in the snapshot should not be overwritten. Various snapshot algorithms have been proposed in academia to trade off throughput and latency, but industrial IMDBs such as Redis adhere to the simple fork algorithm. To understand this phenomenon, we conduct comprehensive performance evaluations on mainstream snapshot algorithms. Surprisingly, we observe that the simple fork algorithm indeed outperforms the state-of-the-arts in update-intensive workload scenarios. On this basis, we identify the drawbacks of existing research and propose two lightweight improvements. Extensive evaluations on synthetic data and Redis show that our lightweight improvements yield better performance than fork, the current industrial standard, and the representative snapshot algorithms from academia. Finally, we have opensourced the implementation of all the above snapshot algorithms so that practitioners are able to benchmark the performance of each algorithm and select proper methods for different application scenarios. [ABSTRACT FROM AUTHOR]

For over many decades, relational database model has been considered as the leading model for data storage and management. However, as the Big Data explosion has generated a large volume of data, alternative models like NoSQL and NewSQL have emerged. With the advancement of communication technology, these database systems have given the potential to change the existing architecture from centralized mechanism to distributed in nature, to deploy as cloud-based solutions. Though all of these evolving technologies mostly focus on performance guarantees, it is still being a major concern how these systems can ensure the security and privacy of the information they handle. Different datastores support different types of integrated security mechanisms, however, most of the non-relational database systems have overlooked the security requirements of modern Big Data applications. This paper reviews security implementations in today's leading database models giving more emphasis on security and privacy attributes. A set of standard security mechanisms have been identified and evaluated based on different security classifications. Further, it provides a thorough review and a comprehensive analysis on maturity of security and privacy implementations in these database models along with future directions/enhancements so that data owners can decide on most appropriate datastore for their data-driven Big Data applications. [ABSTRACT FROM AUTHOR]

Geo-textual data is ubiquitous nowadays, where each object has a location and is associated with some keywords. Many types of queries based on geo-textual data, termed as spatial keyword queries, have been proposed, and are to find optimal object(s) in terms of both its (their) location(s) and keywords. In this paper, we propose a new type of query called nearby-fit spatial keyword query (NSKQ), where an optimal object is defined based not only on the location and the keywords of the object itself, but also on those of the objects nearby. For example, in an application of finding a hotel, not only the location of a hotel but also the objects near the hotel (e.g., shopping malls, restaurants, and bus stops nearby) might need to be taken into consideration. The query is proved to be NP-hard, and in order to perform the query efficiently, we developed two approximate algorithms with small constant approximation factors equal to 1.155 and 1.79. We conducted extensive experiments based on both real and synthetic datasets, which verified our algorithms. [ABSTRACT FROM AUTHOR]

User data can be acquired from various domains and is characterized by a combination of demographics such as age and occupation, and user actions such as rating a movie or recording one's blood pressure. User data is appealing to analysts in their role as data scientists who seek to conduct large-scale population studies, and gain insights on various population segments. It is also appealing to users in their role as information consumers who use the social Web for routine tasks such as finding a book club or choosing a physical activity. User data analytics usually relies on identifying group-level behaviors such as “Asian women who publish regularly in databases”. Group analytics addresses peculiarities of user data such as noise and sparsity to enable insights. In this survey, we discuss different approaches for each component of user group analytics, i.e., discovery, exploration, and visualization. We focus on related work which arises from combining those components. We also discuss challenges and future directions of having an all-in-one system, where all those components are combined. This survey has been presented in the form of two tutorials ,. [ABSTRACT FROM AUTHOR]

Conceptual and relational data models of online transaction processing (OLTP) applications are usually created and maintained following the principle of normalization, which implies avoidance of redundancy. Data retrieval from a disk-based normalized relational database often requires complex and inefficient queries that may cause noticeable performance issues when executed on larger volumes of data. Computer professionals sometimes intentionally trade off the strict normal form to optimize data retrieval queries through error-prone manual tuning and denormalization. We propose a fully automatic optimization approach, based on data redundancy, that relies on a formal cost-benefit model. We prove that finding the optimal level of data redundancy, for given workload statistics, is an NP-Complete optimization problem. A detailed reduction of the problem to binary linear programming is presented in the paper. The proposed optimization approach was evaluated using the TPCE benchmark for OLTP systems. The evaluation has shown that the proposed optimization approach is highly scalable, and that it can be efficiently applied to real-life relational data models. [ABSTRACT FROM AUTHOR]

In this paper, we consider a scenario where a user queries a user profile database, maintained by a social networking service provider, to identify users whose profiles match the profile specified by the querying user. A typical example of this application is online dating. Most recently, an online dating website, Ashley Madison, was hacked, which resulted in a disclosure of a large number of dating user profiles. This data breach has urged researchers to explore practical privacy protection for user profiles in a social network. In this paper, we propose a privacy-preserving solution for profile matching in social networks by using multiple servers. Our solution is built on homomorphic encryption and allows a user to find out matching users with the help of multiple servers without revealing to anyone the query and the queried user profiles in clear. Our solution achieves user profile privacy and user query privacy as long as at least one of the multiple servers is honest. Our experiments demonstrate that our solution is practical. [ABSTRACT FROM AUTHOR]

Searching similar graphs in graph databases for a query graph has attracted extensive attention recently. Existing works on graph similarity queries are threshold based approaches which return graphs with distances to the query smaller than a given threshold. However, in many applications the number of answer graphs for the same threshold can vary significantly for different queries. In this paper, we study the problem of finding top- $k$ k most similar graphs for a query under the distance measure based on maximum common subgraph (MCS). Since computing MCS is NP-hard, we devise a novel framework to prune unqualified graphs based on the lower bounds of graph distance, and accordingly derive four lower bounds with different tightness and computational cost for pruning. To further reduce the number of MCS computations, we also propose an improved framework based on both lower and upper bounds, and derive three new upper bounds. To support efficient pruning, we design three indexes with different tradeoffs between pruning power and construction cost. To accelerate the index construction, we explore bound relaxation techniques, based on which approximate indexes can be efficiently built. We conducted extensive performance studies on real-life graph datasets to validate the effectiveness and efficiency of our approaches. [ABSTRACT FROM AUTHOR]

Skyline, aiming at finding a Pareto optimal subset of points in a multi-dimensional dataset, has gained great interest due to its extensive use for multi-criteria analysis and decision making. The skyline consists of all points that are not dominated by any other points. It is a candidate set of the optimal solution, which depends on a specific evaluation criterion for optimum. However, conventional skyline queries, which return individual points, are inadequate in group querying case since optimal combinations are required. To address this gap, we study the skyline computation in the group level and propose efficient methods to find the Group-based skyline (G-skyline). For computing the front $l$ l skyline layers, we lay out an efficient approach that does the search concurrently on each dimension and investigates each point in the subspace. After that, we present a novel structure to construct the G-skyline with a queue of combinations of the first-layer points. We further demonstrate that the G-skyline is a complete candidate set of top- $l$ l solutions, which is the main superiority over previous group-based skyline definitions. However, as G-skyline is complete, it contains a large number of groups which can make it impractical. To represent the “contour” of the G-skyline, we define the Representative G-skyline (RG-skyline). Then, we propose a Group-based clustering (G-clustering) algorithm to find out RG-skyline groups. Experimental results show that our algorithms are several orders of magnitude faster than the previous work. [ABSTRACT FROM AUTHOR]

With 5G on the verge of being adopted as the next mobile network, there is a need to analyze its impact on the landscape of computing and data management. In this paper, we analyze the impact of 5G on both traditional and emerging technologies and project our view on future research challenges and opportunities. With a predicted increase of 10-100x in bandwidth and 5-10x decrease in latency, 5G is expected to be the main enabler for smart cities, smart IoT and efficient healthcare, where machine learning is conducted at the edge. In this context, we investigate how 5G can help the development of federated learning. Network slicing, another key feature of 5G, allows running multiple isolated networks on the same physical infrastructure. However, security remains the main concern in the context of virtualization, multi-tenancy and high device density. Formal verification of 5G networks can be applied to detect security issues in massive virtualized environments. In summary, 5G will make the world even more densely and closely connected. What we have experienced in 4G connectivity will pale in comparison to the vast amounts of possibilities engendered by 5G. [ABSTRACT FROM AUTHOR]

Traditional graph-based Semi-Supervised Learning (SSL) methods usually contain two separate steps. First, constructing an affinity matrix. Second, inferring the unknown labels. While such a two-step method has been successful, it cannot take full advantage of the correlation between affinity matrix and label information. In order to address the above problem, we propose a novel graph-based SSL method. It can learn the affinity matrix and infer the unknown labels simultaneously. Moreover, feature selection with auto-weighting is introduced to extract the effective and robust features. Further, the proposed method learns the data similarity matrix by assigning the adaptive neighbors for each data point based on the local distance. We solve the unified problem via an alternative minimization algorithm. Extensive experimental results on synthetic data and benchmark data show that the proposed method consistently outperforms the state-of-the-art approaches. [ABSTRACT FROM AUTHOR]

Sequence classification deals with the task of finding discriminative and concise sequential patterns. To this purpose, many techniques have been proposed, which mainly resort to the use of partial orders to capture the underlying sequences in a database according to the labels. Partial orders, however, pose many limitations, especially on expressiveness, i.e., the aptitude towards capturing certain behavior, and on conciseness, i.e., doing so in a compact and informative way. These limitations can be addressed by using a better representation. In this paper, we present the interesting Behavioral Constraint Miner (iBCM), a sequence classification technique that discovers patterns using behavioral constraint templates. The templates comprise a variety of constraints and can express patterns ranging from simple occurrence, to looping and position-based behavior over a sequence. Furthermore, iBCM also captures negative constraints, i.e., absence of particular behavior. The constraints can be discovered by using simple string operations in an efficient way. Finally, deriving the constraints with a window-based approach allows to pinpoint where the constraints hold in a string, and to detect whether patterns are subject to concept drift. Through empirical evaluation, it is shown that iBCM is better capable of classifying sequences more accurately and concisely in a scalable manner. [ABSTRACT FROM AUTHOR]

ChronoGraph is a novel system enabling temporal graph traversals. Compared to snapshot-oriented systems, this traversal-oriented system is suitable for analyzing information diffusion over time without violating a time constraint on temporal paths. The cornerstone of ChronoGraph aims at bridging the chasm between point-based semantics and period-based semantics and the gap between temporal graph traversals and static graph traversals. Therefore, our graph model and traversal language provide the temporal syntax for both semantics, and we present a method converting point-based semantics to period-based ones. Also, ChronoGraph exploits the temporal support and parallelism to handle the temporal degree, which explosively increases compared to static graphs. We demonstrate how three traversal recipes can be implemented on top of our system: temporal breadth-first search (tBFS), temporal depth-first search (tDFS), and temporal single source shortest path (tSSSP). According to our evaluation, our temporal support and parallelism enhance temporal graph traversals in terms of convenience and efficiency. Also, ChronoGraph outperforms existing property graph databases in terms of temporal graph traversals. We prototype ChronoGraph by extending Tinkerpop, a de facto standard for property graphs. Therefore, we expect that our system would be readily accessible to existing property graph users. [ABSTRACT FROM AUTHOR]

To fully utilize the resources of a main memory database cluster, we additionally take the independent parallelism into account to parallelize multiple pipelines of one query. However, scheduling resources to multiple pipelines is an intractable problem. Traditional static approaches to this problem may lead to a serious waste of resources and suboptimal execution order of pipelines, because it is hard to predict the actual data distribution and fluctuating workloads at compile time. In response, we propose a dynamic scheduling algorithm, List with Filling and Preemption (LFPS), based on two novel techniques. (1) Adaptive filling improves resource utilization by issuing more extra pipelines to adaptively fill idle resource “holes” during execution. (2) Rank-based preemption strictly guarantees scheduling the pipelines on the critical path first at run time. Interestingly, the latter facilitates the former filling idle “holes” with best efforts to finish multiple pipelines as soon as possible. We implement LFPS in our prototype database system. Under the workloads of TPC-H, experiments show our work improves the finish time of parallelizable pipelines from one query up to 2.5X than a static approach and 2.1X than a serialized execution. [ABSTRACT FROM AUTHOR]

As flash-based solid-state drive (SSD) becomes more prevalent because of the rapid fall in price and the significant increase in capacity, customers expect better data services than traditional disk-based systems. However, the order of magnitude performance provided and new characteristics of flash require a rethinking of data services. For example, backup and recovery is an important service in a database system since it protects data against unexpected hardware and software failures. To provide backup and recovery, backup/recovery tools or backup/recovery methods by operating systems can be used. However, the tools perform time-consuming jobs, and the methods may negatively affect run-time performance during normal operation even though high-performance SSDs are used. To handle these issues, we propose an SSD-assisted backup/recovery scheme for database systems. Our scheme is to utilize the characteristics (e.g., out-of-place update) of flash-based SSD for backup/recovery operations. To this end, we exploit the resources (e.g., flash translation layer and DRAM cache with supercapacitors) inside SSD, and we call our SSD with new backup/recovery functionality BR-SSD. We design and implement the functionality in the Samsung enterprise-class SSD (i.e., SM843Tn) for more realistic systems. Furthermore, we exploit and integrate BR-SSDs into database systems (i.e., MySQL) in replication and redundant array of independent disks (RAID) environments, as well as a database system in a single BR-SSD. The experimental result demonstrates that our scheme provides fast backup and recovery but does not negatively affect the run-time performance during normal operation. [ABSTRACT FROM AUTHOR]

Incomplete information often occurs along with many database applications, e.g., in data integration, data cleaning, or data exchange. The idea of data imputation is often to fill the missing data with the values of its neighbors who share the same/similar information. Such neighbors could either be identified certainly by editing rules or extensively by similarity relationships. Owing to data sparsity, the number of neighbors identified by editing rules w.r.t. value equality is rather limited, especially in the presence of data values with variances. To enrich the imputation candidates, a natural idea is to extensively consider the neighbors with similarity relationship. However, the candidates suggested by these (heterogenous) similarity neighbors may conflict with each other. In this paper, we propose to utilize the similarity rules with tolerance to small variations (instead of the aforesaid editing rules with strict equality constraints) to rule out the invalid candidates provided by similarity neighbors. To enrich the data imputation, i.e., imputing the missing values more, we study the problem of maximizing the missing data imputation. Our major contributions include (1) the np-hardness analysis on solving as well as approximating the problem, (2) exact algorithms for tackling the problem, and (3) efficient approximation with performance guarantees. Experiments on real and synthetic data sets demonstrate the superiority of our proposal in filling accuracy. We also demonstrate that the record matching application is indeed improved, after applying the proposed imputation. [ABSTRACT FROM AUTHOR]

In multi-view re-ranking, multiple heterogeneous visual features are usually projected onto a low-dimensional subspace, and thus the resulting latent representation can be used for the subsequent similarity-based ranking. Albeit effective, this standard mechanism underplays the intrinsic structure underlying the latent subspace and does not take into account the substantial noise in the original spaces. In this paper, we propose a robust multi-view image re-ranking strategy. Due to the dramatic variability in image visual appearance, it is necessary to uncover the shared components underlying those query-related instances that are visually unlike for improving the re-ranking accuracy. Consequently, it is reasonable to assume the latent subspace enjoys the low-rank property and thus the subspace recovery can be achieved via the low-rank modeling accordingly. In addition, since the real-world data are usually partially contaminated, we employ $\ell _{2, 1}$ ℓ 2 , 1 -norm based sparsity constraint to appropriately model the sample-specific mapping noise for enhancing the model robustness. In order to produce discriminative representations, we encode a similarity preserving term in our multi-view embedding framework. As a result, the sample separability is maximally maintained in the latent subspace with sufficient discriminative power. The extensive evaluations on public landmark benchmarks demonstrate the efficacy and superiority of the proposed method. [ABSTRACT FROM AUTHOR]