Time series segmentation (TSS) is often an unsupervised data mining task that partitions a given time series into homogeneous regions. Existing TSS algorithms either scale poorly or perform poorly on complex large-scale time series (TS) commonly observed in real-world applications. This paper introduces Deep Clustering for Time Series Segmentation (DC-TSS). DC-TSS is a domain-agnostic method that uses a three-phase neural-based model to segment a given time series. DC-TSS includes a carefully designed neural architecture and a newly designed data augmentation approach to efficiently learn TS representations, utilizes a neural-based clustering model to refine such representations, designs a novel efficient component to infer segments from clustered TS representation, and provides mechanisms to understand/interpret the segmentation results. We test DC-TSS on 27 multivariate time series datasets, which are much larger and more complex than others typically used in TSS studies. We also test DC-TSS on a more traditional repository of 98 simpler time series datasets. The experiments from both types of dataset provide an in-depth analysis of DC-TSS’s performance and limitations. We compare five variations of our method against seven strong baselines. The results show that DC-TSS significantly outperforms other methods and scales well to larger and more complex datasets and shows some limitation on shorter simple datasets. DC-TSS addresses a growing need for unsupervised TSS algorithms designed to segment large-scale, complex datasets, which are becoming more common as evolving technology allows collecting and storing greater volumes of data.

Dimensionality reduction aims to find low-dimensional embeddings of high-dimensional data such that the low-dimensional representation preserves some meaningful properties of structures in the original data. When low-dimensional space is 2- or 3-dimensional, the low-dimensional embeddings can be visualized using a scatterplot map. Most of the existing methods try to preserve the local neighborhoods of all data points. However, in general, it is impossible to retain all such information for all data points in the low-dimensional space. As a result, there could be some data points whose neighborhoods are not faithfully displayed in the visualization due to information loss. If the information loss happens around a specific set of points of interest (e.g., specific patients, or proteins under observed), this may be problematic because the withdrawn insights may not be accurate for these observed data points. Therefore, in this paper, we introduce a problem called focused dimensionality reduction where given an original high-dimensional dataset and a set of points of interest, we want to find 2- or 3-dimensional embeddings of the original data such that the information loss in the local neighborhoods surrounding the points of interest is minimized as much as possible. In other words, if the information loss is inevitable, it should not happen around the points of interest. To solve the problem, we extend the stochastic neighbor embedding method and introduce a focused objective function where we put more weight on losses that involve points of interest. Experiments on real-world datasets show that our proposed method is better in preserving the local neighborhood structure of points of interest while the generated visualizations are as good as those generated by the stochastic neighbor embedding method.

Recommender Systems ( RecSys ) provide suggestions in many decision-making processes. Given that groups of people can perform many real-world activities (e.g., a group of people attending a conference looking for a place to dine), the need for recommendations for groups has increased. A wide range of Group Recommender Systems ( GRecSys ) has been developed to aggregate individual preferences to group preferences. We analyze 175 studies related to GRecSys . Previous works evaluate their systems using different types of groups (sizes and cohesiveness), and most of such works focus on testing their systems using only one type of item, called Experience Goods (EG). As a consequence, it is hard to get consistent conclusions about the performance of GRecSys . We present the aggregation strategies and aggregation functions that GRecSys commonly use to aggregate group members’ preferences. This study experimentally compares the performance (i.e., accuracy, ranking quality, and usefulness) using four metrics (Hit Ratio, Normalize Discounted Cumulative Gain, Diversity, and Coverage) of eight representative RecSys for group recommendations on ephemeral groups. Moreover, we use two different aggregation strategies, 10 different aggregation functions, and two different types of items on two types of datasets (EG and Search Goods (SG)) containing real-life datasets. The results show that the evaluation of GRecSys needs to use both EG and SG types of data, because the different characteristics of datasets lead to different performance. GRecSys using Singular Value Decomposition or Neural Collaborative Filtering methods work better than others. It is observed that the Average aggregation function is the one that produces better results.

Change point detection is widely used for finding transitions between states of data generation within a time series. Methods for change point detection currently assume this transition is instantaneous and therefore focus on finding a single point of data to classify as a change point. However, this assumption is flawed because many time series actually display short periods of transitions between different states of data generation. Previous work has shown Bayesian Online Change Point Detection (BOCPD) to be the most effective method for change point detection on a wide range of different time series. This paper explores adapting the change point detection algorithms to detect abrupt changes over short periods of time. We design a segment-based mechanism to examine a window of data points within a time series, rather than a single data point, to determine if the window captures abrupt change. We test our segment-based Bayesian change detection algorithm on 36 different time series and compare it to the original BOCPD algorithm. Our results show that, for some of these 36 time series, the segment-based approach for detecting abrupt changes can much more accurately identify change points based on standard metrics.

Multivariate time series (MTS) are collected for different variables in studying scientific phenomena or monitoring system health where each time series records the values of one variable for a time period. Among the different variables, it is common that only a few variables contribute significantly to a specific phenomenon. Furthermore, the variables contributing significantly to different phenomena are often different. We denote the different variables that contribute to the occurrences of different phenomena as Phenomenon-specific Variables (PVs). In this paper, we formulate a novel problem of identifying significant PVs from MTS datasets. To analyze MTS data, feature extraction techniques have been extensively studied. However, most of them identify important global features for one dataset and do not utilize the temporal order of time series. To solve the newly introduced problem, we propose a solution framework, CNNmts-X, which is a new variant of the Convolutional Neural Networks (CNN) and can embed other feature extraction techniques (as X). Furthermore, we design a CNNmts-LR method that implements a new feature identification approach (LR) as Xin the CNNmts-X framework. The LR method leverages both Linear Discriminant Analysis (LDA) and Random Forest (RF). Our extensive experiments on five real datasets show that the CNNmts-LR method has exhibited much better performance than several other baseline methods. Using 30 percent of the PVs discovered from the CNNmts-LR, classifications can achieve better or similar performance than using all the variables.

Skyline queries find the representative data points from a multi-dimensional dataset, which are better than other data points on at least one dimension. A multi-cost transportation network (MCTN) can be modeled as a multi-dimensional dataset. The MCTN-constrained skyline query (CSQ) is a type of skyline queries on MCTN where the query point and the skyline answer-objects are points of interest (POI) that are off the network, and the answer-points need to be reached from the query point by utilizing the MCTN. CSQ is useful in many applications such as trip planning and apartment selection. For example, when a person wants to find an apartment, he/she may consider not only the price and the number of rooms of the apartment but also the cost and travel time of using public transportation from his apartment to his/her office.In this paper, we present a system to answer MCTN-constrained CSQs, namely CSQ system. This system is implemented as a web application, which allows users to input a query point from a web interface, get the skyline result by using several algorithms, and display the result on the web interface. We load the POIs and public transportation networks of three cities (Los Angeles, San Francisco, and New York) to the system, and explain how users can interact with the CSQ system.

Skyline queries are used to find the Pareto optimal solution from datasets containing multi-dimensional data points. In this paper, we propose a new type of skyline queries whose evaluation is constrained by a multi-cost transportation network (MCTN) and whose answers are off the network. This type of skyline queries is useful in many applications. For example, a person wants to find an apartment by considering not only the price and the surrounding area of the apartment, but also the transportation cost, time, and distance between the apartment and his/her work place. Most existing works that evaluate skyline queries on multi-cost networks (MCNs), which are either MCTNs or road networks, find interesting objects that locate on edges of the networks. Formally, our new type of skyline queries takes as input an MCTN, a query point q, and a set of objects of interest D with spatial information, where q and the objects in D are off the network. The answers to such queries are objects in D that are not dominated by other D objects when considering the multiple attributes of these objects and the multiple network cost from q to the solution objects. To evaluate such queries, we propose an exact search algorithm and its improved version by implementing several properties. The space of the exact skyline solutions is huge and can easily reach the order of thousands and incur long evaluation time. We further design much more efficient heuristic methods to find approximate solutions. We run extensive experiments using both real and synthetic datasets to test the effectiveness and efficiency of our proposed approaches. The results show that the exact search algorithm can be dramatically improved by utilizing several properties. The heuristic approaches to find approximate answers can largely reduce the query time and retrieve results that are comparable to the exact solutions.

Latent Dirichlet Allocation (LDA) has been widely used in text mining to discover topics from documents. One major approach to learn LDA is Gibbs sampling. The basic Collapsed Gibbs Sampling (CGS) algorithm requires O(NZ) computations to learn an LDA model with Z topics from a corpus containing N tokens. Existing approaches that improve the complexity of CGS focus on reducing the factor Z. In this work, we propose a novel and general Sub-Gibbs Sampling (SGS) strategy to improve the Gibbs-Sampling computation by reducing the sample space. This new strategy targets at reducing the factor N by sampling only a subset of the whole corpus. The design of the SGS strategy is based on two properties that we observe: (i) topic distributions of tokens are skewed and (ii) a subset of documents can approximately represent the semantics of the whole corpus. We prove that the SGS strategy can achieve comparable effectiveness (with bounded errors) and significantly reduce the complexity of existing Gibbs sampling algorithms. Extensive experiments on large real-world data sets show that the proposed SGS strategy is much faster than several state-of-the-art fast Gibbs sampling algorithms and the proposed SGS strategy can learn comparable LDA models as other Gibbs sampling algorithms.

Graphs have been widely used to represent objects and object connections in applications such as the web, social networks, and citation networks. Mining influence relationships from graphs has gained increasing interests in recent years because providing information on how graph objects influence each other can facilitate graph exploration, graph search, and connection recommendations. In this paper, we study the problem of detecting influence aspects, on which objects are connected, and influence degree (or influence strength), with which one graph node influences another graph node on a given aspect. Existing techniques focus on inferring either the overall influence degrees or the influence types from graphs. In this paper, we propose a systematic approach to extract influence aspects and learn aspect-level influence strength. In particular, we first present a novel instance-merging based method to extract influence aspects from the context of object connections. We then introduce two generative models, Observed Aspect Influence Model (OAIM) and Latent Aspect Influence Model (LAIM), to model the topological structure of graphs, the text content associated with graph objects, and the context in which the objects are connected. To learn OAIM and LAIM, we design both non-parallel and parallel Gibbs sampling algorithms. We conduct extensive experiments on synthetic and real data sets to show the effectiveness and efficiency of our methods. The experimental results show that our models can discover more effective results than existing approaches. Our learning algorithms also scale well on large data sets.

A solution of a keyword query over graphs is a Group Steiner tree, which is rooted at a node and whose nodes collectively satisfy the query (e.g. node keywords cover all the query keywords), and in which the sum of edge weights satisfies given conditions (e.g., need to be minimum or be the first K minimal among all possible sub-graphs satisfying the query). Most existing techniques for evaluating keyword queries over graphs run on a centralized computer. We propose a new approach, SOverlapping, to evaluate keyword queries over graphs on MapReduce framework by utilizing probabilistic theory to partition graphs. The new approach has shown to be effective and efficient when tested on real graph data sets.

Influence among objects prevalently exists in graph structured data. However, most existing research efforts detect influence among objects from snapshots of homogeneous graphs. In this paper, we study a new problem of detecting time-evolving influence among objects from dynamic heterogeneous graphs. We propose a probabilistic graphical model, Time-evolving Influence Model (TIM), to capture the temporal dynamics of graphs, in which the time-evolving influence is hidden, and to leverage the information from heterogeneous graphs, with which we can improve the learned knowledge. To learn the graphical model, we design both non-parallel and parallel Gibbs sampling algorithms. We conduct extensive experiments on both synthetic and real data sets to show the effectiveness of the proposed model and the efficiency of the learning algorithms.

Graphs have been widely used to represent objects and object connections in applications such as the Web, social networks, and citation networks. Mining influence relationships from graphs has gained interests in recent years because providing influence information about the object connections in graphs can facilitate graph exploration, graph search, and connection recommendations. In this paper, we study the problem of detecting influence aspects, on which objects are connected, and influence degree (or influence strength), with which one graph node influences another graph node on a given aspect. Existing techniques focus on inferring either the influence degrees or influence types from graphs. We propose two generative Aspect Influence Models, OAIM and LAIM, to detect both influence aspects and influence degrees. These models utilize the topological structure of the graphs, the text content associated with objects, and the context in which the objects are connected. We compare these two models with one baseline approach which considers only the text content associated with objects. The empirical studies on citation graphs and networks of users from Twitter show that our models can discover more effective results than the baseline approach.

It is very helpful for a user to get a moderate amount of information highly related to his/her immediate context (e.g., location, time, discussion topics) during the exploration of digital object collections (e.g., articles, web pages, blogs). For instance, in investigating a research topic, a researcher may be very interested in finding articles that are most related to the articles he/she already read on this topic, which we consider as “context” in this paper. To facilitate users' exploration, we introduce the problem of discovering Context-aware Influential Objects (CIO) from a collection of digital objects with influence relationships. Although there is a large amount of work in detecting direct influence degree between objects to denote how strong an object influences others, very few works utilize such direct influence to find influential objects for a context. To discover CIOs for a context consisting of several objects of a user's interest, the first challenge is to meaningfully measure the collective influence of an object over a context considering both the direct influence and the indirectly derived influence, which is not taken into consideration by most “query by example” approaches. We propose an aggregation framework to formulate the collective influence among objects by leveraging both direct and indirect influence. The second challenge is to discover CIOs efficiently. We present three approaches to calculate collective influence of an object over a context from an influence graph. In particular, the first approach utilizes the breadth-first-search paradigm; the other approaches make use of the topological sorting of graph nodes and perform context-aware search using push and pull mechanisms. We show experimental results on real datasets to demonstrate the effectiveness and efficiency of the proposed methodologies.

Query processing over weighted data graphs often involves searching for a minimum weighted subgraph --a tree-- which covers the nodes satisfying the given query criteria (such as a given set of keywords). Existing works often focus on graphs where the edges have scalar valued weights. In many applications, however, edge weights need to be represented as ranges (or intervals) of possible values. In this paper, we introduce the problem of skynets, for searching minimum weighted subgraphs, covering the nodes satisfying given query criteria, over interval-weighted graphs. The key challenge is that, unlike scalars which are often totally ordered, depending on the application specific semantics of the ≤ operator, intervals may be partially ordered. Naturally, the need to maintain alternative, incomparable solutions can push the computational complexity of the problem (which is already high for the case with totally ordered scalar edge weights) even higher. In this paper, we first provide alternative definitions of the ≤ operator for intervals and show that some of these lend themselves to efficient solutions. To tackle the complexity challenge in the remaining cases, we propose two optimization criteria that can be used to constrain the solution space. We also discuss how to extend existing approximation algorithms for Steiner trees to discover solutions to the skynet problem. For efficient calculation of the results, we introduce a novel skyline union operator. Experiments show that the proposed approach achieves significant gains in efficiency, while providing close to optimal results.

Feedback process has been used extensively in document-centric applications, such as text retrieval and multimedia retrieval. Recently, there have been efforts to apply feedback to semi-structured XML document collections as well. In this paper, we note that feedback can also be an effective tool for exploring (through result ranking and query refinement) large semi-structured data collections. In particular, in large scale data sharing and curation environments, where the user may not know the structure of the data, queries may initially be overly vague. Given a path query and a set of results identified by the system to this query over the data, we consider two types of feedback: Soft feedback captures the user's preference for some features over the others. Hard feedback, on the other hand, expresses users' assertions regarding whether certain features should be further enforced or, in contrast, are to be avoided. Both soft and hard feedback can be "positive" or "negative". For soft feedback, we develop a probabilistic feature significance measure and describe how to use this for ranking results in the presence of dependencies between the path features. To deal with the hard feedback efficiently (i.e., fast enough for interactive exploration), we present finite automata based query refinement solutions. In particular, we present a novel LazyDFA+ algorithm for managing hard feedback. We also describe optimizations that leverage the inherently iterative nature of the feedback process. We bring together these techniques in AXP, a system for adaptive and exploratory path retrieval. The experimental results show the effectiveness of the proposed techniques.

Feedback driven data exploration schemes have been implemented for non-structured data (such as text) and document-centric XML collections where formulating precise queries is often impossible. In this paper, we study the problem of enabling exploratory access, through ranking, to data-centric XML. Given a path query and a set of results identified by the system to this query over the data, we consider feedback which captures the user's preference for some features over the others. The feedback can be "positive" or "negative". To deal with feedback, we develop a probabilistic feature significance measure and describe how to use this for ranking results in the presence of dependencies between the path features. We bring together these techniques in AXP, a system for adaptive and exploratory path retrieval. The experimental results show the effectiveness of the proposed techniques.

Consider a scientist who wants to explore multiple data sets to select the relevant ones for further analysis. Since the visualization real estate may put a stringent constraint on how much detail can be presented to this user in a single page, effective table summarization techniques are needed to create summaries that are both sufficiently small and effective in communicating the available content. In this paper, we first argue that table summarization can benefit from knowledge about acceptable value clustering alternatives for clustering the values in the database. We formulate the problem of table summarization with the help of value lattices. We then provide a framework to express alternative clustering strategies and to account for various utility measures (such as information loss) in assessing different summarization alternatives. Based on this interpretation, we introduce three preference criteria, max-min-util (cautious), max-sum-util (cumulative), and pareto-util, for the problem of table summarization. To tackle with the inherent complexity, we rely on the properties of the fuzzy interpretation to further develop a novel ranked set cover based evaluation mechanism (RSC). These are brought together in an AlphaSum, table summarization system. Experimental evaluations showed that RSC improves both execution times and the summary qualities in AlphaSum, by pruning the search space more effectively than the existing solutions.

Table summarization is necessary in various scenarios where it is hard to display a large table. It can benefit from knowledge about acceptable value clustering alternatives. In this paper, we formulate the problem of table summarization with the help of domain knowledge lattices. We provide the outline of a fuzzy mechanism to express alternative clustering strategies. We further sketch a novel ranked set cover based evaluation mechanism (RSC) to tackle with the inherent complexity.

In many applications that track and analyze spatiotemporal data, movements obey periodic patterns; the objects follow the same routes (approximately) over regular time intervals. For example, people wake up at the same time and follow more or less the same route to their work everyday. The discovery of hidden periodic patterns in spatiotemporal data could unveil important information to the data analyst. Existing approaches for discovering periodic patterns focus on symbol sequences. However, these methods cannot directly be applied to a spatiotemporal sequence because of the fuzziness of spatial locations in the sequence. In this paper, we define the problem of mining periodic patterns in spatiotemporal data and propose an effective and efficient algorithm for retrieving maximal periodic patterns. In addition, we study two interesting variants of the problem. The first is the retrieval of periodic patterns that are frequent only during a continuous subinterval of the whole history. The second problem is the discovery of periodic patterns, whose instances may be shifted or distorted. We demonstrate how our mining technique can be adapted for these variants. Finally, we present a comprehensive experimental evaluation, where we show the effectiveness and efficiency of the proposed techniques

Given a collection of trajectories of moving objects with different types (e.g., pumas, deers, vultures, etc.), we introduce the problem of discovering collocation episodes in them (e.g., if a puma is moving near a deer, then a vulture is also going to move close to the same deer with high probability within the next 3 minutes). Collocation episodes catch the inter-movement regularities among different types of objects. We formally define the problem of mining collocation episodes and propose two scaleable algorithms for its efficient solution. We empirically evaluate the performance of the proposed methods using synthetically generated data that emulate real-world object movements.

Many applications track the movement of mobile objects, which can be represented as sequences of timestamped locations. Given such a spatiotemporal series, we study the problem of discovering sequential patterns, which are routes frequently followed by the object. Sequential pattern mining algorithms for transaction data are not directly applicable for this setting. The challenges to address are: (i) the fuzziness of locations in patterns, and (ii) the identification of non-explicit pattern instances. In this paper, we define pattern elements as spatial regions around frequent line segments. Our method first transforms the original sequence into a list of sequence segments, and detects frequent regions in a heuristic way. Then, we propose algorithms to find patterns by employing a newly proposed substring tree structure and improving a priori technique. A performance evaluation demonstrates the effectiveness and efficiency of our approach.

In many applications that track and analyze spatiotemporal data, movements obey periodic patterns; the objects follow the same routes (approximately) over regular time intervals. For example, people wake up at the same time and follow more or less the same route to their work everyday. The discovery of hidden periodic patterns in spatiotemporal data, apart from unveiling important information to the data analyst, can facilitate data management substantially. Based on this observation, we propose a framework that analyzes, manages, and queries object movements that follow such patterns. We define the spatiotemporal periodic pattern mining problem and propose an effective and fast mining algorithm for retrieving maximal periodic patterns. We also devise a novel, specialized index structure that can benefit from the discovered patterns to support more efficient execution of spatiotemporal queries. We evaluate our methods experimentally using datasets with object trajectories that exhibit periodicity.