Multivariate time series (mts ) analysis have extensive applications in various areas such as human activity recognition, healthcare, and economics, among others. Recently, Transformer approaches have been specifically designed for MTS and have consistently reported superior performance. In this paper, we demonstrate a software system for a recent efficient shape-aware Transformer (SDD ), where time-series subsequences (a.k.a shapes) are made available to users for investigation. First, a time-series Transformer, called SVP-T, takes shapes, together with their variable position information (VP information) as input to the training of a Transformer model. These shapes are computed from different variables and time intervals, enabling the Transformer model to learn dependencies simultaneously across both time and variables. Second, a data-driven kernel-based attention mechanism, called DARKER, reduces the time complexity of training Transformer models from O(N2) to O(N), where N is the number of inputs. As a result, the training process by using DARKER offers about 3x-4x speedup over vanilla Transformers'. In this demo, we present the first system (SDD ) that integrates SVP-T and DARKER. In particular, SDD visualizes the SVP-T's attention matrix and allows users to explore key shapes that have high attention weights. Furthermore, users can use SDD to decide the shape input to train a new model, to further balance between efficiency and accuracy.

Time series similarity search (TSSS) is a fundamental task across various applications, including classification, motif discovery, and anomaly detection. However, existing iSAX-based index methods, while known for their efficiency, often rely on hand-crafted techniques (e.g., PAA and SAX) for z-normalized time series data. However, these techniques do not fully exploit the full representation space and pose challenges to indexing. In this paper, we propose a learned index approach for TSSS. Specifically, we introduce SAXnet, a novel two-stage neural network that generates the learned SAX representation (leSAX representation) for both z-normalized and non-z-normalized time series data. The benefits of SAXnet are threefold: ① full exploitation of latent space, ② preservation of time series shapes and global information for indexing, and ③ elimination of the need for hand-crafted techniques. We then propose leSaxindex, a novel learned SAX representation index, which consists of a leSAX tree and a learned index. The distribution of the leSAX representations in the leSAX tree is adjusted to achieve a near-uniform distribution for index efficiency. Furthermore, we propose a learned index structure that works alongside the leSAX tree, applied recursively in case of large index leaf nodes. We have conducted comprehensive experiments on exact similarity search using our SAXnet and leSAX index on both real and synthetic time series datasets. The results demonstrate that our leSAX method outperforms state-of-the-art methods in efficiency, achieving performance improvements ranging from 3.6× to 17×.

Recently, numerous community search methods for large graphs have been proposed, at the core of which is defining and measuring cohesion. This paper experimentally evaluates the effectiveness of these community search algorithms w.r.t. cohesiveness in the context of online social networks. Social communities are formed and developed under the influence of group cohesion theory, which has been extensively studied in social psychology. However, current generic methods typically measure cohesiveness using structural or attribute-based approaches and overlook domain-specific concepts such as group cohesion. We introduce five novel psychology-informed cohesiveness measures, based on the concept of group cohesion from social psychology, and propose a novel framework called CHASE for evaluating eight representative community search algorithms w.r.t. these measures on online social networks. Our analysis reveals that there is no clear correlation between structural and psychological cohesiveness, and no algorithm effectively identifies psychologically cohesive communities in online social networks. This study provides new insights that could guide the development of future community search methods.

Abstract This study introduces an innovative framework named scale for processing dynamic skyline queries securely in cloud environments. Unlike previous approaches that require complex operations on encrypted data, scale simplifies dynamic skyline domination to mere comparisons, significantly improving query efficiency. Through empirical evaluations over four datasets, we show that scale accelerates query processing nearly 1000-fold compared to existing state-of-the-art methods. Specifically, scale shows significant efficiency improvements by simplifying query interactions to a single round between the user and the cloud, which is validated through empirical studies on multiple datasets. Moreover, we introduce two distributed versions of scale , dist-scale-s and dist-scale-e , which further optimize performance by facilitating parallel processing. This adaptation showcases a substantial reduction in response times and computational overhead, underpinning the scalability and effectiveness of our framework in handling large-scale, secure cloud-based queries.

Property graph schemas are essential for organizing property graph data, serving both prescriptive and descriptive roles. This has led to the recent development of property graph schema languages such as PG Schema . While understanding of these languages requires familiarity with complex syntax, this poses usability challenges, particularly for domain experts who are not programmers. Current visual abstractions, such as the labeled schema graph (łsg), simplify representation but suffers from visual clutter and limited feature support. To address these challenges, we propose a novel, generic, and extensible visual abstraction, labeled iconized composite schema (łics), whose design is informed by theories and principles from HCI, cognitive psychology, and visualization. A novel łics-based visual interface coined PASCAL is also proposed to facilitate visualization of property graph schemas. Under the hood, it leverages the Map-Paint algorithm for creating the visual components of łics. A user study demonstrates that łics is superior to the traditional łsg abstraction w.r.t. usability, effectiveness, query formulation efficiency, and schema comprehension.

Addressing the complexities of querying unstructured graphs such as knowledge graphs and social networks, this paper introduces D KWS, a novel distributed keyword search system. Leveraging a monotonic property, we ensure correct parallelization of our advanced keyword search algorithm, which incorporates tight pruning bounds and is divided into monotonic backward and forward search phases. The system is further augmented by the notify-push paradigm and the PINE programming model, facilitating asynchronous communication and preemptive searches to mitigate staleness in distributed environments. Extensive experiments on real-world datasets demonstrate DKWS's performance advantage, being up to two orders of magnitude faster and incurring 7.6 times lower communication costs than the existing systems.

JSON keyword search searches the current versions of documents in a collection. However, JSON documents change over time due to edits. Some applications, such as data forensics and auditing, need to search past versions of documents and for changes to documents. This paper introduces a system called Temporal JSON Keyword Search (TJKS) for search in a collection of JSON documents that vary over time. TJKS lets users control which temporal slice, or part of the history, can be searched using a temporal search semantics; we support both of the major temporal semantics: sequenced and nonsequenced search. This paper presents the semantics of temporal JSON keyword search, discusses an efficient implementation, and evaluates the implementation. Our extensions are largely orthogonal to specific keyword search techniques, so this research provides a blueprint for extending keyword search to include time and potentially other kinds of metadata.

GPU-accelerated relational query execution engines have parallelized the execution of a pipeline, a sequence of operators. For the parallelization, the engines evenly partition the tuples in a table that will be scanned by the pipeline's first operator (a scan), and each thread executes the pipeline for the tuples in a partition. However, this approach leads to load imbalances since an operator returns a varying number of output tuples per input tuple, particularly under non-uniform data distributions such as skewed join key values. The load imbalances are classified into intra- and inter-warp load imbalances (intra-WLIs and inter-WLIs) since 1) threads are grouped into warps and 2) every thread in a warp evaluates the same operator for an input tuple concurrently following a single-instruction-multiple-thread manner. In contrast, threads in different warps can evaluate different operators concurrently. Although load balancing techniques have been proposed, however, they fail to solve the load imbalances on various workloads. In this paper, we propose a query execution engine, Themis, named after the deity of fairness, which symbolizes balanced workloads within our context. Themis minimizes intra-WLIs and inter-WLIs across various workloads. First, Themis minimizes intra-WLIs by redistributing tuples between the threads in a warp and making the threads evaluate an operator only when all of them hold inputs. Second, Themis mitigates the inter-WLIs by redistributing the tuples of warps with heavy workloads to idle warps. To check whether a warp's workload is heavy, we propose a method to approximate the sizes of warps' workloads. Based on these approximations, Themis adaptively adjusts the threshold for determining a warp's workload as heavy. In a recent benchmark JCC-H, which introduces skewed join key distributions to TPC-H, Themis significantly alleviates the inter-WLIs and intra-WLIs, outperforming the runner-up by up to 379x.

Transformer-based models have facilitated numerous applications with superior performance. A key challenge in transformers is the quadratic dependency of its training time complexity on the length of the input sequence. A recent popular solution is using random feature attention (RFA) to approximate the costly vanilla attention mechanism. However, RFA relies on only a single, fixed projection for approximation, which does not capture the input distribution and can lead to low efficiency and accuracy, especially on time series data. In this paper, we propose DARKER, an efficient transformer with a novelDAta-dRivenKERnel-based attention mechanism. To precisely present the technical details, this paper discusses them with a fundamental time series task, namely, time series classification (tsc). First, the main novelty of DARKER lies in approximating the softmax kernel by learning multiple machine learning models with trainable weights as multiple projections offline, moving beyond the limitation of a fixed projection. Second, we propose a projection index (called pIndex) to efficiently search the most suitable projection for the input for training transformer. As a result, the overall time complexity of DARKER is linear with the input length. Third, we propose an indexing technique for efficiently computing the inputs required for transformer training. Finally, we evaluate our method on 14 real-world and 2 synthetic time series datasets. The experiments show that DARKER is 3×-4× faster than vanilla transformer and 1.5×-3× faster than other SOTAs for long sequences. In addition, the accuracy of DARKER is comparable to or higher than that of all compared transformers.

Due to the unstructuredness and the lack of schemas of graphs, such as knowledge graphs, social networks, and RDF graphs, keyword search for querying such graphs has been proposed. As graphs have become voluminous, large-scale distributed processing has attracted much interest from the database research community. While there have been several distributed systems, distributed querying techniques for keyword search are still limited. This paper proposes a novel distributed keyword search system called$\mathsf {DKWS}$. First, we present amonotonicproperty with keyword search algorithms that guarantees correct parallelization. Second, we present a keyword search algorithm as monotonic backward and forward search phases. Moreover, we propose new tight bounds for pruning nodes being searched. Third, we propose anotify-pushparadigm and$\mathsf {PINE}$programming modelof$\mathsf {DKWS}$. The notify-push paradigm allowsasynchronouslyexchanging the upper bounds of matches across the workers and the coordinator in$\mathsf {DKWS}$. The$\mathsf {PINE}$programming model naturally fits keyword search algorithms, as they have distinguished phases, to allowpreemptivesearches to mitigate staleness in a distributed system. Finally, we investigate the performance and effectiveness of$\mathsf {DKWS}$through experiments using real-world datasets. We find that$\mathsf {DKWS}$is up to two orders of magnitude faster than related techniques, and its communication costs are 7.6 times smaller than those of other techniques.

Existing visual abstraction of a property graph query by representing it as a labeled atomic graph (LAG) has great potential to democratize the usage of property graph databases as it enables user-friendly visual query formulation without demanding the need to learn a property graph query language e.g., Cypher. Unfortunately, existing LAG-based query interfaces do not embrace HCI principles and psychology theories to inform their design and as a result may have adverse impact on their usability and aesthetics. In this paper, we depart from the classical theory- and principles-oblivious LAG abstraction to present a novel theory-informed visual abstraction called labeled composite graph (LCG) to address this limitation. It realizes a novel and extensible visual shape definition language called VEDA to create and maintain an LCG systematically, guided by a variety of theories and principles from HCI, visualization and psychology. We build a novel LCG-based visual property graph query interface for Cypher called SIERRA and demonstrate through a user study its superiority to an industrial-strength LAG-based query interface for property graphs w.r.t. usability, aesthetics and efficient query formulation.

This paper studies privacy preserving graph pattern query services in a cloud computing paradigm. In such a paradigm, data owner stores the large data graph to a powerful cloud hosted by a service provider (SP) and users send their queries to SP for query processing. However, as SP may not always be trusted, the sensitive information of users' queries, importantly, the query structures, should be protected. In this paper, we study how to outsource the localized graph pattern queries (LGPQs) on the SP side with privacy preservation. LGPQs include a rich set of semantics, such as subgraph homomorphism, subgraph isomorphism, and strong simulation, for which each matched graph pattern is located in a subgraph called ball that have a restriction on its size. To provide privacy preserving query service for LGPQs, this paper proposes the first framework, called Prilo, that enables users to privately obtain the query results. To further optimize Prilo, we propose Prilo* that comprises the first bloom filter for trees in the trust execution environment (TEE) on SP, a query-oblivious twiglet-based technique for pruning non-answers, and a secure retrieval scheme of balls that enables user to obtain query results early. We conduct detailed experiments on real world datasets to show that Prilo* is on average 4x faster than the baseline, and meanwhile, preserves query privacy.

Time series classification (TSC) has been one of the most fundamental problems of time series data. Time series shapelets (or simply, shapelets) are discriminative subsequences that have been recently found both effective and interpretable for solving TSC. However, shapelet discovery is known to be computationally costly. Meanwhile, matrix profile has been recently proposed for efficient motif discovery and anomaly detection. Our preliminary experiment shows that a direct adoption of the matrix profile on TSC does not bring superior classification accuracy. We have identified two main issues of such an adoption: 1) discords as “shapelets”, and 2) lack of shapelet diversity. In response to these issues, we propose instance profile for shapelets, called IPS, for shapelet discovery for TSC. The main challenge is to utilize the instance profile (IP) to capture the characteristics of shapelets in a robust manner and then to discover high-quality shapelets efficiently. First, we use our IP to generate abundant shapelet candidates. We next efficiently prune candidates that do not align with the definition of shapelets using a novel distribution-aware bloom filter (DABF). Three utility functions are proposed to measure the shapelet candidates and DABF is used to efficiently compute the functions. We have conducted comprehensive experiments on IPS with 12 competitive state-of-the-art methods using UCR Archive datasets. The efficiency is on average 25 times faster than that of BSPCOVER (the current state-of-the-art method). The accuracy of IPS is comparable to or higher than that of existing work. Furthermore, we select one case study to illustrate the interpretability of the shapelets.

The Data Management community has explored many options in recent years to improve our publication culture and review processes, ranging from innovative journal-conference hybrids that decouple publication from presentation, incorporating journal-style reviewing for conference-style papers, requesting code reproducibility and code/data availability, multiple submission deadlines in a year, new categories of papers, informal shepherding processes, guidelines for diversity and inclusion, automated COI check, and so on. This panel seeks to examine our many experiments, comparing them with other CS disciplines, and help determine (i) have our experiments worked? (ii) what has their impact been? and (iii) can we do better?

Visual graph query interfaces (VQI) widen the reach of graph querying frameworks across a variety of end users by enabling non-programmers to use them. Several industrial and academic frameworks for querying graphs expose such visual interfaces. In this tutorial, we survey recent developments in the emerging area of data-driven visual query interface that is grounded on the principles of human-computer interaction (HCI) and cognitive psychology to enhance usability of graph querying frameworks. A data-driven VQI has many benefits such as reducing the cost in constructing and maintaining an interface, superior support for query formulation, and increased portability of the interface. We discuss the notion of making VQIs data-driven and compare it with its classical manual counterpart, and review techniques for automatic construction and maintenance of these interfaces. In addition, the tutorial suggests open problems and new research directions. In summary, in this tutorial, we review and summarize the research thus far into data-driven visual graph query interface management, giving researchers a snapshot of the current state of the art in this topic, and future research directions.

The database systems course in an undergraduate computer science degree program is gaining increasing importance due to the continuous supply of database-related jobs as well as the rise of Data Science. A key learning goal of learners taking such a course is to understand how SQL queries are executed in an RDBMS in practice. An RDBMS typically exposes a query execution plan (QEP) in a visual or textual format, which describes the execution steps for a given query. However, it is often daunting for a learner to comprehend these QEPs containing vendor-specific implementation details. In this demonstration, we present a novel, generic, and portable system called LANTERN that generates a natural language (NL)-based description of the execution strategy chosen by the underlying RDBMS to process a query. It provides a declarative framework called POOL for subject matter experts (SME) to efficiently create and manipulate the NL descriptions of physical operators of any RDBMS. It then exploits POOL to generate the NL descriptions of QEPs by integrating a rule-based and a deep learning-based techniques to infuse language variability in the descriptions. Such an NL generation strategy mitigates the impact of boredom on learners caused by repeated exposure of similar text generated by a rule-based system.

Visual graph query interfaces (VQI) facilitate non-programmers to query graph data effortlessly. The construction of these interfaces for large networks is typically not data-driven. That is, they do not exploit the underlying networks to automatically generate the contents of various panels of a VQI. Such data-driven construction has several benefits such as facilitating efficient top-down and bottom-up query formulation and portability of an interface across different application domains and sources. In this demonstration, we present a novel plug-and-play visual subgraph query interface construction engine called PLAYPEN that can be plugged on any large network G with a plug specification b to automatically generate the VQI for G that satisfies b by populating various components of the interface.

Abstract Graph query autocompletion (GQAC) takes a user’s graph query as input and generates top-k query suggestions as output, to help alleviate the verbose and error-prone graph query formulation process in a visual interface. To compose a target query with GQAC, the user may iteratively adopt suggestions or manually add edges to augment the existing query. The current state-of-the-art of GQAC, however, focuses on a large collection of small- or medium-sized graphs only. The subgraph features exploited by existing GQAC are either too small or too scarce in large graphs. In this paper, we present Flexible graph query autocompletion for LArge Graphs, called FLAG. We are the first to propose wildcard labels in the context of GQAC, which summarizes query structures that have different labels. FLAG allows augmenting users’ queries with subgraph increments with wildcard labels to form suggestions. To support wildcard-enabled suggestions, a new suggestion ranking function is proposed. We propose an efficient ranking algorithm and extend an index to further optimize the online suggestion ranking. We have conducted a user study and a set of large-scale simulations to verify both the effectiveness and efficiency of FLAG. The results show that the query suggestions saved roughly 50% of mouse clicks and FLAG returns suggestions in few seconds.

The database systems course is offered in many major universities. A key learning goal of learners taking such a course is to understand how sql queries are processed in an RDBMS in practice. To this end, comprehension of the impact of various physical operators on the selected query execution plan (QEP) of a query is paramount. Unfortunately, off-the-shelf RDBMS typically only expose the QEP to users without revealing information about the impact of alternative choices of various physical operators on it in a user-friendly manner to aid learning. In this demonstration, we present a novel system called MOCHA that facilitates exploration and visualization of the impact of alternative physical operator choices on the QEP of a given SQL query. MOCHA accepts an SQL query as input, and compares and visualizes the QEP and alternative plans which are selected based on learner-specified operator preferences. Furthermore, it intuitively explains why the key operators in a QEP are chosen by connecting them to established knowledge in the literature.

Sketching is a common approach to visually query time series data. However, a recent study reported that sketching a pattern for querying is "often ineffective on its own" in practice due to lack of "representative objects" to facilitate bottom-up search. In this demonstration, we present a novel data-driven sketch-based visual query interface (VQI) construction system called SENSOR to alleviate this challenge. Given a time series dataset, SENSOR automatically constructs its VQI by populating different components from the underlying data. Specifically, it discovers and exposes a set of representative objects in the form of VST-aware shapelets to facilitate query formulation. Such data-driven construction has several potential benefits such as empowering efficient top-down and bottom-up search and portability of the interface across different application domains and sources.

Time-series shapelets are discriminative subsequences, recently found effective for time series classification (tsc). It is evident that the quality of shapelets is crucial to the accuracy oftsc. However, major research has focused on building accurate models from some shapelet candidates. To determine such candidates, existing studies are surprisingly simple, e.g., enumerating subsequences of some fixed lengths, or randomly selecting some subsequences as shapelet candidates. The major bulk of computation is then on building the model from the candidates. In this paper, we propose a novelefficient shapelet discoverymethod, calledbspcover, to discover a set of high-quality shapelet candidates for model building. Specifically,bspcovergenerates abundant candidates via Symbolic Aggregate approXimation with sliding window, then prunes identical and highly similar candidates viaBloom filters, andsimilarity matching, respectively. We next propose a$p$p-Cover algorithmto efficiently determine discriminative shapelet candidates that maximally represent each time-series class. Finally, any existing shapelet learning method can be adopted to build a classification model. We have conducted extensive experiments with well-known time-series datasets and representative state-of-the-art methods. Results show thatbspcoverspeeds up the state-of-the-art methods by more than 70 times, and the accuracy is often comparable to or higher than existing works.

Graph query autocompletion (gQAC) generates a small list of ranked query suggestions during the graph query formulation process in a visual environment. The current state-of-the-art ofgQACprovides suggestions that are formed by adding subgraph increments to arbitrary places of an existing (partial) user query. However, according to the research results on human-computer interaction (HCI), humans can only interact with a small number of recent software artifacts in hand. Hence, many of such suggestions could be irrelevant. In this paper, we present theGFocusframework that exploits a novel notion ofuser focus of graph query formulation(or simplyfocus). Intuitively, the focus is the subgraph that a user is working on. We formulatelocality principlesinspired by the HCI research to automatically identify and maintain the focus. We propose novel monotone submodular ranking functions for generatingpopularandcomprehensivequery suggestions only at the focus. In particular, the query suggestions ofGFocushave high result counts (when they are used as queries) and maximally cover the possible suggestions at the focus. We propose efficient algorithms and an index for ranking the suggestions. Our results show thatGFocussaves 12-32 percent more mouse clicks and is 35× more efficient than the state-of-the-art competitor.

Due to the unstructuredness and the lack of schema information of knowledge graphs, social networks and RDF graphs, keyword search has been proposed for querying such graphs/networks. Recently, various keyword search semantics have been designed. In this work, we propose a generic ontologybased indexing framework for keyword search, called Bisimulation of Generalized Graph Index (BiG-index), to enhance the search performance. Novelties of BiG-index reside in using an ontology graph GOnt to summarize and index a data graph G iteratively, to form a hierarchical index structure G. BiG-index is generic since it is applicable to keyword search algorithms that have two properties. BiG-index reduced the runtimes of popular keyword search work Blinks by 50.5% and r-clique by 29.5%.

Time-series shapelets are discriminative subsequences, recently found effective for time series classification (TSC). It is evident that the quality of shapelets is crucial to the accuracy of TSC. However, major research has focused on building accurate models from some shapelet candidates. To determine such candidates, existing studies are surprisingly simple, e.g., enumerating subsequences of some fixed lengths, or randomly selecting some subsequences as shapelet candidates. The major bulk of computation is then on building the model from the candidates. In this paper, we propose a novel efficient shapelet discovery method, called BSPCOVER, to discover a set of high-quality shapelet candidates for model building. We have conducted extensive experiments with well-known UCR time-series datasets and representative state-of-the-art methods. Results show that BSPCOVER speeds up the state-of-the-art methods by more than 70 times, and the accuracy is often comparable to or higher than existing works.

This paper studies privacy preserving query services for strong simulation queries in the database outsourcing paradigm. In such a paradigm, clients send their queries to a third-party service provider (SP), who has the outsourced large graph data, and the SP computes the query answers. However, as SP may not always be trusted, the sensitive information of the clients' queries, importantly, the query structures, should be protected. Moreover, graph pattern queries often have high complexities, whereas data graphs can be large. This paper adopts strong simulation as a practical query semantic for this paradigm. Under this semantic, queries are matched with a notion of balls, which are subgraphs related to the query diameter. We transform the core of the existing strong simulation algorithm using data-oblivious operations (ObSSA) and propose its secure version. We show that the algorithm may encounter an overflow problem even partially homomorphic encryption (PHE) has been used. We then propose an efficient inexact algorithm EncSSA, which is secure under chosen plaintext attack (CPA). The results of privacy analysis are presented. We have conducted experiments on Twitter and Citeseer datasets, and the results show that EncSSA is both efficient and effective.

Several visual graph query interfaces (a.k.a gui) expose a set of canned patterns (i.e., small subgraph patterns) to expedite subgraph query formulation by enabling pattern-at-a-time construction. Unfortunately, manual generation of canned patterns is not only labour intensive but also may lack diversity to support efficient visual formulation of a wide range of subgraph queries. Recent efforts have taken a data-driven approach to select high-quality canned patterns for a gui automatically from the underlying graph database. However, as the underlying database evolves, these selected patterns may become stale and adversely impact efficient query formulation. In this paper, we present a novel framework called Midas for efficient and effective maintenance of the canned patterns as the database evolves. Specifically, it adopts a selective maintenance strategy that guarantees progressive gain of coverage of the patterns without sacrificing their diversity and cognitive load. Experimental study with real-world datasets and visual graph interfaces demonstrates the effectiveness of Midas compared to static guis.

The database systems course is offered as part of an undergraduate computer science degree program in many major universities. A key learning goal of learners taking such a course is to understand how sql queries are processed in a rdbms in practice. Since aquery execution plan (qep ) describes the execution steps of a query, learners can acquire the understanding by perusing the qep s generated by a rdbms. Unfortunately, in practice, it is often daunting for a learner to comprehend these qep s containing vendor-specific implementation details, hindering her learning process. In this paper, we present a novel, end-to-end,generic system called lantern that generates a natural language description of a qep to facilitate understanding of the query execution steps. It takes as input an sql query and its qep, and generates a natural language description of the execution strategy deployed by the underlying rdbms. Specifically, it deploys adeclarative framework called pool that enablessubject matter experts to efficiently create and maintain natural language descriptions of physical operators used in qep s. Arule-based framework called rule-lantern is proposed that exploits pool to generate natural language descriptions of qep s. Despite the high accuracy of rule-lantern, our engagement with learners reveal that, consistent with existing psychology theories, perusing such rule-based descriptions lead toboredom due to repetitive statements across different qep s. To address this issue, we present a noveldeep learning-based language generation framework called neural -lantern that infuses language variability in the generated description by exploiting a set ofparaphrasing tools andword embedding. Our experimental study with real learners shows the effectiveness of lantern in facilitating comprehension of qep s.

Canned patterns ( i.e. , small subgraph patterns) in visual graph query interfaces (a.k.a GUI) facilitate efficient query formulation by enabling pattern-at-a-time construction mode. However, existing GUIS for querying large networks either do not expose any canned patterns or if they do then they are typically selected manually based on domain knowledge. Unfortunately, manual generation of canned patterns is not only labor intensive but may also lack diversity for supporting efficient visual formulation of a wide range of subgraph queries. In this paper, we present a novel, generic, and extensible framework called TATTOO that takes a data-driven approach to automatically select canned patterns for a GUI from large networks. Specifically, it first decomposes the underlying network into truss-infested and truss-oblivious regions. Then candidate canned patterns capturing different real-world query topologies are generated from these regions. Canned patterns based on a user-specified plug are then selected for the GUI from these candidates by maximizing coverage and diversity , and by minimizing the cognitive load of the pattern set. Experimental studies with real-world datasets demonstrate the benefits of TATTOO. Importantly, this work takes a concrete step towards realizing plug-and-play visual graph query interfaces for large networks.

Due to the unstructuredness and the lack of schema information of knowledge graphs, social networks and RDF graphs, keyword search has been proposed for querying such graphs/networks. Recently, various keyword search semantics have been designed. In this paper, we propose a generic ontology-based indexing framework for keyword search, called Bisimulation of Generalized Graph Index (BiG-index BiG-index), to enhance the search performance. The novelties of BiG-index BiG-index reside in using an ontology graph GOntGOnt to summarize and index a data graph G G iteratively, to form a hierarchical index structure G. BiG-index BiG-index is generic since it only requires keyword search algorithms to generate query answers from summary graphs having two simple properties. Regarding query evaluation, we transform a keyword search q q into Q according to GOntGOnt in runtime. The transformed query is searched on the summary graphs in G. The efficiency is due to the small sizes of the summary graphs and the early pruning of semantically irrelevant subgraphs. To illustrate BiG-index BiG-index's applicability, we show popular indexing techniques for keyword search (e.g., Blinks Blinks and r-clique r-clique) can be easily implemented on top of BiG-index BiG-index. Our extensive experiments show that BiG-index BiG-index reduced the runtimes of popular keyword search work Blinks Blinks by 50.5 percent and r-clique r-clique by 29.5 percent.

Time series classification (TSC) has attracted considerable attention from both academia and industry. TSC methods that are based on shapelets (intuitively, small highly-discriminative subsequences have been found effective and are particularly known for their interpretability, as shapelets themselves are subsequences. A recent work has significantly improved the efficiency of shapelet discovery. For instance, the shapelets of more than 65% of the datasets in the UCR Archive (containing data from different application domains) can be computed within an hour, whereas those of 12 datasets can be computed within a minute. Such efficiency has made it possible for demo attendees to interact with shapelet discovery and explore high-quality shapelets. In this demo, we present Visualet -- a tool for visualizing shapelets, and exploring effective and interpretable ones.

Due to the unstructuredness and the lack of schemas of graphs, such as knowledge graphs, social networks and RDF graphs, keyword search has been proposed for querying such graphs/networks. In many applications (e.g., social networks), users may prefer to hide parts or all of her/his data graphs (e.g., private friendships) from the public. This leads to a recent graph model, namely the public-private network model, in which each user has his/her own network. While there have been studies on public-private network analysis, keyword search on public- private networks has not yet been studied. For example, query answers on private networks and on a combination of private and public networks can be different. In this paper, we propose a new keyword search framework, called public-private keyword search (PPKWS). PPKWS consists of three major steps: partial evaluation, answer refinement, and answer completion. Since there have been plenty of keyword search semantics, we select three representative ones and show that they can be implemented on the model with minor modifications. We propose indexes and optimizations for PPKWS. We have verified through experiments that, on average, the algorithms implemented on top of PPKWS run 113 times faster than the original algorithms directly running on the public network attached to the private network for retrieving answers that spans through them.

Several commercial and academic frameworks for querying a large collection of small- or medium-sized data graphs (eg. chemical compounds) provide visual graph query interfaces (a.k.a GUI) to facilitate non-programmers to query these sources. However, construction of these visual interfaces is not data-driven. That is, it does not exploit the underlying data graphs to automatically generate the contents of various panels in a GUI. Such data-driven construction has several benefits such as facilitating efficient subgraph query formulation and portability of the interface across different application domains and sources. In this demonstration, we present a novel data-driven visual subgraph query interface construction engine called AURORA. Specifically, given a graph repository D containing a collection of small- or medium-sized data graphs, it automatically generates the GUI for D by populating various components of the interface. We demonstrate various innovative features of AURORA.

Online information diffusion generates huge volumes of social activities (eg. tweets, retweets posts, comments, likes) among individuals. Existing information diffusion modeling techniques are oblivious to conformity of individuals during the diffusion process, a fundamental human trait according to social psychology theories. Intuitively, conformity captures the extent to which an individual complies with social norms or expectations. In this paper, we present a novel framework called chassis to characterize online information diffusion by bridging classical information diffusion model with conformity from social psychology. To this end, we first extend "Hawkes Process", a well-known statistical technique utilized to model information diffusion, to quantitatively capture two flavors of conformity, informational conformity and normative conformity, hidden in activity sequences. Next, we present a novel semi-parametric inference approach to learn the proposed model. Experimental study with real-world datasets demonstrates the superiority of chassis to state-of-the-art conformity-unaware information diffusion models.

Despite the crucial role of cardinality estimation in query optimization, there has been no systematic and in-depth study of the existing cardinality estimation techniques for subgraph matching queries. In this paper, for the first time, we present a comprehensive study of the existing cardinality estimation techniques for subgraph matching queries, scaling far beyond the original experiments. We first introduce a novel framework called g-care that enables us to realize all existing techniques on top of it and that provides insights on their performance. By using g-care, we then reimplement representative cardinality estimation techniques for graph databases as well as relational databases. We next evaluate these techniques w.r.t accuracy on rdf and non-rdf graphs from different domains with subgraph matching queries of various topologies so far considered. Surprisingly, our results reveal that all existing techniques have serious problems in accuracy for various scenarios and datasets. Intriguingly, a simple sampling method based on an online aggregation technique designed for relational data, consistently outperforms all existing techniques.

The paradigm of interleaving (i.e. blending) visual subgraph query formulation and processing by exploiting the latency offered by the GUI brings in several potential benefits such as superior system response time (SRT) and opportunities to enhance usability of graph databases. Recent efforts at implementing this paradigm are focused on subgraph isomorphism-based queries, which are often restrictive in many real-world graph applications. In this demonstration, we present a novel system called BOOMER to realize this paradigm on more generic but complex bounded 1-1 p-homomorphic(BPH) queries on large networks. Intuitively, a BPH query maps an edge of the query to bounded paths in the data graph. We demonstrate various innovative features of BOOMER, its flexibility, and its promising performance.

Smart contracts enable developers to run instructions on blockchains (eg. Ethereum) and have broad range of real-world applications. Solidity is the most popular high-level smart contract programming language on Ethereum. Coding in such language, however, demands a user to be proficient in contract programming and debugging to construct smart contracts correctly. In practice, such expectation makes it harder for non-programmers to take advantage of smart contracts. In this demonstration, we present a novel visual smart contract construction system on Ethereum called latte to make smart contract development accessible to non-programmers. Specifically, it allows a user to construct a contract without writing Solidity code by manipulating visual objects in a direct manipulation-based interface. Furthermore, latte interactively guides users and makes them aware of the cost (in units of Gas) of visual actions undertaken by them during contract construction.

Given a graph G where each node is associated with a set of attributes, attributed network embedding (ANE) maps each node v ∈ G to a compact vector X v , which can be used in downstream machine learning tasks. Ideally, X v should capture node v 's affinity to each attribute, which considers not only v 's own attribute associations, but also those of its connected nodes along edges in G . It is challenging to obtain high-utility embeddings that enable accurate predictions; scaling effective ANE computation to massive graphs with millions of nodes pushes the difficulty of the problem to a whole new level. Existing solutions largely fail on such graphs, leading to prohibitive costs, low-quality embeddings, or both. This paper proposes PANE, an effective and scalable approach to ANE computation for massive graphs that achieves state-of-the-art result quality on multiple benchmark datasets, measured by the accuracy of three common prediction tasks: attribute inference, link prediction, and node classification. In particular, for the large MAG data with over 59 million nodes, 0.98 billion edges, and 2000 attributes, PANE is the only known viable solution that obtains effective embeddings on a single server, within 12 hours. PANE obtains high scalability and effectiveness through three main algorithmic designs. First, it formulates the learning objective based on a novel random walk model for attributed networks. The resulting optimization task is still challenging on large graphs. Second, PANE includes a highly efficient solver for the above optimization problem, whose key module is a carefully designed initialization of the embeddings, which drastically reduces the number of iterations required to converge. Finally, PANE utilizes multi-core CPUs through non-trivial parallelization of the above solver, which achieves scalability while retaining the high quality of the resulting embeddings. Extensive experiments, comparing 10 existing approaches on 8 real datasets, demonstrate that PANE consistently outperforms all existing methods in terms of result quality, while being orders of magnitude faster.

Given an input graph G and a node v ∈ G , homogeneous network embedding (HNE) maps the graph structure in the vicinity of v to a compact, fixed-dimensional feature vector. This paper focuses on HNE for massive graphs, e.g. , with billions of edges. On this scale, most existing approaches fail, as they incur either prohibitively high costs, or severely compromised result utility. Our proposed solution, called Node-Reweighted PageRank (NRP), is based on a classic idea of deriving embedding vectors from pairwise personalized PageRank (PPR) values. Our contributions are twofold: first, we design a simple and efficient baseline HNE method based on PPR that is capable of handling billion-edge graphs on commodity hardware; second and more importantly, we identify an inherent drawback of vanilla PPR, and address it in our main proposal NRP. Specifically, PPR was designed for a very different purpose, i.e. , ranking nodes in G based on their relative importance from a source node's perspective. In contrast, HNE aims to build node embeddings considering the whole graph. Consequently, node embeddings derived directly from PPR are of suboptimal utility. The proposed NRP approach overcomes the above deficiency through an effective and efficient node reweighting algorithm, which augments PPR values with node degree information, and iteratively adjusts embedding vectors accordingly. Overall, NRP takes O ( m log n ) time and O ( m ) space to compute all node embeddings for a graph with m edges and n nodes. Our extensive experiments that compare NRP against 18 existing solutions over 7 real graphs demonstrate that NRP achieves higher result utility than all the solutions for link prediction, graph reconstruction and node classification, while being up to orders of magnitude faster. In particular, on a billion-edge Twitter graph, NRP terminates within 4 hours, using a single CPU core.

The facility relocation (FR) problem, which aims to optimize the placement of facilities to accommodate the changes of users’ locations, has a broad spectrum of applications. Despite the significant progress made by existing solutions to the FR problem, they all assume each user is stationary and represented as a single point. Unfortunately, in reality, objects (e.g., people, animals) are mobile. For example, a car-sharing user picks up a vehicle from a station close to where he or she is currently located. Consequently, these efforts may fail to identify a superior solution to the FR problem. In this article, for the first time, we take into account the movement history of users and introduce a novel FR problem, called motion-fr , to address the preceding limitation. Specifically, we present a framework called frost to address it. frost comprises two exact algorithms: index based and index free . The former is designed to address the scenario when facilities and objects are known a priori , whereas the latter solves the motion-fr problem by jettisoning this assumption. Further, we extend the index-based algorithm to solve the general k - motion-fr problem, which aims to relocate k inferior facilities. We devise an approximate solution due to NP-hardness of the problem. Experimental study over both real-world and synthetic datasets demonstrates the superiority of our framework in comparison to state-of-the-art FR techniques in efficiency and effectiveness.

With the proliferation of mobile devices and location-based services, continuous generation of massive volume of streaming spatial objects (i.e., geo-tagged data) opens up new opportunities to address real-world problems by analyzing them. In this paper, we present a novel continuous bursty region detection (SURGE) problem that aims to continuously detect a burstyregion of a given size in a specified geographical area from a stream of spatial objects. Specifically, a bursty region shows maximum spike in the number of spatial objects in a given time window. The SURGE problem is useful in addressing several real-world challenges such as surge pricing problem in online transportation and disease outbreak detection. To solve the problem, we propose an exact solution and two approximate solutions, and the approximation ratio is 1-α/4 in terms of the burst score, where α is a parameter to control the burst score. We further extend these solutions to support detection of top-k bursty regions. Extensive experiments with real-world data are conducted to demonstrate the efficiency and effectiveness of our solutions.

Old documents tend to be difficult to be analyzed and understood, not only for average users but oftentimes for professionals as well. This is due to the context shift, vocabulary evolution and, in general, the lack of precise knowledge about the writing styles in the past. We propose a concept of positioning document in the context of its time, and develop an interactive system to support such an objective. Our system helps users to know whether the vocabulary used by an author in the past were frequent at the time of text creation, whether the author used anachronisms or neologisms, and so on. It also enables detecting terms in text that underwent considerable semantic change and provides more information on the nature of such change. Overall, the proposed tool offers additional knowledge on the writing style and vocabulary choice in documents by drawing from data collected at the time of their creation or at other user-specified time.

Estimation of path travel time provides great value to applications like bus line designs and route plannings. Existing approaches are mainly based on single-source trajectory datasets that are usually large in size to ensure a satisfactory performance. This leads to two limitations: 1) Large-scale data may not always be attainable, e.g. city-scale public bus data is usually small compared to taxi data due to relative fewer bus trips in a day. 2) Considering only single-source trajectory data neglects the potential estimation-improving insights of external data, e.g. trajectory dataset of other vehicle sources obtained from the same geographical region. A challenge is how to effectively utilize such other trajectory sources. Moreover, existing work does not attend the important attributes of a trajectory including vehicle ID, day of week, rainfall level etc., which are important for estimating the path travel time. Motivated by these and the recent successes of neural network models, we propose Attribute-related Hybrid Trajectories Network~(AtHy-TNet), a neural model that effectively utilizes the attribute correlations, as well as the spatial and temporal relationships across hybrid trajectory data. We apply this to a novel problem of estimating path travel time of a type of vehicles using a hybrid trajectory dataset that includes trajectories from other vehicle types. We demonstrate in our experiments the benefits of considering hybrid data for travel time estimation, and show that AtHy-TNet significantly outperforms state-of-the-art methods on real-world trajectory datasets.

Composing queries is evidently a tedious task. This is particularly true of graph queries as they are typically complex and prone to errors. This is compounded by the fact that graph schemas can be missing or too loose to be helpful for query formulation. Graph Query AutoCompletion (gQAC) alleviates users from the potentially painstaking task of graph query formulation. This demonstration presents an interactive visual Focused GRaph quEry AutocompleTion framework, called FGreat. Its novelty relies on the user focus for gQAC, which is a subgraph of the current query that a user is focusing on. FGreat automatically computes a focus and completes the query at the focus, as opposed to an arbitrary query subgraph. This demonstration presents two complementary approaches to compute the user focus for different circumstances. It computes the focus from either (i) the sequence of edges that a user recently added to his/her query, or (ii) the position of the mouse cursor, if it is available. We demonstrate that the user focus enhances both the effectiveness and efficiency of graph query autocompletion.

Although exploratory search has received significant attention recently in the context of structured data, scant attention has been paid for graph-structured data. In this paper, we present two novel index structures called VACCINE and ADVISE to efficiently support exploratory subgraph search in a visual environment (VESS). VACCINE is an offline, feature-based index that stores rich information related to frequent and infrequent subgraphs in the underlying graph database and how they can be transformed from one subgraph to another. ADVISE, on the other hand, is an adaptive, compact, on-the-fly index instantiated during iterative visual formulation/reformulation of a subgraph query for exploratory search and records relevant information to efficiently support its repeated evaluation. These indexes engender more efficient and scalable visual exploratory subgraph search framework compared to a state-of-the-art technique.

Many social media sites allow users to upload text, images, and videos (collectively referred to asanchor post) for public consumption. These posts may attract hundreds of comments from many social users leading to social conversations (ie discussions). Tools that can facilitate user-friendly and effective understanding and analysis of large volumes of comments associated with anchor posts can be of great benefit to individuals and organizations. In this demonstration, we present a novel end-to-end visualization system called Kandinsky to supportmulti-faceted visualization of social discussions associated with an anchor post. In Kandinsky, the social discussion landscape is visualized using a collection of colorfulcircles andconcentric circles, which are inspired from the famous abstract arts called"Squares with Concentric Circles" and"Several Circles" by Russian painter Wassily Kandinsky (1866-1944). Intuitively, a circle and a concentric circle represent a social comment and a collection of comments in a discussion thread, respectively. We discuss various innovative features of Kandinsky and demonstrate its effectiveness.

Visual graph query interfaces (a.k.a gui ) widen the reach of graph querying frameworks across different users by enabling non-programmers to use them. Consequently, several commercial and academic frameworks for querying a large collection of small- or medium-sized data graphs (\textite.g., chemical compounds) provide such visual interfaces. Majority of these interfaces expose a fixed set ofcanned patterns (\textiti.e., small subgraph patterns) to expedite query formulation by enabling pattern-at-a-time in lieu of edge-at-a-time construction mode. Canned patterns to be displayed on a gui are typically selected manually based on domain knowledge. However, manual generation of canned patterns is labour intensive. Furthermore, these patterns may not sufficiently cover the underlying data graphs to expedite visual formulation of a wide range of subgraph queries. In this paper, we present a generic and extensible framework called Catapult to address these limitations. Catapult takes a data-driven approach toautomatically select canned patterns, thereby taking a concrete step towards the vision of data-driven construction of visual query interfaces. Specifically, it firstclusters the underlying data graphs based on their topological similarities and thensummarize each cluster to create acluster summary graph (csg ). The canned patterns within a user-specifiedpattern budget are then generated from these csg s by maximizingcoverage anddiversity, and minimizingcognitive load of the patterns. Experimental study with real-world datasets and visual graph interfaces demonstrates the superiority of Catapult compared to traditional techniques.

A core component of a database systems course at the undergraduate level is the design and implementation of the query optimizer in an rdbms. The query optimization process produces aquery execution plan (qep ), which represents an execution strategy for an sql query. Unfortunately, in practice, it is often difficult for a student to comprehend a query execution strategy by perusing its qep, hindering her learning process. In this demonstration, we present a novel system called neuron that facilitates natural language interaction with qep s to enhance its understanding. neuron accepts an sql query (which may include joins, aggregation, nesting, among other things) as input, executes it, and generates a simplified natural language description (both in text and voice form) of the execution strategy deployed by the underlying rdbms. Furthermore, it facilitates understanding of various features related to a qep through anatural language question answering (nlqa ) framework. We advocate that such tool, world's first of its kind, can greatly enhance students' learning of the query optimization topic.

Given an undirected graph G and a seed node s, the local clustering problem aims to identify a high-quality cluster containing s in time roughly proportional to the size of the cluster, regardless of the size of G. This problem finds numerous applications on large-scale graphs. Recently, heat kernel PageRank (HKPR), which is a measure of the proximity of nodes in graphs, is applied to this problem and found to be more efficient compared with prior methods. However, existing solutions for computing HKPR either are prohibitively expensive or provide unsatisfactory error approximation on HKPR values, rendering them impractical especially on billion-edge graphs. In this paper, we present TEA and TEA+, two novel local graph clustering algorithms based on HKPR, to address the aforementioned limitations. Specifically, these algorithms provide non-trivial theoretical guarantees in relative error of HKPR values and the time complexity. The basic idea is to utilize deterministic graph traversal to produce a rough estimation of exact HKPR vector, and then exploit Monte-Carlo random walks to refine the results in an optimized and non-trivial way. In particular, TEA+ offers practical efficiency and effectiveness due to non-trivial optimizations. Extensive experiments on real-world datasets demonstrate that TEA+ outperforms the state-of-the-art algorithm by more than four times on most benchmark datasets in terms of computational time when achieving the same clustering quality, and in particular, is an order of magnitude faster on large graphs including the widely studied Twitter and Friendster datasets.

In recent years, we have witnessed a rapid increase of text content stored in digital archives such as newspaper archives or web archives. With the passage of time, it is however difficult to effectively perform search within such collections due to vocabulary and context change. In this paper, we present a system that helps to find analogical terms across temporal text collections by applying non-linear transformation. We implement two approaches for analog retrieval where one of them allows users to also input an aspect term specifying particular perspective of a query. The current prototype system permits temporal analog search across two different time periods based on New York Times Annotated Corpus.

Abstract We propose a novel way of utilizing and accessing information stored in news archives as well as a new style of investigating the history. Our idea is to automatically generate similar entity pairs given two sets of entities, one from the past and one representing the present. This allows performing entity-oriented mapping between different times. We introduce an effective method to solve the aforementioned task based on a concise integer linear programming framework. In particular, our model first conducts typicality analysis to estimate entity representativeness. It next constructs orthogonal transformation between the two entity collections. The result is a set of typical across-time comparables. We demonstrate the effectiveness of our approach on the New York Times dataset through both qualitative and quantitative tests.

Tweets summarization aims to find a group of representative tweets for a specific set of input tweets or a given topic. In recent times, there have been several research efforts toward devising a variety of techniques to summarize tweets in Twitter. However, these techniques are either not personal (that is, consider only tweets in the timeline of a specific user) or are too expensive to be realized on a mobile device. Given that 80% of active Twitter users access the site on mobile devices, in this article we present a lightweight, personal, on‐demand, topic modeling‐based tweets summarization engine called TOTEM, designed for such devices. Specifically, TOTEM first preprocesses recent tweets in a user's timeline and exploits Latent Dirichlet Allocation‐based topic modeling to assign each preprocessed tweet to a topic. Then it generates a ranked list of relevant tweets, a topic label, and a topic summary for each of the topics. Our experimental study with real‐world data sets demonstrates the superiority of TOTEM.

Human language constantly evolves due to the changing world and the need for easier forms of expression and communication. Our knowledge of language evolution is however still fragmentary despite significant interest of both researchers as well as wider public in the evolution of language. In this paper, we present an interactive framework that permits users study the evolution of words and concepts. The system we propose offers a rich online interface allowing arbitrary queries and complex analytics over large scale historical textual data, letting users investigate changes in meaning, context and word relationships across time.

With the proliferation of location-based services, the generation of massive geo-tagged data opens up new opportunities to address real-world problems. In this paper, we present a novel continuous bursty region detection (SURGE) problem that aims to continuously detect a bursty region of a given size in a specified geographical area from a stream of spatial objects. The SURGE problem is useful in addressing several real-world challenges such as disease outbreak detection. We propose an exact solution to address the problem, and show the efficiency and effectiveness by conducting experiments on real-world datasets.

Tag-based Social Image Retrieval (TagIR) aims to find relevant social images using keyword queries. State-of-the-art TagIR techniques typically rank query results based on relevance, temporal or popularity criteria. However, these criteria may not always be sufficient to match diverse search intents of users. In this paper, we present a novel ranking scheme that ranks query results (images) based on their historical relevance. Informally, an image is historically relevant if its visual content is relevant to the query and it depicts objects, scenes, or events that are related to human history. To this end, we propose a learning-agnostic technique that leverages Wikipedia to quantify historical relevance of images. We empirically demonstrate the effectiveness of our ranking scheme using Flickr dataset.

User-generated comments and tags can reveal important visual concepts associated with an image in Flickr. However, due to the inherent noisiness of the metadata, not all user tags are necessarily descriptive of the image. Likewise, comments may contain spam or chatter that are irrelevant to the image. Hence, identifying and ranking relevant tags and comments can boost applications such as tag-based image search, tag recommendation, etc. In this paper, we present a lightweight visual signature-based model to concurrently generate ranked lists of comments and tags of a social image based on their joint relevance to the visual features, user comments, and user tags. The proposed model is based on sparse reconstruction of the visual content of an image using its tags and comments. Through empirical study on Flickr dataset, we demonstrate the effectiveness and superiority of the proposed technique against state-of-the-art tag ranking and refinement techniques.

Visual graph query interfaces (a.k.a GUI) make it easy for non-expert users to query graphs. Recent research has laid out and implemented a vision of a novel subgraph query processing paradigm where the latency offered by the GUI is exploited to blend visual query construction and processing by generating and refining candidate result matches iteratively during query formulation. This paradigm brings in several potential benefits such as superior system response time (srt) and opportunities to enhance usability of graph databases. However, these early efforts focused on subgraph isomorphism-based graph queries where blending is performed by iterative edge-to-edge mapping. In this paper, we explore how this vision can be realized for more generic but complex 1-1 p-homomorphic p-hom) queries introduced by Fan et al. A 1-1 p-hom query maps an edge of the query to paths in the data graph. We present a novel framework called BOOMER for blending bounded 1-1 p-hom (bph ) queries, a variant of 1-1 p-hom where the length of the path is bounded instead of arbitrary length. Our framework is based on a novel online , adaptive indexing scheme called cap index. We present two strategies for CAP index construction, immediate and deferment-based, and show how they can be utilized to facilitate judicious interleaving of visual bph query formulation and query processing. BOOMER is also amenable to modifications to a bph query during visual formulation. Experiments on real-world datasets demonstrate both efficiency and effectiveness of Boomer for realizing the visual querying paradigm on an important type of graph query.

Detecting conflicts of interest (COIs) is key for guaranteeing the fairness of a peer-review process. In many conference management systems, the COIs of authors and reviewers are self-declared, and the declaration process is time consuming and potentially incomplete. To address this problem, we demonstrate a novel interactive system called PISTIS that assists the declaration process in a semi-automatic manner. Apart from keyword search and simple filtering, our system provides an interactive graphical interface that helps users explore potential COIs based on the heterogenous data sources. To simply the process of declaration, we also recommend latent COIs using a supervised ranking model that can be iteratively refined from the data collected from past declarations. We believe that PISTIS can be useful as an assistant tool in many real world conference management systems.

A large body of research on subgraph query processing on large networks assumes that a query is posed in the form of a connected graph. Unfortunately, end users in practice may not always have precise knowledge about the topological relationships between nodes in a query graph to formulate a connected query. In this demonstration, we present a novel graph querying paradigm called partial topology-based network search and a query processing system called panda to efficiently find top-k matches of a partial topology query ( ptq ) in a single machine. A ptq is a disconnected query graph containing multiple connected query components . ptq s allow an end user to formulate queries without demanding precise information about the complete topology of a query graph. We demonstrate various innovative features of panda and its promising performance.

Peer review is the most critical process in evaluating an article to be accepted for publication in an academic venue. When assigning a reviewer to evaluate an article, the assignment should be aware of conflicts of interest (COIs) such that the reviews are fair to everyone. However, existing conference management systems simply ask reviewers and authors to declare their explicit COIs through a plain search user interface guided by some simple conflict rules. We argue that such declaration system is not enough to discover all latent COI cases. In this work, we study a graphical declaration system that visualizes the relationships of authors and reviewers based on a heterogeneous co-authorship network. With the help of the declarations, we attempt to detect the latent COIs automatically based on the meta-paths of a heterogeneous network.

The location selection (LS) problem aims to mine the optimal location to place a new facility from a set of candidates such that the benefit or influence on a given set of objects is maximized. State-of-the-art LS techniques assume each object is static and can only be influenced by a single facility. However, in reality, objects (e.g., people, vehicles) are mobile and are influenced by multiple facilities. Consequently, classical LS solutions fail to select locations accurately. In this work, we introduce a generalized LS problem called PRIME-LS which takes mobility and probability factors into consideration to address the aforementioned limitations. To solve the problem, we propose an algorithm called PINOCCHIO, which leverages two pruning rules based on a novel distance measure, and further extend it by incorporating two optimization strategies. Experimental study over two real-world datasets demonstrates superiority of our framework in comparison to state-of-the-art LS techniques.

Tweets summarization aims to find a group of representative tweets for a specific topic. In recent times, there have been several research efforts toward devising a variety of techniques to summarize tweets in Twitter. However, these techniques are either not personal (i.e., consider only tweets in the timeline of a specific user) or are too expensive to be realized on a mobile device. Given that 80% of active Twitter users access the site on mobile devices, in this demonstration we present a lightweight, personalized, on-demand, topic modeling-based tweets summarization engine called TOTEM, designed for such devices. Specifically, TOTEM summarizes most recent tweets on a user's timeline and enables her to visualize and navigate representative topics and associated tweets in a user-friendly tap-and-swipe manner.

Despite a decade of research on XML keyword search (XKS), demonstration of a high quality XKS system has still eluded the information retrieval community. Existing XKS engines primarily suffer from two limitations. First, although the smallest lowest common ancestor (SLCA) algorithm (or a variant, e.g., ELCA) is widely accepted as a meaningful way to identify subtrees containing the query keywords, SLCA typically performs poorly on documents with missing elements, i.e., (sub)elements that are optional, or appear in some instances of an element type but not all. Second, since keyword search can be ambiguous with multiple possible interpretations, it is desirable for an XKS engine to automatically expand the original query by providing a classification of different possible interpretations of the query w.r.t. the original results. However, existing XKS systems do not support such result-based query expansion. We demonstrate ASTERIX, an innovative XKS engine that addresses these limitations.

Querying graph databases has emerged as an important research problem for real-world applications that center on large graph data. Given the syntactic complexity of graph query languages (e.g., SPARQL, Cypher), visual graph query interfaces make it easy for non-expert users to query such graph data repositories. In this tutorial, we survey recent developments in the emerging area of visual graph querying paradigm that bridges traditional graph querying with human computer interaction (HCI). We discuss manual and data-driven visual graph query interfaces, various strategies and guidance for constructing graph queries visually, interleaving processing of graph queries and visual actions, and visual exploration of graph query results. In addition, the tutorial suggests open problems and new research directions. In summary, in this tutorial we review and summarize the research thus far into HCI and graph querying in the database community, giving researchers a snapshot of the current state of the art in this topic, and future research directions.

Recently, exploratory search has received much attention in information retrieval and database fields. This search paradigm assists users who do not have a clear search intent and are unfamiliar with the underlying data space. Specifically, query formulation evolves iteratively as the user becomes more familiar with the content. Despite its growing importance, exploratory search on graph-structured data has received little attention in the literature. We demonstrate a system called picasso to realize exploratory sub-structure search on a graph database containing a set of small or medium-sized data graphs. picasso embodies several novel features such as progressive ( i.e. , iterative) formulation of queries visually and incremental processing, multi-stream results exploration wall to visualize, explore, and analyze search results to identify possible search directions.

Large-scale, highly-interconnected networks pervade our society and the natural world around us, including the World Wide Web, social networks, knowledge graphs, genome and scientific databases, medical and government records. The massive scale of graph data often surpasses the available computation and storage resources. Besides, users get overwhelmed by the daunting task of understanding and using such graphs due to their sheer volume and complexity. Hence, there is a critical need to summarize large graphs into concise forms that can be more easily visualized, processed, and managed. Graph summarization has indeed attracted a lot of interests from various research communities, such as sociology, physics, chemistry, bioinformatics, and computer science. Different ways of summarizing graphs have been invented that are often complementary to each other. In this tutorial, we discuss algorithmic advances on graph summarization in the context of both classical (e.g., static graphs) and emerging (e.g., dynamic and stream graphs) applications. We emphasize the current challenges and highlight some future research directions.

Visual graph interfaces improve the usability of graph databases by making it easier for users to formulate queries. Recently, a variety of interactive query formulation-based techniques (e.g., blending of visual query construction and processing, visual query suggestions) have been proposed to enhance query performance and usability. Comprehensive user studies are needed to exhaustively and systematically evaluate performance of the proposed techniques, but, unfortunately, user studies are expensive and time consuming. To reduce the cost and time needed, we present a novel synthetic visual subgraph query simulator called VISUAL. VISUAL realistically simulates subgraph query construction without requiring human users. It can automatically generate test subgraph queries having different user-specified characteristics by utilizing the underlying indexes and simulate their formulation based on different query formulation sequences. A key feature of this simulator is that it is built on top of an HCI-inspired, extensible quantitative model which enables us to model the visual query formulation process quantitatively. Our experimental study demonstrates the effectiveness of VISUAL in accurately simulating visual subgraph queries.

Subgraph query (via subgraph isomorphism) is a fundamental and powerful query in various real graph applications. It has actively been investigated for performance enhancements recently. However, due to the high complexity of subgraph query, hosting efficient subgraph query services has been a technically challenging task, because the owners of graph data may not always possess the IT expertise to offer such services and hence may outsource to query service providers (SP). SPs are often equipped with high performance computing utilities (e.g., a cloud) that offer better scalability, elasticity and IT management. Unfortunately, as SPs may not always be trusted, security (such as the confidentiality of messages exchanged) has been recognized as one of the critical attributes of Quality of Services (QoS) [4]. This influences the willingness of both data owners and query clients to use SP's services. Recently, there is a bloom on the research on query processing with privacy preservation1, e.g., in the context of relational databases, spatial databases and graph databases. However, up to date, private subgraph query has not yet been studied.

The increasing popularity and growth of mobile devices and location-based services enable us to utilize large-scale geo-tagged data to support novel location-based applications. This paper introduces a novel problem called the best region search (BRS) problem and provides efficient solutions to it. Given a set O of spatial objects, a submodular monotone aggregate score function, and the size a x b of a query rectangle, the BRS problem aims to find a x b rectangular region such that the aggregate score of the spatial objects inside the region is maximized. This problem is fundamental to support several real-world applications such as most influential region search (eg. the best location for a signage to attract most audience) and most diversified region search (eg. region with most diverse facilities). We propose an efficient algorithm called SliceBRS to find the exact answer to the BRS problem. Furthermore, we propose an approximate solution called CoverBRS and prove that the answer found by it is bounded by a constant. Our experimental study with real-world datasets and applications demonstrates the effectiveness and superiority of our proposed algorithms.

Subgraph enumeration is important for many applications such as subgraph frequencies, network motif discovery, graphlet kernel computation, and studying the evolution of social networks. Most earlier work on subgraph enumeration assumes that graphs are resident in memory, which results in serious scalability problems. Recently, efforts to enumerate all subgraphs in a large-scale graph have seemed to enjoy some success by partitioning the data graph and exploiting the distributed frameworks such as MapReduce and distributed graph engines. However, we notice that all existing distributed approaches have serious performance problems for subgraph enumeration due to the explosive number of partial results. In this paper, we design and implement a disk-based, single machine parallel subgraph enumeration solution called DualSim that can handle massive graphs without maintaining exponential numbers of partial results. Specifically, we propose a novel concept of the dual approach for subgraph enumeration. The dual approach swaps the roles of the data graph and the query graph. Specifically, instead of fixing the matching order in the query and then matching data vertices, it fixes the data vertices by fixing a set of disk pages and then finds all subgraph matchings in these pages. This enables us to significantly reduce the number of disk reads. We conduct extensive experiments with various real-world graphs to systematically demonstrate the superiority of DualSim over state-of-the-art distributed subgraph enumeration methods. DualSim outperforms the state-of-the-art methods by up to orders of magnitude, while they fail for many queries due to explosive intermediate results.

Visual query interfaces make it easy for scientists and other nonexpert users to query a data collection. Heretofore, visual query interfaces have been statically-constructed, independent of the data. In this paper we outline a vision of a different kind of interface, one that is built (in part) from the data. In our data-driven approach, the visual interface is dynamically constructed and maintained. A data-driven approach has many benefits such as reducing the cost in constructing and maintaining an interface, superior support for query formulation, and increased portability of the interface. We focus on graph databases, but our approach is applicable to several other kinds of databases such as JSON and XML.

Composing queries is evidently a tedious task. This is particularly true of graph queries as they are typically complex and prone to errors, compounded by the fact that graph schemas can be missing or too loose to be helpful for query formulation. Despite the great success of query formulation aids, in particular, automatic query completion , graph query autocompletion has received much less research attention. In this demonstration, we present a novel interactive visual subgraph query autocompletion framework called A uto G which alleviates the potentially painstaking task of graph query formulation. Specifically, given a large collection of small or medium-sized graphs and a visual query fragment q formulated by a user, A uto G returns top- k query suggestions Q ′ as output at interactive time. Users may choose a query from Q ′ and iteratively apply A uto G to compose their queries. We demonstrate various features of A uto G and its superior ability to generate high quality suggestions to aid visual subgraph query formulation.

The increasing availability and significance of large-scale protein-protein interaction (PPI) data has resulted in a flurry of research activity to comprehend the organization, processes, and functioning of cells by analyzing these data at network level. Network clustering, that analyzes the topological and functional properties of a PPI network to identify clusters of interacting proteins, has gained significant popularity in the bioinformatics as well as data mining research communities. Many studies since the last decade have shown that clustering PPI networks is an effective approach for identifying functional modules, revealing functions of unknown proteins, etc. In this paper, we examine this issue by classifying, discussing, and comparing a wide ranging approaches proposed by the bioinformatics community to cluster PPI networks. A pervasive desire of this review is to emphasize the uniqueness of the network clustering problem in the context of PPI networks and highlight why generic network clustering algorithms proposed by the data mining community cannot be directly adopted to address this problem effectively. We also review a closely related problem to PPI network clustering, network summarization, which can enable us to make sense out of the information contained in large PPI networks by generating multi-level functional summaries.

The location selection (ls) problem, which aims to mine the optimal location from a set of candidates to place a new facility such that a score (i.e., benefit or influence on some given objects) can be maximized, has drawn significant research attention in recent years. State-of-the-art ls techniques assume each object is static and can only be influenced by a single facility. However, in reality, objects (e.g., people, vehicles) are mobile and are influenced by multiple facilities, which prevents classical ls solutions from selecting accurate results. In this paper, we introduce a generalizedls problem called Prime-ls which takes mobility and probability factors into consideration to address the aforementioned limitations. Specifically, given a set of candidate locations, Prime-ls aims to mine the optimal location which can influence the most number of moving objects. Also, to address the problem we propose an efficient algorithm called Pinocchio that leverages two pruning rules based on a novel distance measure. These rules enable us to prune many inferior candidate locations prior to influence computation, paving the way to efficient and accurate solution. Furthermore, we extend Pinocchio (Pinocchio-vo) by incorporating two optimization strategies during candidate validation phase, which further reduce unnecessary computations. Experimental study over two real-world datasets demonstrates superiority of our framework in comparison to state-of-the-art ls techniques.

Numerous archives and collections of past documents have become available recently thanks to mass scale digitization and preservation efforts. Libraries, national archives, and other memory institutions have started opening up their collections to interested users. Yet, searching within such collections usually requires knowledge of appropriate keywords due to different context and language of the past. Thus, non-professional users may have difficulties with conceptualizing suitable queries, as, typically, their knowledge of the past is limited. In this paper, we propose a novel approach for the temporal correspondence detection task that requires finding terms in the past which are semantically closest to a given input present term. The approach we propose is based on vector space transformation that maps the distributed word representation in the present to the one in the past. The key problem in this approach is obtaining correct training set that could be used for a variety of diverse document collections and arbitrary time periods. To solve this problem, we propose an effective technique for automatically constructing seed pairs of terms to be used for finding the transformation. We test the performance of proposed approaches over short as well as long time frames such as 100 years. Our experiments demonstrate that the proposed methods outperform the best-performing baseline by 113 percent for the New York Times Annotated Corpus and by 28 percent for the Times Archive in MRR on average, when the query has a different literal form from its temporal counterpart.

The usability of visual querying schemes for tree and graph-structured data can be greatly enhanced by providing feedback during query construction, but feedback at inopportune times can hamper query construction. In this paper, we rethink the traditional way of providing feedback. We describe a novel vision of interruption-sensitive query feedback where relevant notifications are delivered quickly but at an appropriate moment when the mental workload of the user is low. Though we focus on one class of query feedback, namely empty result detection, where a user is notified when a partially constructed visual query yields an empty result, our new paradigm is applicable to other kinds of feedback. We present a framework called iSERF that bridges the classical database problem of empty-result detection with intelligent notification management from the domains of HCI and psychology. Instead of immediate notification, iSERF considers the structure of query formulation tasks and breakpoints when reasoning about when to notify the user. We present an HCI-inspired model to quantify the performance bounds that iSERF must abide by for checking for an empty result in order to ensure interruption-sensitive notification at optimal breakpoints. We implement this framework in the context of visual XML query formulation and highlight its effectiveness empirically.

In [3], we laid out the vision of a novel graph query processing paradigm, where visual subgraph query formulation is interleaved (or “blended”) with query processing by exploiting the latency offered by the gui. Our recent attempts at implementing this vision [6], [7] do not provide any robust framework to systematically investigate the performance of this novel paradigm. This is because it is prohibitively expensive to engage a large number of users to formulate a large number of visual queries in order to measure the performance of blending query formulation with query processing. In this demonstration, we present a novel synthetic visual subgraph query simulator called ViSual that can evaluate the performance of this paradigm for a large number of visual subgraph queries without requiring a large number of users to formulate them. Specifically, it leverages principles from hci to quantify the gui latency that is necessary to realistically simulate blending of query formulation and query processing.

One fundamental type of query for graph databases is subgraph isomorphism queries (a.k.a subgraph queries). Due to the computational hardness of subgraph queries coupled with the cost of managing massive graph data, outsourcing the query computation to a third-party service provider has been an economical and scalable approach. However, confidentiality is known to be an important attribute of Quality of Service (QoS) in Query as a Service (QaaS). In this paper, we propose the first practical private approach for subgraph query services, asymmetric structure-preserving subgraph query processing, where the data graph is publicly known and the query structure/topology is kept secret. Unlike other previous methods for subgraph queries, this paper proposes a series of novel optimizations that only exploit graph structures, not the queries. Further, we propose a robust query encoding and adopt the novel cyclic group based encryption so that query processing is transformed into a series of private matrix operations. Our experiments confirm that our techniques are efficient and the optimizations are effective.

Subgraph queries have been a fundamental query for retrieving patterns from graph data. Due to the well known NP hardness of subgraph queries, those queries may sometimes take a long time to complete. Our recent investigation on real- world datasets revealed that the performance of queries on graphs generally varies greatly. In other words, query clients may occasionally encounter “unexpectedly” long execution from a subgraph query processor. This paper aims to demonstrate a tool that alleviates the problem by monitoring subgraph query progress. Specifically, we present a novel subgraph query progress indicator called PIGEON that exploits query-time information to report to users accurate estimated query progress. In the demonstration, users may interact with PIGEON to gain insights on the query evaluation, which include the following: Users are enabled to (i) monitor query progress; (ii) analyze the causes of long query times; and (iii) abort queries that run abnormally long, which may sometimes contain human errors.

Due to the complexity of graph query languages, the need for visual query interfaces that can reduce the burden of query formulation is fundamental to the spreading of graph data management tools to a wider community. Despite the significant progress towards building such query interfaces to simplify visual subgraph query formulation task, construction of current generation visual interfaces is not data-driven. That is, it does not exploit the underlying data graphs to automatically generate the contents of various panels in the interface. Such data-driven construction has several benefits such as superior support for subgraph query formulation and portability of the interface across different graph databases. In this demonstration, we present a novel data-driven visual subgraph query interface construction engine called DaVinci. Specifically, it automatically generates from the underlying database two key components of the visual interface to aid subgraph query formulation, namely canned patterns and node labels.

State-of-the-art classical influence maximization (IM) techniques are "competition-unaware" as they assume that a group (company) finds seeds (users) in a network independent of other groups who are also simultaneously interested in finding such seeds in the same network. However, in reality several groups often compete for the same market (e.g., Samsung, HTC, and Apple for the smart phone market) and hence may attempt to select seeds in the same network. This has led to increasing body of research in devising IM techniques for competitive networks. Despite the considerable progress made by these efforts toward finding seeds in a more realistic settings, unfortunately, they still make several unrealistic assumptions (e.g., a new company being aware of a rival's strategy, alternate seed selection, etc.) making their deployment impractical in real-world networks. In this paper, we propose a novel framework based on game theory to provide a more realistic solution to the IM problem in competitive networks by jettisoning these unrealistic assumptions. Specifically, we seek to find the "best" IM strategy (an algorithm or a mixture of algorithms) a group should adopt in the presence of rivals so that it can maximize its influence. As each group adopts some strategy, we model the problem as a game with each group as competitors and the expected influences under the strategies as payoffs. We propose a novel algorithm called GetReal to find each group's best solution by leveraging the competition between different groups. Specifically, it seeks to find whether there exist a Nash Equilibrium (NE) in a game, which guarantees that there exist an "optimal" strategy for each group. Our experimental study on real-world networks demonstrates the superiority of our solution in a more realistic environment.

XQuery programs can be hard to write and port to new data collections because the path expressions in a query aredependenton the hierarchy of the data. We propose to demonstrate a system to liberate query writers from this dependence. Aplug-and-play querycontains a specification of what data the query needs in order to evaluate. We implementedvirtual eXist-dbto support plug-and-play XQuery queries. Our system adds avirtualDocfunction that lets a programmer sketch the hierarchy needed by the query, which may well be different than what the data has, and logically (not physically) transforms the data (with information loss guarantees) to the hierarchy specified by thevirtualDoc.The demonstration will consist of a sequence of XQuery queries using a virtual hierarchy, including queries suggested by the audience. We will also demonstrate a GUI tool to construct a virtual hierarchy.

Most existing tag-based social image search engines present search results as a ranked list of images, which cannot be consumed by users in a natural and intuitive manner. In this demonstration, we present a novel concept-preserving image search results summarization system called prism . prism exploits both visual features and tags of the search results to generate high quality summary , which not only breaks the results into visually and semantically coherent clusters but it also maximizes the coverage of the original top- k search results. It first constructs a visual similarity graph where the nodes are images in the top- k search results and the edges represent visual similarities between pairs of images. This graph is optimally decomposed and compressed into a set of concept-preserving subgraphs based on a set of summarization criteria. One or more exemplar images from each subgraph is selected to form the exemplar summary of the result set. We demonstrate various innovative features of prism and the promise of superior quality summary construction of social image search results.

A fundamental problem of graph databases is subgraph isomorphism query (a.k.a subgraph query): given a query graph Q and a graph database, it retrieves the graphs Gs from the database that contain Q. Due to the cost of managing massive data coupled with the computational hardness of subgraph isomorphism testing, outsourcing the computations to a third-party provider is an appealing alternative. However, confidentiality has been a critical attribute of quality of service (QoS) in query services. To the best of our knowledge, subgraph query services with tunable preservation of privacy of structural information have never been addressed. In this paper, we present the first work on structure-preserving subIso (SPsubIso). A crucial step of our work is to transform subIso-the seminal subgraph isomorphism algorithm (the Ullmann's algorithm)-into a series of matrix operations. We propose a novel cyclic group based encryption (CGBE) method for private matrix operations. We propose a protocol that involves the query client and static indexes to optimize SPsubIso. We prove that the structural information of both Q and G are preserved under CGBE and analyze the privacy preservation in the presence of the optimizations. Our extensive experiments on both real and synthetic datasets verify that SPsubIso is efficient and the optimizations are effective.

Subgraph similarity search is used in graph databases to retrieve graphs whose subgraphs are similar to a given query graph. It has been proven successful in a wide range of applications including bioinformatics and chem-informatics, etc. Due to the cost of providing efficient similarity search services on ever-increasing graph data, database outsourcing is apparently an appealing solution to database owners. Unfortunately, query service providers may be untrusted or compromised by attacks. To our knowledge, no studies have been carried out on the authentication of the search. In this paper, we propose authentication techniques that follow the popular filtering-and-verification framework. We propose an authentication-friendly metric index called GMTree. Specifically, we transform the similarity search into a search in a graph metric space and derive small verification objects (VOs) to-be-transmitted to query clients. To further optimize GMTree, we propose a sampling-based pivot selection method and an authenticated version of MCS computation. Our comprehensive experiments verified the effectiveness and efficiency of our proposed techniques.

Most existing tag-based social image search engines present search results as a ranked list of images, which cannot be consumed by users in a natural and intuitive manner. In this paper, we present a novel concept-preserving image search results summarization algorithm named Prism. Prism exploits both visual features and tags of the search results to generate high quality summary, which not only breaks the results into visually and semantically coherent clusters but it also maximizes the coverage of the summary w.r.t the original search results. It first constructs a visual similarity graph where the nodes are images in the search results and the edges represent visual similarities between pairs of images. This graph is optimally decomposed and compressed into a set of concept-preserving subgraphs based on a set of summarization objectives. Images in a concept-preserving subgraph are visually and semantically cohesive and are described by a minimal set of tags or concepts. Lastly, one or more exemplar images from each subgraph is selected to form the exemplar summary of the result set. Through empirical study, we demonstrate the effectiveness of Prism against state-of-the-art image summarization and clustering algorithms.

Prefix-based numbering is a popular method for numbering nodes in a hierarchy. But prefix-based numbering breaks down when a node's location within a hierarchy changes, such as when XML data is queried after being transformed by an XSLT program or when data is reformatted in the return clause of an inner FLWR expression in a nested XQuery program. A query on transformed data cannot be evaluated as efficiently since the extant prefix-based node numbers cannot be used (unless the data is materialized and then renumbered, which can be expensive). In this paper we present a novel strategy to virtually transform the data without instantiating and renumbering. Our method, which we call virtual prefix-based numbering, couples each prefix-based node number with a level array that locates the node in the numbering space of the virtual hierarchy. The virtual numbering space preserves the property that location-based relationships between nodes can be determined by comparing (virtual) numbers.

Recently, with the emergence of event-based online social services(e.g. Meetup), there have been increasing online activities to create, distribute, and organize social events. In this paper, we take the first systematic step to discover influential event organizers from online social networks who are essential to the overall success of social events. Informally, such event organizers comprise a small group of people who not only have the relevant skills or expertise that are required for an event (e.g. conference) but they are also able to influence largest number of people to actively contribute to it. We formulate it as the problem of mining influential cover set (ICS) where we wish to find k users in a social network G that together have the required skills or expertise (modeled as attributes of nodes in G) to organize an event such that they can influence the greatest number of individuals to participate in the event. The problem is, however, NP-hard. Hence, we propose three algorithms to find approximate solutions to the problem. The first two algorithms are greedy; they run faster, but have no guarantees. The third algorithm is 2-approximate and guarantees to find a feasible solution if any. Our empirical study over several real-world networks demonstrates the superiority of our proposed solutions.

Views and their updates have long been a fundamental technology required in a wide range of applications. However, it has been known that updates through views is a classical intractable problem. In this paper, we propose a novel, data-oriented approach to this problem that provides a practical support for view updates. In particular, we propose a summarization of the source database of views, which serves as an update filter. The update filter aims to efficiently reject untranslatable view updates by estimating the side effects of the updates, thereby avoiding costly translation analysis. For applications where estimation errors are not preferred, our update filter can be tuned to be exact. In this paper, we present our approach with SPJ views, an important class of view definitions. We first revise the notion of estimation errors to quantify the filter's qualities. We then propose a novel join cardinality summary (JCard) derived from cardinality equivalence. An estimation algorithm is proposed. Finally, we present optimizations enabling the construction of an accurate JCard through heuristics and sampling. Our extensive experiments show that update filters are efficient and can be easily tuned to produce accurate estimations on TPC-H and DBLP.

Influence maximization (IM) is the problem of finding a small subset of nodes (seed nodes) in a social network that could maximize the spread of influence. Despite the progress achieved by state-of-the-art greedy IM techniques, they suffer from two key limitations. Firstly, they are inefficient as they can take days to find seeds in very large real-world networks. Secondly, although extensive research in social psychology suggests that humans will readily conform to the wishes or beliefs of others, surprisingly, existing IM techniques are conformity-unaware. That is, they only utilize an individual's ability to influence another but ignores conformity (a person's inclination to be influenced) of the individuals.

In a previous paper, we laid out the vision of a novel graph query processing paradigm where instead of processing a visual query graph after its construction, it interleaves visual query formulation and processing by exploiting the latency offered by the GUI [4]. Our recent attempts at implementing this vision [4,6], show significant improvement in the system response time (SRT) for subgraph queries. However, these efforts are designed specifically for graph databases containing a large collection of small or medium-sized graphs. Consequently, its frequent fragment-based action-aware indexing schemes and query processing strategy are unsuitable for supporting subgraph queries on large networks containing thousands of nodes and edges. In this demonstration, we present a novel system called QUBLE (QUery Blender for Large nEtworks) to realize this novel paradigm on large networks. We demonstrate various innovative features of QUBLE and its promising performance.

Keyword search for smallest lowest common ancestors (SLCAs) in XML data has been widely accepted as a meaningful way to identify matching nodes where their subtrees contain an input set of keywords. Although SLCA and its variants (e.g.,MLCA) perform admirably in identifying matching nodes, surprisingly, they perform poorly for searches on irregular schemas that have missing elements, that is, (sub)elements that are optional, or appear in some instances of an element type but not all (e.g., a "population" subelement in a "city" element might be optional, appearing when the population is known and absent when the population is unknown). In this paper, we generalize the SLCA search paradigm to support queries involving missing elements. Specifically, we propose a novel property called optionality resilience that specifies the desired behaviors of an XML keyword search (XKS) approach for queries involving missing elements. We present two variants of a novel algorithm called MESSIAH (Missing Element-conSciouS hIgh-quality SLCA searcH), which are optionality resilient to irregular documents. MESSIAH logically transforms an XML document to a minimal full document where all missing elements are represented as empty elements, i.e., the irregular schema is made "regular", and then employs efficient strategies to identify partial and complete full SLCA nodes (SLCA nodes in the full document) from it. Specifically, it generates the same SLCA nodes as any state-of-the-art approach when the query does not involve missing elements but avoids irrelevant results when missing elements are involved. Our experimental study demonstrates the ability of MESSIAH to produce superior quality search results.

There have been numerous recent applications of graph databases (e.g., the Semantic Web, ontology representation, social networks, XML, chemical databases, and biological databases). A fundamental structural index for data graphs, namely minimum bisimulation, has been reported useful for efficient path query processing and optimization including selectivity estimation, among many others. Data graphs are subject to change and their indexes are updated accordingly. This paper studies the incremental maintenance problem of the minimum bisimulation of a possibly cyclic data graph. While cyclic graphs are ubiquitous among the data on the web, previous work on the maintenance problem has mostly focused on acyclic graphs. To study the problem with cyclic graphs, we first show that the two existing classes of minimization algorithms - merging algorithm and partition refinement - have their strengths and weaknesses. Second, we propose a novel hybrid algorithm and its analytical model. This algorithm supports an edge insertion or deletion and two forms of batch insertions or deletions. To the best of our knowledge, this is the first maintenance algorithm that guarantees minimum bisimulation of cyclic graphs. Third, we propose to partially reuse the minimum bisimulation before an update in order to optimize maintenance performance. We present an experimental study on both synthetic and real-data graphs that verified the efficiency and effectiveness of our algorithms.

We study a new type of graph queries, which injectively maps its edges to paths of the graphs in a given database, where the length of each path is constrained by a given threshold specified by the weight of the corresponding matching edge. We give important applications of the new graph query and identify new challenges of processing such a query. Then, we devise the cost model of the branch-and-bound algorithm framework for processing the graph query, and propose an efficient algorithm to minimize the cost overhead. We also develop three indexing techniques to efficiently answer the queries online. Finally, we verify the efficiency of our proposed indexes with extensive experiments on large real and synthetic datasets.

Differential privacy is a robust principle for privacy preserving data analysis tasks, and has been successfully applied to a variety of applications. However, the number of queries that can be answered is limited for preventing privacy disclosure. Once the privacy budget is exhausted, all succeeding queries must be rejected. Therefore, each of the historical query answers is valuable and it is important to exploit them together to learn more about the data. We propose to integrate all available linear query answers into a consistent form that embodies our knowledge learned from the noisy answers, obtaining more accurate answers to past queries and even new queries, improving the data utility. Two distinct approaches are developed for this purpose, one via principle component analysis, and another via maximum entropy method. The second approach also generates a synthetic database, which is useful for differentially private data publishing. One important goal of our work is to ensure that the running time of our approaches does not grow with the cardinality of the universe of a data tuple, so that high-dimensional data with very large domain can still be tackled efficiently.

A limitation of XQuery is that a programmer has to be familiar with the shape of the data to query it effectively. And if that shape changes, or if the shape is other than what the programmer expects, the query may fail. One way to avoid this limitation is to transform the data into a desired shape. A data transformation is a rearrangement of data into a new shape. In this paper, we present the semantics and implementation of XMorph 2.0, a shape-polymorphic data transformation language for XML. An XMorph program can act as a query guard. The guard both transforms data to the shape needed by the query and determines whether and how the transformation potentially loses information, a transformation that loses information may lead to a query yielding an inaccurate result. This paper describes how to use XMorph as a query guard, gives a formal semantics for shape-to-shape transformations, documents how XMorph determines how a transformation potentially loses information, and describes the XMorph implementation.

In a previous paper, we laid out the vision of a novel graph query processing paradigm where instead of processing a visual query graph after its construction, it interleaves visual query formulation and processing by exploiting the latency offered by the GUI to filter irrelevant matches and prefetch partial query results [8]. Our first attempt at implementing this vision, called GBLENDER [8], shows significant improvement in system response time (SRT) for sub graph containment queries. However, GBLENDER suffers from two key drawbacks, namely inability to handle visual sub graph similarity queries and inefficient support for visual query modification, limiting its usage in practical environment. In this paper, we propose a novel algorithm called PRAGUE (Practical visu Al Graph QUery Blender), that addresses these limitations by exploiting a novel data structure called spindle-shaped graphs (SPIG). A SPIG succinctly records various information related to the set of super graphs of a newly added edge in the visual query fragment. Specifically, PRAGUE realizes a unified visual framework to support SPIG-based processing of modification-efficient sub graph containment and similarity queries. Extensive experiments on real-world and synthetic datasets demonstrate effectiveness of PRAGUE.

Tags associated with social images are valuable information source for superior tag-based image retrieval (TagIR) experiences. One of the key issues in TagIR is to learn the effectiveness of a tag in describing the visual content of its annotated image, also known as tag relevance. One of the most effective approaches in the literature for tag relevance learning is neighbor voting. In this approach a tag is considered more relevant to its annotated image (also known as the seed image) if the tag is also used to annotate the neighbor images (nearest neighbors by visual similarity). However, the state-of-the-art approach that realizes the neighbor voting scheme does not explore the possibility of exploiting the content (e.g., degree of visual similarity between the seed and neighbor images) and contextual (e.g., tag association by co-occurrence) features of social images to further boost the accuracy of TagIR. In this paper, we identify and explore the viability of four content and context-based dimensions namely, image similarity, tag matching, tag influence, and refined tag relevance, in the context of tag relevance learning for TagIR. With alternative formulations under each dimension, this paper empirically evaluated 20 neighbor voting schemes with 81 single-tag queries on nus-wide dataset. Despite the potential benefits that the contextual information related to tags bring in to image search, surprisingly, our experimental results reveal that the content-based (image similarity) dimension is still the king as it significantly improves the accuracy of tag relevance learning for TagIR. On the other hand, tag relevance learning does not benefit from the context-based dimensions in the voting schemes.

Social influence analysis in online social networks is the study of people's influence by analyzing the social interactions between individuals. There have been increasing research efforts to understand the influence propagation phenomenon due to its importance to information dissemination among others. Despite the progress achieved by state-of-the-art social influence analysis techniques, a key limitation of these techniques is that they only utilize positive interactions (e.g., agreement, trust) between individuals, ignoring two equally important factors, namely, negative relationships (e.g., distrust, disagreement) between individuals and conformity of people, which refers to a person's inclination to be influenced. In this paper, we propose a novel algorithm CASINO (Conformity-Aware Social INfluence cOmputation) to study the interplay between influence and conformity of each individual. Given a social network, CASINO first extracts a set of topic-based subgraphs where each subgraph depicts the social interactions associated with a specific topic. Then it optionally labels the edges (relationships) between individuals with positive or negative signs. Finally, it computes the influence and conformity indices of each individual in each signed topic-based subgraph. Our empirical study with several real-world social networks demonstrates superior effectiveness and accuracy of CASINO compared to state-of-the-art methods. Furthermore, we revealed several interesting characteristics of "influentials" and "conformers" in these networks.

In many real-world applications, it is important to create a local archive containing versions of structured results of continuous queries (queries that are evaluated periodically) submitted to autonomous database-driven Web sites (e.g., deep Web). Such history of digital information is a potential gold mine for all kinds of scientific, media and business analysts. An important task in this context is to maintain the set of common keys of the underlying archived results as they play pivotal role in data modeling and analysis, query processing, and entity tracking. A set of attributes in a structured data is a common key iff it is a key for all versions of the data in the archive. Due to the data-driven nature of key discovery from the archive, unlike traditional keys, the common keys are not temporally invariant. That is, keys identified in one version may be different from those in another version. Hence, in this paper, we propose a novel technique to maintain common keys in an archive containing a sequence of versions of evolutionary continuous query results. Given the current common key set of existing versions and a new snapshot, we propose an algorithm called COKE (COmmon KEy maintenancE) which incrementally maintains the common key set without undertaking expensive minimal keys computation from the new snapshot. Furthermore, it exploits certain interesting evolutionary features of real-world data to further reduce the computation cost. Our exhaustive empirical study demonstrates that COKE has excellent performance and is orders of magnitude faster than a baseline approach for maintenance of common keys.

Due to the complexity of graph query languages, the need for visual query interfaces that can reduce the burden of query formulation is fundamental to the spreading of graph data management tools to wider community. We present a novel HCI (human-computer interaction)-aware graph query processing paradigm, where instead of processing a query graph after its construction, it interleaves visual query construction and processing to improve system response time. We demonstrate a system called GBLENDER that exploits GUI latency to prune false results and prefetch candidate data graphs by employing a novel action-aware indexing scheme and a data structure called spindle-shaped graphs (SPIG). We demonstrate various innovative features of GBLENDER and its promising performance in evaluating subgraph containment and similarity queries.

Large online social rating networks (e.g., Epinions, Blippr) have recently come into being containing information related to various types of products. Typically, each product in these networks is associated with a group of members who have provided ratings and comments on it. These people form a product community. A potential member can join a product community by giving a new rating to the product. We refer to this phenomenon of a product community's ability to “attract” new members as product affinity. The knowledge of a ranked list of products based on product affinity is of much importance for implementing policies, marketing research, online advertisement, and other applications. In this article, we identify and analyze an array of features that exert effect on product affinity and propose a novel model, called AffRank, that utilizes these features to predict the future rank of products according to their affinities. Evaluated on two real-world datasets, we demonstrate the effectiveness and superior prediction quality of AffRank compared with baseline methods. Our experiments show that features such as affinity rank history, affinity evolution distance, and average rating are the most important factors affecting future rank of products. At the same time, interestingly, traditional community features (e.g., community size, member connectivity, and social context) have negligible influence on product affinities.

Tags associated with social images are valuable information source for superior image search and retrieval experiences. Although various heuristics are valuable to boost tag-based search for images, there is a lack of general framework to study the impact of these heuristics. Specifically, the task of ranking images matching a given tag query based on their associated tags in descending order of relevance has not been well studied. In this article, we take the first step to propose a generic, flexible, and extensible framework for this task and exploit it for a systematic and comprehensive empirical evaluation of various methods for ranking images. To this end, we identified five orthogonal dimensions to quantify the matching score between a tagged image and a tag query. These five dimensions are: (i) tag relatedness to measure the degree of effectiveness of a tag describing the tagged image; (ii) tag discrimination to quantify the degree of discrimination of a tag with respect to the entire tagged image collection; (iii) tag length normalization analogous to document length normalization in web search; (iv) tag-query matching model for the matching score computation between an image tag and a query tag; and (v) query model for tag query rewriting. For each dimension, we identify a few implementations and evaluate their impact on NUS-WIDE dataset, the largest human-annotated dataset consisting of more than 269K tagged images from Flickr. We evaluated 81 single-tag queries and 443 multi-tag queries over 288 search methods and systematically compare their performances using standard metrics including Precision at top-K, Mean Average Precision (MAP), Recall, and Normalized Discounted Cumulative Gain (NDCG).

Large online product review websites (e.g., Epinions, Blippr)to various types of products. Typically, each product in these sites is associated with a group of members who have provided ratings and comments on it. These people form a product community. A potential member can join a produce community by giving a new rating to the product. We refer to this phenomenon of a product community's ability to attract new members as product affinity. The knowledge of a ranked list of products based on product affinity is of much importance to be utilized for implementing policies, marketing research, online advertisement, and other applications. In this paper, we identify and analyze an array of features that exert effect on product affinity and propose a novel model, called AffRank, that utilizes these features to predict the future rank of products according to their affinities. Evaluated on a real-world dataset, we demonstrate the effectiveness and superior prediction quality of AffRank compared to baseline methods. Our experiments show that features such as affinity rank history, affinity evolution distance, and average rating are the most important factors affecting future rank of products.

By imposing a single hierarchy on data, XML makes queries brittle in the sense that a query might fail to produce the desired result if it is executed on the same data organized in a different hierarchy, or if the hierarchy evolves during the lifetime of an application. This paper presents a new transformation language, called XMorph, which supports more flexible querying. XMorph is a shape polymorphic language, that is, a single XMorph query can extract and transform data from differently-shaped hierarchies. The XMorph data shredder distills XML data into a graph of closest relationships, which are exploited by the query evaluation engine to produce a result in the shape specified by an XMorph query.

Given a graph database D and a query graph g, an exact subgraph matching query asks for the set S of graphs in D that contain g as a subgraph. This type of queries find important applications in several domains such as bioinformatics and chemoinformatics, where users are generally not familiar with complex graph query languages. Consequently, user-friendly visual interfaces which support query graph construction can reduce the burden of data retrieval for these users. Existing techniques for subgraph matching queries built on top of such visual framework are designed to optimize the time required in retrieving the result set S from D, assuming that the whole query graph has been constructed. This leads to sub-optimal system response time as the query processing is initiated only after the user has finished drawing the query graph.

XMorph is a new, shape polymorphic, domain-specific XML query language. A query in a shape polymorphic language adapts to the shape of the input, freeing the user from having to know the input's shape and making the query applicable to a wide variety of differently shaped inputs. An XMorph query specifies the shape of the output. The XMorph query engine transforms the input to the desired shape by shredding an XML document to a graph of closest relationships, and performing a closeness preserving transformation. We plan to demonstrate XMorph using a Java applet, which can also be used by the audience during the demonstration, to evaluate various XMorph queries. The applet will show the output, the shapes generated by the query, and report on potential data loss in a transformation.

Tags associated with social images are valuable information source for superior image search and retrieval experiences. Due to the nature of tagging, many tags associated with images are not visually descriptive. Consequently, presence of these noisy tags may reduce the effectiveness of tags' role in image retrieval. To address this problem, we demonstrate i Avatar (interActive VisuAl-representative TAgs Relationship) system that uses the notion of Normalized Image Tag Clarity (nitc) to find visual-representative tags . A visual-representative tag effectively describes the visual content of the images. Further, we visually demonstrate relationships between popular tags and visual-representative tags as well as co-occurrence likelihood of a pair of tags associated with a search tag or image using tag relationship graph (trg). We demonstrate various innovative features of i Avatar with a real-world dataset and show that it enriches users' understanding of various important tag features during image search.

XML query languages use directional path expressions to locate data in an XML data collection. They are tightly coupled to the structure of a data collection, and can fail when evaluated on the same data in a different structure. This paper extends path expressions with a new non-directional axis called the rank-distance axis. Given a context node and two positive integers α and β, the rank-distance axis returns those nodes that are ranked between α and β in terms of closeness from the context node in any direction. This paper shows how to evaluate the rank-distance axis in a tree-unaware XML database. A tree-unaware implementation does not invade the database kernel to support XML queries, instead it uses an existing RDBMS such as Microsoft's SQL server as a back-end and provides a front-end layer to translate XML queries to SQL. This paper presents an overview of an algorithm that translates queries with a rank-distance axis to SQL.

Information propagation within the blogosphere is of much importance in implementing policies, marketing research, launching new products, and other applications. In this paper, we take a microscopic view of the information propagation pattern in blogosphere by investigating blog cascade affinity. A blog cascade is a group of posts linked together discussing about the same topic, and cascade affnity refers to the phenomenon of a blog's inclination to join a specific cascade. We identify and analyze an array of features that may affect a blogger's cascade joining behavior and utilize these features to predict cascade affinity of blogs. Evaluated on a real dataset consisting of 873,496 posts, our svm-based prediction achieved accuracy of 0.723 measured by F1. Our experiments also showed that among all features identified, the number of friends was the most important factor affecting bloggers' inclination to join cascades.

Due to the complexity of XML query languages, the need for visual query interfaces that can reduce the burden of query formulation is fundamental to the spreading of XML to wider community. We present a RDBMS-based XML query evaluation system, called XBLEND, that takes a novel and non-traditional approach to improving query performance by blending visual query formulation and query processing. It exploits the latency offered by GUI-based visual query formulation to prefetch portions of the query results. The basic idea is that we prefetch constituent path expressions, store the synopsis of intermediary results, reuse them when connective is added or "Run" is pressed. In our demonstration we show that our system exhibits promising performance in evaluating XML queries and show its usefulness in life sciences domain.

Web archives preserve the history of autonomous Web sites and are potential gold mines for all kinds of media and business analysts. The most common Web archiving technique uses crawlers to automate the process of collecting Web pages. However, (re)downloading entire collection of pages periodically from a large Web site is unfeasible. In this paper, we take a step towards addressing this problem. We devise a data mining-driven policy for selectively (re)downloading Web pages that are located in hierarchical directory structures which are believed to have changed significantly (e.g., a substantial percentage of pages are inserted to/removed from the directory). Consequently, there is no need to download and maintain pages that have not changed since the last crawl as they can be easily retrieved from the archive. In our approach, we propose an off-line data mining algorithm called near- Miner that analyzes the evolution history of Web directory structures of the original Web site stored in the archive and mines negatively correlated association rules (near) between ancestor-descendant Web directories. These rules indicate the evolution correlations between Web directories. Using the discovered rules, we propose an efficient Web archive maintenance algorithm called warm that optimally skips the subdirectories (during the next crawl) which are negatively correlated with it in undergoing significant changes. Our experimental results with real data show that our approach improves the efficiency of the archive maintenance process significantly while sacrificing slightly in keeping the "freshness" of the archives. Furthermore, our experiments demonstrate that it is not necessary to discover nears frequently as the mining rules can be utilized effectively for archive maintenance over multiple versions.

Mining different types of communities from web data have attracted a lot of research efforts in recent years. However, none of the existing community mining techniques has taken into account both the dynamic as well as heterogeneous nature of web data. In this paper, we propose to characterize and predict community members from the evolution of heterogeneous web data. We first propose a general framework for analyzing the evolution of heterogeneous networks. Then, the academic network, which is extracted from 1 million computer science papers, is used as an example to illustrate the framework. Finally, two example applications of the academic network are presented. Experimental results with a real and very large heterogeneous academic network show that our proposed framework can produce good results in terms of community member recommendation. Also, novel knowledge and insights can be gained by analyzing the community evolution pattern.

Recent study showed that native twig join algorithms and tree-aware relational framework significantly outperform tree-unaware approaches in evaluating structural relationships in xml twig queries. In this paper, we present an efficient strategy to evaluate high-selective twig queries containing only parent-child relationships in a tree-unaware relational environment. Our scheme is built on top of our Sucxent++ system. We show that by exploiting the encoding scheme of Sucxent++, we can devise efficient strategy for evaluating such twig queries. Extensive performance studies on various data sets and queries show that our approach performs better than a representative tree-unaware approach (Global-Order) and a state-of-theart native twig join algorithm (TJFast) on all benchmark queries with the highest observed gain factors being 243 and 95, respectively. Additionally, our approach reduces significantly the performance gap between tree-aware and tree-unaware approaches and even outperforms a tree-aware approach (MonetDB/XQuery) for certain high-selective twig queries. We also report our insights to the plan choices a relational optimizer made during twig query evaluation by visually characterizing its behavior over the relational selectivity space. 2 1

Recently, a number of main memory algorithms for detecting the changes to XML data have been proposed. These approaches are not suitable for detecting changes to large XML document as it requires a lot of memory to keep the two versions of XML documents in the memory. We have developed a novel XML change detection system, called XANADUE that uses traditional relational database engines for detecting changes to large XML data. In this approach, we store the XML documents in the relational database and issue SQL queries (whenever appropriate) to detect the changes. This demonstration will showcase the functionality of our system and the effectiveness of XML change detection in relational environment.

Mirroring Web sites is a well-known technique commonly used in the Web community. A mirror site should be updated frequently to ensure that it reflects the content of the original site. Existing mirroring tools apply page-level strategies to check each page of a site, which is inefficient and expensive. In this paper, we propose a novel site-level mirror maintenance strategy. Our approach studies the evolution of Web directorystructures and mines association rules between ancestor-descendant Web directories. Discovered rules indicate the evolution correlations between Web directories. Thus, when maintaining the mirror of a Web site (directory), we can optimally skipsubdirectories which are negatively correlated with it in undergoing significant changes. The preliminary experimental results show that our approach improves the efficiency of the mirror maintenance process significantly while sacrificing slightly in keeping the "freshness" of the mirrors.

formulation and efficient processing of the formulated query. However, due to the nature of XML data, formulating an XML query using an XML query language such as XQuery requires considerable effort. A user must be completely familiar with the syntax of the query language, and must be able to express his/her needs accurately in a syntactically correct form. In many real life applications it is not realistic to assume that users are proficient in expressing such textual queries. Hence, there is a need for a user-friendly visual querying schemes to replace data retrieval aspects of XQuery. In this paper, we address the problem of efficient processing of XQueries in the relational environment where the queries are formulated using a user-friendly GUI. We take a novel and non-traditional approach to improving query performance by prefetching data during the formulation of a query in a single-user environment. The latency offered by the GUI-based query formulation is utilized to prefetch portions of the query results. The basic idea we employ for prefetching is that we prefetch constituent path expressions, store the intermediary results, reuse them when connective is added or "Run" is pressed.

Previous efforts on event detection from the web have focused primarily on web content and structure data ignoring the rich collection of web log data. In this paper, we propose the first approach to detect events from the click-through data, which is the log data of web search engines. The intuition behind event detection from click-through data is that such data is often event-driven and each event can be represented as a set ofquery-page pairs that are not only semantically similar but also have similar evolution pattern over time. Given the click-through data, in our proposed approach, we first segment it into a sequence of bipartite graphs based on theuser-defined time granularity. Next, the sequence of bipartite graphs is represented as a vector-based graph, which records the semantic and evolutionary relationships between queries and pages. After that, the vector-based graph is transformed into its dual graph, where each node is a query-page pair that will be used to represent real world events. Then, the problem of event detection is equivalent to the problem of clustering the dual graph of the vector-based graph. The clustering process is based on a two-phase graph cut algorithm. In the first phase, query-page pairs are clustered based on thesemantic-based similarity such that each cluster in the result corresponds to a specific topic. In the second phase, query-page pairs related to the same topic are further clustered based on the evolution pattern-based similarity such that each cluster is expected to represent a specific event under the specific topic. Experiments with real click-through data collected from a commercial web search engine show that the proposed approach produces high quality results.

It has become a promising direction to measure similarity of Web search queries by mining the increasing amount of click-through data logged by Web search engines, which record the interactions between users and the search engines. Most existing approaches employ the click-through data for similarity measure of queries with little consideration of the temporal factor, while the click-through data is often dynamic and contains rich temporal information. In this paper we present a new framework of time-dependent query semantic similarity model on exploiting the temporal characteristics of historical click-through data. The intuition is that more accurate semantic similarity values between queries can be obtained by taking into account the timestamps of the log data. With a set of user-defined calendar schema and calendar patterns, our time-dependent query similarity model is constructed using the marginalized kernel technique, which can exploit both explicit similarity and implicit semantics from the click-through data effectively. Experimental results on a large set of click-through data acquired from a commercial search engine show that our time-dependent query similarity model is more accurate than the existing approaches. Moreover, we observe that our time-dependent query similarity model can, to some extent, reflect real-world semantics such as real-world events that are happening over time.

Several relational approaches have been proposed to detect the changes to XML documents by using relational databases. These approaches store the XML documents in the relational database and issue SQL queries (whenever appropriate) to detect the changes. All of these relational-based approaches use the schema-oblivious XML storage strategy for detecting the changes. However, there is growing evidence that schema-conscious storage approaches perform significantly better than schema-oblivious approaches as far as XML query processing is concerned. In this paper, we study a relational-based unordered XML change detection technique (called HELIOS) that uses a schema-conscious approach (Shared-Inlining) as the underlying storage strategy. HELIOS is up to 52 times faster than X-Diff [7] for large datasets (more than 1000 nodes). It is also up to 6.7 times faster than XANDY [4]. The result quality of deltas detected by HELIOS is comparable to the result quality of deltas detected by XANDY.

Existing XML query pattern-based caching strategies focus on extracting the set of frequently issued query pattern trees based on the number of occurrences of the query pattern trees in the history. Each occurrence of the same query pattern tree is considered equally important for the caching strategy. However, the same query pattern tree may occur at different timepoints in the history of XML queries. This temporal feature can be used to improve the caching strategy. In this paper, we propose a novel type of query pattern called conserved query paths for efficient caching by integrating the support and temporal features together. Conserved query paths are paths in query pattern trees that never change or do not change significantly most of the time (if not always) in terms of their support values during a specific time period. We proposed an algorithm to extract those conserved query paths. By ranking those conserved query paths, a dynamic-conscious caching (DCC) strategy is proposed for efficient XML query processing. Experiments show that the DCC caching strategy outperforms the existing XML query pattern tree-based caching strategies.

Existing web usage mining techniques focus only on discovering knowledge based on the statistical measures obtained from the static characteristics of web usage data. They do not consider the dynamic nature of web usage data. In this paper, we focus on discovering novel knowledge by analyzing the change patterns of historical web access sequence data. We present an algorithm called WAM-MINER to discover Web Access Motifs (WAMs). WAMs are web access patterns that never change or do not change significantly most of the time (if not always) in terms of their support values during a specific time period. WAMs are useful for many applications, such as intelligent web advertisement, web site restructuring, business intelligence, and intelligent web caching.

No abstract available.

Recently, a large amount of work has been done in XML data mining. However, we observed that most of the existing works focus on the snapshot XML data, while XML data is dynamic in real applications. To the best of our knowledge, none of the existing works has addressed the issue of mining the history of changes to XML documents. Such mining results can be useful in many applications such as XML change detection, XML indexing, association rule mining, and classification etc. In this paper, we propose a novel approach to discover the frequently changing structures from the sequence of historical structural deltas of unordered XML. To make the structure discovering process efficient, an expressive and compact data model, Historical-Document Object Model (H-DOM), is proposed. Using this model, two basic algorithms, which can discover all the frequently changing structures with only two scans of the XML sequence, are presented. Experimental results show that our algorithms, together with the optimization techniques, are efficient and scalable.

In this paper, we describe a graphical workflow management system called HyperThesis to address the challenges of integrating bioinformatics applications. HyperThesis is an integral component of the Genomics Research Network Architecture (gRNA). The gRNA was designed and developed to address the challenges of developing new bioinformatics applications. Specifically, HyperThesis makes constructing workflows (pipelines of execution of applications) in the gRNA fast and intuitive for biologists and bio-programmers alike. It provides a large repository of interconnectable, parameterized workflow components for processing and relating diverse biological data and software programs. It also enables us to add new workflow components as new algorithms develop in ones area of interest. HyperThesis has been fully implemented using Java.

In this paper, we describe a system called XomatiQ to ad-dress the problem of integration, querying and correlation of biological data. XomatiQ is an integral part of the ge-nomics Research Network Architecture (gRNA). The gRNA provides the development environment in which new appli-cations can be quickly written, and the deployment environ-ment in which they can systematically avail of computing resources and integrate information from distributed bio-logical data sources. Specifically, XomatiQ is build on top of the Data Hounds component. The Data Hounds trans-forms data from various sources to XML format and loads them into tuples of relational tables in a standard commer-cial DBMS. The XomatiQ provides capability for querying XML data using the underlying relational engine. XomatiQ has been fully implemented using Java. 1

In this paper, we present a mechanism for detecting and representing changes, given the old and new versions of a set of interlinked Web documents, retrieved in response to a user's query. In particular, we show how to detect and represent Web deltas, i.e., changes in the Web documents that are relevant to a user's query in the context of our Web warehousing system called WHOWEDA (Warehouse of Web Data). In WHOWEDA, Web information is materialized views stored in Web tables in the form of Web tuples. These Web tuples, represented as directed graphs, can be manipulated using a set of Web algebraic operators. In this paper, we present a mechanism to detect relevant Web deltas using Web algebraic operators such as the Web join and the outer Web join. Web join is used to detect identical documents residing in two Web tables, whereas, outer Web join, a derivative of Web join, is used to identify dangling Web tuples. We show how to represent these changes using delta Web tables. We develop formal algorithms for the generation of delta Web tables identifying Web documents which have been added, deleted, or modified since the last query.

With the enormous amount of data stored in the World Wide Web, it is increasingly important to design and develop powerful web warehousing tools. The key objective of our web warehousing project, called WHOWEDA (Warehouse of Web Data), is to design and implement a web warehouse that materializes and manages useful information from the web. We introduce the concept of /spl Pi/-web join in the context of WHOWEDA. /spl Pi/-web join operator is a web information manipulation operator to combine relevant web information residing in two web tables. Informally, it is the combination of web join and web project operators which filter out irrelevant information from a joined web table. We show how to construct the /spl Pi/-joined web table and its schema. We also highlight the benefits of the /spl Pi/-web join operator.

Sets and bags are closely related structures and have been studied in relational databases. A bag is different from a set in that it is sensitive to the number of times an element occurs, while a set is not. In this paper, we introduce the concept of a Web bag in the context of a World Wide Web warehouse called WHOWEDA (WareHouse Of WEb DAta) which we are currently building. Informally, a Web bag is a Web table which allows multiple occurrences of identical Web types. A Web bag helps one to discover useful knowledge from a Web table, such as visible documents or Web sites (i.e. documents/sites which can be reached by many paths), luminous documents (i.e. documents with many outgoing links) and luminous paths (i.e. frequently traversed paths). In this paper, we provide a cost-benefit analysis of materializing Web bags as compared to Web tables with distinct Web tuples.