In temporal graphs, time and topology are considered to be intertwined. As an evidence, it is observed that the vertices in more cohesive subgraphs have more frequent and more numerous interactions between each other in the history. Motivated by that, we study a novel frequency-aware k-core query problem. Different from previous studies that focus on finding k-cores in the projected subgraphs of given time intervals, we look for the subgraphs of k-core in which neighbor vertices have at least a certain number of high-frequency interactions. To address the problem, we propose 1) a minimum slope algorithm for computing the frequency in linear time, 2) a space-efficient index that stores the distinct “core frequency” of vertices for addressing arbitrary queries, 3) a propagation algorithm that collects core frequencies by message passing for index construction, and 4) efficient algorithms for retrieving a specific or all skyline results from the index respectively. The experimental results show that, our algorithms achieve several orders of magnitude improvement on efficiency compared to corresponding baselines, and meanwhile, the size of index is even smaller than that of graph unless the graph has very few timestamps on each edge. More importantly, by both statistics and case study, it is verified that the frequency-aware k-core query indeed find more cohesive subgraphs in the static k-core.

The recently proposed historical k -core query introduces a new paradigm of structure analysis for temporal graphs. However, the query processing based on the existing PHC-index, which preserves the distinct "core time" of each vertex, needs to traverse all vertices for each query, even though the results usually contain only a small subset of vertices. Inspired by the traditional k -shell that ensures the optimal k -core query processing, we propose a novel concept called "core time shell", which reveals the hierarchical structure of vertices with respect to their core time. Based on the core time shell, we design a time-space balanced Merged Core Time Shell index (MCTS-index). It is theoretically guaranteed that, the MCTS-index provides the approximately optimal query performance, and has the approximately same space complexity as the PHC-index. Moreover, we leverage the MCTS-index to efficiently address the brand-new "when" historical k -core queries orthogonal to the current "what" historical k -core queries. Our experimental results on ten real-world temporal graphs demonstrate both the superior efficiency of processing "what" queries and the effectiveness of processing versatile "when" queries for the MCTS-index.

The recent prosperity of temporal graph research redefines many traditional concepts on static graphs, such as triangle, motif,$k$-core, etc. Inspired by that, we propose a novel$(k, \delta)$-truss on temporal graphs, which requires its triangles to exist in short enough time windows ever. The$(k,\delta)$-truss satisfies both static and temporal cohesion, while the original$k$-truss is its special case when$\delta=\infty$. In order to address the$(k, \delta)$-truss query, we propose both index-free and index-based approaches. By leveraging the dual containment relation on$(k, \delta)$-trusses, our indexes can compress all$(k, \delta)$-trusses losslessly into map or tree structures with dramatically less space, so that a specific$(k,\ \delta)$-truss can be retrieved from indexes in the optimal time. To enable our index to scale to large temporal graphs, we develop two index construction algorithms that can reduce redundant computation significantly, based on truss decomposition and truss maintenance respectively. The experimental results demonstrate that index-based approaches process queries in interactive time and outperform the index-free approach by 2~4 orders of magnitude, while indexes achieve compression ratios up to 10-4.

For a temporal graph like transaction network, finding a densely connected subgraph that contains a vertex like a suspicious account during a period is valuable. Thus, we study the Temporal k -Core Component Search (TCCS) problem, which aims to find a connected component of temporal k -core for any given vertex and time interval. Towards this goal, we propose a novel Evolution Forest Index (EF-Index) that can address TCCS in optimal time. Essentially, EF-Index leverages the evolutionary order on temporal k -cores to both compress the connectivity between vertices in temporal k -cores of all time intervals into a minimum set of compactest Minimum Temporal Spanning Forests (MTSFs) and retrieve MTSF for a given time interval rapidly. Here, a crucial innovation is that, we extend the temporal k -core evolution theory by introducing a pair of time-topology isomorphic relations, on top of which the evolutionary order in topology domain can be simply computed by a "kernel function" in time domain. Moreover, we design an efficient mechanism to update EF-Index incrementally for dynamic edge streams. The experimental results on a variety of real-world temporal graphs demonstrate that, EF-Index outperforms the state-of-the-art approach by 1--3 orders of magnitude on processing TCCS, and its space overhead is reduced by 4--5 orders of magnitude compared with preserving connectivity uncompressedly.

Incremental maximal clique enumeration (IMCE), which maintains maximal cliques in dynamic graphs, is a fundamental problem in graph analysis. A maximal clique has a solid descriptive power of dense structures in graphs. Real-world graph data is often large and dynamic. Studies on IMCE face significant challenges in the efficiency of incremental batch computation and hybrid edge changes. Moreover, with growing graph sizes, new requirements occur on indexing global maximal cliques and obtaining maximal cliques under specific vertex scope constraints. This work presents a new data structure SOMEi to maintain intermediate maximal cliques during construction. SOMEi serves as a space-efficient index to retrieve scope-constrained maximal cliques on the fly. Based on SOMEi, we design a procedure-oriented IMCE algorithm to deal with hybrid edge changes within a unified algorithm framework. In particular, the algorithm is able to process a large batch of edge changes and significantly improve the average processing time of a single edge change through an efficient pruning strategy. Experimental results on real and synthetic graph data demonstrate that the proposed algorithm outperforms all the baselines and achieves good efficiency through pruning.

Querying cohesive subgraphs on temporal graphs (e.g., social network, finance network, etc.) with various conditions has attracted intensive research interests recently. In this paper, we study a novel Temporal$(k,\mathcal {X})$-Core Query (TXCQ) that extends a fundamental Temporal$k$-Core Query (TCQ) proposed in our conference paper by optimizing or constraining an arbitrary metric$\mathcal {X}$of$k$-core, such as size, engagement, interaction frequency, time span, burstiness, periodicity, etc. Our objective is to address specific TXCQ instances with conditions on different$\mathcal {X}$in a unified algorithm framework that guarantees scalability. For that, this journal paper proposes a taxonomy of measurement$\mathcal {X}(\cdot )$and achieve our objective using a two-phase framework while$\mathcal {X}(\cdot )$is time-insensitive or time-monotonic. Specifically, Phase 1 still leverages the query processing algorithm of TCQ to induce all distinct$k$-cores during a given time range, and meanwhile locates the “time zones” in which the cores emerge. Then, Phase 2 conducts fast local search and$\mathcal {X}$evaluation in each time zone with respect to the time insensitivity or monotonicity of$\mathcal {X}(\cdot )$. By revealing two insightful concepts named tightest time interval and loosest time interval that bound time zones, the redundant core induction and unnecessary$\mathcal {X}$evaluation in a zone can be reduced dramatically. Our experimental results demonstrate that TXCQ can be addressed as efficiently as TCQ, which achieves the latest state-of-the-art performance, by using a general algorithm framework that leaves$\mathcal {X}(\cdot )$as a user-defined function.

Querying cohesive subgraphs on temporal graphs with various time constraints has attracted intensive research interests recently. In this paper, we study a novel Temporal k -Core Query (TCQ) problem: given a time interval, find all distinct k -cores that exist within any subintervals from a temporal graph, which generalizes the previous historical k -core query. This problem is challenging because the number of subintervals increases quadratically to the span of time interval. For that, we propose a novel Temporal Core Decomposition (TCD) algorithm that decrementally induces temporal k -cores from the previously induced ones and thus reduces "intra-core" redundant computation significantly. Then, we introduce an intuitive concept named Tightest Time Interval (TTI) for temporal k -core, and design an optimization technique with theoretical guarantee that leverages TTI as a key to predict which subintervals will induce duplicated k -cores and prunes the subintervals completely in advance, thereby eliminating "inter-core" redundant computation. The complexity of optimized TCD (OTCD) algorithm no longer depends on the span of query time interval but only the scale of final results, which means OTCD algorithm is scalable. Moreover, we propose a compact in-memory data structure named Temporal Edge List (TEL) to implement OTCD algorithm efficiently in physical level with bounded memory requirement. TEL organizes temporal edges in a "timeline" and can be updated instantly when new edges arrive in dynamical temporal graphs. We compare OTCD algorithm with the incremental historical k -core query on several real-world temporal graphs, and observe that OTCD algorithm outperforms it by three orders of magnitude, even though OTCD algorithm needs none precomputed index.

High utility itemsets can reveal combinations of items that have a high profit, expense, or importance. Mining high utility itemsets in a database with$n$items generally results in a huge search space, composed of$2^{n}$itemsets, and heavy utility calculations for the explored itemsets. Previous algorithms using prefix tree structures perform two phases, namely candidate generation and testing. To avoid generating candidate itemsets, one-phase algorithms use list or hyper-link structures and have been proven to be superior to two-phase algorithms. However, it should be noted that a prefix tree is still an efficient structure for itemset mining problems, and especially algorithms using prefix trees such as FP-Growth have shown excellent performance for mining frequent itemsets. This paper proposes Hamm, a High-performance AlgorithM for Mining high utility itemsets. Hamm employs a novel TV (prefix Tree and utility Vector) structure and mines high utility itemsets in one phase without candidate generation. We also develop an efficient optimization which is incorporated into Hamm as a component. Using prefix trees and utility vectors, Hamm outperforms state-of-the-art algorithms on various databases in experiments. Experimental results also show that the proposed optimization remarkably reduces the search space and speeds up Hamm.

The semantic gap between keyword queries and search intents behind them motivates intensive studies on keyword query interpretation, which aims to interpret a keyword query to structured queries (a.k.a. patterns) representing most possibly relevant search intents. However, there still lacks of study on an important issue: how to guarantee the patterns are "reliable", which means the structured queries can be evaluated as really existing results. In this paper, we regard the reliability as a new metric for ranking patterns, and present a keyword query interpretation approach to find both reliable and relevant pattern trees on an arbitrary summary graph of underlying data. Specifically, we firstly propose a reliability estimation model to measure how possibly a pattern tree can be evaluated as a nonempty result set by statistics under reasonable assumptions. Secondly, we develop constrained top-k search algorithms that guarantee to return the optimal pattern trees for a specific keyword query. Moreover, to improve the efficiency of online search, we also design elaborate indexes, search heuristics and pruning strategies. Lastly, we perform comprehensive experiments on two real-world datasets, DBpedia and Yago, with both QALD-9 queries and random queries. The observations indicate our approach improves the accuracy and overall quality of top-k results significantly.

The Point-of-Interest (POI) transition behaviors could hold absolute sparsity and relative sparsity very differently for different cities. Hence, it is intuitive to transfer knowledge across cities to alleviate those data sparsity and imbalance problems for next POI recommendation. Recently, pre-training over a large-scale dataset has achieved great success in many relevant fields, like computer vision and natural language processing. By devising various self-supervised objectives, pre-training models can produce more robust representations for downstream tasks. However, it is not trivial to directly adopt such existing pre-training techniques for next POI recommendation, due to thelacking of common semantic objects (users or items) across different cities. Thus in this paper, we tackle such a new research problem ofpre-training across different citiesfor next POI recommendation. Specifically, to overcome the key challenge that different cities do not share any common object, we propose a novel pre-training model namedCATUS, by transferring thecategory-leveluniversal transition knowledge over different cities. Firstly, we build two self-supervised objectives inCATUS:next category predictionandnext POI prediction, to obtain the universal transition-knowledge across different cities and POIs. Then, we design acategory-transition oriented sampleron the data level and animplicit and explicit transfer strategyon the encoder level to enhance this transfer process. At the fine-tuning stage, we propose adistance oriented samplerto better align the POI representations into the local context of each city. Extensive experiments on two large datasets consisting of four cities demonstrate the superiority of our proposedCATUSover the state-of-the-art alternatives. The code and datasets are available at https://github.com/NLPWM-WHU/CATUS.

Abstract Streaming graph partitioning methods have recently gained attention due to their ability to scale to very large graphs with limited resources. However, many such methods do not consider workload and graph characteristics. This may degrade the performance of queries by increasing inter-node communication and computational load imbalance. Moreover, existing workload-aware methods cannot consistently provide good performance as they do not consider dynamic workloads that keep emerging in graph applications. We address these issues by proposing a novel workload-adaptive streaming partitioner named WASP, that aims to achieve low-latency and high-throughput online graph queries. As each workload typically contains frequent query patterns, WASP exploits the existing workload to capture active vertices and edges which are frequently visited and traversed, respectively. This information is used to heuristically improve the quality of partitions either by avoiding the concentration of active vertices in a few partitions proportional to their visit frequencies or by reducing the probability of the cut of active edges proportional to their traversal frequencies. In order to assess the impact of WASP on a graph store and to show how easily the approach can be plugged on top of the system, we exploit it in a distributed graph-based RDF store. Our experiments over three synthetic and real-world graph datasets and the corresponding static and dynamic query workloads show that WASP achieves a better query performance against state-of-the-art graph partitioners, especially in dynamic query workloads.

The social network is a theoretical construct useful in the social sciences to study relationships between individuals, groups, organizations, or even entire societies. To deal with social networks, various approaches have been proposed to analyze them. What has not been done is to properly and effectively represent, manage and use various social networks. In this paper, we propose a semantic model that can naturally represent various academic social networks, especially various complex semantic relationships among social actors. This model can be used as the foundation for managing, manipulating and querying academic social networks. We also introduce a concise language to represent and query academic social networks.

High utility itemsets refer to the sets of items with high utility like profit in a database, and efficient mining of high utility itemsets plays a crucial role in many real-life applications and is an important research issue in data mining area. To identify high utility itemsets, most existing algorithms first generate candidate itemsets by overestimating their utilities, and subsequently compute the exact utilities of these candidates. These algorithms incur the problem that a very large number of candidates are generated, but most of the candidates are found out to be not high utility after their exact utilities are computed. In this paper, we propose an algorithm, called HUI-Miner (High Utility Itemset Miner), for high utility itemset mining. HUI-Miner uses a novel structure, called utility-list, to store both the utility information about an itemset and the heuristic information for pruning the search space of HUI-Miner. By avoiding the costly generation and utility computation of numerous candidate itemsets, HUI-Miner can efficiently mine high utility itemsets from the utility-lists constructed from a mined database. We compared HUI-Miner with the state-of-the-art algorithms on various databases, and experimental results show that HUI-Miner outperforms these algorithms in terms of both running time and memory consumption.

Object properties are often based on their contexts, and contexts can be nested to form complex context-dependent information. Existing data models cannot naturally and directly represent such context-dependent information. In this paper, we propose a novel mechanism called context constructor in an object-oriented framework to solve this problem.

As the ubiquitous interplay of structured, semi-structured and unstructured data from different sources, neither DB-style structured query requiring knowledge of full schema and complex language, nor IR-style keyword search ignoring latent structures, can satisfy users. In this paper, we present a novel Semi-Structured Search Engine (3SE) that provides easy, flexible, precise and rapid access to heterogeneous data represented by a semi-structured graph model.

Current keyword proximity search approaches on general graph lack effective means to reduce the search space, and thus suffer from low efficiency when dealing with large search space. In this paper, we present a novel approach in order to address this problem. Our approach employs a best-effort frontier-reduce strategy that aims to find a set of subgraphs containing the best answers. So we need only to search over these small subgraphs to get the top-k answers, and thus the efficiency can be significantly improved. To fulfill our strategy, we define a d-distance subgraph with upper size bound, and extract such subgraphs from the graph to build a new index structure combining the mappings between keywords, vertexes and subgraphs, by which we can quickly look up the target subgraphs for specific queries. Then, we perform an efficient algorithm to find the top-k answers, which can overcome the subgraph overlap problem and support existing optimal prioritization techniques.

With the extensive use of XML in applications over the Web, how to update XML data is becoming an important issue because the role of XML has expanded beyond traditional applications, in which XML is used as a mean for data representation and exchange on the Web. This paper presents a novel declarative XML update language, which is an extension of the XML-RL query language. Compared with other existing XML update languages, it has the following features. First, it is the only XML data manipulation language based on a higher data model. All of the other update languages adopt so-called graph-based or tree-based data models. Therefore, update requests can be expressed in a more intuitive and natural way in our language than in the other languages. Second, our language is designed to deal with ordered and unordered data. Some of the existing languages cannot handle the order of documents. Third, our language can express complex update requests at multiple level in a hierarchy in a simple and fast way. Some existing languages have to express such complex requests in nested updates, which is too complicated and nonintuitive to comprehend for end users. Fourth, our language directly supports the functionality of updating complex objects while all other update language do not support these operations. Lastly, most of existing languages use rename to modify attribute and element names, which is a different way from updates on value. Our language modifies tag names, values, and objects in a unified way by the introduction of three kinds of logical binding variables: object variables, value variables, and name variables. The powerful ability of our language is shown by various examples.

Use of path expressions is a common feature in most XML query languages, and many evaluation methods for path expression queries have been proposed recently. However, there are few researches on the issue of optimizing regular path expression queries. In this paper, two kinds of path expression optimization principles are proposed, named path shortening and path complementing, respectively. The path shortening principle reduces the querying cost by shortening the path expressions with the knowledge of XML schema. While the path complementing principle substitutes the user queries with the equivalent lower-cost path expressions. The experimental results show that these two techniques can largely improve the performance of path expression query processing.

Extracting data from XML documents is an important issue for XML research and development. However, how XML documents are viewed determines how they can be queried. We first describe a natural way of viewing XML documents as in complex object data models so that we can easily comprehend XML data from a database point of view. We then illustrate how to use logical variables to extract data from XML documents. We also describe a rule-based declarative query language for XML. We demonstrate that our rule-based language provides a uniform framework that has the following advantages over other XML query languages including XQuery. First, it provides a natural way of separating querying and result constructing using the body and head respectively. Second, several rules can be used for the same query so that complex queries can be expressed in a simple and natural way. Also, its use of logical variables and rules makes many functions and operators in XQuery and XPath unnecessary or definable constructively. Finally, it provides natural and direct support for recursion as in deductive databases and has logical foundations that have played a significant role in database research in the past.

Over the past decade, a large number of deductive object-oriented database languages have been proposed. The earliest of these languages had few object-oriented features, and more and more features have systematically been incorporated in successive languages. However, a language with a clean logical semantics that naturally accounts for all the key object-oriented features, is still missing from the literature. This article takes us another step towards solving this problem. Two features that are currently missing are the encapsulation of rule-based methods in classes, and nonmonotonic structural and behavioral inheritance with overriding, conflict resolution and blocking. This article introduces the syntax of a language with these features. The language is restricted in the sense that we have omitted other object-oriented and deductive features that are now well understood, in order to make our contribution clearer. It then defines a class of databases, called well-defined databases , that have an intuitive meaning and develops a direct logical semantics for this class of databases. The semantics is based on the well-founded semantics from logic programming. The work presented in this article establishes a firm logical foundation for deductive object-oriented databases.

Over the past decade, a large number of deductive object-oriented database languages have been proposed. The earliest of these languages had few object-oriented features, and more and more features have systematically been incorporated in successive languages. However, a language with a clean logical semantics that naturally accounts for all the key object-oriented features, is still missing from the literature. Two features that are currently missing are the encapsulation of rule-based methods in classes, and nonmonotonic behavioral inheritance with overriding, conflict resolution and blocking. This paper introduces the syntax of a language with these features. It then defines a class of databases, called well-defined databases, that have an intuitive meaning and develops a direct logical semantics for this class of databases. The semantics is based on the well-founded semantics from logic programming. The work presented in this paper establishes a firm logical foundation for deductive object-oriented databases.

With the recent popularity of the Web, an enormous amount of information is now available online. Most Web documents available over the Web are in HTML format and are hierarchically structured in nature. How to query such Web documents based on their internal hierarchical structure becomes more and more important. We present a rule-based language called WebQL to support effective and flexible Web queries. Unlike other Web query languages, WebQL is a high level declarative query language with a logical semantics. It allows us to query Web documents based on their internal hierarchical structures. It supports not only negation and recursion, but also query result restructuring in a natural way. We also describe the implementation of the system that supports the WebQL query language.

Data integration from several sources has gained considerable attention with the recent popularity of the World Wide Web. In the real world, some information may be missing (i.e. partial) and some may be inconsistent from several sources. How to obtain information that is as complete as possible and how to detect inconsistency from these sources is thus an interesting question. Most existing work uses a simple graph-based or tree-based semistructured data model to represent heterogeneous data coming from various sites, which fails to account for the existence of partial and inconsistent information. In this paper, we redefine the notion of semistructured objects to reflect the existence of partial and inconsistent information and study how to integrate such objects spread over various sources and check their consistency in the meantime. We propose a new integration operator for this purpose and discuss its semantic properties.

Summary form only given. ROL (Rule-based Object Language) is a deductive object-oriented database system. It provides a uniform language for defining, querying and manipulating a database. The ROL language integrates important features of deductive databases and object-oriented databases with well-defined declarative semantics. ROL also supports structured values, treating them as first-class citizens, and providing powerful mechanisms for representing both partial and complete information about sets. As a result, it directly supports non-first normal form relations and is an extension of pure value-oriented deductive database languages. A ROL database consists of three parts: a schema, a set of facts and a set of rules. The ROL system is organized into three layers: (1) the user interface (textual and graphical); (2) the query manager and the update manager; and (3) the memory manager and the object manager.

The ROL system is a novel deductive object-oriented database system that has been implemented at the University of Regina. It provides a uniform rule-based declarative language for defining, manipulating and querying databases, which integrates important features of deductive databases and object-oriented databases. It supports object identity, complex objects, classes, class hierarchies, multiple inheritance with overriding and blocking, and schema definition. It also supports structured values such as functor objects and sets, treating them as first class citizens, and providing powerful mechanisms for representing both partial and complete information about sets. This paper describes the query processing mechanism in the ROL system. A novel feature is that it effectively combines the top-down and bottom-up strategies and automatically decides which evaluation strategies to use based on the nature of the query and data in the databases.