Search

This paper introduces the TRGST data structure, which is designed to handle queries related to topological relations between paths represented as sequences of stops in a network. As an example, these paths could correspond to stops on a public transport network, and a query of interest is to retrieve paths that share at least k consecutive stops. While topological relations among spatial objects have received extensive attention, the efficient processing of these relations in the context of trajectory paths, considering both time and space efficiency, remains a relatively less explored domain. Taking inspiration from pattern matching implementations, the TRGST data structure is constructed on the foundation of the Generalized Suffix Tree. Its purpose is to provide a compact representation of a set of paths and to efficiently handle topological relation queries by leveraging the pattern search capabilities inherent in this structure. The paper provides a detailed account of the structure and algorithms of TRGST , followed by a performance analysis utilizing both real and synthetic data. The results underscore the remarkable scalability of the TRGST in terms of both query time and space utilization. [ABSTRACT FROM AUTHOR]

In this paper, we discuss methods to assess the interestingness of a query in an environment of data cubes. We assume a hierarchical multidimensional database, storing data cubes and level hierarchies. We start with a comprehensive review of related work in the fields of human behavior studies and computer science. We define the interestingness of a query as a vector of scores along different aspects, like novelty, relevance, surprise and peculiarity and complement this definition with a taxonomy of the information that can be used to assess each of these aspects of interestingness. We provide both syntactic (result-independent) and extensional (result-dependent) checks, measures and algorithms for assessing the different aspects of interestingness in a quantitative fashion. We also report our findings from a user study that we conducted, analyzing the significance of each aspect, its evolution over time and the behavior of the study's participants. [ABSTRACT FROM AUTHOR]

The point of interest (POI) recommendation algorithm in location based social network (LBSN) can assist people to find more appealing locations and satisfy their specific demands. However, it is challengeable to infer user's preference due to the sparsity of the user's check-in data. To address the problem and improve recommendation performance, this paper proposes an improved context-aware weighted matrix factorization algorithm for POI recommendation (ICWMF). It takes advantage of time factor, geographical information, and social relationship to obtain user's preference for locations. Firstly, the Ebbinghaus forgetting curve is employed to model the influence of time attenuation, so as to reflect that user preferences change over time. In order to assign dynamic weights to unvisited POI and infer user preference, we build the implicit feedback term by modeling the geographical influence from user perspective and the social relationship. In addition, the Gaussian model is employed to construct proximity location relationship to represent the probability of locations being discovered by users. Then, it is taken as the regularization term to avoid overfitting. Finally, the objective function of weighted matrix factorization is reconstructed with the implicit feedback term and the regularization term we designed. ICWMF naturally learns two potential feature matrices during weighted matrix decomposition based on new designed objective function to achieve better recommendation results. The results of simulation experiments on Brightkite and Gowalla dataset indicate that ICWMF outperforms other four comparison methods in terms of precision and recall. [ABSTRACT FROM AUTHOR]

Abstract Recent years have witnessed the rapid development of knowledge bases (KBs) such as WordNet, Yago and DBpedia, which are useful resources in AI-related applications. However, most of the existing KBs are suffering from incompleteness and manually adding knowledge into KBs is inefficient. Therefore, automatically mining knowledge becomes a critical issue. To this end, in this paper, we propose to develop a model (S 2 AMT) to extract knowledge triples, such as < Barack Obama, wife, Michelle Obama > , from the Internet and add them to KBs to support many downstream applications. Particularly, because the seed instances 1 1 In this paper, seed instances refer to labeled positive instances. for every relation is difficult to obtain, our model is capable of mining knowledge triples with limited available seed instances. To be more specific, we treat the knowledge triple mining task for each relation as a single task and use multi-task learning (MTL) algorithms to solve the problem, because MTL algorithms can often get better results than single-task learning (STL) ones with limited training data. Moreover, since finding proper task groups is a fatal problem in MTL which can directly influences the final results, we adopt a clustering algorithm to find proper task groups to further improve the performance. Finally, we conduct extensive experiments on real-world data sets and the experimental results clearly validate the performance of our MTL algorithms against STL ones. Highlights • We propose S 2 AMT to solve the problem of KTM with limited seed instances. • Our framework obtain better performance using MTL methods. • Our framework jointly use labeled and unlabeled instances during the training stage. • We give a fast method to find related tasks to further improve the performance. • Our work provides a new perspective for KTM when having limited seed instances. [ABSTRACT FROM AUTHOR]

In order to improve recommendation quality of recommendation algorithms, this paper proposes a hybrid recommendation algorithm based on user comments sentiment and matrix decomposition (abbreviate as RACSMD). This algorithm first calculates the sentiment tendency towards the user's comment through the LSTM algorithm, and then integrates the sentiment value of the user's rating to increase the accuracy of the user's actual rating before combining the matrix decomposition recommendation algorithm to improve recommendation quality. This paper theoretically verifies the feasibility of RACSMD through an algorithm example. Moreover, corresponding experimental analysis is conducted on the basis of three data sets of Beeradvocate, Modcloth and Amazon. Experimental results show that the introduction to sentiment tendencies towards user comments can effectively improve recommendation quality of recommendation algorithms. • A hybrid recommendation algorithm based on user comments sentiment and matrix decomposition (abbreviate as RACSMD) is proposed to improve recommendation quality of recommendation algorithms. • LSTM algorithm is introduced to calculate the emotional tendency of user comments and integrate the emotional value of user ratings to improve the accuracy of actual user ratings. • Matrix decomposition method and sentiment analysis method are integrated into the hybrid recommendation algorithm to improve the recommendation quality. • RACSMD is a hybrid recommendation algorithm which can effectively improve recommendation quality. [ABSTRACT FROM AUTHOR]

Retrieving, analyzing, and processing large data can be challenging. An effective and efficient mechanism for overcoming these challenges is to cluster the data into a compact and meaningful format that reflect the whole data. The learning techniques for clustering can be classified into supervised, semi-supervised, and un-supervised learning. Semi-supervised and un-supervised learning are more advantageous than supervised learning because it is laborious, and that prior knowledge is unavailable for most practical real-word problems. Towards this, we provide in this paper a review on semi-supervised and un-supervised learning methods. Unfortunately, most current survey papers categorize semi-supervised and un-supervised learning algorithms into broad clustering classes and do not drive clear boundaries between the specific techniques employed by the algorithms. That is, they do not set clear distinguishable boundaries between the specific techniques adopted by the algorithms. To overcome this, we provide a detailed methodology-based taxonomy that categorizes the algorithms into hierarchically nested, specific, and fine-grained classes. The taxonomy is hierarchically nested as follows: clustering categories → clustering methods → clustering sub-methods. First, the algorithms are classified into broad categories. In turn, each category is further classified into various methods. These methods are classified into sub-methods. We survey and describe over 200 state-of-the-art algorithms that employ the underlying principles of each clustering method/sub-method. We experimentally evaluate and rank the following: (1) the various clustering sub-methods that fall under a same clustering method, (2) the various clustering methods that fall under a same clustering category, (3) the various clustering categories. • Providing a taxonomy that categorizes semi-supervised and un-supervised algorithms into hierarchically nested, specific, and fine-grained classes. • Reviewing over 200 un-supervised and semi-supervised algorithms. • Experimentally evaluating and ranking all clustering sub-methods, methods, and categories. • Providing detailed discussion of the results. [ABSTRACT FROM AUTHOR]

Cluster analysis is a crucial data mining technology widely used in image segmentation, language processing, and pattern recognition. Most existing clustering algorithms cannot identify complex shapes in manifold data sets and data sets with varying-density distribution, especially when clusters with significant differences in density are close to each other. Hierarchical clustering algorithms can identify data sets of arbitrary shapes. However, hierarchical clustering algorithms not only cannot cluster datasets with significant density variations but also have a high time cost. So in this paper, we propose a novel hierarchical clustering algorithm based on density-distance cores, called HCDC. It first selects the density-distance representative points for each point from the set of candidate representative points. Then it selects density-distance cores from all density-distance representatives. And it replaces the whole data set with density-distance cores and uses a new distance between them to apply hierarchical clustering. To avoid the influence of noise points in the dataset when finding density-distance cores, we also propose the noise point detection method and verify the feasibility of this method. In this paper, we compare our proposed algorithm with existing classical and novel algorithms on synthetic and real datasets. Experiments show that our algorithm clusters better than existing algorithms on complex-shaped datasets and datasets with different densities. On datasets with sparse and dense clusters close to each other, the ARI score of HCDC is more than 0.1 higher than that of LDP-MST. In particular, on the grid dataset, HCDC's ARI score is 0.997 higher than LDP-MST. On DS3 and DS8, HCDC's ARI score is more than 0.14 higher than the second-best algorithm, RNN-DBSCAN. Moreover, on the zoo dataset, HCDC's ARI score is 0.15 and 0.6 higher than RNN-DBSCAN and LDP-MST, respectively. On the olivetti face dataset, HCDC is the only algorithm with an NMI score above 0.9 on photo1 and photo2 datasets. [ABSTRACT FROM AUTHOR]

Certain answers are a widely accepted semantics of query answering over incomplete databases. As their computation is a coNP-hard problem, recent research has focused on developing (polynomial time) evaluation algorithms with correctness guarantees , that is, techniques computing a sound but possibly incomplete set of certain answers. The aim is to make the computation of certain answers feasible in practice, settling for under-approximations. In this paper, we present novel evaluation algorithms with correctness guarantees, which provide better approximations than current techniques, while retaining polynomial time data complexity. The central tools of our approach are conditional tables and the conditional evaluation of queries. We propose different strategies to evaluate conditions, leading to different approximation algorithms—more accurate evaluation strategies have higher running times, but they pay off with more certain answers being returned. Thus, our approach offers a suite of approximation algorithms enabling users to choose the technique that best meets their needs in terms of balance between efficiency and quality of the results. • Algorithms to compute sound sets of certain query answers over incomplete databases. • Approximation algorithms trading-off evaluation time vs. quality of the approximation. • Suite of algorithms enabling users to choose the method that best meets their needs. [ABSTRACT FROM AUTHOR]

Cluster analysis plays an important role in identifying the natural structure of the target dataset. It has been widely used in many fields, such as pattern recognition, machine learning, image segmentation, document clustering and so on. There are many different methods to conduct cluster analysis. Namely, most real datasets are non-spherical and have complex shapes. Although these methods are widely used to deal with clustering tasks, they are susceptible to noise and arbitrary shapes. Thus, we propose a novel clustering algorithm (called RNN-NSDC) in this paper, which is based on the natural reverse nearest neighbor structure. Firstly, we apply the reverse nearest neighbors in the algorithm to extract core objects. Secondly, our algorithm uses the neighbor structure information of core objects to cluster. And excluding noise effects, core sets can well represent the structure of clusters. Therefore, the RNN-NSDC can obtain the optimal cluster numbers for the datasets which contain clusters of outliers and arbitrary shapes. To verify the efficiency and accuracy of the RNN-NSDC, synthetic datasets and real datasets are used for experiments. The results indicate the superiority of the RNN-NSDC compared with K-means, DBSCAN, DPC, SNNDPC, DCore and NaNLORE. • The criterion of extracting the core objects is simple and efficient. • There is no need to set parameters in RNN-NSDC. • RNN-NSDC can be applied to complex patterns with extremely large variations in density. • RNN-NSDC is robust to outliers and noises. [ABSTRACT FROM AUTHOR]

This paper aims to predict incomes of customers for banks. In this large-scale income prediction benchmarking paper, we study the performance of various state-of-the-art regression algorithms (e.g. ordinary least squares regression, beta regression, robust regression, ridge regression, MARS, ANN, LS-SVM and CART, as well as two-stage models which combine multiple techniques) applied to five real-life datasets. A total of 16 techniques are compared using 10 different performance measures such as R2, hit rate and preciseness etc. It is found that the traditional linear regression results perform comparable to more sophisticated non-linear and two-stage models. [ABSTRACT FROM AUTHOR]

In current large-scale distributed key–value stores, the tail latency of the hundreds of key–value access operations generated by an end-user request determines the response time of this request. Therefore, this tail latency has great impacts on the user experience and revenue. Replica selection algorithms, which select the best replica server for the service of each key–value access operation as much as possible, is the key to cut the tail latency of these key–value access operations. This paper summarizes current replica selection algorithms, including both the algorithms employed by current key–value stores and the classic algorithms of other similar systems. These algorithms are classified into three categories: information-agnostic, client-independence and feedback, according to their demanded information. As a step further, simulation-based performance analysis of these algorithms is conducted. The result brings us the insights that the response time (RPT) is useful to measure the service rate, but will lead to the herd behaviors. Moreover, the number of outstanding key–value access operations (OSKs) is helpful to both the selection of the fastest replica server and the avoidance of herd behaviors. Based on these insights, we design the L2 algorithm by assembling the basic ideas of the Least OSK algorithm and the Least RPT algorithm. The L2 algorithm is much simpler than the recently proposed C3 algorithm and has a similar best performance with C3 as confirmed by the simulation and experimental results. • We do survey and classification on the replica selection algorithms of key-value stores. • Performance evaluation of replica selection algorithms shows their advantages and disadvantages. • We design and evaluate the L2 algorithm, which is very simple but has good performance. [ABSTRACT FROM AUTHOR]

Abstract Binary relations are commonly used to represent relationships between real-world objects. Classical representations for binary relations can be very space-consuming when the set of elements is large. In these cases, compressed representations, such as the k 2 -tree, have proven to be a competitive solution, as they are efficient in time while consuming very little space. Moreover, k 2 -trees can successfully represent both sparse and dense binary relations, using different variants of the technique. In this paper, we propose and evaluate algorithms to efficiently perform set operations over binary relations represented using k 2 -trees. More specifically, we present algorithms for computing the union, intersection, difference, symmetric difference, and complement of binary relations. Thus, this work extends the functionality of the different variants of the k 2 -tree representation for binary relations. Our algorithms are computed directly over the compressed representation, without requiring previous decompression, and generate the result in compressed form. The experimental evaluation shows that they are efficient in terms of space and time, compared with different baselines where the binary relations are represented in plain form or require a previous decompression to perform the set operation. Highlights • We present algorithms for computing set operations over compressed binary relations. • These operations extend the functionality of k 2 -trees. • We evaluate the performance over real datasets of different nature. • Set operations are computed efficiently and in compressed space. [ABSTRACT FROM AUTHOR]

Highlights • A structured ontology that allows to model and integrate evolving data. • A method that handles schema evolution on the sources. • A query answering algorithm that is capable of unambiguously resolving LAV mappings. Abstract Big Data architectures allow to flexibly store and process heterogeneous data, from multiple sources, in their original format. The structure of those data, commonly supplied by means of REST APIs, is continuously evolving. Thus data analysts need to adapt their analytical processes after each API release. This gets more challenging when performing an integrated or historical analysis. To cope with such complexity, in this paper, we present the Big Data Integration ontology, the core construct to govern the data integration process under schema evolution by systematically annotating it with information regarding the schema of the sources. We present a query rewriting algorithm that, using the annotated ontology, converts queries posed over the ontology to queries over the sources. To cope with syntactic evolution in the sources, we present an algorithm that semi-automatically adapts the ontology upon new releases. This guarantees ontology-mediated queries to correctly retrieve data from the most recent schema version as well as correctness in historical queries. A functional and performance evaluation on real-world APIs is performed to validate our approach. [ABSTRACT FROM AUTHOR]

Highlights • Similarity-based comparison of XML document revisions. • Polinominal asymptotic complexity. • Speed up of almost 45 times if compared to state-of-the-art algorithms. • Superior Efficiency if compared to state-of-the-art algorithms. • Equivalent Efficacy of state-of-the-art algorithms. Abstract XML documents are widely used to interchange information among heterogeneous systems, ranging from office applications to scientific experiments. Independently of the domain, XML documents may evolve, so identifying and understanding the changes they undergo becomes crucial. Some syntactic diff approaches have been proposed to address this problem. They are mainly designed to compare revisions of XML documents using explicit IDs to match elements. However, elements in different revisions may not share IDs due to tool incompatibility or even divergent or missing schemas. In this paper, we present Phoenix, a similarity-based approach for comparing revisions of XML documents that does not rely on explicit IDs. Phoenix uses dynamic programming and optimization algorithms to compare different features (e.g., element name, content, attributes, and sub-elements) of XML documents and calculate the similarity degree between them. We compared Phoenix with X-Diff and XyDiff, two state-of-the-art XML diff algorithms. XyDiff was the fastest approach but failed in providing precise matching results. X-Diff presented higher efficacy in 30 of the 56 scenarios but was slow. Phoenix executed in a fraction of the running time required by X-Diff and achieved the best results in terms of efficacy in 26 of 56 tested scenarios. In our evaluations, Phoenix was by far the most efficient approach to match elements across revisions of the same XML document. [ABSTRACT FROM AUTHOR]

Abstract In this paper, we study the problem of discovering and learning sensational episodes of news events. A sensational episode of news events is in the form of lhs → rhs , where lhs is an antecedent event, rhs is a consequent event, and rhs often happens shortly after lhs. Such pairs of co-occurring news events within short period, while not necessarily bearing causal relationship between each other, are possible essential to media since they deliberately seek and broadcast examples of uncommon events to fascinate crowd attentions. First, to find all frequent episodes, we propose an efficient algorithm, MEELO, which significantly outperforms conventional algorithms. There can be a large number of frequent episodes. We rank them by their sensational effect from the perspectives of news audience, through learning from manually labeled examples. Instead of limiting ourselves to any individual subjective measure of sensational effect, we utilize a learning-to-rank approach that exploits multiple features to capture the sensational effect of a news episode from various aspects. NLP tools combined with knowledge bases are used in extracting and aggregating news events from news text. Experiments on real data verify our approach’s efficiency and effectiveness. [ABSTRACT FROM AUTHOR]

Spatial objects in reality are often associated with geographic locations (e.g., longitude and latitude) as well as multiple quality attributes. Quality attributes make it possible to compare spatial objects according to the dominance concept. Specifically, an object p i is said to dominate another object p j if p i is no worse than p j on all quality attributes and better than p j on at least one quality attribute. In many contexts, an object’s dominators in its neighborhood indicate the negative effect to the object. In this paper, we study the problem of querying spatial objects by their dominators in the neighborhood. We propose three meaningful score functions to quantify the negative effects of dominators in a spatial object’s neighborhood. The most endangered object (MEO) query thus defined has multiple practical applications such as business planning, online war games, and wild animal protection. For processing MEO queries, we design several algorithms that require different indexes on spatial data sets. Each algorithm is generic and flexible such that each can support all three score functions (and even more) without significant changes. We conduct extensive experiments to evaluate the algorithms. The experimental results disclose the performance differences of the algorithms under various settings. [ABSTRACT FROM AUTHOR]

Clustering has become one of the widely used automatic data-labeling techniques applied in a variety of disciplines. Kernel-based clustering is a technique designed to identify non-linearly separable clusters with irregular shapes. However, existing kernel-based clustering algorithms usually produce weaker clustering outcomes than density-based clustering, and they have high computational cost which limits their applications to small datasets only. In this paper, we contend that these limitations are mainly due to the use of (a) the Expectation-and-Maximization algorithm as an optimization procedure, and (b) a non-adaptive kernel. In addition, to address the limitations of current kernel-based algorithms, we propose the first clustering algorithm that employs an adaptive distributional kernel without any optimization, while achieving a similar optimization objective function. We demonstrate its superior performance of identifying complex clusters on massive datasets under different real-world application scenarios. • Revealing the cause of poor clustering performance of existing kernel-based clustering. • Proposing a new kernel-based clustering algorithm without any optimization. • The new algorithm can discover clusters of arbitrary shapes and sizes. • Showing its effectiveness on massive datasets under different application scenarios. [ABSTRACT FROM AUTHOR]

Graph pattern matching is a fundamental operation for exploring and analyzing large graphs, which are widely used to represent entities and their relationships in a plethora of applications. However, existing algorithms do not perform satisfactorily as they generate a large number of intermediate results. In this paper, we introduce a novel framework to address the problem of efficiently finding homomorphic matches of hybrid tree-patterns over large graphs. These are patterns that can include two types of edges: child edges (which are mapped to edges in the data graph) and/or descendant edges (which are mapped to paths in the data graph), thus allowing for higher expressiveness and flexibility in query formulation. We introduce the concept of answer graph to compactly represent the query results and exploit computation sharing. Leveraging the answer graph, our approach is able to avoid the generation of intermediate results not participating in the query answer, and can produce the query answer in time linear on the size of the input data graph and the output. Moreover, the answer graph allows query counting without explicitly enumerating query results. We design a bottom-up algorithm (BUP) and a simulation-based algorithm (SIM) for building the answer graph, each having their own strengths in different cases. We also present two algorithms for enumerating the results using the answer graph. Our extensive experimental evaluation on real and synthetic datasets shows that our proposed techniques greatly outperform the state-of-the-art graph matching algorithms as well as a popular graph DBMS on evaluating various hybrid tree-pattern queries. Our source code, datasets and queries are publicly available at https://github.com/wuxyng/TwigMatchOnGraph. [ABSTRACT FROM AUTHOR]

Empirical evidence shows that repositories of business process models used in industrial practice contain significant amounts of duplication. This duplication arises for example when the repository covers multiple variants of the same processes or due to copy-pasting. Previous work has addressed the problem of efficiently retrieving exact clones that can be refactored into shared subprocess models. This paper studies the broader problem of approximate clone detection in process models. The paper proposes techniques for detecting clusters of approximate clones based on two well-known clustering algorithms: DBSCAN and Hierarchical Agglomerative Clustering (HAC). The paper also defines a measure of standardizability of an approximate clone cluster, meaning the potential benefit of replacing the approximate clones with a single standardized subprocess. Experiments show that both techniques, in conjunction with the proposed standardizability measure, accurately retrieve clusters of approximate clones that originate from copy-pasting followed by independent modifications to the copied fragments. Additional experiments show that both techniques produce clusters that match those produced by human subjects and that are perceived to be standardizable. [ABSTRACT FROM AUTHOR]

Process Aware Information Systems manage processes within organisations on the basis of business process models. These models can be created either from scratch or by reusing exiting reference process models. Particular types of reference models are configurable process models that are created by merging multiple models into a single one that can be customized to the needs of the business experts. Using those models presents two main challenges: their creation and their configuration. In this paper, we focus on the first challenge and propose a novel algorithm for merging process models into a configurable process model. The difference in our work is the pre-annotated process models with their business capabilities that report on what actions each process element achieves. Our algorithm generates configurable models that are also annotated with their capabilities that can be used to face the second challenge of these models: the configuration phase. We tested our algorithm using real-world process models to evaluate the required creation time and resulting compression rate after merging the input models. The results show that the models can be created in few milliseconds and achieving a compression rate of 50%. We further carried out interviews with domain experts to assess the usefulness and the level of maturity of this work. The results show the importance of the automation of process merging using a tool support that we proposed. However, further adaptation efforts are required to integrate this work in the working environments of the interviewed experts. [ABSTRACT FROM AUTHOR]

The optimal k -segments of an ordered dataset of size n consists of k tuples that are obtained by merging consecutive tuples such that a given error metric is minimized. The problem is general and has been studied in various flavors, e.g., piecewise-constant approximation, parsimonious temporal aggregation, and v-optimal histograms. A well-known computation scheme for the optimal k -segments is based on dynamic programming, which computes a k × n error matrix E and a corresponding split point matrix J of the same size. This yields O ( n · k ) space and O ( n 2 · k ) runtime complexity. In this paper, we propose three optimization techniques for the runtime complexity and one for the space complexity. First, diagonal pruning identifies regions of the error matrix E that need not to be computed since they cannot lead to a valid solution. Second, for those cells in E that are computed, we provide a heuristic to determine a better seed value, which in turn leads to a tighter lower bound for the potential split points to be considered for the calculation of the minimal error. Third, we show how the algorithm can be effectively parallelized . The space complexity is dominated by the split point matrix J , which needs to be kept till the end. To tackle this problem, we replace the split point matrix by a dynamic split point graph , which eliminates entries that are not needed to retrieve the optimal solution. A detailed experimental evaluation shows the effectiveness of the proposed solutions. Our optimization techniques significantly improve the runtime of state-of-the-art matrix implementations, and they guarantee a comparable performance of an implementation that uses the split point graph. The split point graph reduces the memory consumption up to two orders of magnitude and allows us to process large datasets for which the memory explodes if the matrix is used. [ABSTRACT FROM AUTHOR]

As RDF becomes more widely established and the amount of linked data is rapidly increasing, the efficient querying of large amount of data becomes a significant challenge. In this paper, we propose a family of algorithms for querying large amount of linked data in a distributed manner. These query evaluation algorithms are independent of the way the data is stored, as well as of the particular implementation of the query evaluation. We then use the MapReduce paradigm to present a distributed implementation of these algorithms and experimentally evaluate them, although the algorithms could be straightforwardly translated into other distributed processing frameworks. We also investigate and propose multiple query decomposition approaches of Basic Graph Patterns (subclass of SPARQL queries) that are used to improve the overall performance of the distributed query answering. A deep analysis of the effectiveness of these decomposition algorithms is also provided. [ABSTRACT FROM AUTHOR]

Conditional functional dependencies (CFDs) generalize functional dependencies and lend themselves to wide applicability. CFDs on data are usually unknown and too costly to be designed manually. To this end, CFD discovery methods are studied for discovering hidden CFDs from data. In the setting of data cleaning, only a small number of CFDs are used to detect and repair errors, while common CFD discovery methods find all CFDs (approximately) holding on data, and an expensive post-processing step is further required for selecting those relevant ones. In this paper, we present an approach to discover CFDs that can detect errors in data, guided by a small set of erroneous attribute values labeled by users. (1) We present a method that consists of several modules of data sampling, CFD discovery and refinement guided by the user labeling and data re-sampling guided by the discovered CFDs, working in an iterative way. (2) We present novel efficient techniques to facilitate our approach, aiming at identifying CFDs useful for cleaning and reducing user interactions. (3) We conduct extensive experimental evaluations to verify our approach, against the state-of-the-art CFD discovery algorithms with or without user interactions. • A framework of conditional functional dependency discovery leveraging user labeling. • A set of techniques underlying the framework. • Evaluations of the effectiveness and efficiency of user-guided discovery. [ABSTRACT FROM AUTHOR]

A process discovery algorithm aims to construct a process model that represents the real-world process stored in event data well; it is precise, generalizes the data correctly, and is simple. At the same time, it is reasonable to expect that better quality input event data should lead to constructed process models of better quality. However, existing process discovery algorithms omit the discussion of this relationship between the inputs and outputs and, as it turns out, often do not guarantee it. We demonstrate the latter claim using several quality measures for event data and discovered process models. Consequently, this paper requests for more rigor in the design of process discovery algorithms, including properties that relate the qualities of the inputs and outputs of these algorithms. We present four incremental maturity stages for process discovery algorithms, along with concrete guidelines for formulating relevant properties and experimental validation. We then use these stages to review several state of the art process discovery algorithms to confirm the need to reflect on how we perform algorithmic process discovery. • We propose measures for the quality of event logs using random sampling techniques; • We show the effect random sampling techniques have on the quality of event logs; • Empirical evidence that quality of event logs is not correlated with quality of models; • We propose four maturity stages for process discovery algorithms. [ABSTRACT FROM AUTHOR]

Abstract: Case-Based reasoning (CBR) applications are increasingly used for problems involving structured data, especially in process-oriented domains. Available CBR frameworks rely primarily on flat case representations, leaving developers of process-oriented CBR systems without general-purpose tools aimed at their needs. This paper discusses needs to support structure-based retrieval for CBR and how they have been addressed in the development of the Structure Access Interface (SAI), a toolkit for representation and retrieval of structured cases which is now available for general use. Integrating SAI into a CBR project eliminates the need for developing a storage scheme for graph data structures and facilitates the development of retrieval algorithms by (1) providing useful code for common retrieval tasks and (2) delineating the tasks which may require domain-specific implementations. SAI maintains flexibility through its customizability yet carries solutions for many common tasks for CBR developers, as well as illuminating some general principles for addressing common representation and retrieval needs for process-oriented CBR tasks and the relationship between CBR needs for structured retrieval and needs and methods in graph oriented database research. The paper closes with an evaluation of SAI's scalability and demonstration of the value of enabling developers to select retrieval methods suited to their tasks. It closes with a discussion of SAI's relationship to the growing body of work on graph databases. [Copyright &y& Elsevier]

A fundamental problem in conformance checking is aligning event data with process models. Unfortunately, existing techniques for this task are either complex, or can only be applicable to restricted classes of models. This in practice means that for large inputs, current techniques often fail to produce a result. In this paper we propose a method to compute alignments for unconstrained process models, which relies on the use of relaxation labeling techniques on top of a partial order representation of the process model. The technique proposed in this paper precomputes information used in the search for alignments, and is able to produce real alignments that may be close to optimal ones by combining the aforementioned techniques with a locally applied A ∗ strategy. Remarkably, the implementation on the proposed technique achieves a speed-up of several orders of magnitude with respect to the approaches in the literature (either optimal, sup-optimal or approximate), often with a reasonable trade-off on the cost of the obtained alignment. • Suboptimal conformance checking algorithm using relaxation labeling and local A* search. • Alignment costs comparable to other state-of-the-art methods. • Execution times one or two orders of magnitude faster than other state-of-the-art methods. [ABSTRACT FROM AUTHOR]

The comparison of trace variants of business processes opens the door for a fine-grained analysis of the distinctive features inherent in the executions of a process in an organization. The current approaches for trace variant analysis do not consider the situation where a process model is present, and therefore, it can guide the derivation of the trace variants by considering high-level structures present in the process model. In this paper we propose a fresh alternative to trace variant analysis, which proposes a generalized notion of trace variant that incorporates concurrency and iteration. This way, the analyst may be relieved from analyzing trace variants that are essentially the same, if these aspects are disregarded. We propose a general algorithm for model based trace variant analysis which is grounded in encoding the problem into SAT, and a family of heuristic alternatives including a very light sampling technique that represents a good trade-off between quality of the trace variants identified, and the complexity of the analysis. All the techniques of the paper are implemented in two open-source tools, and experiments with publicly available benchmarks are reported. • A novel approach to generalize the notion of trace variant of an event log. • Proposal for two generalized trace variants: process and subnets, to cope with concurrency and loop behavior. • An encoding of the problem into SAT. • A sampling strategy to cope with the complexity of the problem, that incorporates certain statistical guarantees. • A qualitative and quantitative evaluation over well-known benchmarks. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we identify a novel and interesting type of queries, contextual ranking queries, which return the ranks of query tuples among some context tuples given in the queries. Contextual ranking queries are useful for olap and decision support applications in non-traditional data exploration. They provide a mechanism to quickly identify where tuples stand within the context. In this paper, we extend the sql language to express contextual ranking queries and propose a general partition-based framework for processing them. In this framework, we use a novel method that utilizes bitmap indices built on ranking functions. This method can efficiently identify a small number of candidate tuples, thus achieves lower cost than alternative methods. We analytically investigate the advantages and drawbacks of these methods, according to a preliminary cost model. Experimental results suggest that the algorithm using bitmap indices on ranking functions can be substantially more efficient than other methods. [Copyright &y& Elsevier]

In this paper, we formulate a novel question on maximum flow queries. Specifically, this problem aims to find which k edges would have the largest impact on a maximum flow query on a network. This problem has important applications in areas like social network and network planning. We show the inapproximability of the problems and present our heuristic algorithms. Experimental evaluations are carried out on real datasets and results show that our algorithms are scalable and return high quality solutions. [ABSTRACT FROM AUTHOR]

Topic modeling is used in information retrieval to infer the hidden themes in a collection of documents and thus provides an automatic means to organize, understand and summarize large collections of textual information. Topic models also offer an interpretable representation of documents used in several downstream Natural Language Processing (NLP) tasks. Modeling techniques vary from probabilistic graphical models to the more recent neural models. This paper surveys topic models from four aspects. The first aspect categorizes different topic modeling techniques into four categories: algebraic, fuzzy, probabilistic, and neural. We review the wide variety of available models from each category, highlight differences and similarities between models and model categories using a unified perspective, investigate these models' characteristics and limitations, and discuss their proper use cases. The second aspect illustrates six criteria for proper evaluation of topic models, from modeling quality to interpretability, stability, efficiency, and beyond. Topic modeling has found applications in various disciplines, owing to its interpretability. We examine these applications along with some popular software tools which provide an implementation of some models. The fourth aspect reviews available datasets and benchmarks. Using two benchmark datasets, we conducted experiments to compare seven topic models along the proposed metrics. The discussion highlights the differences between the models and their relative suitability for various applications. It notes the relationship between evaluation metrics and proposes four key aspects to help decide which model to use for an application. Our discussion also shows that the research trends move towards developing and tuning neural topic models and leveraging the power of pre-trained language models. Finally, it highlights research gaps in developing unified benchmarks and evaluation metrics. • Categorization of topic models into algebraic, probabilistic, fuzzy and neural. • Surveys models' evaluation criteria and different metrics used. • Surveys topic modeling software and applications. • Proposes a method to help select a topic model for an application. • Compares topic models across coherence, diversity, stability and efficiency. [ABSTRACT FROM AUTHOR]

Abstract: Process mining is the research domain that is dedicated to the a posteriori analysis of business process executions. The techniques developed within this research area are specifically designed to provide profound insight by exploiting the untapped reservoir of knowledge that resides within event logs of information systems. Process discovery is one specific subdomain of process mining that entails the discovery of control-flow models from such event logs. Assessing the quality of discovered process models is an essential element, both for conducting process mining research as well as for the use of process mining in practice. In this paper, a multi-dimensional quality assessment is presented in order to comprehensively evaluate process discovery techniques. In contrast to previous studies, the major contribution of this paper is the use of eight real-life event logs. For instance, we show that evaluation based on real-life event logs significantly differs from the traditional approach to assess process discovery techniques using artificial event logs. In addition, we provide an extensive overview of available process discovery techniques and we describe how discovered process models can be assessed regarding both accuracy and comprehensibility. The results of our study indicate that the HeuristicsMiner algorithm is especially suited in a real-life setting. However, it is also shown that, particularly for highly complex event logs, knowledge discovery from such data sets can become a major problem for traditional process discovery techniques. [Copyright &y& Elsevier]

Abstract: Many recent applications involve processing and analyzing uncertain data. In this paper, we combine the feature of top-k objects with that of skyline to model the problem of top-k skyline objects against uncertain data. The problem of efficiently computing top-k skyline objects on large uncertain datasets is challenging in both discrete and continuous cases. In this paper, firstly an efficient exact algorithm for computing the top-k skyline objects is developed for discrete cases. To address applications where each object may have a massive set of instances or a continuous probability density function, we also develop an efficient randomized algorithm with an guarantee. Moreover, our algorithms can be immediately extended to efficiently compute p-skyline; that is, retrieving the uncertain objects with skyline probabilities above a given threshold. Our extensive experiments on synthetic and real data demonstrate the efficiency of both algorithms and the randomized algorithm is highly accurate. They also show that our techniques significantly outperform the existing techniques for computing p-skyline. [Copyright &y& Elsevier]

Abstract: A suffix tree is a fundamental data structure for string searching algorithms. Unfortunately, when it comes to the use of suffix trees in real-life applications, the current methods for constructing suffix trees do not scale for large inputs. As suffix trees are larger than the input sequences and quickly outgrow the main memory, the first attempts at building large suffix trees focused on algorithms which avoid massive random access to the trees being built. However, all the existing practical algorithms perform random access to the input string, thus requiring in essence that the input be small enough to be kept in main memory. The constantly growing pool of string data, especially biological sequences, requires us to build suffix trees for much larger strings. We are the first to present an algorithm which is able to construct suffix trees for input sequences significantly larger than the size of the available main memory. Both the input string and the suffix tree are kept on disk and the algorithm is designed to avoid multiple random I/Os to both of them. 1 [1] The preliminary version of this paper was presented as a short paper at CIKM 2009 conference. As a proof of concept, we show that our method allows to build the suffix tree for 12GB of real DNA sequences in 26h on a single machine with 2GB of RAM. This input is four times the size of the Human Genome, and the construction of suffix trees for inputs of such magnitude was never reported before. [Copyright &y& Elsevier]

Abstract: The proliferation of sensor technology, especially in the context of embedded systems, has brought forward novel types of applications that make use of streams of continuously generated sensor data. Many applications like telemonitoring in healthcare or roadside traffic monitoring and control particularly require data stream management (DSM) to be provided in a distributed, yet reliable way. This is even more important when DSM applications are deployed in a failure-prone distributed setting including resource-limited mobile devices, for instance in applications which aim at remotely monitoring mobile patients. In this paper, we introduce a model for distributed and reliable DSM. The contribution of this paper is threefold. First, in analogy to the SQL isolation levels, we define levels of reliability and describe necessary consistency constraints for distributed DSM that specify the tolerated loss, delay, or re-ordering of data stream elements, respectively. Second, we use this model to design and analyze an algorithm for reliable distributed DSM, namely efficient coordinated operator checkpointing (ECOC). We show that ECOC provides lossless and delay-limited reliable data stream management and thus can be used in critical application domains such as healthcare, where the loss of data stream elements cannot be tolerated. Third, we present detailed performance evaluations of the ECOC algorithm running on mobile, resource-limited devices. In particular, we can show that ECOC provides a high level of reliability while, at the same time, featuring good performance characteristics with moderate resource consumption. [Copyright &y& Elsevier]

Abstract: We study the problem of clustering data objects with location uncertainty. In our model, a data object is represented by an uncertainty region over which a probability density function (pdf) is defined. One method to cluster such uncertain objects is to apply the UK-means algorithm , an extension of the traditional K-means algorithm, which assigns each object to the cluster whose representative has the smallest expected distance from it. For arbitrary pdf, calculating the expected distance between an object and a cluster representative requires expensive integration of the pdf. We study two pruning methods: pre-computation (PC) and cluster shift (CS) that can significantly reduce the number of integrations computed. Both pruning methods rely on good bounding techniques. We propose and evaluate two such techniques that are based on metric properties (Met) and trigonometry (Tri). Our experimental results show that Tri offers a very high pruning power. In some cases, more than 99.9% of the expected distance calculations are pruned. This results in a very efficient clustering algorithm. 1 [1] Part of this paper appears in Ngai et al., 2006 , in which the algorithms PC and CS were described. The idea of trigonometric pruning (), most of the empirical performance study (), discussion (), and all proofs of theorems (Appendixes), have not been previously published. The new materials amount to about of the current paper. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents the most comprehensive analysis and comparison of the most-known multimedia group and inter-stream synchronization approaches. Several types of multimedia synchronization are identified but only inter-stream and group synchronization algorithms are considered. This is the first survey including group synchronization techniques. A classification of the main synchronization techniques included in most of the analyzed algorithms complements the paper. Finally, a table is presented summarizing the main characteristics of each analyzed algorithm according to those techniques and other critical issues. [Copyright &y& Elsevier]

This paper reconsiders common benchmarking approaches to nearest neighbor search. It is shown that the concepts of local intrinsic dimensionality (LID), local relative contrast (RC), and query expansion allow to choose query sets of a wide range of difficulty for real-world datasets. Moreover, the effect of the distribution of these dimensionality measures on the running time performance of implementations is empirically studied. To this end, different visualization concepts are introduced that allow to get a more fine-grained overview of the inner workings of nearest neighbor search principles. Interactive visualizations are available on the companion website. 1 1 https://cecca.github.io/role-of-dimensionality/. The paper closes with remarks about the diversity of datasets commonly used for nearest neighbor search benchmarking. It is shown that such real-world datasets are not diverse: results on a single dataset predict results on all other datasets well. • Local dimensionality measures allow to build query sets of different degrees of difficulty. • Local Intrinsic Dimensionality is the most effective at selecting queries. • Using average performance measures hides interesting behavior of algorithms. • Datasets commonly used as benchmarks are not diverse enough. [ABSTRACT FROM AUTHOR]

The emergence of Location-based social networks (LBSNs) in recent years has boosted improvements in Recommender Systems for a new and specific task: the recommendation of points-of-interest (POI). Despite all the blunt advances recently observed, the area still lacks an updated and consolidated view about the main limitations, common assumptions, and directions we are following as a community. Thus, this paper aims to provide an updated picture of POI recommendation, identifying relevant efforts, results, contributions, and limitations. In this sense, through a systematic mapping, we selected 74 relevant papers published in the last three years (2017, 2018, and 2019) in the main conferences and journals of the area. Most of these studies have focused on the general POI recommendation problem, although we still could identify a significant number of efforts addressing specific problems in the area, such as Time-Aware, Next POI, and In/Out-of-Town Recommendations. Also, we found user contexts, such as social network and geolocation, as recurring data types used to improve preference elicitation when exploring different methods (e.g., collaborative filtering, factorization, probabilistic, link-based, and hybrid methods). As major limitations, first, we identified that these studies prioritize accuracy over other quality dimensions, despite the consensus in the RS community that accuracy alone is not enough to assess the practical effectiveness of Recommender Systems. Further, we found a low intersection of metrics and datasets used to evaluate the proposed solutions, along with a large number of metrics used in a few distinct studies. These observations point out the potential damage to reproducibility and straightforward comparison of results in the area, motivating us to propose an extensible POI recommendation benchmark. Through this benchmark, we showed that when proper evaluations are carried out, by considering different datasets, metrics, and baselines, identifying which algorithm is the best one becomes non-trivial. Finally, we highlight as a promising future work the in-depth exploitation of textual data since just a few evaluated studies marginally use this rich data source. • A systematic mapping of the POI recommendation area. • An analysis of 74 studies of the main conferences and journals from lat three years. • A discussion of contributions/limitations of recent studies on POI recommendation. • An extensible POI recommendation benchmark. • Directions for future works highlighting the needs of the reproducibility of results. [ABSTRACT FROM AUTHOR]

Abstract: General patterns of execution that have been frequently scheduled by a workflow management system provide the administrator with previously unknown, and potentially useful information, e.g., about the existence of unexpected causalities between subprocesses of a given workflow. This paper investigates the problem of mining unconnected patterns on the basis of some execution traces, i.e., of detecting sets of activities exhibiting no explicit dependency relationships that are frequently executed together. The problem is faced in the paper by proposing and analyzing two algorithms. One algorithm takes into account information about the structure of the control-flow graph only, while the other is a smart refinement where the knowledge of the frequencies of edges and activities in the traces at hand is also accounted for, by means of a sophisticated graphical analysis. Both algorithms have been implemented and integrated into a system prototype, which may profitably support the enactment phase of the workflow. The correctness of the two algorithms is formally proven, and several experiments are reported to evidence the ability of the graphical analysis to significantly improve the performances, by dramatically pruning the search space of candidate patterns. [Copyright &y& Elsevier]

Algebraic optimisation is both theoretically and practically important for query processing in complex value databases. In this paper, we consider this issue and investigate some algebraic properties concerning the nested relational operators.The join operation is one of the most time-consuming operations in nested relational query processing. We introduce a new join operator, called P-join, which combines the advantages of Roth''s extended natural join and Colby''s recursive join for efficient data access. We also investigate some algebraic properties concerning the P-join operator and extended relational operators, which can be used for query optimisation in nested relational databases.We then examine the role of the restructuring operators nest and unnest in their interactions with the extended relational operators proposed by Roth et al. Under certain functional and mutual data dependencies, the six nested relational equations will hold.Finally, we outline the steps of a heuristic optimisation algorithm that utilises algebraic transformation rules developed in this paper and previous related work to transform an initial query to an optimised one that is more efficient to execute. [Copyright &y& Elsevier]

In this paper we propose a matching algorithm for measuring the structural similarity between an XML document and a DTD. The matching algorithm, by comparing the document structure against the one the DTD requires, is able to identify commonalities and differences. Differences can be due to the presence of extra elements with respect to those the DTD requires and to the absence of required elements. The evaluation of commonalities and differences gives raise to a numerical rank of the structural similarity. Moreover, in the paper, some applications of the matching algorithm are discussed. Specifically, the matching algorithm is exploited for the classification of XML documents against a set of DTDs, the evolution of the DTD structure, the evaluation of structural queries, the selective dissemination of XML documents, and the protection of XML document contents. [Copyright &y& Elsevier]

Answering statistical queries about streams of online arriving data is becoming increasingly important. Often, such data includes multiple-attributes, so data elements can be viewed as points in a multi-dimensional universe. This paper extends existing works on streaming algorithms by studying the ability to perform box queries on online multi-dimensional data streams. We develop three algorithms C-DARQ , DARQ and MARQ that support such capabilities for a large number of statistical functions including (but not limited to) counting, frequency estimation, heavy-hitters etc. We also apply our algorithms in distributed settings, in which measurements are recorded independently by multiple sites (e.g., multiple routers), and the goal is to obtain a global network analysis. The protocols are analyzed and evaluated over synthetic dataset, Chicago dataset, and a Facebook dataset from Kaggle in multiple dimensions (up to 10). Our algorithms asymptotically improve the space bounds as well as update and query performance of existing works. Unlike known approaches, our algorithms can also be used to solve a larger class of problems beyond counting. We further discuss extending our work to the sliding window model and when the dimensions' bounds are a-priori unknown. [ABSTRACT FROM AUTHOR]

Denial constraints (DCs) are expressive enough to subsume many other dependencies, and proven useful in data cleaning for improving data quality. As a complement to the methods of computing a single (nearly) optimum repair of DC violations, in this paper we make the first effort to diversify repairs of DC violations, aiming to generate a set of diversified repairs. (1) We adapt the concept of cardinality-set-minimal repairs to DCs, and relate a cardinality-set-minimal repair to a minimal vertex cover of the conflict hypergraph w.r.t. a given set Σ of DCs on a relational instance I. (2) We formalize the problem of diversifying cardinality-set-minimal repairs of DC violations, and address the problem by presenting a set of algorithms and optimizations to generate a set of diversified minimal vertex covers of the conflict hypergraph. (3) Using both real-life and synthetic data, we conduct extensive experiments to verify the effectiveness and efficiency of our methods. • Relationship between repairs and vertex covers of the conflict hypergraph. • Methods to diversify minimal vertex covers. • Evaluations of the effectiveness and efficiency of diversifying repairs. [ABSTRACT FROM AUTHOR]

Set similarity join (SSJ) is a well studied problem with many algorithms proposed to speed up its performance. However, its scalability and performance are rarely discussed in modern multicore environments. Existing algorithms assume a single-threaded execution that leaves the abundant parallelism provided by modern machines unused, or use distributed setups that may not yield efficient runtimes and speedups that are proportional to the amount of hardware resources (e.g., CPU cores). In this paper, we focus on a widely-used family of SSJ algorithms that are based on the filter-and-verification paradigm, and study the potential of speeding them up in the context of multicore machines. We adapt state-of-the-art SSJ algorithms including PPJoin and AllPairs. Our experiments using 12 real-world datasets highlight important findings: (1) Using the exact number of hardware-provided hyperthreads leads to optimal runtimes for most experiments, (2) hand-crafted data structures do not always lead to better performance, and (3) PPJoin's position filter is more effective in the multithreaded case compared to the single-threaded execution. • Multi-threading has not yet been considered to speed up set similarity joins. • We propose a novel data-parallel set similarity join algorithm. • Multi-threading speeds up the set similarity join 2 to 10 times. • Implementation optimizations are not benefitial for the runtime. [ABSTRACT FROM AUTHOR]

The Recommender System (RS) is an efficient tool for decision makers that assists in the selection of appropriate items according to their preferences and interests. This system has been applied to various domains to personalize applications by recommending items such as books, movies, songs, restaurants, news articles and jokes, among others. An important issue for the RS that has greatly captured the attention of researchers is the new user cold-start problem, which occurs when there is a new user that has been registered to the system and no prior rating of this user is found in the rating table. In this paper, we first present a classification that divides the relevant studies addressing the new user cold-start problem into three major groups and summarize their advantages and disadvantages in a tabular format. Next, some typical algorithms of these groups, such as MIPFGWC-CS, NHSM, FARAMS and HU–FCF, are described. Finally, these algorithms are implemented and validated on some benchmark RS datasets under various settings of the new user cold start. The experimental results indicate that NHSM achieves better accuracy and computational time than the relevant methods. [ABSTRACT FROM AUTHOR]

This paper presents a memory-constrained hash join algorithm (PaMeCo Join) designed to operate with main-memory column-store database systems. Whilst RAM has become more affordable and the popularity of main-memory database systems continues to grow, we recognize that RAM is a finite resource and that database systems rarely have an excess of memory available to them. Therefore, we design PaMeCo to operate within an arbitrary memory limitation by processing the input relations by parts, and by using a compact hash table that represents the contained tuples in a compact format. Coupled with a radix-clustering system that lowers memory latencies, we find that PaMeCo can offer competitive performance levels to other contemporary hash join algorithms in an unconstrained environment, while being up to three times faster than a high-performing hash join when memory constraints are applied. [ABSTRACT FROM AUTHOR]

Snapshot Isolation (SI) is in wide use by database systems but does not guarantee serializability. Serializable snapshot isolation (SSI) was defined in 2008 by Cahill, Röhm, and Fekete in Ref. [1] and an enhanced version that we call ESSI was defined in 2009 by the same authors [2] . Both guarantee serializable execution by aborting transactions that might be involved in anomalies, but occasional transactions are aborted unnecessarily. The resulting commit order is often different from the serialization order and this can confuse bank auditors, for example. In this paper we show how to determine the proper serialization order of these transactions and store this information for later access. With this known serialization order the database system can perform time-travel queries to capture snapshots of consistent database states in the past. Our algorithm assigns to each SSI or ESSI transaction at its commit time an appropriate serialization order timestamp that falls within the transaction lifetime, i.e., between its start-time and commit-time. The algorithm uses only information already gathered by the algorithm implementing ESSI in [2] . [ABSTRACT FROM AUTHOR]

Advancements in mobile technology and computing have fostered the collection of a large number of civic datasets that capture the pulse of urban life. Furthermore, the open government and data initiative has led many local authorities to make these datasets publicly available, hoping to drive innovation that will further improve the quality of life for the city-dwellers. In this paper, we develop a novel application that utilizes crime data to provide safe urban navigation. Specifically, using crime data from Chicago and Philadelphia we develop a risk model for their street urban network, which allows us to estimate the relative probability of a crime on any road segment. Given such model we define two variants of the SafePaths problem where the goal is to find a short and low-risk path between a source and a destination location. Since both the length and the risk of the path are equally important but cannot be combined into a single objective, we approach the urban-navigation problem as a biobjective shortest path problem. Our algorithms aim to output a small set of paths that provide tradeoffs between distance and safety. Our experiments demonstrate the efficacy of our algorithms and their practical applicability. [ABSTRACT FROM AUTHOR]

Process discovery is the task of generating process models from event logs. Mining processes that operate in an environment of high variability is an ongoing research challenge because various algorithms tend to produce spaghetti-like process models. This is particularly the case when procedural models are generated. A promising direction to tackle this challenge is the usage of declarative process modelling languages like Declare, which summarise complex behaviour in a compact set of behavioural constraints on activities. A Declare constraint is branched when one of its parameters is the disjunction of two or more activities. For example, branched Declare can be used to express rules like “in a bank, a mortgage application is always eventually followed by a notification to the applicant by phone or by a notification by e-mail”. However, branched Declare constraints are expensive to be discovered. In addition, it is often the case that hundreds of branched Declare constraints are valid for the same log, thus making, again, the discovery results unreadable. In this paper, we address these problems from a theoretical angle. More specifically, we define the class of Target-Branched Declare constraints and investigate the formal properties it exhibits. Furthermore, we present a technique for the efficient discovery of compact Target-Branched Declare models. We discuss the merits of our work through an evaluation based on a prototypical implementation using both artificial and real-life event logs. [ABSTRACT FROM AUTHOR]

Hierarchical data are often modelled as trees. An interesting query identifies pairs of similar trees. The standard approach to tree similarity is the tree edit distance, which has successfully been applied in a wide range of applications. In terms of runtime, the state-of-the-art algorithm for the tree edit distance is RTED, which is guaranteed to be fast independent of the tree shape. Unfortunately, this algorithm requires up to twice the memory of its competitors. The memory is quadratic in the tree size and is a bottleneck for the tree edit distance computation. In this paper we present a new, memory efficient algorithm for the tree edit distance, AP-TED (All Path Tree Edit Distance). Our algorithm runs at least as fast as RTED without trading in memory efficiency. This is achieved by releasing memory early during the first step of the algorithm, which computes a decomposition strategy for the actual distance computation. We show the correctness of our approach and prove an upper bound for the memory usage. The strategy computed by AP-TED is optimal in the class of all-path strategies, which subsumes the class of LRH strategies used in RTED. We further present the AP-TED + algorithm, which requires less computational effort for very small subtrees and improves the runtime of the distance computation. Our experimental evaluation confirms the low memory requirements and the runtime efficiency of our approach. [ABSTRACT FROM AUTHOR]