Querying and extracting potentially a large number of entities that are the user's intention is a challenging problem for knowledge graphs. The conventional query mechanism of subgraph pattern matching would not work well as the user in general does not know the graph pattern to search for. Moreover, there may not be a single subgraph pattern that fits all the intended entities. Using keywords also may not be a viable approach, as it is very difficult to come up with the right set of keywords, and the results are often very diverse and overwhelming. We propose a novel approach that does not require users to know much about the knowledge graph but only simple keywords about the desired entities. We retrieve a sample of matches and learn the entity context patterns as what we call the subgraph sketch signatures. We provide clustered patterns for the user to prune. Moreover, we devise a novel index to finally perform efficient entity retrieval over the whole knowledge graph.

Knowledge graphs have seen increasingly broad applications. However, they are known to be incomplete. We define the notion of a virtual knowledge graph which extends a knowledge graph with predicted edges and their probabilities. We focus on two important types of queries: top-k entity queries and aggregate queries. To improve query processing efficiency, we propose an incremental index on top of low dimensional entity vectors transformed from network embedding vectors. We also devise query processing algorithms with the index. Moreover, we provide theoretical guarantees of accuracy, and conduct a systematic experimental evaluation. The experiments show that our approach is very efficient and effective. In particular, with the same or better accuracy guarantees, it is one to two orders of magnitude faster in query processing than the closest previous work which can only handle one relationship type.

We study a practical problem of predicting the upcoming events in data streams using a novel approach. Treating event time orders as relationship types between event entities, we build a dynamic knowledge graph and use it to predict future event timing. A unique aspect of this knowledge graph embedding approach for prediction is that we enhance conventional knowledge graphs with the notion of "states"---in what we call the ephemeral state nodes---to characterize the state of a data stream over time. We devise a complete set of methods for learning relevant events, for building the event-order graph stream from the original data stream, for embedding and prediction, and for theoretically bounding the complexity. We evaluate our approach with four real world stream datasets and find that our method results in high precision and recall values for event timing prediction, ranging between 0.7 and nearly 1, significantly outperforming baseline approaches. Moreover, due to our choice of efficient translation-based embedding, the overall throughput that the stream system can handle, including continuous graph building, training, and event predictions, is over one thousand to sixty thousand tuples per second even on a personal computer---which is especially important in resource constrained environments, including edge computing.

Dynamic networks are very common in urban systems today. As data are acquired, unfortunately, they are rarely complete observations of the whole system. It is important to reliably infer the unobserved attribute values anywhere in the graphs, at certain times---either in the past or in the future. Previous work does not sufficiently capture the correlations inherent with graph topology and with time. We propose a machine learning approach using a novel probabilistic graphical model. We devise a series of algorithms to efficiently group the vertices, to learn the model parameters, and to infer the unobserved values for query processing. Furthermore, we propose a method to incrementally and automatically update the model. Finally, we perform an extensive experimental study using two real-world dynamic graph datasets to evaluate our approach.

Online dating sites have become popular platforms for people to look for potential romantic partners. Different from traditional user-item recommendations where the goal is to match items (e.g., books, videos, etc) with a user's interests, a recommendation system for online dating aims to match people who are mutually interested in and likely to communicate with each other. We introduce similarity measures that capture the unique features and characteristics of the online dating network, for example, the interest similarity between two users if they send messages to same users, and attractiveness similarity if they receive messages from same users. A reciprocal score that measures the compatibility between a user and each potential dating candidate is computed and the recommendation list is generated to include users with top scores. The performance of our proposed recommendation system is evaluated on a real-world dataset from a major online dating site in China. The results show that our recommendation algorithms significantly outperform previously proposed approaches, and the collaborative filtering-based algorithms achieve much better performance than content-based algorithms in both precision and recall. Our results also reveal interesting behavioral difference between male and female users when it comes to looking for potential dates. In particular, males tend to be focused on their own interest and oblivious towards their attractiveness to potential dates, while females are more conscientious to their own attractiveness to the other side of the line.

Large-scale information gathering becomes more and more common with the increasing popularity of smartphones, GPS, social networks, and sensor networks. Services based on this real-time data are the logical next step. Service Oriented Stream Systems (SOSS) have a focus on one-time ad hoc queries as op-posed to continuous queries. High availability is crucial in these services. However, data replication has inherent costs, which are particularly burdensome for high rate, often overloaded, SOSS. To provide high availability and to cope with the problem of over-loading the system, we propose a mechanism called soft quorums. Soft quorums incorporate a tuning knob that provides a trade off between query result accuracy and performance. Thus, in essence, soft quorums simultaneously offer high availability and per-query load shedding as needed. This is done in a system-wise optimal way. The parameter choices of soft quorums automatically adapt to dynamic data stream rates and query rates, and minimize the overall system load, given an accuracy requirement. We devise a recovery algorithm and study data quality after recovery. Finally, we conduct a comprehensive experimental study using two real-world and some synthetic datasets.

A graph is a fundamental and general data structure underlying all data applications. Many applications today call for the management and query capabilities directly on graphs. Real time graph streams, as seen in road networks, social and communication networks, and web requests, are such applications. Event pattern matching requires the awareness of graph structures, which is different from traditional complex event processing. It also requires a focus on the dynamicity of the graph, time order constraints in patterns, and online query processing, which deviates significantly from previous work on subgraph matching as well. We study the semantics and efficient online algorithms for this important and intriguing problem, and evaluate our approaches with extensive experiments over real world datasets in four different domains.

Online dating sites have become popular platforms for people to look for potential romantic partners. It is important to understand users' dating preferences in order to make better recommendations on potential dates. The message sending and replying actions of a user are strong indicators for what he/she is looking for in a potential date and reflect the user's actual dating preferences. We study how users' online dating behaviors correlate with various user attributes using a real-world dateset from a major online dating site in China. Our study provides a firsthand account of the user online dating behaviors in China, a country with a large population and unique culture. The results can provide valuable guidelines to the design of recommendation engine for potential dates.

Regular expression matching over sequences in real time is a crucial task in complex event processing on data streams. Given that such data sequences are often noisy and errors have temporal and spatial correlations, performing regular expression matching effectively and efficiently is a challenging task. Instead of the traditional approach of learning a distribution of the stream first and then processing queries, we propose a new approach that efficiently does the matching based on an error model. In particular, our algorithms are based on the realistic Markov chain error model, and report all matching paths to trace relevant basic events that trigger the matching. This is much more informative than a single matching path. We also devise algorithms to efficiently return only top-k matching paths, and to handle negations in an extended regular expression. Finally, we conduct a comprehensive experimental study to evaluate our algorithms using real datasets.

Enriching many location-based applications, various new skyline queries are proposed and formulated based on the notion of locational dominance, which extends conventional one by taking objects' nearness to query positions into account additional to objects' nonspatial attributes. To answer a representative class of skyline queries for location-based applications efficiently, this paper presents two index-based approaches, namely, augmented R-tree and dominance diagram. Augmented R-tree extends R-tree by including aggregated nonspatial attributes in index nodes to enable dominance checks during index traversal. Dominance diagram is a solution-based approach, by which each object is associated with a precomputed nondominance scope wherein query points should have the corresponding object not locationally dominated by any other. Dominance diagram enables skyline queries to be evaluated via parallel and independent comparisons between nondominance scopes and query points, providing very high search efficiency. The performance of these two approaches is evaluated via empirical studies, in comparison with other possible approaches.

Read-Optimized databases are well suited for read intensive Data Warehouse applications. In addition, data in these applications grow rapidly and hence need a dynamically scalable environment like Cloud. Cloud provides a flexible environment where user can load data, execute queries and scale resources on demand. However, cloud has its own challenges. To reduce the inter-node communication during the execution of query, tables are horizontally partitioned on join attribute and then related partitions are stored on the same physical system. In cloud environment it is not possible to ensure that these related partitions are always stored on the same physical system. As the resources are scaled up, the number of nodes involved increases, resulting in the increased inter-node communication. This becomes critical when we have huge data (in Tera or Peta bytes) stored across a large number of nodes. So with the increase in number of nodes and data size, the communication message size increases. All these factors result in increased bandwidth usage and performance degradation. When the number of joins in a query increases, the performance will further degrade. These problems emphasize a need for good storage structure and query execution plan. In this paper we propose a storage structure PK-map and a query processing algorithm. We show, through experiments, that this approach not only decreases the inter-node communication overhead but also decreases the work load of joins.

The skyline query can help identify the “best” objects in a multi-attribute dataset. During the past decade, this query has received considerable attention in the database research community. Most research focused on computing the “skyline” of a dataset, or the set of “skyline objects” that are not dominated by any other object. Such algorithms are not appropriate in an online system, which should respond in real time to skyline query requests with arbitrary subsets of the attributes (also called subspaces). To guarantee real-time response, an online system should precompute the skylines for all subspaces, and look up a skyline upon query. Unfortunately, because the number of subspaces is exponential to the number of attributes, such pre computation has very expensive storage cost and update cost. We propose the Compressed SkyCube (CSC) that is much more compact, yet can still return the skyline of any subspace without consulting the base table. The CSC therefore combines the advantage of precomputation in that it can respond to queries in real time, and the advantage of no-precomputation in that it has efficient space cost and update cost. This article presents the CSC data structures, the CSC query algorithm, the CSC update algorithm, and the CSC initial computation scheme. A solution to extend to high-dimensional data is also proposed.

Multi-dimensional spatial data are obtained when a number of data acquisition devices are deployed at different locations to measure a certain set of attributes of the study subject. How to manipulate these spatial data remains a challenge to the database community, especially when the spatial locations are represented in 3D. In this work, we establish a data model to handle multi-dimensional spatial data with three spatial dimensions. In particular, firstly, a clustering algorithm is applied to group the data set into "point clouds". Secondly, each cloud is considered as a 3D spatial convex object and triangulated into a set of tetrahedrons. Thirdly, all tetrahedron sets are stored in the database and spatial analysis is performed. In this paper, we focus on defining 3D spatial operations and relationships for 3D spatial elements (points, segments, triangles and tetrahedrons), and further applying these operations on 3D spatial objects, where each object is composed of a set of tetrahedrons.

Multiple sequence alignment represents a class of powerful bioinformatics tools with many uses in computational biology ranging from discovery of characteristic motifs and conserved regions in protein families to improved prediction of secondary and tertiary structure. Today, with rapidly growing data repositories offering scientists significantly more data with which to make better decisions, it is increasingly important to run these multiple alignment calculations as rapidly as possible. However, while several multiple alignment algorithms have been developed, these algorithms remain computationally expensive taking as long as 2 to 3 days for some queries. In this paper, we propose a new caching technique to improve the performance of multiple sequence alignment algorithms. In particular, we propose a nested two level cache hierarchy that provides caching of pairwise alignment results - a computationally expensive subcomponent of the multiple sequence alignment algorithms. A key contribution of our work is the development of two novel cache replacement policies that closely track the scientist’s query patterns over time. We present experimental results that validate the benefits of caching over the repeated computation of the alignments, provide heuristics for determining which alignments would benefit from the caching, and show the effectiveness of the developed cache replacement policies.

We present a valid-time extension of SQL and investigate its efficient implementation on an object-relational database system. We propose an approach, where temporal queries are expressed using a point-based time model, which only requires minimal extensions to SQL: 1999. Our prototype system called TENORS (for Temporal ENhanced Object-Relational System) maps the external point-based temporal queries and data model into equivalent internal representations based on time intervals. We describe the mapping of queries from external views to internal relations, and the temporal clustering and indexing methods used to support these queries on DB2.

Temporal reasoning and temporal query languages present difficult research problems of theoretical interest and practical importance. One problem is the chasm between point-based temporal reasoning and interval-based reasoning. Another problem is the lack of robustness and universality in many proposed solutions, whereby temporal extensions designed for one language cannot be easily applied to other query languages, e.g. extensions proposed for SQL cannot be applied to QBE or Datalog. In this paper, we provide a simple solution to both problems by observing that all query languages support (i) single-value-based reasoning, and (ii) aggregate-based reasoning, and then showing that these two modalities can be naturally extended to support, respectively, point-based and interval-based temporal queries. We follow TSQL2 insofar as practical requirements are concerned, and show that its functionality can be captured by simpler constructs which can be applied uniformly to Datalog, QBE and SQL. Then, we show that an efficient implementation can be achieved by mapping into a different storage representation, and discuss a prototype built along these lines using the /spl Lscr//spl Dscr//spl Lscr/++ system with extended aggregates.