Search

Abstract: Continuous queries applied over nonterminating data streams usually specify windows in order to obtain an evolving–yet restricted–set of tuples and thus provide timely and incremental results. Although sliding windows get frequently employed in many user requests, additional types like partitioned or landmark windows are also available in stream processing engines. In this paper, we set out to study the existence of monotonic-related semantics for a rich set of windowing constructs in order to facilitate a more efficient maintenance of their changing contents. After laying out a formal foundation for expressing windowed queries, we investigate update patterns observed in most common window variants as well as their impact on adaptations of typical operators (like windowed join, union or aggregation), thus offering more insight towards design and implementation of stream processing mechanisms. Furthermore, we identify syntactic equivalences in algebraic expressions involving windows, to the potential benefit of query optimizations. Finally, this framework is validated for several windowed operations against streaming datasets with simulations at diverse arrival rates and window specifications, providing concrete evidence of its significance. [ABSTRACT FROM AUTHOR]

In this article, we present the design and implementation of SISYPHUS, a storage manager for data cubes that provides an efficient physical base for performing on-line analytical processing (OLAP) operations. OLAP poses new requirements to the physical storage layer of a database management system. Special characteristics of OLAP cubes such as multidimensionality, hierarchical structure of dimensions, data sparseness, etc., are difficult to handle with ordinary record-oriented storage managers. The SISYPHUS storage manager is based on a chunk-based data model that enables the hierarchical clustering of data with a very low storage cost. In this article we present the implementation of SISYPHUS’ chunk-oriented file system as well as present the core architecture of the system and reason on various design choices and implementation solutions. [Copyright &y& Elsevier]

Abstract Event detection over microblogs has attracted great research interest due to its wide application in crisis management and decision making etc. In natural disasters, complex events are reported in real time on social media sites, but these reports are invisible to crisis coordinators. Detecting these crisis events helps watchers to make right decisions rapidly, reducing injuries, deaths and economic loss. In sporting activities, detecting events helps audiences make better and more timely game viewing plans. However, existing event detection techniques are not effective at handling complex social events that evolve over time. In this paper, we propose an event detection method that takes advantage of retweeting behavior for handling the events evolution. Specifically, we first propose a topic model called RL-LDA to capture the social media information over hashtag, location, textual and retweeting behavior. Using RL-LDA, a complex event can be well handled by exploring the correlation between retweeting behavior and the event. Then to maintain the RL-LDA in a dynamic environment, we propose a dynamic update algorithm, which incrementally updates events over real time streams. Experiments over real-world datasets show that RL-LDA detects the temporal evolution of complex events effectively and efficiently. [ABSTRACT FROM AUTHOR]

Abstract: Sharing structured data in a P2P network is a challenging problem, especially in the absence of a mediated schema. The standard practice of answering a consecutively rewritten query along the propagation path often results in significant loss of information. On the opposite, the use of mediated schemas requires human interaction and global agreement, both during creation and maintenance. In this paper we present GrouPeer, an adaptive, automated approach to both issues in the context of unstructured P2P database overlays. By allowing peers to individually choose which rewritten version of a query to answer and evaluate the received answers, information-rich sources left hidden otherwise are discovered. Gradually, the overlay is restructured as semantically similar peers are clustered together. Experimental results show that our technique produces very accurate answers and builds clusters that are very close to the optimal ones by contacting a very small number of nodes in the overlay. [Copyright &y& Elsevier]

Abstract: Sharing of structured data in decentralized environments is a challenging problem, especially in the absence of a global schema. Social network structures map network links to semantic relations between participants in order to assist in efficient resource discovery and information exchange. In this work, we propose a scheme that automates the process of creating schema synopses from semantic clusters of peers which own autonomous relational databases. The resulting mediated schemas can be used as global interfaces for relevant queries. Active nodes are able to initiate the group schema creation process, which produces a mediated schema representative of nodes with similar semantics. Group schemas are then propagated in the overlay and used as a single interface for relevant queries. This increases both the quality and the quantity of the retrieved answers and allows for fast discovery of interest groups by joining peers. As our experimental evaluations show, this method increases both the quality and the quantity of the retrieved answers and allows for faster discovery of semantic groups by joining peers. [Copyright &y& Elsevier]

• The reasons for recommendations are extracted from the preference aspects. • The rating-based aspect contributions are matched with verbal reviews. • Graphs of aspect contributions in ratings provide a visual rationale. Word clouds show the opinions in reviews that explain a recommendation. Recommender systems based on collaborative filtering suggest items to users according to the similarity of items or similarity of preferences of other users. Latent factor models produce rather accurate predictions of user preferences, but the latency of the features extracted make it difficult to substantiate a recommendation to a user. The realisation that many aspects tend to exist in rating and social connections data, such as social influence or bias, led to the development of a component-based matrix factorisation approach in earlier work. The ability to quantify the contributions of a component to a recommendation opens up possibilities to identify reasons for recommendations which can be presented to the consumer receiving them. Reviews that accompany rating data can be analysed and correlated with latent factors to provide more detailed reasons for recommendations. This paper introduces a general comprehensive framework which supplements earlier work that models a users' preferences and makes recommendations by extracting reasons from the recommendation framework as well as the accompanying reviews. Both rating-based and review-based reasons for recommending an item are presented in a visual manner. These visualisations help the user understand the origins of the recommendations but also assist businesses in identifying properties in users and communities that open up opportunities for targeted marketing and customer management. The usefulness of the explanation tool is demonstrated with an example recommendation of four items for a user in the Yelp restaurants dataset. [ABSTRACT FROM AUTHOR]

Individuals use Twitter for personal communication, whereas businesses, politicians and celebrities use Twitter for branding purposes. Distinguishing Personal from Branding Twitter accounts is important for Twitter analytics. Existing studies of Twitter account classification apply classical supervised learning, which requires intensive manual annotation for training. In this paper, we propose CDS (Collaborative Distant Supervision), a novel learning scheme for Twitter account classification that does not require intensive manual labelling. Twitter accounts are automatically labelled using heuristics for distant supervision learning. To achieve effective learning from heuristic labels, active learning is applied to identify and correct false positive labels, and semi-supervised learning is applied to further use false negatives missed by labelling heuristics for learning. Extensive experiments on Twitter data showed that CDS achieved high classification accuracy. [ABSTRACT FROM AUTHOR]

The ever increasing size of graphs makes them difficult to query and store. In this paper, we present Shrink , a compression method that reduces the size of the graph while preserving the distances between the nodes. The compression is based on the iterative merging of the nodes. During each merging, a system of linear equations is solved to define new edge weights in a way that the new weights have the least effect on the distances. Merging nodes continues until the desired size for the compressed graph is reached. The compressed graph, also known as the coarse graph, can be queried without decompression. As the complexity of distance-based queries such as shortest path queries is highly dependent on the size of the graph, Shrink improves the performance in terms of time and storage. Shrink not only provides the length of the shortest path but also identifies the nodes on the path. The approach has been applied to both weighted and unweighted graphs including road network, friendship network, collaboration network, web graph and social network. In the experiment, a road network with more than 2.5 million nodes is reduced to fifth while the average relative error is less than 1%. [ABSTRACT FROM AUTHOR]

Finding an expert plays a crucial role in driving successful collaborations and speeding up high-quality research development and innovations. However, the rapid growth of scientific publications and digital data makes identifying the right experts a challenging problem. Existing approaches for finding experts given a topic can be categorised into information retrieval techniques such as vector space models, document language models, and graph-based models. In this paper, we propose ExpFinder , a new hybrid model for expert finding, that integrates a novel N -gram vector space model, denoted as n VSM, and a graph-based model, denoted as μ CO-HITS , that is a proposed variation of the CO-HITS algorithm. The key of n VSM is to exploit recent inverse document frequency weighting method for N -gram words, and ExpFinder incorporates n VSM into μ CO-HITS to achieve expert finding. We comprehensively evaluate ExpFinder on four different datasets from the academic domains in comparison with six different expert finding models. The evaluation results show that ExpFinder is an highly effective model for expert finding, substantially outperforming all the compared models in 19% to 160.2%. • We propose a hybrid model, ExpFinder, for expert finding from expertise text data. • ExpFinder integrates a novel n-gram vector space model and an extension of CO-HITS. • ExpFinder achieves a very high performance over 6 competitive models on 4 datasets. [ABSTRACT FROM AUTHOR]

Influential community search (ICS) on a graph finds a closely connected group of vertices having a dominance over other groups of vertices. The ICS has many applications in recommendations, event organization, and so on. In this paper, we introduce a new variant of ICS, namely keyword-aware influential community query (KICQ), that finds the communities with the highest influential scores and whose keywords match with the query terms (a set of keywords) and predicates (AND or OR). It is challenging to find such communities from a large network as the traditional pre-computation approach is not applicable with the change of query terms at every instance of the search. To solve this problem, we design two efficient algorithms: (i) a branch-and-bound approach that exploits the bounds computed from already explored communities to prune the search space, and (ii) a novel index based approach that hierarchically organizes sub-communities and keywords with associated bounds to quickly identify the desired communities. We propose a new influence measure for a community that considers both the cohesiveness and influence of the community and eliminates the need for specifying values of internal parameters of a network. We present detailed experiments and a case study to demonstrate the effectiveness and efficiency of the proposed approaches. • The query considers user preference (as keywords) for influential community search. • Considering the semantics of the keywords adds flexibility for the users. • The proposed influence measure eliminates the need for internal parameters as input. • A novel index is proposed to efficiently retrieve the most influential communities. • The datasets are shared publicly to help future works in this direction. [ABSTRACT FROM AUTHOR]

Abstract: Optimizing queries using materialized views has not been addressed adequately in the context of XML due to the many limitations associated with the definition and usability of materialized views in traditional XML query evaluation models. In this paper, we address the XML query optimization problem using materialized views in the framework of the inverted lists evaluation model which has been established as the most prominent one for evaluating queries on large persistent XML data. Under this framework, we propose a novel approach which instead of materializing the answer of a view materializes exactly the sublists of the inverted lists that are necessary for computing the answer of the view. A further originality of our approach is that the view materializations are stored as compressed bitmaps. This technique not only minimizes the materialization space but also reduces CPU and I/O costs by translating view materialization processing into bitwise operations. Our approach departs from the traditional approach which identifies a compensating expression that rewrites the query using the materialized views. Instead, it computes the query answer by executing holistic stack-based algorithms on the view materializations. We experimentally compared our approach with recent outstanding structural summary and B-tree based approaches. In order to make the comparison more competitive we also proposed an extension of a structural index approach to resolve combinatorial explosion problems. Our experimental results show that our compressed bitmapped materialized views approach is the most efficient, robust, and stable one for optimizing XML queries. It obtains significant performance savings at a very small space overhead and has negligible optimization time even for a large number of materialized views in the view pool. [Copyright &y& Elsevier]

Abstract: The processing and management of XML data are popular research issues. However, operations based on the structure of XML data have not received strong attention. These operations involve, among others, the grouping of structurally similar XML documents. Such grouping results from the application of clustering methods with distances that estimate the similarity between tree structures. This paper presents a framework for clustering XML documents by structure. Modeling the XML documents as rooted ordered labeled trees, we study the usage of structural distance metrics in hierarchical clustering algorithms to detect groups of structurally similar XML documents. We suggest the usage of structural summaries for trees to improve the performance of the distance calculation and at the same time to maintain or even improve its quality. Our approach is tested using a prototype testbed. [Copyright &y& Elsevier]

To meet the requirement of social influence analytics in various applications, the problem of influence maximization has been studied in recent years. The aim is to find a limited number of nodes (i.e., users) which can activate (i.e. influence) the maximum number of nodes in social networks. However, the community diversity of influenced users is largely ignored even though it has unique value in practice. For example, the higher community diversity reduces the risk of marketing campaigns as you should not put all your eggs in one basket; the diversity can also prolong the effect of a marketing campaign in the future promotion. Motivated by this observation, this paper investigates Community-diversified Influence Maximization (CDIM) problem to efficiently find k nodes such that, if a message is initiated and spread by the k nodes, the number as well as the community diversity of the activated nodes will be maximized at the end of propagation process. This work proposes a metric to measure the community-diversified influence and addresses a series of computational challenges. Two algorithms and an innovative CPSP-Tree index have been developed. This study also investigates the situation that community definition is not specified. The effectiveness and efficiency of the proposed solutions have been verified through extensive experimental studies on five real-world social network datasets. • A new problem, named community-diversified influence maximization (CDIM), is introduced in this paper. • A deliberately designed metric has been proposed in this paper to evaluate the CDIM. • Two algorithms (greedy and upper bound) are developed in this paper to solve the CDIM problem effectively. [ABSTRACT FROM AUTHOR]