Search

Influence maximization is a recent but well-studied problem which helps identify a small set of users that are most likely to “influence” the maximum number of users in a social network. The problem has attracted a lot of attention as it provides a way to improve marketing, branding, and product adoption. However, existing studies rarely consider the physical locations of the users, but location is an important factor in targeted marketing. In this paper, we propose and investigate the problem of influence maximization in location-aware social networks, or, more generally, Geo-social Influence Spanning Maximization. Given a query $q$ composed of a region $R$ , a regional acceptance rate $\rho$ , and an integer $k$ as a seed selection budget, our aim is to find the maximum geographic spanning regions (MGSR). We refer to this as the MGSR problem. Our approach differs from previous work as we focus more on identifying the maximum spanning geographical regions within a region $R$ , rather than just the number of activated users in the given network like the traditional influence maximization problem  [14] . Our research approach can be effectively used for online marketing campaigns that depend on the physical location of social users. To address the MGSR problem, we first prove NP-Hardness. Next, we present a greedy algorithm with a $1-1/e$ approximation ratio to solve the problem, and further improve the efficiency by developing an upper bounded pruning approach. Then, we propose the OIR -Tree index, which is a hybrid index combining ordered influential node lists with an R -tree. We show that our index based approach is significantly more efficient than the greedy algorithm and the upper bounded pruning algorithm, especially when $k$ is large. Finally, we evaluate the performance for all of the proposed approaches using three real datasets. [ABSTRACT FROM AUTHOR]

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]

Presents analytical models that estimate the cost in terms of node and disk access of selection and join queries using R-tree-based structures. Importance of access methods and spatial query cost models for spatial query processing and estimation; Use of selection and join queries as fundamental operations in Data Base Management Systems.

In this paper we study database query languages and their use for programming nontraditional applications, such as engineering and artificial intelligence applications. In such environments, database programs are used to code applications that work over large data sets it- siding in databases. Optimizing such programs then becomes a necessity. We look at various optimization techniques and suggest transformations to be used for Improving the performance of database programs. These transformations result in new equivalent database programs with better space and lime performance. Several of these techniques apply to classical query languages, although the primary focus of this paper is on extended query languages which include an iteration operator. [ABSTRACT FROM AUTHOR]

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]

In this paper, we present HomeSeeker, an interactive visual analytics system to serve users with different backgrounds of the local real estate market and meet different degrees of user requirements. As a result, HomeSeeker augments existing commercial systems to help users discover hidden patterns, link various location-centered data to the price, as well as explore, filter and compare the properties, in order to easily find their preferred properties. In particular, we make the following contributions: (1) We present a problem abstraction for designing visualizations that help home buyers analyse the real estate data. Specifically, our data abstraction integrates heterogeneous data from different channels into a location-centred integrated real estate dataset. (2) We propose an interactive visual analytic procedure to help less informed users gradually learn about the local real estate market, upon which users exploit this learned knowledge to specify their individual requirements in property seeking. (3) We propose a series of designs to visualize properties/suburbs in different dimensions and in different granularities. We have collected, integrated and cleaned last 10 year’s real estate sold records in Australia as well as their location-related education, facility and transportation profiles, to generate a real multi-dimensional data repository, and implemented a system prototype for public access ( http://115.146.89.158 ). At last, we present case studies based on real-world datasets and real scenario to demonstrate the usefulness and effectiveness of our system. [ABSTRACT FROM AUTHOR]

Event popularity prediction over social media is crucial for estimating information propagation scope, decision making, and emergency prevention. However, existing approaches only focus on predicting the occurrences of single attribute such as a message, a hashtag or an image, which are not comprehensive enough for representing complex social event propagation. In this paper, we predict the event popularity, where an event is described as a set of messages containing multiple hashtags. We propose a novel hashtag-influence-based event popularity prediction by mining the impact of an influential hashtag set on the event propagation. Specifically, we first propose a hashtag-influence-based cascade model to select the influential hashtags over an event hashtag graph built by the pairwise hashtag similarity and the topic distribution of event-related hashtags. A novel measurement is proposed to identify the hashtag influence of an event over its content and social impacts. A hashtag correlation-based algorithm is proposed to optimize the seed selection in a greedy manner. Then, we propose an event-fitting boosting model to predict the event popularity by embedding the feature importance over events into the XGBOOST model. Moreover, we propose an event-structure-based method, which incrementally updates the prediction model over social streams. We have conducted extensive experiments to prove the effectiveness and efficiency of the proposed approach. [ABSTRACT FROM AUTHOR]

Accurate house prediction is of great significance to various real estate stakeholders such as house owners, buyers, and investors. We propose a location-centered prediction framework that differs from existing work in terms of data profiling and prediction model. Regarding data profiling, we make an important observation as follows – besides the in-house features such as floor area, the location plays a critical role in house price prediction. Unfortunately, existing work either overlooked it or had a coarse grained measurement of locations. Thereby, we define and capture a fine-grained location profile powered by a diverse range of location data sources, including transportation profile, education profile, suburb profile based on census data, and facility profile. Regarding the choice of prediction model, we observe that a variety of approaches either consider the entire data for modeling, or split the entire house data and model each partition independently. However, such modeling ignores the relatedness among partitions, and for all prediction scenarios, there may not be sufficient training samples per partition for the latter approach. We address this problem by conducting a careful study of exploiting the Multi-Task Learning (MTL) model. Specifically, we map the strategies for splitting the entire house data to the ways the tasks are defined in MTL, and select specific MTL-based methods with different regularization terms to capture and exploit the relatedness among tasks. Based on real-world house transaction data collected in Melbourne, Australia, we design extensive experimental evaluations, and the results indicate a significant superiority of MTL-based methods over state-of-the-art approaches. Meanwhile, we conduct an in-depth analysis on the impact of task definitions and method selections in MTL on the prediction performance, and demonstrate that the impact of task definitions on prediction performance far exceeds that of method selections. [ABSTRACT FROM AUTHOR]

Influence maximization has recently received significant attention for scheduling online campaigns or advertisements on social network platforms. However, most studies only focus on user influence via cyber interactions while ignoring their physical interactions which are also essential to gauge influence propagation. Additionally, targeted campaigns or advertisements have not received sufficient attention. To address these issues, we first devise a novel holistic influence diffusion model that takes into account both cyber and physical user interactions in an effective and practical way. Based on the new diffusion model, we formulate a new problem of holistic influence maximization, denoted as HIM query, for targeted advertisements in a spatial social network. The HIM query problem aims to find a minimum set of users whose holistic influence can cover all target users in the network, which belongs to a set covering problem. Since the HIM query problem is NP-hard, we develop a greedy baseline algorithm and then improve on this algorithm to reduce the computational cost. To deal with large networks, we also design a spatial-social index to maintain the social, spatial and textual information of users, as well as developing an index-based efficient solution. Finally, we conduct extensive experiments using one synthetic and three real-world datasets to validate the efficiency and effectiveness of the proposed holistic influence diffusion model and our developed algorithms. [ABSTRACT FROM AUTHOR]

This work introduces decentralized query processing techniques based on MIDAS, a novel distributed multidimensional index. In particular, MIDAS implements a distributed k-d tree, where leaves correspond to peers, and internal nodes dictate message routing. MIDAS requires that peers maintain little network information, and features mechanisms that support fault tolerance and load balancing. The proposed algorithms process point and range queries over the multidimensional indexed space in only O(log n) hops in expectance, where n is the network size. For nearest neighbor queries, two processing alternatives are discussed. The first, termed eager processing, has low latency (expected value of O(log n) hops) but may involve a large number of peers. The second, termed iterative processing, has higher latency (expected value of O(log n) hops) but involves far fewer peers. A detailed experimental evaluation demonstrates that our query processing techniques outperform existing methods for settings involving real spatial data as well as in the case of high dimensional synthetic data. [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]

The peer-to-peer (P2P) paradigm has become very popular for storing and sharing information in a totally decentralized manner. At first, research focused on P2P systems that host 1 D data. Nowadays, the need for P2P applications with multidimensional data has emerged, motivating research on P2P systems that manage such data. The majority of the proposed techniques are based either on the distribution of centralized indexes or on the reduction of multidimensional data to one dimension. Our goal is to create from scratch a technique that is inherently distributed and also maintains the multidimensionality of data. Our focus is on structured P2P systems that share spatial information. We present SPATIALP2P, a totally decentralized indexing and searching framework that is suitable for spatial data. SPATIALP2P supports P2P applications in which spatial information of various sizes can be dynamically inserted or deleted, and peers can join or leave. The proposed technique preserves well locality and directionality of space. [ABSTRACT FROM AUTHOR]

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]

In this paper, we introduce a family of expressive models for qualitative spatial reasoning with directions. The proposed family is based on the cognitive plausible cone-based model. We formally define the directional relations that can be expressed in each model of the family. Then, we use our formal framework to study two interesting problems: computing the inverse of a directional relation and composing two directional relations. For the composition operator, in particular, we concentrate on two commonly used definitions, namely, consistency-based and existential composition. Our formal framework allows us to prove that our solutions are correct. The presented solutions are handled in a uniform manner and apply to all of the models of the family. [ABSTRACT FROM AUTHOR]

Extraction-Transformation-Loading (ETL) tools are pieces of software responsible for the extraction of data from several sources, their cleansing, customization, and insertion into a data warehouse. In this paper, we delve into the logical optimization of ETL processes, modeling it as a state-space search problem. We consider each ETL workflow as a state and fabricate the state space through a set of correct state transitions. Moreover, we provide an exhaustive and two heuristic algorithms toward the minimization of the execution cost of an ETL workflow. The heuristic algorithm with greedy characteristics significantly outperforms the other two algorithms for a large set of experimental cases. [ABSTRACT FROM AUTHOR]

It has been recently recognized that fuzzy set theory provides useful concepts and tools for both the representation and analysis of the uncertainty related to geographical data. Hence the incorporation of fuzzy set methodologies into a DBMS repository for the application domain of GIS should be beneficial and will improve its level of intelligence. Focusing in this area the paper addresses both a representation and a reasoning issue. Specifically, it extends a general spatial data model to deal with the uncertainty of geographical entities, and shows how the standard data interpretation operations available in GIS packages may be extended to support the fuzzy spatial reasoning. Representative geographical operations, suchas the fuzzy overlay, fuzzy distance and fuzzy select, are examined, while several real world examples are given. [ABSTRACT FROM AUTHOR]

Commercially available database systems do not meet the information and processing needs of design and manufacturing environments. A new generation of systems-engineering Information systems-must be built to meet these needs. In this paper, we address the architectural and computational aspects of such systems and propose solutions. We argue that a mainframe-workstation architecture is needed to provide distributed functionality while ensuring high availability and low communication overhead, that explicit control of meta-knowledge is needed to support extendibility and evolution, that large rule bases are needed to make the knowledge of the systems active, and that incremental computation models are needed to achieve the required performance of such engineering information systems. [ABSTRACT FROM AUTHOR]

Pictorial databases require efficient and direct spatial search based on the analog form of spatial objects and relationships instead of search based on some cumbersome alphanumeric encodings of the pictures. This paper briefly describes PSQL, a query language which allows pictorial domains to be presented to the user in their analog form and allows him to do direct manipulation on the objects found on those domains. Direct spatial search and computation on the pictures is done using efficient data structures, R- and R+-trees (multi-dimensional B-trees), which are excellent devices for searching spatial objects and relationships found on pictures. [ABSTRACT FROM AUTHOR]

An introduction is presented in which the guest editors discuss articles in the issue on topics including passive and partially active (PPA) fault tolerance, smart drill-down for data exploration, and core graph decomposition.

• 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]

The widespread availability of GPS and the growing popularity of location based social networking applications such as Flickr, Yelp, etc., enable more and more users to share their route activities or trajectories. At the same time, the recent advancement in large-scale 3D modeling has inspired applications that combine visibility and spatial queries, which in turn can be integrated with user trajectories to provide answers for many real-life user queries, such as "How can I choose the route which provides the best view of a historic site?". In this work, we propose and investigate the k Aggregate Maximum Visibility Trajectory (k AMVT) query and its variants. Given sets of targets, obstacles, and trajectories, the k AMVT query finds top-k trajectories that provide the best view of the targets. We extend the k AMVT query to incorporate different weights (or preferences) with trajectories and targets. To provide an efficient solution to our problem, we employ obstacle and trajectory pruning mechanisms. We also employ an effective target ordering technique, which can further improve query efficiency. Furthermore, we extend the proposed queries to introduce preferences on trajectories in situations where smaller trajectories are preferred due to time constraints, or trajectories closer to the query user are preferred. To verify the efficiency and effectiveness of our solutions, we conduct an extensive experimental study using large synthetic and real datasets. [ABSTRACT FROM AUTHOR]

The urban road networks undergo frequent traffic congestions during the peak hours and around the city center. Capturing the spatiotemporal evolution of the congestion scenario in real-time in an urban-scale can aid in developing smart traffic management systems, and guiding commuters in making informed decision about route choice. The congestion scenario is often represented by a set of distinguishable network partitions that have a homogeneous level of congestion inside them but are heterogeneous to others. Due to the dynamic nature of traffic, these partitions evolve with time in terms of their structure and location. In this paper, we propose a comprehensive framework to capture the evolution by incrementally updating the partitions in an efficient manner using a two-layer approach. The physical layer maintains a set of small-sized road network building blocks in a fine granularity, and performs low-level computations to incrementally update them, whereas the logical layer performs high-level computations in order to serve as an interface to query the physical layer about the congested partitions in a coarse granularity. We also propose an in-memory index called Bin that compactly stores the historical sets of building blocks in the main memory with no information loss, and facilitates their efficient retrieval. Our experimental results show that the proposed method is much efficient than the existing re-partitioning methods without significant sacrifice in accuracy. The proposed Bin consumes a minimum space with least redundancy at different time stamps. [ABSTRACT FROM AUTHOR]

GPS enables mobile devices to continuously provide new opportunities to improve our daily lives. For example, the data collected in applications created by Uber or Public Transport Authorities can be used to plan transportation routes, estimate capacities, and proactively identify low coverage areas. In this paper, we study a new kind of query—Reverse k Nearest Neighbor Search over Trajectories (\mathbf{R}{k}\mathbf{NNT} ), which can be used for route planning and capacity estimation. Given a set of existing routes \mathcal{D}_{\mathcal{R}} , a set of passenger transitions \mathcalD\mathcal{T} , and a query route Q , an \mathbfRk\mathbfNNT  query returns all transitions that take Q as one of its k nearest travel routes. To solve the problem, we first develop an index to handle dynamic trajectory updates, so that the most up-to-date transition data are available for answering an \mathbfRk\mathbfNNT query. Then we introduce a filter refinement framework for processing \mathbfRk\mathbfNNT queries using the proposed indexes. Next, we show how to use \mathbfRk\mathbfNNT to solve the optimal route planning problem \mathbfMaxRk\mathbfNNT ( \mathbfMinRk\mathbfNNT ), which is to search for the optimal route from a start location to an end location that could attract the maximum (or minimum) number of passengers based on a predefined travel distance threshold. Experiments on real datasets demonstrate the efficiency and scalability of our approaches. To the best of our knowledge, this is the first work to study the \mathbfRk\mathbfNNT problem for route planning. [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]

Social networks are a vital mechanism to disseminate information to friends and colleagues. In this work, we investigate an important problem—the personalized influential topic search, or PIT-Search in a social network: Given a keyword query $q$ issued by a user $u$ in a social network, a PIT-Search is to find the top-$k$ $q$-related topics that are most influential for the query user $u$. The influence of a topic to a query user depends on the social connection between the query user and the social users containing the topic in the social network. To measure the topics’ influence at the similar granularity scale, we need to extract the social summarization of the social network regarding topics. To make effective topic-aware social summarization, we propose two random-walk based approaches: random clustering and an L-length random walk. Based on the proposed approaches, we can find a small set of representative users with assigned influential scores to simulate the influence of the large number of topic users in the social network with regards to the topic. The selected representative users are denoted as the social summarization of topic-aware influence spread over the social network. And then, we verify the usefulness of the social summarization by applying it to the problem of personalized influential topic search. Finally, we evaluate the performance of our algorithms using real-world datasets, and show the approach is efficient and effective in practice. [ABSTRACT FROM PUBLISHER]

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]

XML query languages typically allow the specification of structural patterns using XPath. Usually, these structural patterns are in the form of trees (Tree-Pattern Queries—TPQs). Finding the occurrences of such patterns in an XML tree is a key operation in XML query evaluation. The multiple previous algorithms presented for this operation focus mainly on the evaluation of tree-pattern queries. Recently, requirements for flexible querying of XML data have motivated the consideration of query classes that are more expressive and flexible than TPQs for which efficient nonmain-memory evaluation algorithms are not known. In this paper, we consider a class of queries, called Partial Tree-Pattern Queries (PTPQs), which generalize and strictly contain TPQs. PTPQs represent a broad fragment of XPath which is very useful in practice. In order to process PTPQs, we introduce a set of sound and complete inference rules to characterize structural relationship derivation. We provide necessary and sufficient conditions for detecting query unsatisfiability and node redundancy. We also show that PTPQs can be represented as directed acyclic graphs augmented with the “same-path” constraints. In order to leverage existing efficient evaluation algorithms for less expressive classes of queries, we design two approaches that evaluate a PTPQ by decomposing it into a set of simpler queries: algorithm IndexTPQGen, exploits a structural summary of the XML data and evaluates a PTPQ by generating an equivalent set of TPQs and unioning their answers. Algorithm PartialPathJoin decomposes the PTPQ into partial-path queries, and merge-joins their solutions. We also develop PartialTreeStack, an original polynomial time holistic algorithm for PTPQs. To the best of our knowledge, this is the first algorithm to support the evaluation of such a broad structural fragment of XPath in the inverted lists evaluation model. We provide a theoretical analysis of our algorithm and identify cases where it is asymptotically optimal. An extensive experimental evaluation shows that it is more efficient, robust, and stable than the other two and it outperforms a state-of-the art XQuery engine on PTPQs. [ABSTRACT FROM PUBLISHER]

A correction to the article "A Family of Directional Relation Models for Extended Objects" that was published in the August 2007 issue is presented.

Finding the occurrences of structural patterns in XML data is a key operation in XML query processing. Existing algorithms for this operation focus almost exclusively on path patterns or tree patterns. Current applications of XML require querying of data whose structure is complex or is not fully known to the user, or integrating XML data sources with different structures. These applications have motivated recently the introduction of query languages that allow a partial specification of path patterns in a query. In this paper, we consider partial path queries, a generalization of path pattern queries, and we focus on their efficient evaluation under the indexed streaming evaluation model. Our approach explicitly deals with repeated labels (that is, multiple occurrences of the same label in a query). We show that partial path queries can be represented as rooted dags for which a topological ordering of the nodes exists. We present three algorithms for the efficient evaluation of these queries. The first one exploits a structural summary of data to generate a set of path patterns that together are equivalent to a partial path query. To evaluate these path patterns, we extend a previous algorithm for path-pattern queries so that it can work on path patterns with repeated labels. The second one extracts a spanning tree from the query dag, uses a stack-based algorithm to find the matches of the root-to-leaf paths in the tree, and merge-joins the matches to compute the answer. Finally, the third one exploits multiple pointers of stack entries and a topological ordering of the query dag to apply a stack-based holistic technique. We analyze our algorithms and perform extensive experimental evaluations. Our experimental results show that the holistic algorithm outperforms the other ones. Our approaches are the first ones to efficiently evaluate this class of queries in the indexed streaming model. [ABSTRACT FROM AUTHOR]

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]

Qualitative spatial reasoning forms an important part of the commonsense reasoning required for building intelligent Geographical Information Systems (GIS). Previous research has come up with models to capture cardinal direction relations for typical GIS data. In this paper, we target the problem of efficiently computing the cardinal direction relations between regions that are composed of sets of polygons and present two algorithms for this task. The first of the proposed algorithms is purely qualitative and computes, in linear time, the cardinal direction relations between the input regions. The second has a quantitative aspect and computes, also in linear time, the cardinal direction relations with percentages between the input regions. Our experimental evaluation indicates that the proposed algorithms outperform existing methodologies. The algorithms have been implemented and embedded in an actual system, CARDIRECT, that allows the user to 1) specify and annotate regions of interest in an image or a map, 2) compute cardinal direction relations between them, and 3) pose queries in order to retrieve combinations of interesting regions. [ABSTRACT FROM AUTHOR]

Identifying, amongst millions of publications available in MEDLINE, those that are relevant to specific microRNAs (miRNAs) of interest based on keyword search faces major obstacles. References to miRNA names in the literature often deviate from standard nomenclature for various reasons, since even the official nomenclature evolves. For instance, a single miRNA name may identify two completely different molecules or two different names may refer to the same molecule. mirPub is a database with a powerful and intuitive interface, which facilitates searching for miRNA literature, addressing the aforementioned issues. To provide effective search services, mirPub applies text mining techniques on MEDLINE, integrates data from several curated databases and exploits data from its user community following a crowdsourcing approach. Other key features include an interactive visualization service that illustrates intuitively the evolution of miRNA data, tag clouds summarizing the relevance of publications to particular diseases, cell types or tissues and access to TarBase 6.0 data to oversee genes related to miRNA publications. [ABSTRACT FROM AUTHOR]

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]