Multimodal Large Language Models (MLLMs) have exhibited remarkable advancements in integrating different modalities, excelling in complex understanding and generation tasks. Despite their success, MLLMs remain vulnerable to conversational adversarial inputs. In this paper, we systematically study gaslighting negation attacks—a phenomenon where models, despite initially providing correct answers, are persuaded by user-provided negations to reverse their outputs, often fabricating justifications. We conduct extensive evaluations of state-of-the-art MLLMs across diverse benchmarks and observe substantial performance drops when negation is introduced. Notably, we introduce the first benchmark GaslightingBench, specifically designed to evaluate the vulnerability of MLLMs to negation arguments. GaslightingBench consists of multiple-choice questions curated from existing datasets, along with generated negation prompts across 20 diverse categories. Throughout extensive evaluation, we find that proprietary models such as Gemini-1.5-flash and GPT-4o demonstrate better resilience compared to open-source counterparts like Qwen2-VL and LLaVA, though even advanced reasoning-oriented models like Gemini-2.5-Pro remain susceptible. Our category-level analysis further shows that subjective or socially nuanced domains (e.g., Social Relation, Image Emotion) are especially fragile, while more objective domains (e.g., Geography) exhibit relatively smaller but still notable drops. Overall, all evaluated MLLMs struggle to maintain logical consistency under gaslighting negation attack. These findings highlight a fundamental robustness gap and provide insights for developing more reliable and trustworthy multimodal AI systems. Project website: https://yxg1005.github.io/GaslightingNegationAttacks.

Nutrition estimation is an important component of promoting healthy eating and mitigating diet-related health risks. Despite advances in tasks such as food classification and ingredient recognition, progress in nutrition estimation is limited due to the lack of datasets with nutritional annotations. To address this issue, we introduce FastFood, a dataset with 84,446 images across 908 fast food categories, featuring ingredient and nutritional annotations. In addition, we propose a new model-agnostic Visual-Ingredient Feature Fusion (VIF2) method to enhance nutrition estimation by integrating visual and ingredient features. Ingredient robustness is improved through synonym replacement and resampling strategies during training. The ingredient-aware visual feature fusion module combines ingredient features and visual representation to achieve accurate nutritional prediction. During testing, ingredient predictions are refined using large multimodal models by data augmentation and majority voting. Our experiments on both FastFood and Nutrition5k datasets validate the effectiveness of our proposed method built in different backbones (e.g., Resnet, InceptionV3 and ViT), which demonstrates the importance of ingredient information in nutrition estimation.

In today's competitive and fast-evolving business environment, it is a critical time for organizations to rethink how to deal with talent and management-related tasks in a quantitative manner. Indeed, thanks to the era of big data, the availability of large-scale talent data provides unparalleled opportunities for business leaders to understand the rules of talent and management, which in turn deliver intelligence for effective decision-making and management for their organizations. In the past few years, talent and management computing have increasingly attracted attention from KDD communities, and a number of research/applied data science efforts have been devoted. To this end, the purpose of this workshop, i.e., the 5th International Workshop on Talent and Management Computing (TMC'2024), is to bring together researchers and practitioners to discuss both the critical problems faced by talent and management-related domains and potential data-driven solutions by leveraging state-of-the-art data mining technologies.

Many deep learning works on financial time-series forecasting focus on predicting future prices/returns of individual assets with numerical price-related information for trading, and hence propose models designed for univariate, single-task, and/or unimodal settings. Forecasting for investment and risk management involves multiple tasks in multivariate settings: forecasts of expected returns and risks of assets in portfolios, and correlations between these assets. As different sources/types of time-series influence future returns, risks, and correlations of assets in different ways, it is also important to capture time-series from different modalities. Hence, this article addresses financial time-series forecasting for investment and risk management in a multivariate, multitask, and multimodal setting. Financial time-series forecasting, however, is challenging due to the low signal-to-noise ratios typical in financial time-series, and as intra-series and inter-series relationships of assets evolve across time. To address these challenges, our proposed Temporal Implicit Multimodal Network (TIME) model learns implicit inter-series relationship networks between assets from multimodal financial time-series at multiple time-steps adaptively. TIME then uses dynamic network and temporal encoding modules to jointly capture such evolving relationships, multimodal financial time-series, and temporal representations. Our experiments show that TIME outperforms other state-of-the-art models on multiple forecasting tasks and investment and risk management applications.

Dynamic multimodal networks are networks with node attributes from different modalities where the attributes and network relationships evolve across time, i.e., both networks and multimodal attributes are dynamic; for example, dynamic relationship networks between companies that evolve across time due to changes in business strategies and alliances, which are associated with dynamic company attributes from multiple modalities such as textual online news, categorical events, and numerical financial-related data. Such information can be useful in predictive tasks involving companies. Environmental, social, and governance (ESG) ratings of companies are important for assessing the sustainability risks of companies. The process of generating ESG ratings by expert analysts is, however, laborious and time-intensive. We thus explore the use of dynamic multimodal networks extracted from the web for forecasting ESG ratings. Learning such dynamic multimodal networks from the web for forecasting ESG ratings is, however, challenging due to its heterogeneity and the low signal-to-noise ratios and non-stationary distributions of web information. Human analysts cope with such issues by learning concepts from past experience through relational thinking and scanning for such concepts when analyzing new information about a company. In this article, we propose the Dynamic Multimodal Slot Concept Attention-based Network (DynScan) model. DynScan utilizes slot attention mechanisms together with slot concept alignment and disentanglement loss functions to learn latent slot concepts from dynamic multimodal networks to improve performance on ESG rating forecasting tasks. DynScan is evaluated on forecasting tasks on six datasets, comprising three ESG ratings across two sets of companies. Our experiments show that DynScan outperforms other state-of-the-art models on these forecasting tasks. We also visualize the slot concepts learned by DynScan on five synthetic datasets and three real-world datasets and observe distinct and meaningful slot concepts being learned by DynScan across both synthetic and real-world datasets.

In today's competitive and fast-evolving business environment, it is a critical time for organizations to rethink how to deal with the talent and management related tasks in a quantitative manner. Indeed, thanks to the era of big data, the availability of large-scale talent data provides unparalleled opportunities for business leaders to understand the rules of talent and management, which in turn deliver intelligence for effective decision making and management for their organizations. In the past few years, talent and management computing have increasingly attracted attentions from KDD communities, and a number of research/applied data science efforts have been devoted. To this end, the purpose of this workshop, i.e., the 4th International Workshop on Talent and Management Computing (TMC'2023), is to bring together researchers and practitioners to discuss both the critical problems faced by talent and management related domains, and potential data-driven solutions by leveraging state-of-the-art data mining technologies.

Contextual path retrieval (CPR) refers to the task of finding contextual path(s) between a pair of entities in a knowledge graph that explains the connection between them in a given context. For this novel retrieval task, we propose the Embedding-based Contextual Path Retrieval (ECPR) framework. ECPR is based on a three-component structure that includes a context encoder and path encoder that encode query context and path, respectively, and a path ranker that assigns a ranking score to each candidate path to determine the one that should be the contextual path. For context encoding, we propose two novel context encoding methods, i.e., context-fused entity embeddings and contextualized embeddings. For path encoding, we propose PathVAE, an inductive embedding approach to generate path representations. Finally, we explore two path-ranking approaches. In our evaluation, we construct a synthetic dataset from Wikipedia and two real datasets of Wikinews articles constructed through crowdsourcing. Our experiments show that methods based on ECPR framework outperform baseline methods, and that our two proposed context encoders yield significantly better performance than baselines. We also analyze a few case studies to show the distinct features of ECPR-based methods.

Stock price movements in financial markets are influenced by large volumes of news from diverse sources on the web, e.g., online news outlets, blogs, social media. Extracting useful information from online news for financial tasks, e.g., forecasting stock returns or risks, is, however, challenging due to the low signal-to-noise ratios of such online information. Assessing the relevance of each news article to the price movements of individual stocks is also difficult, even for human experts. In this article, we propose the Guided Global-Local Attention-based Multimodal Heterogeneous Network (GLAM) model, which comprises novel attention-based mechanisms for multimodal sequential and graph encoding, a guided learning strategy, and a multitask training objective. GLAM uses multimodal information, heterogeneous relationships between companies and leverages significant local responses of individual stock prices to online news to extract useful information from diverse global online news relevant to individual stocks for multiple forecasting tasks. Our extensive experiments with multiple datasets show that GLAM outperforms other state-of-the-art models on multiple forecasting tasks and investment and risk management application case-studies.

Many financial forecasting deep learning works focus on the single task of predicting stock returns for trading with unimodal numerical inputs. Investment and risk management however involves multiple financial t asks - forecasts of expected returns, risks and correlations of multiple stocks in portfolios, as well as important events affecting different stocks - to support decision making. Moreover, stock returns are influenced by large volumes of non-stationary time-series information from a variety of modalities and the propagation of such information across inter-company relationship networks. Such networks could be explicit - observed co-occurrences in online news; or implicit -inferred from time-series information. Such networks are often dynamic, i.e. they evolve across time. Therefore, we propose the Dynamic Multimodal Multitask Implicit Explicit (DynMIX) network model, which pairs explicit and implicit networks across multiple modalities for a novel dynamic self-supervised learning approach to improve performance across multiple financial tasks. Our experiments show that DynMIX outperforms other state-of-the-art models on multiple forecasting tasks, and investment and risk management applications.

Recently, contrastive learning has been applied to the sequential recommendation task to address data sparsity caused by users with few item interactions and items with few user adoptions. Nevertheless, the existing contrastive learning-based methods fail to ensure that the positive (or negative) sequence obtained by some random augmentation (or sequence sampling) on a given anchor user sequence remains to be semantically similar (or different). When the positive and negative sequences turn out to be false positive and false negative respectively, it may lead to degraded recommendation performance. In this work, we address the above problem by proposing Explanation Guided Augmentations (EGA) and Explanation Guided Contrastive Learning for Sequential Recommendation (EC4SRec) model framework. The key idea behind EGA is to utilize explanation method(s) to determine items' importance in a user sequence and derive the positive and negative sequences accordingly. EC4SRec then combines both self-supervised and supervised contrastive learning over the positive and negative sequences generated by EGA operations to improve sequence representation learning for more accurate recommendation results. Extensive experiments on four real-world benchmark datasets demonstrate that EC4SRec outperforms the state-of-the-art sequential recommendation methods and two recent contrastive learning-based sequential recommendation methods, CL4SRec and DuoRec. Our experiments also show that EC4SRec can be easily adapted for different sequence encoder backbones (e.g., GRU4Rec and Caser), and improve their recommendation performance.

Recommender systems learn from historical user-item interactions to identify preferred items for target users. These observed interactions are usually unbalanced following a long-tailed distribution. Such long-tailed data lead to popularity bias to recommend popular but not personalized items to users. We present a gradient perspective to understand two negative impacts of popularity bias in recommendation model optimization: (i) the gradient direction of popular item embeddings is closer to that of positive interactions, and (ii) the magnitude of positive gradient for popular items are much greater than that of unpopular items. To address these issues, we propose a simple yet efficient framework to mitigate popularity bias from a gradient perspective. Specifically, we first normalize each user embedding and record accumulated gradients of users and items via popularity bias measures in model training. To address the popularity bias issues, we develop a gradient-based embedding adjustment approach used in model testing. This strategy is generic, model-agnostic, and can be seamlessly integrated into most existing recommender systems. Our extensive experiments on two classic recommendation models and four real-world datasets demonstrate the effectiveness of our method over state-of-the-art debiasing baselines.

Finding influential users in online social networks (OSNs) is an important problem with many possible useful applications. Many methods have been proposed to identify influential users in OSNs. PageRank and HITs are two well known examples that determine influential users through link analysis. In recent years, new models that consider both content and social network links have been developed. The Hub and Authority Topic (HAT) model is one that extends HITS to identify topic-specific hubs and authorities by jointly learning hubs, authorities, and topical interests from users' relationship and textual content. However, many of the previous works are confined to identifying influential users within a single OSN. These models, when applied to multiple OSNs, could not learn influential users under a common set of topics nor address platform preferences. In this paper, we therefore propose the MPHAT model, an extension of HAT, to jointly model the topic-specific hub users, authority users, their topical interests and platform preferences. We evaluate MPHAT against several existing state-of-the-art methods in three tasks: (i) modeling of topics, (ii) platform choice prediction, and (iii) link recommendation. Based on our extensive experiments in multiple OSNs settings using synthetic datasets and real-world datasets from Twitter and Instagram, we show that MPHAT is comparable to state-of-the-art topic models in learning topics but outperforms the state-of-the-art models in platform prediction and link recommendation tasks. We also empirically demonstrate the ability of MPHAT to determine influential users within and across multiple OSNs.

Textual data is common and informative auxiliary information for recommender systems. Most prior art utilizes text for rating prediction, but rare work connects it to top-recommendation. Moreover, although advanced recommendation models capable of incorporating auxiliary information have been developed, none of these are specifically designed to model textual information, yielding a limited usage scenario for typical user-to-item recommendation. In this work, we present a framework of text-aware preference ranking (TPR) for top- recommendation, in which we comprehensively model the joint association of user-item interaction and relations between items and associated text. Using the TPR framework, we construct a joint likelihood function that explicitly describes two ranking structures: 1) item preference ranking (IPR) and 2) word relatedness ranking (WRR), where the former captures the item preference of each user and the latter captures the word relatedness of each item. As these two explicit structures are by nature mutually dependent, we propose TPR-OPT, a simple yet effective learning criterion that additionally includes implicit structures, such as relatedness between items and relatedness between words for each user for model optimization. Such a design not only successfully describes the joint association among users, words, and text comprehensively but also naturally yields powerful representations that are suitable for a range of recommendation tasks, including user-to-item, item-to-item, and user-to-word recommendation, as well as item-to-word reconstruction. In this paper, extensive experiments have been conducted on eight recommendation datasets, the results of which demonstrate that by including textual information from item descriptions, the proposed TPR model consistently outperforms state-of-the-art baselines on various recommendation tasks.

We study the problem of representation learning for multiple types of entities in a co-ordered network where order relations exist among entities of the same type, and association relations exist across entities of different types. The key challenge in learning co-ordered network embedding is to preserve order relations among entities of the same type while leveraging on the general consistency in order relations between different entity types. In this paper, we propose an embedding model, CO2Vec, that addresses this challenge using mutually reinforced order dependencies. Specifically, CO2Vec explores in-direct order dependencies as supplementary evidence to enhance order representation learning across different types of entities. We conduct extensive experiments on both synthetic and real world datasets to demonstrate the robustness and effectiveness of CO2Vec against several strong baselines in link prediction task. We also design a comprehensive evaluation framework to study the performance of CO2Vec under different settings. In particular, our results show the robustness of CO2Vec with the removal of order relations from the original networks.

Personality inference has received widespread attention for its potential to infer psychological well being, job satisfaction, romantic relationship success, and professional performance. In this research, we focus on Conscientiousness, one of the well studied Big Five personality traits, which determines if a person is self-disciplined, organized, and hard-working. Research has shown that Conscientiousness is related to a person's academic and workplace success. For an expert to evaluate a person's Conscientiousness, long-term observation of the person's behavior at work place or at home is usually required. To reduce this evaluation effort as well as to cope with the increasing trend of human behavior turning digital, there is a need to conduct the evaluation using digital traces of human behavior. In this paper, we propose a novel framework, called HAPE, to automatically infer an individual's Conscientiousness scores using his/her behavioral data in an E-learning system. We first determine how users learn in the E-learning system, and design a novel Pattern Relational Graph Embedding method to learn the representations of users, their learning actions, and learning situations. The interaction between users, learning actions and situations characterizes the learning style of a user. Through experimental studies on real data, we demonstrate that HAPE framework outperforms the baseline methods in the Conscientiousness inference task.

To leverage on entity and word semantics in entity linking, embedding models have been developed to represent entities, words and their context such that candidate entities for each mention can be determined and ranked accurately using their embeddings. To leverage on entity and word semantics in entity linking, embedding models have been developed to represent entities, words and their context such that candidate entities for each mention can be determined and ranked accurately using their embeddings. In this paper, we leverage on human intelligence for embedding-based interactive entity linking. We adopt an active learning approach to select mentions for human annotation that can best improve entity linking accuracy at the same time updating the embedding model. We propose two mention selection strategies based on: (1) coherence of entities linked, and (2) contextual closeness of candidate entities with respect to mention. Our experiments show that our proposed interactive entity linking methods outperform their batch counterpart in all our experimented datasets with relatively small amount of human annotations.

The labor market refers to the market between job seekers and employers. As much of job seeking and talent hiring activities are now performed online, a large amount of job posting and application data have been collected and can be re-purposed for labor market analysis. In the labor market, both supply and demand are the key factors in determining an appropriate salary for both job applicants and employers in the market. However, it is challenging to discover the supply and demand for any labor market. In this paper, we propose a novel framework to built a labor market model using a large amount of job post and applicant data. For each labor market, the supply and demand of the labor market are constructed by using offer salaries of job posts and the response of applicants. The equilibrium salary and the equilibrium job quantity are calculated by considering the supply and demand. This labor market modeling framework is then applied to a large job repository dataset containing job post and applicant data of Singapore, a developed economy in Southeast Asia. Several issues are discussed thoroughly in the paper including developing and evaluate salary prediction models to predict missing offer salaries and estimate reserved salaries. Moreover, we propose a way to empirically evaluate of equilibrium salary of the proposed model. The constructed labor market models are then used to explain the job seeker and employer specific challenges in various market segments. We also report gender and age biases that exist in labor markets. Finally, we present a wage dashboard system that yields interesting salary insights using the model.

An important aspect of health monitoring is effective logging of food consumption. This can help management of diet-related diseases like obesity, diabetes, and even cardiovascular diseases. Moreover, food logging can help fitness enthusiasts, and people who wanting to achieve a target weight. However, food-logging is cumbersome, and requires not only taking additional effort to note down the food item consumed regularly, but also sufficient knowledge of the food item consumed (which is difficult due to the availability of a wide variety of cuisines). With increasing reliance on smart devices, we exploit the convenience offered through the use of smart phones and propose a smart-food logging system: FoodAI, which offers state-of-the-art deep-learning based image recognition capabilities. FoodAI has been developed in Singapore and is particularly focused on food items commonly consumed in Singapore. FoodAI models were trained on a corpus of 400,000 food images from 756 different classes.

Learning the dependency relations among entities and the hierarchy formed by these relations by mapping entities into some order embedding space can effectively enable several important applications, including knowledge base completion and prerequisite relations prediction. Nevertheless, it is very challenging to learn a good order embedding due to the existence of partial ordering and missing relations in the observed data. Moreover, most application scenarios do not provide non-trivial negative dependency relation instances. We therefore propose a framework that performs dependency relation prediction by exploring both rich semantic and hierarchical structure information in the data. In particular, we propose several negative sampling strategies based on graph-specific centrality properties, which supplement the positive dependency relations with appropriate negative samples to effectively learn order embeddings. This research not only addresses the needs of automatically recovering missing dependency relations, but also unravels dependencies among entities using several real-world datasets, such as course dependency hierarchy involving course prerequisite relations, job hierarchy in organizations, and paper citation hierarchy. Extensive experiments are conducted on both synthetic and real-world datasets to demonstrate the prediction accuracy as well as to gain insights using the learned order embedding.

In fine-grained tweet geolocation, tweets are linked to the specific venues (e.g., restaurants, shops) from which they were posted. This explicitly recovers the venue context that is essential for applications such as location-based advertising or user profiling. For this geolocation task, we focus on geolocating tweets that are contained in tweet sequences. In a tweet sequence, tweets are posted from some latent venue(s) by the same user and within a short time interval. This scenario arises from two observations: (1) It is quite common that users post multiple tweets in a short time and (2) most tweets are not geocoded. To more accurately geolocate a tweet, we propose a model that performs query expansion on the tweet (query) using two novel approaches. The first approach temporal query expansion considers users’ staying behavior around venues. The second approach visitation query expansion leverages on user revisiting the same or similar venues in the past. We combine both query expansion approaches via a novel fusion framework and overlay them on a Hidden Markov Model to account for sequential information. In our comprehensive experiments across multiple datasets and metrics, we show our proposed model to be more robust and accurate than other baselines.

The Linguistic Inquiry and Word Count (LIWC) tool is a psycholinguistics tool that has been widely used in both psychology and sociology research, and the LIWC scores derived from user-generated content are known to be good features for personality prediction [1], [2]. LIWC, however, is language specific as it relies on counting the percentage of predefined dictionary words occurring in the content. For content written in English Creoles which are languages based on English, the original English LIWC may not perform optimally due to its lack of words which are only used in the English Creoles. In this paper, we therefore study the learning of LIWC for an English Creole using word embeddings, a way to encode contextual meaning of words in a vector representation. We particularly focus on an English Creole known as Singlish (which is a popular English creole in Singapore and it contains words from non-English languages including Malay, Chinese, Chinese dialects, and Indian languages). Instead of a manual effort to construct LIWC for Singlish, we automate the construction of a Singlish-specific LIWC dictionary, called S-LIWC by learning a word embedding model using a large corpus of Singapore tweets, and extracting new words semantically similar to the LIWC dictionary words. We show that the S-LIWC can be used to predict LIWC summary variables. Moreover, we conduct a personality prediction experiment on Singapore university students using their Facebook status updates. Our results show that our personality prediction method using S-LIWC outperforms that using LIWC for most personality traits. We finally show some interesting case examples of explaining the weaknesses and strength of S-LIWC.

The knowledge of all occupied and unoccupied trips made by self-employed drivers are essential for optimized vehicle dispatch by ride-hailing services (e.g., Didi Dache, Uber, Lyft, Grab, etc.). However, the occupancy status of vehicles is not always known to the service operators due to adoption of multiple ride-hailing apps. In this paper, we propose a novel framework, Learning to INfer Trips (LINT), to infer occupancy of car trips by exploring characteristics of observed occupied trips. Two main research steps, stop point classification and structural segmentation, are included in LINT. In the stop point classification step, we represent a vehicle trajectory as a sequence of stop points, and assign stop points with pick-up, drop-off, and intermediate labels. The classification of vehicle trajectory stop points produces a stop point label sequence. For structural segmentation, we further propose several segmentation algorithms, including greedy segmentation (GS), efficient greedy segmentation (EGS), and dynamic programming-based segmentation (DP) to infer occupied trip from stop point label sequences. Our comprehensive experiments on real vehicle trajectories from self-employed drivers show that (1) the proposed stop point classifier predicts stop point labels with high accuracy, and (2) the proposed segmentation algorithm GS delivers the best accuracy performance with efficient running time.

As road transportation supports both economic and social activities in developed cities, it is important to maintain smooth traffic on all highways and local roads. Whenever possible, traffic congestions should be detected early and resolved quickly. While existing traffic monitoring dashboard systems have been put in place in many cities, these systems require high-cost vehicle speed monitoring instruments and detect traffic congestion as independent events. There is a lack of low-cost dashboards to inspect and analyze the lifecycle of traffic congestion which is critical in assessing the overall impact of congestion, determining the possible the source(s) of congestion and its evolution. In the absence of publicly available sophisticated road sensor data which measures on-road vehicle speed, we make use of publicly available vehicle trajectory data to detect the lifecycle of traffic congestion, also known as congestion cascade. We have developed Traffic-Cascade, a dashboard system to identify traffic congestion events, compile them into congestion cascades, and visualize them on a web dashboard. Traffic-Cascade unveils spatio-temporal insights of the congestion cascades.

User identity linkage (UIL), the problem of matching user account across multiple online social networks (OSNs), is widely studied and important to many real-world applications. Most existing UIL solutions adopt a supervised or semi-supervised approach which generally suffer from scarcity of labeled data. In this paper, we propose Factoid Embedding, a novel framework that adopts an unsupervised approach. It is designed to cope with different profile attributes, content types and network links of different OSNs. The key idea is that each piece of information about a user identity describes the real identity owner, and thus distinguishes the owner from other users. We represent such a piece of information by a factoid and model it as a triplet consisting of user identity, predicate, and an object or another user identity. By embedding these factoids, we learn the user identity latent representations and link two user identities from different OSNs if they are close to each other in the user embedding space. Our Factoid Embedding algorithm is designed such that as we learn the embedding space, each embedded factoid is "translated" into a motion in the user embedding space to bring similar user identities closer, and different user identities further apart. Extensive experiments are conducted to evaluate Factoid Embedding on two real-world OSNs data sets. The experiment results show that Factoid Embedding outperforms the state-of-the-art methods even without training data.

Finding influential users in online social networks is an important problem with many possible useful applications. HITS and other link analysis methods, in particular, have been often used to identify hub and authority users in web graphs and online social networks. These works, however, have not considered topical aspect of links in their analysis. A straightforward approach to overcome this limitation is to first apply topic models to learn the user topics before applying the HITS algorithm. In this paper, we instead propose a novel topic model known as Hub and Authority Topic (HAT) model to combines the two process so as to jointly learn the hub, authority and topical interests. We evaluate HAT against several existing state-of-the-art methods in two aspects: (i) modeling of topics, and (ii) link recommendation. We conduct experiments on two real-world datasets from Twitter and Instagram. Our experiment results show that HAT is comparable to state-of-the-art topic models in learning topics and it outperforms the state-of-the-art in link recommendation task.

Analyzing job hopping behavior is important for understanding job preference and career progression of working individuals. When analyzed at the workforce population level, job hop analysis helps to gain insights of talent flow among different jobs and organizations. Traditionally, surveys are conducted on job seekers and employers to study job hop behavior. Beyond surveys, job hop behavior can also be studied in a highly scalable and timely manner using a data-driven approach in response to fast-changing job landscape. Fortunately, the advent of online professional networks (OPNs) has made it possible to perform a large-scale analysis of talent flow. In this paper, we present a new data analytics framework to analyze the talent flow patterns of close to 1 million working professionals from three different countries/regions using their publicly accessible profiles in an established OPN. As OPN data are originally generated for professional networking applications, our proposed framework repurposes the same data for a different analytics task. Prior to performing job hop analysis, we devise a job title normalization procedure to mitigate the amount of noise in the OPN data. We then devise several metrics to measure the amount of work experience required to take up a job, to determine that the duration of a job’s existence (also known as the job age), and the correlation between the above metric and propensity of hopping. We also study how job hop behavior is related to job promotion/demotion. Lastly, we perform connectivity analysis at job and organization levels to derive insights on talent flow as well as job and organizational competitiveness.

Which venue is a tweet posted from? We call this a fine-grained geolocation problem. Given an observed tweet, the task is to infer its discrete posting venue, e.g., a specific restaurant. This recovers the venue context and differs from prior work, which geolocats tweets to location coordinates or cities/neighborhoods. First, we conduct empirical analysis to uncover venue and user characteristics for improving geolocation. For venues, we observe spatial homophily , in which venues near each other have more similar tweet content (i.e., text representations) compared to venues further apart. For users, we observe that they are spatially focused and more likely to visit venues near their previous visits. We also find that a substantial proportion of users post one or more geocoded tweet(s), thus providing their location history data. We then propose geolocation models that exploit spatial homophily and spatial focus characteristics plus posting time information. Our models rank candidate venues of test tweets such that the actual posting venue is ranked high. To better tune model parameters, we introduce a learning-to-rank framework. Our best model significantly outperforms state-of-the-art baselines. Furthermore, we show that tweets without any location-indicative words can be geolocated meaningfully as well.

The knowledge of traffic health status is essential to the general public and urban traffic management. To identify congestion cascades, an important phenomenon of traffic health, we propose a Bus Trajectory based Congestion Identification (BTCI) framework that explores the anomalous traffic health status and structure properties of congestion cascades using bus trajectory data. BTCI consists of two main steps, congested segment extraction and congestion cascades identification. The former constructs path speed models from historical vehicle transitions and design a non-parametric Kernel Density Estimation (KDE) function to derive a measure of congestion score. The latter aggregates congested segments (i.e., those with high congestion scores) into traffic congestion cascades by unifying both attribute coherence and spatio-temporal closeness of congested segments within a cascade. Extensive evaluations on 11.8 million bus trajectory data show that (1) BTCI can effectively identify congestion cascades, (2) the proposed congestion score is effective in extracting congested segments, (3) the proposed unified approach significantly outperforms alternative approaches in terms of extended precision, and (4) the identified congestion cascades are realistic, matching well with the traffic news and highly correlated with vehicle speed bands.

Which venue is a tweet posted from? We referred this as fine-grained geolocation. To solve this problem effectively, we develop novel techniques to exploit each posting user's content history. This is motivated by our finding that most users do not share their visitation history, but have ample content history from tweet posts.

In many practical contexts, networks are weighted as their links are assigned numerical weights representing relationship strengths or intensities of inter-node interaction. Moreover, the links' weight can be positive or negative, depending on the relationship or interaction between the connected nodes. The existing methods for network clustering however are not ideal for handling very large signed weighted networks. In this paper, we present a novel method called LPOCSIN (short for "Linear Programming based Overlapping Clustering on Signed Weighted Networks") for efficient mining of overlapping clusters in signed weighted networks. Different from existing methods that rely on computationally expensive cluster cohesiveness measures, LPOCSIN utilizes a simple yet effective one. Using this measure, we transform the cluster assignment problem into a series of alternating linear programs, and further propose a highly efficient procedure for solving those alternating problems. We evaluate LPOCSIN and other state-of-the-art methods by extensive experiments covering a wide range of synthetic and real networks. The experiments show that LPOCSIN significantly outperforms the other methods in recovering ground-truth clusters while being an order of magnitude faster than the most efficient state-of-the-art method.

Topic modeling has traditionally been studied for single text collections and applied to social media data represented in the form of text documents. With the emergence of many social media platforms, users find themselves using different social media for posting content and for social interaction. While many topics may be shared across social media platforms, users typically show preferences of certain social media platform(s) over others for certain topics. Such platform preferences may even be found at the individual level. To model social media topics as well as platform preferences of users, we propose a new topic model known as MultiPlatform-LDA (MultiLDA). Instead of just merging all posts from different social media platforms into a single text collection, MultiLDA keeps one text collection for each social media platform but allowing these platforms to share a common set of topics. MultiLDA further learns the user-specific platform preferences for each topic. We evaluate MultiLDA against TwitterLDA, the state-of-the-art method for social media content modeling, on two aspects: (i) the effectiveness in modeling topics across social media platforms, and (ii) the ability to predict platform choices for each post. We conduct experiments on three real-world datasets from Twitter, Instagram and Tumblr sharing a set of common users. Our experiments results show that the MultiLDA outperforms in both topic modeling and platform choice prediction tasks. We also show empirically that among the three social media platforms, "Daily matters" and "Relationship matters" are dominant topics in Twitter, "Social gathering", "Outing" and "Fashion" are dominant topics in Instagram, and "Music", "Entertainment" and "Fashion" are dominant topics in Tumblr.

Microblogging encompasses both user-generated content and behavior. When modeling microblogging data, one has to consider personal and background topics, as well as how these topics generate the observed content and behavior. In this article, we propose theGeneralized Behavior-Topic(GBT) model for simultaneously modeling background topics and users’ topical interest in microblogging data. GBT considers multiple topical communities (or realms) with different background topical interests while learning the personal topics of each user and the user’s dependence on realms to generate bothcontentandbehavior. This differentiates GBT from other previous works that consider eitherone realmonly orcontent dataonly. By associating user behavior with the latent background and personal topics, GBT helps to model user behavior by the two types of topics. GBT also distinguishes itself from other earlier works by modeling multiple types of behavior together. Our experiments on two Twitter datasets show that GBT can effectively mine the representative topics for each realm. We also demonstrate that GBT significantly outperforms other state-of-the-art models in modeling content topics and user profiling.

Efficient and commuter friendly public transportation system is a critical part of a thriving and sustainable city. As cities experience fast growing resident population, their public transportation systems will have to cope with more demands for improvements. In this paper, we propose a crowdsensing and analysis framework to gather and analyze realtime commuter feedback from Twitter. We perform a series of text mining tasks identifying those feedback comments capturing bus related micro-events; extracting relevant entities; and, predicting event and sentiment labels. We conduct a series of experiments involving more than 14K labeled tweets. The experiments show that incorporating domain knowledge or domain specific labeled data into text analysis methods improves the accuracies of the above tasks. We further apply the tasks on nearly 200M public tweets from Singapore over a six month period to show that interesting insights about bus services and bus events can be derived in a scalable manner.

The advent of the Web brought about major changes in the way people search for jobs and companies look for suitable candidates. As more employers and recruitment firms turn to the Web for job candidate search, an increasing number of people turn to the Web for uploading and creating their online resumes. Resumes are often the first source of information about candidates and also the first item of evaluation in candidate selection. Thus, it is imperative that resumes are complete, free of errors and well-organized. We present an automated resume evaluation tool called “CareerMapper”. Our tool is designed to conduct a thorough review of a user's LinkedIn profile and provide best recommendations for improved online resumes by analyzing a large number of online user profiles.

Modeling user check-in behavior provides useful insights about venues as well as the users visiting them. These insights can be used in urban planning and recommender system applications. Unlike previous works that focus on modeling distance effect on user's choice of check-in venues, this paper studies check-in behaviors affected by two venue-related factors, namely, area attractiveness and neighborhood competitiveness. The former refers to the ability of an area with multiple venues to collectively attract check-ins from users, while the latter represents the ability of a venue to compete with its neighbors in the same area for check-ins. We first embark on a data science study to ascertain the two factors using two Foursquare datasets gathered from users and venues in Singapore and Jakarta, two major cities in Asia. We then propose the VAN model incorporating user-venue distance, area attractiveness and neighborhood competitiveness factors. The results from real datasets show that VAN model outperforms the various baselines in two tasks: home location prediction and check-in prediction.

In social media, the magnitude of information propagation hinges on the virality and susceptibility of users spreading and receiving the information respectively, as well as the virality of information items. These users' and items' behavioral factors evolve dynamically at the same time interacting with one another. Previous works however measure the factors statically and independently in a restricted case: each user has only a single adoption on each item, and/or users' exposure to items are observable. In this work, we investigate the inter-relationship among the factors and users' multiple adoptions on items to propose both new static and temporal models for measuring the factors without requiring user - item exposure. These models are designed to cope with even more realistic propagation scenarios where an item may be propagated many times from the same user(s) to the same other user(s). We further propose an incremental model for measuring the factors in large data streams. We evaluated the proposed models and existing models through extensive experiments on a large Twitter dataset covering information propagation in one month. The experiments show that our proposed models can effectively mine the behavioral factors and outperform the existing ones in a propagation prediction task. The incremental model is shown more than 10 times faster than the temporal model, while still obtains very similar results.

This paper aims to investigate efficient and scalable machine learning algorithms for resolving Non-negative Matrix Factorization (NMF), which is important for many real-world applications, particularly for collaborative filtering and recommender systems. Unlike traditional batch learning methods, a recently proposed online learning technique named "NN-PA" tackles NMF by applying the popular Passive-Aggressive (PA) online learning, and found promising results. Despite its simplicity and high efficiency, NN-PA falls short in at least two critical limitations: (i) it only exploits the first-order information and thus may converge slowly especially at the beginning of online learning tasks; (ii) it is sensitive to some key parameters which are often difficult to be tuned manually, particularly in a practical online learning system. In this work, we present a novel family of online Adaptive Passive-Aggressive (APA) learning algorithms for NMF, named "NN-APA", which overcomes two critical limitations of NN-PA by (i) exploiting second-order information to enhance PA in making more informative updates at each iteration; and (ii) achieving the parameter auto-selection by exploring the idea of online learning with expert advice in deciding the optimal combination of the key parameters in NMF. We theoretically analyze the regret bounds of the proposed method and show its advantage over the state-of-the-art NN-PA method, and further validate the efficacy and scalability of the proposed technique through an extensive set of experiments on a variety of large-scale real recommender systems datasets.

Social networks are an important class of networks that span a wide variety of media, ranging from social websites such as Facebook and Google Plus, citation networks of academic papers and patents, caller networks in telecommunications, and hyperlinked document collections such as Wikipedia - to name a few. Many of these social networks now exceed millions of users or actors, each of which may be associated with rich attribute data such as user profiles in social websites and caller networks, or subject classifications in document collections and citation networks. Such attribute data is often incomplete for a number of reasons - for example, users may be unwilling to spend the effort to complete their profiles, while in the case of document collections, there may be insufficient human labor to accurately classify all documents. At the same time, the tie or link information in these networks may also be incomplete - in social websites, users may simply be unaware of potential acquaintances, while in citation networks, authors may be unaware of appropriate literature that should be referenced. Completing and predicting these missing attributes and ties is important to a spectrum of applications, such as recommendation, personalized search, and targeted advertising, yet large social networks can pose a scalability challenge to existing algorithms designed for this task. Towards this end, we propose an integrative probabilistic model, SLR, that captures both attribute and tie information simultaneously, and can be used for attribute completion and tie prediction, in order to enable the above mentioned applications. A key innovation in our model is the use of triangle motifs to represent ties in the network, in order to scale to networks with millions of nodes and beyond. Experiments on real world datasets show that SLR significantly improves the accuracy of attribute prediction and tie prediction compared to well-known methods, and our distributed, multi-machine implementation easily scales up to millions of users. In addition to fast and accurate attribute and tie prediction, we also demonstrate how SLR can identify the attributes most responsible for homophily within the network, thus revealing which attributes drive network tie formation.

User identity linkage across social platforms is an important problem of great research challenge and practical value. In real applications, the task often assumes an extra degree of difficulty by requiring linkage across multiple platforms. While pair-wise user linkage between two platforms, which has been the focus of most existing solutions, provides reasonably convincing linkage, the result depends by nature on the order of platform pairs in execution with no theoretical guarantee on its stability. In this paper, we explore a new concept of ``Latent User Space'' to more naturally model the relationship between the underlying real users and their observed projections onto the varied social platforms, such that the more similar the real users, the closer their profiles in the latent user space. We propose two effective algorithms, a batch model(ULink) and an online model(ULink-On), based on latent user space modelling. Two simple yet effective optimization methods are used for optimizing objective function: the first one based on the constrained concave-convex procedure(CCCP) and the second on accelerated proximal gradient. To our best knowledge, this is the first work to propose a unified framework to address the following two important aspects of the multi-platform user identity linkage problem --- (I) the platform multiplicity and (II) online data generation. We present experimental evaluations on real-world data sets for not only traditional pairwise-platform linkage but also multi-platform linkage. The results demonstrate the superiority of our proposed method over the state-of-the-art ones.

When a microblogging user adopts some content propagated to her, we can attribute that to three behavioral factors, namely, topic virality, user virality, and user susceptibility. Topic virality measures the degree to which a topic attracts propagations by users. User virality and susceptibility refer to the ability of a user to propagate content to other users, and the propensity of a user adopting content propagated to her, respectively. In this paper, we study the problem of mining these behavioral factors specific to topics from microblogging content propagation data. We first construct a three dimensional tensor for representing the propagation instances. We then propose a tensor factorization framework to simultaneously derive the three sets of behavioral factors. Based on this framework, we develop a numerical factorization model and another probabilistic factorization variant. We also develop an efficient algorithm for the models' parameters learning. Our experiments on a large Twitter dataset and synthetic datasets show that the proposed models can effectively mine the topic-specific behavioral factors of users and tweet topics. We further demonstrate that the proposed models consistently outperforms the other state-of-the-art content based models in retweet prediction over time.

Twitter has become one of the largest microblogging platforms for users around the world to share anything happening around them with friends and beyond. A bursty topic in Twitter is one that triggers a surge of relevant tweets within a short period of time, which often reflects important events of mass interest. How to leverage Twitter for early detection of bursty topics has therefore become an important research problem with immense practical value. Despite the wealth of research work on topic modelling and analysis in Twitter, it remains a challenge to detect bursty topics in real-time. As existing methods can hardly scale to handle the task with the tweet stream in real-time, we propose in this paper$\sf {TopicSketch}$, a sketch-based topic model together with a set of techniques to achieve real-time detection. We evaluate our solution on a tweet stream with over 30 million tweets. Our experiment results show both efficiency and effectiveness of our approach. Especially it is also demonstrated that$\sf {TopicSketch}$on a single machine can potentially handle hundreds of millions tweets per day, which is on the same scale of the total number of daily tweets in Twitter, and present bursty events in finer-granularity.

Large cities today are facing major challenges in planning and policy formulation to keep their growth sustainable. In this paper, we aim to gain useful insights about people living in a city by developing novel models to mine user lifestyles represented by the users' activity centers. Two models, namely ACMM and ACHMM, have been developed to learn the activity centers of each user using a large dataset of bus and subway train trips performed by passengers in Singapore. We show that ACHMM and ACMM yield similar accuracies in location prediction task. We also propose methods to automatically predict "home", "work" and "others" labels of locations visited by each user. Through validating with human-labeled home and work locations, we show that the accuracy of location label assignment is surprisingly very good even using an unsupervised method. With the location labels assigned, we further derive interesting insights of urban lifestyles at both individual and population levels.

This paper investigates how digital traces of people's movements and activities in the physical world (e.g., at college campuses and commutes) may be used to detect local, short-lived events in various urban spaces. Past work that use occupancy-related features can only identify high-intensity events (those that cause large-scale disruption in visit patterns). In this paper, we first show how longitudinal traces of the coordinated and group-based movement episodes obtained from individual-level movement data can be used to create a socio-physical network (with edges representing tie strengths among individuals based on their physical world movement & collocation behavior). We then investigate how two additional families of socio-physical features: (i) group-level interactions observed over shorter timescales and (ii) socio-physical network tie-strengths derived over longer timescales, can be used by state-of-the-art anomaly detection methods to detect a much wider set of both high & low intensity events. We utilize two distinct datasets--one capturing coarse-grained SMU campus-wide indoor location data from hundreds of students, and the other capturing commuting behavior by millions of users on Singapore's public transport network--to demonstrate the promise of our approaches: the addition of group and socio-physical tie-strength based features increases recall (the percentage of events detected) more than 2-folds (to 0.77 on the SMU campus and to 0.73 at sample MRT stations), compared to pure occupancy-based approaches.

Taxi bookings are events where requests for taxis are made by passengers either over voice calls or mobile apps. As the demand for taxis changes with space and time, it is important to model both the space and temporal dimensions in dynamic booking data. Several applications can benefit from a good taxi booking model. These include the prediction of number of bookings at certain location and time of the day, and the detection of anomalous booking events. In this paper, we propose a Grid-based Gaussian Mixture Model (GGMM) with spatio-temporal dimensions that groups booking data into a number of spatio-temporal clusters by observing the bookings occurring at different time of the day in each spatial grid cell. Using a large-scale real-world dataset consisting of over millions of booking records, we show that GGMM outperforms two strong baselines: a Gaussian Mixture Model (GMM) and the state-of-the-art spatio-temporal behavior model, Periodic Mobility Model (PMM), in estimating the spatio-temporal distribution of bookings at specific grid cells during specific time intervals. GGMM can achieve up to 95.8% (96.5%) reduction in perplexity compared against GMM (PMM). Further, we apply GGMM to detect anomalous bookings and successfully relate the anomalies with some known events, demonstrating GGMM's effectiveness in this task.

The popularity of social media has led many users to create accounts with different online social networks. Identifying these multiple accounts belonging to same user is of critical importance to user profiling, community detection, user behavior understanding and product recommendation. Nevertheless, linking users across heterogeneous social networks is challenging due to large network sizes, heterogeneous user attributes and behaviors in different networks, and noises in user generated data. In this paper, we propose an unsupervised method, Collective Network Linkage (CNL), to link users across heterogeneous social networks. CNL incorporates heterogeneous attributes and social features unique to social network users, handles missing data, and performs in a collective manner. CNL is highly accurate and efficient even without training data. We evaluate CNL on linking users across different social networks. Our experiment results on a Twitter network and another Foursquare network demonstrate that CNL performs very well and its accuracy is superior than the supervised Mobius approach.

In e-commerce environments, the trustworthiness of a seller is utterly important to potential buyers, especially when a seller is not known to them. Most existing trust evaluation models compute a single value to reflect the general trustworthiness of a seller without taking any transaction context information into account. With such a result as the indication of reputation, a buyer may be easily deceived by a malicious seller in a transaction where the notorious value imbalance problem is involved—in other words, a malicious seller accumulates a high-level reputation by selling cheap products and then deceives buyers by inducing them to purchase more expensive products. In this article, we first present a trust vector consisting of three values for contextual transaction trust (CTT). In the computation of CTT values, three identified important context dimensions , including Product Category, Transaction Amount, and Transaction Time, are taken into account. In the meantime, the computation of each CTT value is based on both past transactions and the forthcoming transaction. In particular, with different parameters specified by a buyer regarding context dimensions, different sets of CTT values can be calculated. As a result, all of these trust values can outline the reputation profile of a seller that indicates the dynamic trustworthiness of a seller in different products, product categories, price ranges, time periods, and any necessary combination of them. We name this new model ReputationPro . Nevertheless, in ReputationPro , the computation of reputation profile requires new data structures for appropriately indexing the precomputation of aggregates over large-scale ratings and transaction data in three context dimensions, as well as novel algorithms for promptly answering buyers’ CTT queries. In addition, storing precomputed aggregation results consumes a large volume of space, particularly for a system with millions of sellers. Therefore, reducing storage space for aggregation results is also a great demand. To solve these challenging problems, we first propose a new index scheme CMK-tree by extending the two-dimensional K-D-B-tree that indexes spatial data to support efficient computation of CTT values. Then, we further extend the CMK-tree and propose a CMK-tree RS approach to reducing the storage space allocated to each seller. The two approaches are not only applicable to three context dimensions that are either linear or hierarchical but also take into account the characteristics of the transaction-time model—that is, transaction data is inserted in chronological order. Moreover, the proposed data structures can index each specific product traded in a time period to compute the trustworthiness of a seller in selling a product. Finally, the experimental results illustrate that the CMK-tree is superior in efficiency of computing CTT values to all three existing approaches in the literature. In particular, while answering a buyer’s CTT queries for each brand-based product category, the CMK-tree has almost linear query performance. In addition, with significantly reduced storage space, the CMK-tree RS approach can further improve the efficiency in computing CTT values. Therefore, our proposed ReputationPro model is scalable to large-scale e-commerce Web sites in terms of efficiency and storage space consumption.

Deep within the networks of distributed systems, one often finds anomalies that affect their efficiency and performance. These anomalies are difficult to detect because the distributed systems may not have sufficient sensors to monitor the flow of traffic within the interconnected nodes of the networks. Without early detection and making corrections, these anomalies may aggravate over time and could possibly cause disastrous outcomes in the system in the unforeseeable future. Using only coarse-grained information from the two end points of network flows, we propose a network transmission model and a localization algorithm, to detect the location of anomalies and rank them using a proposed metric within distributed systems. We evaluate our approach on passengers' records of an urbanized city's public transportation system and correlate our findings with passengers' postings on social media micro blogs. Our experiments show that the metric derived using our localization algorithm gives a better ranking of anomalies as compared to standard deviation measures from statistical models. Our case studies also demonstrate that transportation events reported in social media micro blogs matches the locations of our detect anomalies, suggesting that our algorithm performs well in locating the anomalies within distributed systems.

Gaming expertise is usually accumulated through playing or watching many game instances, and identifying critical moments in these game instances called turning points. Turning point rules (shorten as TPRs) are game patterns that almost always lead to some irreversible outcomes. In this paper, we formulate the notion of irreversible outcome property which can be combined with pattern mining so as to automatically extract TPRs from any given game datasets. We specifically extend the well-known PrefixSpan sequence mining algorithm by incorporating the irreversible outcome property. To show the usefulness of TPRs, we apply them to Tetris, a popular game. We mine TPRs from Tetris games and generate challenging game sequences so as to help training an intelligent Tetris algorithm. Our experiment results show that 1) TPRs can be found from historical game data automatically with reasonable scalability, 2) our TPRs are able to help Tetris algorithm perform better when it is trained with challenging game sequences.

In this paper, we propose the CBS topic model, a probabilistic graphical model, to derive the user communities in microblogging networks based on the sentiments they express on their generated content and behaviors they adopt. As a topic model, CBS can uncover hidden topics and derive user topic distribution. In addition, our model associates topic-specific sentiments and behaviors with each user community. Notably, CBS has a general framework that accommodates multiple types of behaviors simultaneously. Our experiments on two Twitter datasets show that the CBS model can effectively mine the representative behaviors and emotional topics for each community. We also demonstrate that CBS model perform as well as other state-of-the-art models in modeling topics, but outperforms the rest in mining user communities.

User preferences change over time and capturing such changes is essential for developing accurate recommender systems. Despite its importance, only a few works in collaborative filtering have addressed this issue. In this paper, we consider evolving preferences and we model user dynamics by introducing and learning a transition matrix for each user's latent vectors between consecutive time windows. Intuitively, the transition matrix for a user summarizes the time-invariant pattern of the evolution for the user. We first extend the conventional probabilistic matrix factorization and then improve upon this solution through its fully Bayesian model. These solutions take advantage of the model complexity and scalability of conventional Bayesian matrix factorization, yet adapt dynamically to user's evolving preferences. We evaluate the effectiveness of these solutions through empirical studies on six large-scale real life data sets.

Religious belief plays an important role in how people behave, influencing how they form preferences, interpret events around them, and develop relationships with others. Traditionally, the religion labels of user population are obtained by conducting a large scale census study. Such an approach is both high cost and time consuming. In this paper, we study the problem of predicting users' religion labels using their microblogging data. We formulate religion label prediction as a classification task, and identify content, structure and aggregate features considering their self and social variants for representing a user. We introduce the notion of representative user to identify users who are important in the religious user community. We further define features using representative users. We show that SVM classifiers using our proposed features can accurately assign Christian and Muslim labels to a set of Twitter users with known religion labels.

Mobile advertising has recently seen dramatic growth, fueled by the global proliferation of mobile phones and devices. The task of predicting ad response is thus crucial for maximizing business revenue. However, ad response data change dynamically over time, and are subject to cold-start situations in which limited history hinders reliable prediction. There is also a need for a robust regression estimation for high prediction accuracy, and good ranking to distinguish the impacts of different ads. To this end, we develop a Hierarchical Importance-aware Factorization Machine (HIFM), which provides an effective generic latent factor framework that incorporates importance weights and hierarchical learning. Comprehensive empirical studies on a real-world mobile advertising dataset show that HIFM outperforms the contemporary temporal latent factor models. The results also demonstrate the efficacy of the HIFM's importance-aware and hierarchical learning in improving the overall prediction and prediction in cold-start scenarios, respectively.

In an urban city, its transportation network supports efficient flow of people between different parts of the city. Failures in the network can cause major disruptions to commuter and business activities which can result in both significant economic and time losses. In this paper, we investigate the use of centrality measures to determine critical nodes in a transportation network so as to improve the design of the network as well as to devise plans for coping with network failures. Most centrality measures in social network analysis research unfortunately consider only topological structure of the network and are oblivious of transportation factors. This paper proposes a new centrality measure called DelayFlow that incorporates travel time delay and commuter flow volume. We apply the proposed measures on the Singapore's subway network and its about 2 million commuter trips per day, and compare them with traditional topology based centrality measures.

In political contexts, it is known that people act as "motivated reasoners", i.e., information is evaluated first for emotional affect, and this emotional reaction influences later deliberative reasoning steps. As social media becomes a more and more prevalent way of receiving political information, it becomes important to understand more completely the interaction between information, emotion, social community, and information-sharing behavior. In this paper, we describe a high-precision classifier for politically-oriented tweets, and an accurate classifier of a Twitter user's political affiliation. Coupled with existing sentiment-analysis tools for microblogs, these methods enable us to systematically study the interaction of emotion and sharing in a large corpus of politically-oriented microblog messages, collected from just before the 2012 US presidential election. In particular, we seek to understand how information sharing is influenced by the political affiliation of the sender and receiver of a message, and the sentiment associated with the message.

The problem of recommending items to users is relevant to many applications and the problem has often been solved using methods developed from Collaborative Filtering (CF). Collaborative Filtering model-based methods such as Matrix Factorization have been shown to produce good results for static rating-type data, but have not been applied to time-stamped item adoption data. In this paper, we adopted a Dynamic Matrix Factorization (DMF) technique to derive different temporal factorization models that can predict missing adoptions at different time steps in the users' adoption history. This DMF technique is an extension of the Non-negative Matrix Factorization (NMF) based on the well-known class of models called Linear Dynamical Systems (LDS). By evaluating our proposed models against NMF and TimeSVD++ on two real datasets extracted from ACM Digital Library and DBLP, we show empirically that DMF can predict adoptions more accurately than the NMF for several prediction tasks as well as outperforming TimeSVD++ in some of the prediction tasks. We further illustrate the ability of DMF to discover evolving research interests for a few author examples.

Twitter has become one of the largest platforms for users around the world to share anything happening around them with friends and beyond. A bursty topic in Twitter is one that triggers a surge of relevant tweets within a short time, which often reflects important events of mass interest. How to leverage Twitter for early detection of bursty topics has therefore become an important research problem with immense practical value. Despite the wealth of research work on topic modeling and analysis in Twitter, it remains a huge challenge to detect bursty topics in real-time. As existing methods can hardly scale to handle the task with the tweet stream in real-time, we propose in this paper Topic Sketch, a novel sketch-based topic model together with a set of techniques to achieve real-time detection. We evaluate our solution on a tweet stream with over 30 million tweets. Our experiment results show both efficiency and effectiveness of our approach. Especially it is also demonstrated that Topic Sketch can potentially handle hundreds of millions tweets per day which is close to the total number of daily tweets in Twitter and present bursty event in finer-granularity.

When a user retweets, there are three behavioral factors that cause the actions. They are the topic virality, user virality and user susceptibility. Topic virality captures the degree to which a topic attracts retweets by users. For each topic, user virality and susceptibility refer to the likelihood that a user attracts retweets and performs retweeting respectively. To model a set of observed retweet data as a result of these three topic specific factors, we first represent the retweets as a three-dimensional tensor of the tweet authors, their followers, and the tweets themselves. We then propose the V2S model, a tensor factorization model, to simultaneously derive the three sets of behavioral factors. Our experiments on a real Twitter data set show that the V2S model can effectively mine the behavioral factors of users and tweet topics during an election event. We also demonstrate that the V2S model outperforms the other topic based models in retweet prediction.

Users face many choices on the web when it comes to choosing which product to buy, which video to watch, and so on. In making adoption decisions, users rely not only on their own preferences, but also on friends. We call the latter social correlation, which may be caused by the homophily and social influence effects. In this paper, we focus on modeling social correlation on users item adoptions. Given a user-user social graph and an item-user adoption graph, our research seeks to answer the following questions: Whether the items adopted by a user correlate with items adopted by her friends, and how to model item adoptions using social correlation. We propose a social correlation framework that considers a social correlation matrix representing the degrees of correlation from every user to the users friends, in addition to a set of latent factors representing topics of interests of individual users. Based on the framework, we develop two generative models, namely sequential and unified, and the corresponding parameter estimation approaches. From each model, we devise the social correlation only and hybrid methods for predicting missing adoption links. Experiments on LiveJournal and Epinions data sets show that our proposed models outperform the approach based on latent factors only (LDA).

In service-based industries, churn poses a significant threat to the integrity of the user communities and profitability of the service providers. As such, research on churn prediction methods has been actively pursued, involving either intrinsic, user profile factors or extrinsic, social factors. However, existing approaches often address each type of factors separately, thus lacking a comprehensive view of churn behaviors. In this paper, we propose a new churn prediction approach based on collective classification (CC), which accounts for both the intrinsic and extrinsic factors by utilizing the local features of, and dependencies among, individuals during prediction steps. We evaluate our CC approach using real data provided by an established mobile social networking site, with a primary focus on prediction of churn in chat activities. Our results demonstrate that using CC and social features derived from interaction records and network structure yields substantially improved prediction in comparison to using conventional classification and user profile features only.

Link prediction is an important problem in social network mining. Traditional neighborhood based methods such as Common neighbors, Jaccard Coefficient and Adamic/Adar are well studied in link prediction. However, the concept of structural holes does not receive significant attention in link prediction. As a preliminary work in studying structural holes, we focus on bipartite social networks, which is a special class of social networks that consists of two distinct roles for the users, and links are between users of different roles. In this study, a few implementations of structural holes are proposed, which are then validated with extended neighborhood based methods on a real dataset derived from IMDb network. The results show that structural holes help in improving accuracies in link prediction.

Many event monitoring systems rely on counting known keywords in streaming text data to detect sudden spikes in frequency. But the dynamic and conversational nature of Twitter makes it hard to select known keywords for monitoring. Here we consider a method of automatically finding noun phrases (NPs) as keywords for event monitoring in Twitter. Finding NPs has two aspects, identifying the boundaries for the subsequence of words which represent the NP, and classifying the NP to a specific broad category such as politics, sports, etc. To classify an NP, we define the feature vector for the NP using not just the words but also the author's behavior and social activities. Our results show that we can classify many NPs by using a sample of training data from a knowledge-base.

The recent boom of weblogs and social media has attached increasing importance to the identification of suspicious users with unusual behavior, such as spammers or fraudulent reviewers. A typical spamming strategy is to employ multiple dummy accounts to collectively promote a target, be it a URL or a product. Consequently, these suspicious accounts exhibit certain coherent anomalous behavior identifiable as a collection. In this paper, we propose the concept of Coherent Anomaly Collection (CAC) to capture this kind of collections, and put forward an efficient algorithm to simultaneously find the top-K disjoint CACs together with their anomalous behavior patterns. Compared with existing approaches, our new algorithm can find disjoint anomaly collections with coherent extreme behavior without having to specify either their number or sizes. Results on real Twitter data show that our approach discovers meaningful and informative hashtag spammer groups of various sizes which are hard to detect by clustering-based methods.

Bipartite graphs can model many real life applications including users-rating-products in online marketplaces, users-clicking-webpages on the World Wide Web and users referring- users in social networks. In these graphs, the anomalousness of nodes in one partite often depends on that of their connected nodes in the other partite. Previous studies have shown that this dependency can be positive (the anomalousness of a node in one partite increases or decreases along with that of its connected nodes in the other partite) or negative (the anomalousness of a node in one partite rises or falls in opposite direction to that of its connected nodes in the other partite). In this paper, we unify both positive and negative mutual dependency relationships in an unsupervised framework for detecting anomalous nodes in bipartite graphs. This is the first work that integrates both mutual dependency principles to model the complete set of anomalous behaviors of nodes that cannot be identified by either principle alone. We formulate our principles and design an iterative algorithm to simultaneously compute the anomaly scores of nodes in both partites. Moreover, we mathematically prove that the ranking of nodes by anomaly scores in each partite converges. Our framework is examined on synthetic graphs and the results show that our model outperforms existing models with only positive or negative mutual dependency principles. We also apply our framework to two real life datasets: Goodreads as a users-rating-books setting and Buzzcity as a users-clicking advertisements setting. The results show that our method is able to detect suspected spamming users and spammed books in Goodreads and achieve higher precision in identifying fraudulent advertisement publishers than existing approaches.

Microblogging is a new trend to communicate and to disseminate information. One microblog post could potentially reach millions of users. Millions of microblogs are generated on a daily basis on popular sites such as Twitter. The popularity of microblogging among programmers, software engineers, and software users has also led to their use of microblogs to communicate software engineering issues apart from using emails and other traditional communication channels. Understanding how millions of users use microblogs in software engineering related activities would shed light on ways we could leverage the fast evolving microblogging content to aid software development efforts. In this work, we perform a preliminary study on what the software engineering community microblogs about. We analyze the content of microblogs from Twitter and categorize the types of microblogs that are posted. We investigate the relative popularity of each category of microblogs. We also investigate what kinds of microblogs are diffused more widely in the Twitter network via the “retweet” feature. Our experiments show that microblogs commonly contain job openings, news, questions and answers, or links to download new tools and code. We find that microblogs concerning real-world events are more widely diffused in the Twitter network.

User-to-user interactions have become ubiquitous in Web 2.0. Users exchange emails, post on newsgroups, tag web pages, co-author papers, etc. Through these interactions, users co-produce or co-adopt content items (e.g., words in emails, tags in social bookmarking sites). We model such dynamic interactions as a user interaction network, which relates users, interactions, and content items over time. After some interactions, a user may produce content that is more similar to those produced by other users previously. We term this effect social dependency, and we seek to mine from such networks the degree to which a user may be socially dependent on another user over time. We propose a Decay Topic Model to model the evolution of a user's preferences for content items at the topic level, as well as a Social Dependency Metric that quantifies the extent of social dependency based on interactions and content changes. Our experiments on two user interaction networks induced from real-life datasets show the effectiveness of our approach.

Modern social networks often consist of multiple relations among individuals. Understanding the structure of such multi-relational network is essential. In sociology, one way of structural analysis is to identify different positions and roles using blockmodels. In this paper, we generalize stochastic blockmodels to Generalized Stochastic Blockmodels (GSBM) for performing positional and role analysis on multi-relational networks. Our GSBM generalizes many different kinds of Multivariate Probability Distribution Function (MVPDF) to model different kinds of multi-relational networks. In particular, we propose to use multivariate Poisson distribution for multi-relational social networks. Our experiments show that GSBM is able to identify the structures for both synthetic and real world network data. These structures can further be used for predicting relationships between individuals.

Anomaly or outlier detection has a wide range of applications, including fraud and spam detection. Most existing studies focus on detecting point anomalies, i.e., individual, isolated entities. However, there is an increasing number of applications in which anomalies do not occur individually, but in small collections. Unlike the majority, entities in an anomalous collection tend to share certain extreme behavioral traits. The knowledge essential in understanding why and how the set of entities becomes outliers would only be revealed by examining at the collection level. A good example is web spammers adopting common spamming techniques. To discover this kind of anomalous collections, we introduce a novel definition of anomaly, called Extreme Rank Anomalous Collection. We propose a statistical model to quantify the anomalousness of such a collection, and present an exact as well as a heuristic algorithms for finding top-K extreme rank anomalous collections. We apply the algorithms on real Web spam data to detect spamming sites, and on IMDB data to detect unusual actor groups. Our algorithms achieve higher precisions compared to existing spam and anomaly detection methods. More importantly, our approach succeeds in finding meaningful anomalous collections in both datasets.

The emerging trend of social information processing has resulted in Web users’ increased reliance on user-generated content contributed by others for information searching and decision making. Rating scores, a form of user-generated content contributed by reviewers in online rating systems, allow users to leverage others’ opinions in the evaluation of objects. In this article, we focus on the problem of summarizing the rating scores given to an object into an overall score that reflects the object’s quality. We observe that the existing approaches for summarizing scores largely ignores the effect of reviewers exercising different standards in assigning scores. Instead of treating all reviewers as equals, our approach models the leniency of reviewers, which refers to the tendency of a reviewer to assign higher scores than other coreviewers. Our approach is underlined by two insights: (1) The leniency of a reviewer depends not only on how the reviewer rates objects, but also on how other reviewers rate those objects and (2) The leniency of a reviewer and the quality of rated objects are mutually dependent. We develop the leniency-aware quality , or LQ model, which solves leniency and quality simultaneously. We introduce both an exact and a ranked solution to the model. Experiments on real-life and synthetic datasets show that LQ is more effective than comparable approaches. LQ is also shown to perform consistently better under different parameter settings.

Bipartite networks are often used to capture the relationships between different classes of objects. To model the structure of bipartite networks, we propose a new hierarchical model based on a hierarchical random graph model originally designed for one-mode networks. The new model can better preserve the network fidelity as well as the assortative and disassortative structures of bipartite networks. We apply the proposed model on some paper-author networks in DBLP to find their optimal hierarchical structures. Using the optimal bipartite hierarchical structure, we regenerate networks that exhibit the similar network properties and degree distribution as the observed networks.

Socialness refers to the ability to elicit social interaction and social links among people. It is a concept often associated with individuals. Although there are tangible benefits in socialness, there is little research in its modeling. In this paper, we study socialness as a property that can be associated with items, beyond its traditional association with people. We aim to model an item's socialness as a quantitative measure based on the how popular the item is adopted by members of multiple communities. We propose two socialness models, namely Basic and Mutual Dependency, to compute item socialness based on different sets of principles. In developing the Mutual Dependency Model, we demonstrate that items' socialness can be related to the socialness of communities. Our model have been evaluated on a set of users and application items from a mobile social network. We also conducted experiments to study how socialness can be related to network effects such as homophily, social influence and friendship formation.

There has been a recent increase of interest in analyzing trust and friendship networks to gain insights about relationship dynamics among users. Many sites such as Epinions, Facebook, and other social networking sites allow users to declare trusts or friendships between different members of the community. In this work, we are interested in extracting direct antagonistic communities (DACs) within a rich trust network involving trusts and distrusts. Each DAC is formed by two subcommunities with trust relationships among members of each sub-community but distrust relationships across the sub-communities. We develop an efficient algorithm that could analyze large trust networks leveraging the unique property of direct antagonistic community. We have experimented with synthetic and real data-sets (myGamma and Epinions) to demonstrate the scalability of our proposed solution.

Users face a dazzling array of choices on the Web when it comes to choosing which product to buy, which video to watch, etc. The trend of social information processing means users increasingly rely not only on their own preferences, but also on friends when making various adoption decisions. In this paper, we investigate the effects of social correlation on users' adoption of items. Given a user-user social graph and an item-user adoption graph, we seek to answer the following questions: 1) whether the items adopted by a user correlate to items adopted by her friends, and 2) how to incorporate social correlation in order to improve prediction of unobserved item adoptions. We propose the Social Correlation model based on Latent Dirichlet Allocation (LDA) that decomposes the adoption graph into a set of latent factors reflecting user preferences, and a social correlation matrix reflecting the degree of correlation from one user to another. This matrix is learned (rather than pre-assigned), has probabilistic interpretation, and preserves the underlying social network structure. We further devise a Hybrid model that combines a user's own latent factors with her friends' for adoption prediction. Experiments on Epinions and LiveJournal data sets show that our proposed models outperform the approach based on latent factors only (LDA).

We demonstrate SSNetViz that is developed for integrating, visualizing and querying heterogeneous semantic social networks obtained from multiple information sources. A semantic social network refers to a social network graph with multi-typed nodes and links. We demonstrate various innovative features of SSNetViz with social networks from three information sources covering a similar set of entities and relationships in terrorism domain.

In email networks, user behaviors affect the way emails are sent and replied. While knowing these user behaviors can help to create more intelligent email services, there has not been much research into mining these behaviors. In this paper, we investigate user engagingness and responsiveness as two interaction behaviors that give us useful insights into how users email one another. Engaging users are those who can effectively solicit responses from other users. Responsive users are those who are willing to respond to other users. By modeling such behaviors, we are able to mine them and to identify engaging or responsive users. This paper proposes four types of models to quantify engagingness and responsiveness of users. These behaviors can be used as features in the email reply order prediction task which predicts the email reply order given an email pair. Our experiments show that engagingness and responsiveness behavior features are more useful than other non-behavior features in building a classifier for the email reply order prediction task. When combining behavior and non-behavior features, our classifier is also shown to predict the email reply order with good accuracy.

In recent years, opinion mining attracted a great deal of research attention. However, limited work has been done on detecting opinion spam (or fake reviews). The problem is analogous to spam in Web search [1, 9 11]. However, review spam is harder to detect because it is very hard, if not impossible, to recognize fake reviews by manually reading them [2]. This paper deals with a restricted problem, i.e., identifying unusual review patterns which can represent suspicious behaviors of reviewers. We formulate the problem as finding unexpected rules. The technique is domain independent. Using the technique, we analyzed an Amazon.com review dataset and found many unexpected rules and rule groups which indicate spam activities.

Link structures are important patterns one looks out for when modeling and analyzing social networks. In this paper, we propose the task of mining interesting Link Formation rules (LF-rules) containing link structures known as Link Formation patterns (LF-patterns). LF-patterns capture various dyadic and/or triadic structures among groups of nodes, while LF-rules capture the formation of a new link from a focal node to another node as a postcondition of existing connections between the two nodes. We devise a novel LF-rule mining algorithm, known as LFR-Miner, based on frequent subgraph mining for our task. In addition to using a support-confidence framework for measuring the frequency and significance of LF-rules, we introduce the notion of expected support to account for the extent to which LF-rules exist in a social network by chance. Specifically, only LF-rules with higher-than-expected support are considered interesting. We conduct empirical studies on two real-world social networks, namely Epinions and myGamma. We report interesting LF-rules mined from the two networks, and compare our findings with earlier findings in social network analysis.

This paper aims to detect users generating spam reviews or review spammers. We identify several characteristic behaviors of review spammers and model these behaviors so as to detect the spammers. In particular, we seek to model the following behaviors. First, spammers may target specific products or product groups in order to maximize their impact. Second, they tend to deviate from the other reviewers in their ratings of products. We propose scoring methods to measure the degree of spam for each reviewer and apply them on an Amazon review dataset. We then select a subset of highly suspicious reviewers for further scrutiny by our user evaluators with the help of a web based spammer evaluation software specially developed for user evaluation experiments. Our results show that our proposed ranking and supervised methods are effective in discovering spammers and outperform other baseline method based on helpfulness votes alone. We finally show that the detected spammers have more significant impact on ratings compared with the unhelpful reviewers.

When micro logging becomes a very popular social media, finding interesting posts from high volume stream of user posts is a challenging research problem. To organize large number of posts, users can assign tags to posts so that these posts can be navigated and searched by tag. In this paper, we focus on modeling the interestingness of hash tags in Twitter, the largest and most active micro logging site. We propose to first construct communities based on both follow links and tagged interactions. We then measure the dispersion and divergence of users and tweets using hash tags among the constructed communities. The interestingness of hash tags are then derived from these community-based dispersion and divergence features. We further introduce a supervised approach to rank hash tags by interestingness. Our experiments on a Twitter dataset show that the proposed approach achieves a fairly good performance.

The development of numerous information sharing platforms have led to the emergence of multimedia user-generated content. With the prevalence of networking mobile devices and Global Positioning System (GPS) functionality, these contents could also be tagged with their location (geo-tagged) and visualised on a map through a geospatial information system. This in turn raises new challenges to manage the information retrieval process due to the potentially large amounts of data presented on the map. In this paper, we present a spatial clustering approach to enhance the searching feature of MobiTOP, a geospatial annotation system. The technique, which is a modification of DBSCAN (Density based spatial clustering applications with noise) coupled with our ranking schemes, is compared against other techniques. The evaluation results suggest the viability of our approach, and implications are also discussed.

In an online rating system, raters assign ratings to objects contributed by other users. In addition, raters can develop trust and distrust on object contributors depending on a few rating and trust related factors. Previous study has shown that ratings and trust links can influence each other but there has been a lack of a formal model to relate these factors together. In this paper, we therefore propose Trust Antecedent Factor (TAF) Model, a novel probabilistic model that generate ratings based on a number of rater's and contributor's factors. We demonstrate that parameters of the model can be learnt by Collapsed Gibbs Sampling. We then apply the model to predict trust and distrust between raters and review contributors using a real data-set. Our experiments have shown that the proposed model is capable of predicting both trust and distrust in a unified way. The model can also determine user factors which otherwise cannot be observed from the rating and trust data.

Trust reciprocity, a special form of link reciprocity, exists in many networks of trust among users. In this paper, we seek to determine the extent to which reciprocity exists in a trust network and develop quantitative models for measuring reciprocity and reciprocity related behaviors. We identify several reciprocity behaviors and their respective measures. These behavior measures can be employed for predicting if a trustee will return trust to her trustor given that the latter initiates a trust link earlier. We develop for this reciprocal trust prediction task a number of ranking method and classification methods, and evaluated them on an Epinions trust network data. Our results show that reciprocity related behaviors provide good features for both ranking and classification based methods under different parameter settings.

This paper focuses on the problem of identifying influential users of micro-blogging services. Twitter, one of the most notable micro-blogging services, employs a social-networking model called "following", in which each user can choose who she wants to "follow" to receive tweets from without requiring the latter to give permission first. In a dataset prepared for this study, it is observed that (1) 72.4% of the users in Twitter follow more than 80% of their followers, and (2) 80.5% of the users have 80% of users they are following follow them back. Our study reveals that the presence of "reciprocity" can be explained by phenomenon of homophily. Based on this finding, TwitterRank, an extension of PageRank algorithm, is proposed to measure the influence of users in Twitter. TwitterRank measures the influence taking both the topical similarity between users and the link structure into account. Experimental results show that TwitterRank outperforms the one Twitter currently uses and other related algorithms, including the original PageRank and Topic-sensitive PageRank.

Spatio-temporal data concerning the movement of individuals over space and time contains latent information on the associations among these individuals. Sources of spatio-temporal data include usage logs of mobile and Internet technologies. This article defines a spatio-temporal event by the co-occurrences among individuals that indicate potential associations among them. Each spatio-temporal event is assigned a weight based on the precision and uniqueness of the event. By aggregating the weights of events relating two individuals, we can determine the strength of association between them. We conduct extensive experimentation to investigate both the efficacy of the proposed model as well as the computational complexity of the proposed algorithms. Experimental results on three real-life spatio-temporal datasets cross-validate each other, lending greater confidence on the reliability of our proposed model.

Trust plays important roles in diverse decentralized environments, including our society at large. Computational trust models help to, for instance, guide users' judgements in online auction sites about other users; or determine quality of contributions in web 2.0 sites. Most of the existing trust models, however, require historical information about past behavior of a specific agent being evaluated - information that is not always available. In contrast, in real life interactions among users, in order to make the first guess about the trustworthiness of a stranger, we commonly use our "instinct" - essentially stereotypes developed from our past interactions with "similar" people. We propose StereoTrust, a computational trust model inspired by real life stereotypes. A user forms stereotypes using her previous transactions with other agents. A stereotype contains certain features of agents and an expected outcome of the transaction. These features can be taken from agents' profile information, or agents' observed behavior in the system. When facing a stranger, the stereotypes matching stranger's profile are aggregated to derive his expected trust. Additionally, when some information about stranger's previous transactions is available, StereoTrust uses it to refine the stereotype matching. According to our experiments, StereoTrust compares favorably with existing trust models that use different kind of information and more complete historical information. Moreover, because evaluation is done according to user's personal stereotypes, the system is completely distributed and the result obtained is personalized. StereoTrust can be used as a complimentary mechanism to provide the initial trust value for a stranger, especially when there is no trusted, common third parties.

In this paper, we try to predict which category will be less accurately classified compared with other categories in a classification task that involves multiple categories. The categories with poor predicted performance will be identified before any classifiers are trained and additional steps can be taken to address the predicted poor accuracies of these categories. Inspired by the work on query performance prediction in ad-hoc retrieval, we propose to predict classification performance using two measures, namely, category size and category coherence. Our experiments on 20-Newsgroup and Reuters-21578 datasets show that the Spearman rank correlation coefficient between the predicted rank of classification performance and the expected classification accuracy is as high as 0.9.

Web query recommendation has long been considered a key feature of search engines. Building a good Web query recommendation system, however, is very difficult due to the fundamental challenge of predicting users' search intent, especially given the limited user context information. In this paper, we propose a novel "sequential query prediction" approach that tries to grasp a user's search intent based on his/her past query sequence and its resemblance to historical query sequence models mined from massive search engine logs. Different query sequence models were examined, including the naive variable length N-gram model, variable memory Markov (VMM) model, and our proposed mixture variable memory Markov (MVMM) model. Extensive experiments were conducted to benchmark our sequence prediction algorithms against two conventional pairwise approaches on large-scale search logs extracted from a commercial search engine. Results show that the sequence-wise approaches significantly outperform the conventional pair-wise ones in terms of prediction accuracy. In particular, our MVMM approach, consistently leads the pack, making it an effective and practical approach towards Web query recommendation.

This paper analyzes the trustor and trustee factors that lead to inter-personal trust using a well studied Trust Antecedent framework in management science. To apply these factors to trust ranking problem in online rating systems, we derive features that correspond to each factor and develop different trust ranking models. The advantage of this approach is that features relevant to trust can be systematically derived so as to achieve good prediction accuracy. Through a series of experiments on real data from Epinions, we show that even a simple model using the derived features yields good accuracy and outperforms MoleTrust, a trust propagation based model. SVM classifiers using these features also show improvements.

We introduce MobiTOP (mobile tagging of objects and people), a map-based application which allows users to contribute and share geo-referenced multimedia annotations via mobile devices. An important feature of MobiTOP is that annotations are hierarchical, allowing annotations to be annotated to an arbitrary depth. MobiTOPpsilas interface was designed using a participatory design methodology to ensure that the user interface meets the needs of potential users. In an evaluation, a group of student-teachers involved in a geographical field study were tasked to collaboratively identify rock formations using the MobiTOP system. The students who were in the field were guided by their lab counterparts on the tasks required to identify the rock formations. Results suggest the potential of the MobiTOP system for information sharing.

Community Question Answering (QA) portals contain questions and answers contributed by hundreds of millions of users. These databases of questions and answers are of great value if they can be used directly to answer questions from any user. In this research, we address this collaborative QA task by drawing knowledge from the crowds in community QA portals such as Yahoo! Answers. Despite their popularity, it is well known that answers in community QA portals have unequal quality. We therefore propose a quality-aware framework to design methods that select answers from a community QA portal considering answer quality in addition to answer relevance. Besides using answer features for determining answer quality, we introduce several other quality-aware QA methods using answer quality derived from the expertise of answerers. Such expertise can be question independent or question dependent. We evaluate our proposed methods using a database of 95K questions and 537K answers obtained from Yahoo! Answers. Our experiments have shown that answer quality can improve QA performance significantly. Furthermore, question dependent expertise based methods are shown to outperform methods using answer features only. It is also found that there are also good answers not among the best answers identified by Yahoo! Answers users.

Comments left by readers on Web documents contain valuable information that can be utilized in different information retrieval tasks including document search, visualization, and summarization. In this paper, we study the problem of comments-oriented document summarization and aim to summarize a Web document (e.g., a blog post) by considering not only its content, but also the comments left by its readers. We identify three relations (namely, topic, quotation, and mention) by which comments can be linked to one another, and model the relations in three graphs. The importance of each comment is then scored by: (i) graph-based method, where the three graphs are merged into a multi-relation graph; (ii) tensor-based method, where the three graphs are used to construct a 3rd-order tensor. To generate a comments-oriented summary, we extract sentences from the given Web document using either feature-biased approach or uniform-document approach. The former scores sentences to bias keywords derived from comments; while the latter scores sentences uniformly with comments. In our experiments using a set of blog posts with manually labeled sentences, our proposed summarization methods utilizing comments showed significant improvement over those not using comments. The methods using feature-biased sentence extraction approach were observed to outperform that using uniform-document approach.

Blog/news search engines are very important channels to reach information about the real-time happenings. In this paper, we study the popular queries collected over one year period and compare their search results returned by a blog search engine (i.e., Technorati) and a news search engine (i.e., Google News). We observed that the numbers of hits returned by the two search engines for the same set of queries were highly correlated, suggesting that blogs often provide commentary to current events reported in news. As many popular queries are related to some events, we further observed a high cohesiveness among the returned search results for these queries.

Wikipedia 1 is a very large and successful Web 2.0 example. As the number of Wikipedia articles and contributors grows at a very fast pace, there are also increasing disputes occurring among the contributors. Disputes often happen in articles with controversial content. They also occur frequently among contributors who are "aggressive" or controversial in their personalities. In this paper, we aim to identify controversial articles in Wikipedia. We propose three models, namely the Basic model and two Controversy Rank (CR) models. These models draw clues from collaboration and edit history instead of interpreting the actual articles or edited content. While the Basic model only considers the amount of disputes within an article, the two Controversy Rank models extend the former by considering the relationships between articles and contributors. We also derived enhanced versions of these models by considering the age of articles. Our experiments on a collection of 19,456 Wikipedia articles shows that the Controversy Rank models can more effectively determine controversial articles compared to the Basic and other baseline models

Evaluation is prevalent in real life. With the advent of Web 2.0, online evaluation has become an important feature in many applications that involve information (e.g., video, photo, and audio) sharing and social networking (e.g., blogging). In these evaluation settings, a set of reviewers assign scores to a set of objects. As part of the evaluation analysis, we want to obtain fair reviews for all the given objects. However, the reality is that reviewers may deviate in their scores assigned to the same object, due to the potential "bias" of reviewers or "controversy" of objects. The statistical approach of averaging deviations to determine bias and controversy assumes that all reviewers and objects should be given equal weight. In this paper, we look beyond this assumption and propose an approach based on the following observations: 1) evaluation is "subjective," as reviewers and objects have varying bias and controversy, respectively, and 2) bias and controversy are mutually dependent. These observations underlie our proposed reinforcement-based model to determine bias and controversy simultaneously. Our approach also quantifies "evidence," which reveals the degree of confidence with which bias and controversy have been derived. This model is shown to be effective by experiments on real-life and synthetic data sets.

Wikipedia has grown to be the world largest and busiest free encyclopedia, in which articles are collaboratively written and maintained by volunteers online. Despite its success as a means of knowledge sharing and collaboration, the public has never stopped criticizing the quality of Wikipedia articles edited by non-experts and inexperienced contributors. In this paper, we investigate the problem of assessing the quality of articles in collaborative authoring of Wikipedia. We propose three article quality measurement models that make use of the interaction data between articles and their contributors derived from the article edit history. Our B asic model is designed based on the mutual dependency between article quality and their author authority. The P eer R eview model introduces the review behavior into measuring article quality. Finally, our P rob R eview models extend P eer R eview with partial reviewership of contributors as they edit various portions of the articles. We conduct experiments on a set of well-labeled Wikipedia articles to evaluate the effectiveness of our quality measurement models in resembling human judgement.

Much existing research on blogs focused on posts only, ignor-ing their comments. Our user study conducted on summa-rizing blog posts, however, showed that reading comments does change one’s understanding about blog posts. In this research, we aim to extract representative sentences from a blog post that best represent the topics discussed among its comments. The proposed solution first derives repre-sentative words from comments and then selects sentences containing representative words. The representativeness of words is measured using ReQuT (i.e., Reader, Quotation, and Topic). Evaluated on human labeled sentences, ReQuT together with summation-based sentence selection showed promising results.

Specialists who analyze online news have a hard time separating the wheat from the chaff. Moreover, automatic data-mining techniques like clustering of news streams into topical groups can fully recover the underlying true class labels of data if and only if all classes are well separated. In reality, especially for news streams, this is clearly not the case. The question to ask is thus this: if we cannot recover the full C classes by clustering, what is the largest K < C clusters we can find that best resemble the K underlying classes? Using the intuition that bursty topics are more likely to correspond to important events that are of interest to analysts, we propose several new bursty vector space models (B-VSM)for representing a news document. B-VSM takes into account the burstiness (across the full corpus and whole duration) of each constituent word in a document at the time of publication. We benchmarked our B-VSM against the classical TFIDF-VSM on the task of clustering a collection of news stream articles with known topic labels. Experimental results show that B-VSM was able to find the burstiest clusters/topics. Further, it also significantly improved the recall and precision for the top K clusters/topics.

Text representation plays a crucial role in classical text mining, where the primary focus was on static text. Nevertheless, well-studied static text representations including TFIDF are not optimized for non-stationary streams of information such as news, discussion board messages, and blogs. We therefore introduce a new temporal representation for text streams based on bursty features. Our bursty text representation differs significantly from traditional schemes in that it 1) dynamically represents documents over time, 2) amplifies a feature in proportional to its burstiness at any point in time, and 3) is topic independent. Our bursty text representation model was evaluated against a classical bag-of-words text representation on the task of clustering TDT3 topical text streams. It was shown to consistently yield more cohesive clusters in terms of cluster purity and cluster/class entropies. This new temporal bursty text representation can be extended to most text mining tasks involving a temporal dimension, such as modeling of online blog pages.

A frequently encountered problem in decision making is the following review problem: review a large number of objects and select a small number of the best ones. An example is selecting conference papers from a large number of submissions. This problem involves two sub-problems: assigning reviewers to each object, and summarizing reviewers' scores into an overall score that supposedly reflects the quality of an object. In this paper, we address the score summarization sub-problem for the scenario where a small number of reviewers evaluate each object. Simply averaging the scores may not work as even a single reviewer could influence the average significantly. We recognize that reviewers are not necessarily on an equal ground and propose the notion of “leniency” to model this difference of reviewers. Two insights underpin our approach: (1) the “leniency” of a reviewer depends on how s/he evaluates objects as well as on how other reviewers evaluate the same set of objects, (2) the “leniency” of a reviewer and the “quality” of objects evaluated exhibit a mutual dependency relationship. These insights motivate us to develop a model that solves both “leniency” and “quality” simultaneously. We study the effectiveness of this model on a real-life dataset.

We consider the problem of analyzing word trajectories in both time and frequency domains, with the specific goal of identifying important and less-reported, periodic and aperiodic words. A set of words with identical trends can be grouped together to reconstruct an event in a completely un-supervised manner. The document frequency of each word across time is treated like a time series, where each element is the document frequency - inverse document frequency (DFIDF) score at one time point. In this paper, we 1) first applied spectral analysis to categorize features for different event characteristics: important and less-reported, periodic and aperiodic; 2) modeled aperiodic features with Gaussian density and periodic features with Gaussian mixture densities, and subsequently detected each feature's burst by the truncated Gaussian approach; 3) proposed an unsupervised greedy event detection algorithm to detect both aperiodic and periodic events. All of the above methods can be applied to time series data in general. We extensively evaluated our methods on the 1-year Reuters News Corpus [3] and showed that they were able to uncover meaningful aperiodic and periodic events.

In this paper, we investigate how deviation in evaluation activities may reveal bias on the part of reviewers and controversy on the part of evaluated objects. We focus on a 'data-centric approach' where the evaluation data is assumed to represent the 'ground truth'. The standard statistical approaches take evaluation and deviation at face value. We argue that attention should be paid to the subjectivity of evaluation, judging the evaluation score not just on 'what is being said' (deviation), but also on 'who says it' (reviewer) as well as on 'whom it is said about' (object). Furthermore, we observe that bias and controversy are mutually dependent, as there is more bias if there is higher deviation on a less controversial object. To address this mutual dependency, we propose a reinforcement model to identify bias and controversy. We test our model on real-life data to verify its applicability.

The emergence of sensor networks enables applications that deploy sensors to collaboratively monitor environment and process data collected. In some scenarios, we are interested in using join queries to correlate data stored in different regions of a sensor network, where the data volume is large, making it prohibitive to transmit all data to a central server for joining. In this paper, we present an in-network synopsis join strategy for evaluating join queries in sensor networks with communication efficiency. In this strategy, we prune data that do not contribute to the join results in the early stage of the join processing, therefore reducing unnecessary communication overhead. In our simulation-based experiments, we study the performance of synopsis join for different join selectivities and investigate the impact synopsis accuracy and message loss. The results show that synopsis join outperforms the centralized join scheme in terms of communication cost, especially for low join selectivities, thus prolonging the lifetime of the sensor network.

Using open source Web editing software (e.g., wiki), online community users can now easily edit, review and publish articles collaboratively. While much useful knowledge can be derived from these articles, content users and critics are often concerned about their qualities. In this paper, we develop two models, namely basic model and peer review model, for measuring the qualities of these articles and the authorities of their contributors. We represent collaboratively edited articles and their contributors in a bipartite graph. While the basic model measures an article's quality using both the authorities of contributors and the amount of contribution from each contributor, the peer review model extends the former by considering the review aspect of article content. We present results of experiments conducted on some Wikipedia pages and their contributors. Our result show that the two models can effectively determine the articles' qualities and contributors' authorities using the collaborative nature of online communities

Abstract Web pages from a Web site can often be associated with concepts in an ontology, and pairs of Web pages also can be associated with relationships between concepts. With such associations, the Web site can be searched, browsed, or even reorganized based on the concept and relationship labels of its Web pages. In this article, we study the link chain extraction problem that is critical to the extraction of Web pages that are related. A link chain is an ordered list of anchor elements linking two Web pages related by some semantic relationship. We propose a link chain extraction method that derives extraction rules for identifying the anchor elements forming the link chains. We applied the proposed method to two well‐structured Web sites and found that its performance in terms of precision and recall is good, even with a small number of training examples.

Abstract Homepages usually describe important semantic information about conceptual or physical entities; hence, they are the main targets for searching and browsing. To facilitate semantic‐based information retrieval (IR) at a Web site, homepages can be identified and classified under some predefined concepts and these concepts are then used in query or browsing criteria, e.g., finding professor homepages containing “information retrieval.” In some Web sites, relationships may also exist among homepages. These relationship instances (also known as homepage relationships) enrich our knowledge about these Web sites and allow more expressive semantic‐based IR. In this article, we investigate the features to be used in mining homepage relationships. We systematically develop different classes of inter‐homepage features, namely, navigation, relative‐location, and common‐item features. We also propose deriving for each homepage a set of support pages to obtain richer and more complete content about the entity described by the homepage. The homepage together with its support pages are known to be a Web unit. By extracting inter‐homepage features from Web units, our experiments on the WebKB dataset show that better homepage relationship mining accuracies can be achieved.

Data broadcast is an attractive data dissemination method in mobile environments. To improve energy efficiency, existing air indexing schemes for data broadcast have focused on reducing tuning time only, i.e., the duration that a mobile client stays active in data accesses. On the other hand, existing broadcast scheduling schemes have aimed at reducing access latency through nonflat data broadcast to improve responsiveness only. Not much work has addressed the energy efficiency and responsiveness issues concurrently. This paper proposes an energy-efficient indexing scheme called MHash that optimizes tuning time and access latency in an integrated fashion. MHash reduces tuning time by means of hash-based indexing and enables nonflat data broadcast to reduce access latency. The design of hash function and the optimization of bandwidth allocation are investigated in depth to refine MHash. Experimental results show that, under skewed access distribution, MHash outperforms state-of-the-art air indexing schemes and achieves access latency close to optimal broadcast scheduling.

In order to organise and manage geospatial and georeferenced information on the Web making them convenient for searching and browsing, a digital portal known as G-Portal has been designed and implemented. Compared to other digital libraries, G-Portal is unique for several of its features. It maintains metadata resources in XML with flexible resource schemas. Logical groupings of metadata resources as projects and layers are possible to allow the entire metadata collection to be partitioned differently for users with different information needs. These metadata resources can be displayed in both the classification-based and map-based interfaces provided by G-Portal. G-Portal further incorporates both a query module and an annotation module for users to search metadata and to create additional knowledge for sharing respectively. G-Portal also includes a resource classification module that categorizes resources into one or more hierarchical category trees based on user-defined classification schemas. This paper gives an overview of the G-Portal design and implementation. The portal features will be illustrated using a collection of high school geography examination-related resources.

Clustering of text collections is generally difficult due to its high dimensionality, heterogeneity, and large size. These characteristics compound the problem of determining the appropriate similarity space for clustering algorithms. Here, we propose to use the spectral analysis of the similarity space of a text collection to predict clustering behavior before actual clustering is performed. Spectral analysis is a technique that has been adopted across different domains to analyze the key encoding information of a system. Using spectral analysis for prediction is useful in first determining the quality of the similarity space and discovering any possible problems the selected feature set may present.

One common approach in hierarchical text classification involves associating classifiers with nodes in the category tree and classifying text documents in a top-down manner. Classification methods using this top-down approach can scale well and cope with changes to the category trees. However, all these methods suffer from blocking which refers to documents wrongly rejected by the classifiers at higher-levels and cannot be passed to the classifiers at lower-levels. We propose a classifier-centric performance measure known as blocking factor to determine the extent of the blocking. Three methods are proposed to address the blocking problem, namely, threshold reduction, restricted voting, and extended multiplicative. Our experiments using support vector machine (SVM) classifiers on the Reuters collection have shown that they all could reduce blocking and improve the classification accuracy. Our experiments have also shown that the Restricted Voting method delivered the best performance.

The importance of data mining is apparent with the advent of powerful data collection and storage tools; raw data is so abundant that manual analysis is no longer possible. Unfortunately, data mining problems are difficult to solve and this prompted the introduction of several novel data structures to improve mining efficiency. Here, we critically examine existing preprocessing data structures used in association rule mining for enhancing performance in an attempt to understand their strengths and weaknesses. Our analyses culminate in a practical structure called the SOTrielT (support-ordered trie itemset) and two synergistic algorithms to accompany it for the fast discovery of frequent itemsets. Experiments involving a wide range of synthetic data sets reveal that its algorithms outperform FP-growth, a recent association rule mining algorithm with excellent performance, by up to two orders of magnitude and, thus, verifying its' efficiency and viability.

In web classification, most researchers assume that the objects to classify are individual web pages from one or more web sites. In practice, the assumption is too restrictive since a web page itself may not always correspond to a concept instance of some semantic concept (or category) given to the classification task. In this paper, we want to relax this assumption and allow a concept instance to be represented by a subgraph of web pages or a set of web pages. We identify several new issues to be addressed when the assumption is removed, and formulate the web unit mining problem. We also propose an iterative web unit mining (iWUM) method that first finds subgraphs of web pages using some knowledge about web site structure. From these web subgraphs, web units are constructed and classified into semantic concepts (or categories) in an iterative manner. Our experiments using the WebKB dataset showed that iWUM improves the overall classification performance and works very well on the more structured parts of a web site.

Abstract Hierarchical text classification or simply hierarchical classification refers to assigning a document to one or more suitable categories from a hierarchical category space. In our literature survey, we have found that the existing hierarchical classification experiments used a variety of measures to evaluate performance. These performance measures often assume independence between categories and do not consider documents misclassified into categories that are similar or not far from the correct categories in the category tree. In this paper, we therefore propose new performance measures for hierarchical classification. The proposed performance measures consist of category similarity measures and distance‐based measures that consider the contributions of misclassified documents. Our experiments on hierarchical classification methods based on SVM classifiers and binary Naïve Bayes classifiers showed that SVM classifiers perform better than Naïve Bayes classifiers on Reuters‐21578 collection according to the extended measures. A new classifier‐centric measure called blocking measure is also defined to examine the performance of subtree classifiers in a top‐down level‐based hierarchical classification method.

We propose a k-NN query processing algorithm that uses one or more window queries to retrieve the nearest neighbors of a given query point. We also propose two different methods to estimate the ranges to be used by the window queries. Each range estimation method requires different statistical knowledge about the spatial databases. Our experiments on the TIGER data allow us to study the behavior of the proposed algorithm using different range estimation methods. Apart from not requiring direct access to the spatial indices, the window queries used in the proposed algorithm can be easily supported by non-spatial database systems containing spatial objects.

The rising popularity of electronic commerce makes data mining an indispensable technology for business competitiveness. The World Wide Web provides abundant raw data in the form of Web access logs, Web transaction logs and Web user profiles. Without data mining tools, it is impossible to make any sense of such massive data. We focus on Web usage mining because it deals most appropriately with understanding user behavioral patterns which is the key to successful customer relationship management. Previous work dealt separately with specific issues of Web usage mining and made assumptions without taking a holistic view and thus, had limited practical applicability. We formulate a novel and more holistic version of Web usage mining termed transactionized logfile mining (TRALOM) to effectively and correctly identify transactions as well as to mine useful knowledge from Web access logs. We also introduce a new data structure, called the WebTrie, to efficiently hold useful preprocessed data so that TRALOM can be done in an online and incremental fashion. Experiments conducted on real Web server logs verify the usefulness and practicality of our proposed techniques.

While much research has been devoted to data modeling, little attention has been paid to developing constructs for modeling micro-objects, i.e. constructs for modeling low dimension objects such as the attribute Birth_Date and the data type Boolean. Most data models consider attributes as functions of macro-objects (i.e. objects formed from constructs such as entity sets, relations, and object sets). For example, the attribute Birth_Date is often modeled as a function of the entity set Person. This research proposes a Conceptual Micro-Object Model (CMoM), which considers the attribute as the foundation of data modeling. Other constructs such as the Conceptual Data Type Primitive (CDTP) and Attribute Group (AG) are developed to model the constituent components of attributes and objects that can be formed from attributes respectively. CMoM is useful for modeling intricate micro-objects such as dates. It also allows one to identify and resolve redundancy between conceptual macro-objects such as those modeled as entity sets and relations. For example, redundancies between attributes in different relations can be detected. Finally, it facilitates a formal foundation for defining object-oriented concepts such as inheritance, aggregation, and encapsulation.

In any electronic commerce system, the heterogeneity of product descriptions is a critical impediment to efficient business information exchange. In the ABECOS electronic commerce system, buyer agents, seller agents, and directory agents liaise with one another in e-commerce activities. Only when agents have a common ontology of product descriptions (also called product schemas) are they able to interact seamlessly in e-commerce activities. This gives rise to the product schema integration problem (PSI); the problem of integrating heterogeneous schemas of a certain product into one globally compatible schema. We adopt an integration approach based on product attribute synonyms. We give a formal definition of the problem and show that it is NP-complete. We contrast our approach of study to conventional schema integration in federated databases. We also propose a set of approximate algorithms for PSI and evaluate their performance.

The popularity of WWW has made it a prime vehicle for disseminating information. Compared to pure static and dynamic Web pages which are dynamically created by a CGI script at run-time, we focus on semi-dynamic Web pages whose contents are extracted from source databases and they change in response to updates to the source databases. An example of such a page can be found at http://www.fish.com.sg where a list of stock information is refreshed frequently with respect to updates to base data. A crucial problem arises when base data change frequently and there is a need to keep a large set of semi-dynamic pages up-to-date in response to source changes since no one is interested in stale data on the Web; an investor may suffer great losses relying on obsolete stock price on the Web. To differentiate between the contents derived from base data and the trivial contents of a Web page, we refer to that portion of a page derived from base data as a Web view.

Hierarchical classification refers to the assignment of one or more suitable categories from a hierarchical category space to a document. While previous work in hierarchical classification focused on virtual category trees where documents are assigned only to the leaf categories, we propose a top-down level-based classification method that can classify documents to both leaf and internal categories. As the standard performance measures assume independence between categories, they have not considered the documents incorrectly classified into categories that are similar to or not far from correct ones in the category tree. We therefore propose category-similarity measures and distance-based measures to consider the degree of misclassification in measuring the classification performance. An experiment has been carried out to measure the performance of our proposed hierarchical classification method. The results showed that our method performs well for a Reuters text collection when enough training documents are given and the new measures have indeed considered the contributions of misclassified documents.

Advances in wireless technology increase the number of mobile device users and give pace to the rapid development of e-commerce using these devices. The new type of e-commerce, conducting transactions via mobile terminals, is called mobile commerce. Due to its inherent characteristics such as ubiquity, personalization, flexibility, and dissemination, mobile commerce promises businesses unprecedented market potential, great productivity, and high profitability. This paper presents an overview of mobile commerce development by examining the enabling technologies, the impact of mobile commerce on the business world, and the implications to mobile commerce providers. The paper also provides an agenda for future research in the area.

Although much work has been done on WWW information management, research in keeping information on Web sites up-to-date is still in its infancy. For a very large Web site whose content is derived from some source databases, it is important to maintain its freshness in response to changes to the base data. This issue is particularly significant for Web sites presenting fast-changing information, such as stock exchange information and product information. In this paper, we propose a model for studying the problem of refreshing a very large Web site in time. We identify several important research issues in maintaining the currency of information on such Web sites. We also discuss possible approaches to the timely refreshing of a Web site under the framework.

A query routing broker is a software agent that determines from a large set of accessing information sources the ones most relevant to a user's information need. As the number of information sources on the Internet increases dramatically, future users will have to rely on query routing brokers to decide a small number of information sources to query without incurring too much query processing overheads. In this paper, we describe a query routing broker known as ZBroker developed for bibliographic database servers that support the Z39.50 protocol. ZBroker samples the content of each bibliographic database by using training queries and their results, and summarizes the bibliographic database content into a knowledge base. We present the design and implementation of ZBroker and describe its Web-based user interface.

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.

The main purpose of a digital library is to facilitate users easy access to enormous amount of globally networked information. Typically, this information includes preexisting public library catalog data, digitized document collections, and other databases. In this article, we describe the distributed query system of a digital library prototype system known as HARP. In the HARP project, we have designed and implemented a distributed query processor and its query front-end to support integrated queries to preexisting public library catalogs and structured databases. This article describes our experiences in the design of an extended Sequel (SQL) query language known as HarpSQL. It also presents the design and implementation of the distributed query system. Our experience in distributed query processor and user interface design and development will be highlighted. We believe that our prototyping effort will provide useful lessons to the development of a complete digital library infrastructure.

Resolving domain incompatibility among independently developed databases often involves uncertain information. DeMichiel (1989) showed that uncertain information can be generated by the mapping of conflicting attributes to a common domain, based on some domain knowledge. We show that uncertain information can also arise when the database integration process requires information not directly represented in the component databases, but can be obtained through some summary of data. We therefore propose an extended relational model based on Dempster-Shafer theory of evidence to incorporate such uncertain knowledge about the source databases. The extended relation uses evidence sets to represent uncertainty in information, which allow probabilities to be attached to subsets of possible domain values. We also develop a full set of extended relational operations over the extended relations. In particular, an extended union operation has been formalized to combine two extended relations using Dempster's rule of combination. The closure and boundedness properties of our proposed extended operations are formulated. We also illustrate the use of extended operations by some query examples.

Resolving domain incompatibility among independently developed databases often involves uncertain information. DeMichiel (1989) showed that uncertain information can be generated by the mapping of conflicting attributes to a common domain, based on some domain knowledge. The authors show that uncertain information can also arise when the database integration process requires information not directly represented in the component databases, but can be obtained through some summary of data. They therefore propose an extended relational model based on Dempster-Shafer theory of evidence (1976) to incorporate such uncertain knowledge about the source databases. They also develop a full set of extended relational operations over the extended relations. In particular, an extended union operation has been formalized to combine two extended relations using Dempster's rule of combination. The closure and boundedness properties of the proposed extended operations are formulated.>

No abstract available.

Ahmet Cosar, Ee-Peng Lim, Jaideep SrivastavaDepartmentof Computer ScienceUniversity of MinnesotaMinneapolis, MN 55455AbstractIn certain database applications such as deductivedatabases, batch query processing, and recursive queryprocessing etc., a single query can be transformed into aset ofclosely related database queries. Great benefits canbe obtained by executing a group of related queries all to-gether in a single unijied multi-plan instead of executingeach query separately. In order to achieve this, MultipleQuery Optimization (MQO) identifies common task(s)(e.g. common subezpressions, joins, etc.) among a setof query plans and creates a single unified plan (multi-plan) which can be executed to obtain the required out-puts forall queries at once. In this paper, anew heuris-tic function (f=), dynamic query ordering heuristics,and Depth-First Branch-and-Bound (DFBB) are de-jined and experimentally evaluated, and compared withexisting methods which use A* and static query order-ing. Our experiments show that all three of f., DFBB,and dynamic query ordering help to improve the perfor-mance of our h4Q0 algorithm.1 IntroductionThe objective of multiple query optimization (MQO)is to exploit the benefits of sharing common tasks inthe access plans for a group of queries. In certaindatabase applications, e.g. deductive query processing,batch query processing and recursive query processing,often a group of queries are submitted together to theDBMS for execution. The traditional approach of pro-cessing queries one at a time will be inefficient espe-cially when there is a high number of queries sharingPermission to copy without fee all or part of this materisi isgmnted provided that the copies m. not mad. or distributed fordirect commercial advantage, tha ACM copyright notica and thatitla of tha publication and ita data appaar, and

this paper, we have selected a minimal set of core operations that includes the set of relational operations, i.e. foe,ß,1,\\Gamma,[g, as well as three other operators which are useful in specifying the federated views. These are 2-way Outerjoin Operator (

The objective of entity identification is to determine the correspondence between object instances from more than one database. Entity identification at the instance level, assuming that schema level heterogeneity has been resolved a priori, is examined. Soundness and completeness are defined as the desired properties of any entity identification technique. To achieve soundness, a set of identity and distinctness rules are established for entities in the integrated world. The use of extended key, which is the union of keys, and possibly other attributes, from the relations to be matched, and its corresponding identify rule are proposed to determine the equivalence between tuples from relations which may not share any common key. Instance level functional dependencies (ILFD), a form of semantic constraint information about the real-world entities, are used to derive the missing extended key attribute values of a tuple.>