Generative AI is being increasingly integrated into web search for the convenience it provides users. In this work, we aim to understand how generative AI disrupts web search by retrieving and presenting the information and sources differently from traditional search engines. We introduce a public benchmark dataset of 11,500 user queries to support our study and future research of generative search. We compare the search results returned by Google's search engine, the accompanying AI Overview (AIO), and Gemini Flash 2.5 for each query. We have made several key findings. First, we find that for 51.5% of representative, real-user queries, AIOs are generated, and are displayed above the organic search results. Controversial questions frequently result in an AIO. Second, we show that the retrieved sources are substantially different for each search engine (<0.2 average Jaccard similarity). Traditional Google search is significantly more likely to retrieve information from popular or institutional websites in government or education, while generative search engines are significantly more likely to retrieve Google-owned content. Third, we observe that websites that block Google's AI crawler are significantly less likely to be retrieved by AIOs, despite having access to the content. Finally, AIOs are less consistent when processing two runs of the same query, and are less robust to minor query edits. Our findings have important implications for understanding how generative search impacts website visibility, the effectiveness of generative engine optimization techniques, and the information users receive. We call for revenue frameworks to foster a sustainable and mutually beneficial ecosystem for publishers and generative search providers.

Clinical notes provide a wealth of patient information that is valuable for predicting clinical outcomes. In particular, predicting hospital 30-day readmission is important to improve healthcare outcomes and reduce cost. Previous works on outcome prediction using clinical notes overlook complex semantic compositions and syntactic structure when learning the note level embedding, which may fail to capture the note semantics and make accurate predictions.

This paper presents a study of GDPR compliance under the Interactive Advertising Bureau Europe's Transparency and Consent Framework (TCF). This framework provides digital advertising market participants a standard for sharing users' privacy consent choices. TCF is widely used across the Internet, and this paper presents a thorough experimental evaluation of both the compliance of websites with TCF and its impact on user privacy. We reviewed 2,230 websites that use TCF and accepted the automatic decline of user consent by our data collection system. Unlike previous work on GDPR compliance, we found that most websites using TCF properly record the user's consent choice. However, we found that 72.8% of the websites that were TCF compliant claimed legitimate interest as a rationale for overriding the consent choice. While legitimate interest is legal under GDPR, previous studies have shown that most users disagreed with how it is being used to collect data. Additionally, analysis of cookies set to the browsers indicates that TCF may not fully protect user privacy even when websites are compliant. Our research provides regulators and publishers with a data collection and analysis system to monitor compliance, detect non-compliance, and examine questionable practices of circumventing user consent choices using legitimate interest.

Online publishers typically sell ad impressions through auctions held in ad exchanges in real-time, i.e., real-time bidding (RTB). A publisher will accept the winning bid if it is higher than a given reserve price for an ad impression. Setting an appropriate reserve price for an ad impression is critical for publishers’ revenue generation, but also challenging. While this problem has been studied for second-price auctions, it lacks studies for first-price auctions, the de facto industry standard since 2019. This paper proposes a machine learning model that determines the optimal reserve prices for individual ad impressions in real-time. It uses a multi-task learning framework to predict the lower bounds of the highest bids with a coverage probability, using only the data available to publishers. The experiments using data from a large international publisher show that the proposed model outperforms the comparison systems on generating revenue.

The fast increase in ad-blocker usage has resulted in significant revenue loss for online publishers. To mitigate this, many publishers implement the Wall strategy, where an adblock user is asked to whitelist the intended webpage. If the user refuses, the result is a loss-loss situation: the user is denied access to content, and the publisher cannot receive revenue. An alternative strategy, called AAX, is to show only acceptable ads to users. However, acceptable ads generate less revenue than regular ads. This article proposes personalized counter ad-blocking that dynamically chooses a counter ad-blocking strategy for individual users. To implement it, we propose a novel deep learning-based whitelist prediction model. Adblock users predicted to whitelist a page receive the Wall strategy; the others receive the AAX strategy. The proposed Deep Ad-Block Whitelist Network (DAWN) for whitelist prediction captures page characteristics, user interests in pages and their sensitivity to ads, reflected in historic behavior, using a deep learning mechanism. Furthermore, DAWN leverages multi-task learning on whitelist prediction and dwell-time prediction to boost performance. DAWN's effectiveness is validated on a real-world dataset provided by Forbes Media. The experimental results demonstrate the advantages of the proposed counter ad-blocking policy over existing policies on revenue generation and user engagement.

Fine-grained location prediction on smart phones can be used to improve app/system performance. Application scenarios include video quality adaptation as a function of the 5G network quality at predicted user locations, and augmented reality apps that speed up content rendering based on predicted user locations. Such use cases require prediction error in the same range as the GPS error, and no existing works on location prediction can achieve this level of accuracy. We propose Federated Meta-Location Learning (FMLL) on smart phones for fine-grained location prediction, based on GPSt races collected on the phones. FMLL has three components: a meta-location generation module, a prediction model, and a federated learning framework. The meta-location generation module represents the user location data as relative points in an abstract 2D space, which enables learning across different physical spaces. The model fuses Bidirectional Long Short-Term Memory (BiLSTM) and Convolutional Neural Networks (CNN), where BiLSTM learns the speed and direction of the mobile users, and CNN learns information such as user movement preferences. The framework runs on the phones of the users and also on a server that coordinates learning from all users in the system. FMLL uses federated learning to protect user privacy and reduce bandwidth consumption. Our experimental results, using a dataset with over 600,000 users, demonstrate that FMLL outperforms baseline models in terms of prediction accuracy. We also demonstrate that FMLL works well in conjunction with transfer learning, which enables model reusability. Finally, benchmark results on Android phones demonstrate FMLL’s feasibility in real life.

Adverse drug events (ADEs) are a serious health problem that can be life-threatening. While a lot of work on detecting correlation between a drug and an ADE, limited studies have been conducted on personalized ADE risk prediction. Avoiding the drugs with high likelihood of causing severe ADEs helps physicians to provide safer treatments to patients. The goal of this study is to assess personalized ADE risks that a target drug may induce on a target patient, based on patient medical history recorded in claim codes, which provide information about diagnosis, drugs taken, related medical supplies besides billing information. We developed a HTNNR model (Hierarchical Time-aware Neural Network for ADE Risk) that captures characteristics of claim codes and their relationship. Eempirical evaluation shows that the proposed HTNNR model substantially outperforms the comparison methods.

Traditional page recommendation models are endangered by stricter privacy regulations, such as the General Data Protection Regulation (GDPR). The performance of these models suffer when only a part of the users share their personal data, such as cookies, with web servers, while the rest of the users choose to opt-out from sharing these data. Furthermore, these models are not designed to provide recommendations for users who do not share their data. This paper addresses the question of how to provide good page recommendations to all users, independent of their privacy attitudes. We propose Fed4Rec, a privacy-preserving framework for page recommendation based on federated learning (FL) and model-agnostic meta-learning (MAML), which allows machine learning models to train on data collected from both public users, who share data with the server, and private users, who do not share data with the server. Fed4Rec enables recommendations for both public users, computed at the server, and private users, computed at their local devices. Private users' data are stored only on user devices and never shared with the server. FL is used to train on local data, and Fed4Rec shares with the server only partial model parameters, computed on local devices. MAML is used to jointly train on the public data and the model parameters from the private users. We compare Fed4Rec against several baseline frameworks, using a publicly available dataset from a large news portal. The results show that Fed4Rec outperforms the baselines in terms of recommendation accuracy. We also conduct one ablation study to examine the impact of varying the ratio between the number of public and private users. Fed4Rec performs better than the baselines for all ratios, but it is especially beneficial w hen t he p ercentage of public users is low.

Online health communities (OHCs) provide a popular channel for users to seek information, suggestions and support during their medical treatment and recovery processes. To help users find relevant information easily, we present CLIR, an effective system for recommending relevant discussion threads to users in OHCs. We identify that thread content and user interests can be categorized in two dimensions: topics and concepts. CLIR leverages Latent Dirichlet Allocation model to summarize the topic dimension and uses Convolutional Neural Network to encode the concept dimension. It then builds a thread neural network to capture thread characteristics and builds a user neural network to capture user interests by integrating these two dimensions and their interactions. Finally, it matches the target thread's characteristics with candidate users' interests to make recommendations. Experimental evaluation with multiple OHC datasets demonstrates the performance advantage of CLIR over the state-of-the-art recommender systems on various evaluation metrics.

Online Health Communities (OHCs) provide a platform for patients, caregivers, and researchers to exchange information and support each other. Identifying information that describes patient health experiences in OHCs has many important applications, such as trustworthy knowledge discovery and recommendation. To identify patient experience description, we observe that the same word may have different strengths as an indicator of patient experiences when written by different users. Based on this observation, we propose a User-Word Context Vector model, that holistically captures linguistic features of text, user information and context information to classify patient experiences in OHCs. Experimental evaluation shows that the proposed method significantly outperforms the existing methods on patient experience classification.

The fast growing ad-blocker usage results in large revenue decrease for ad-supported online websites. Facing this problem, many online publishers choose either to cooperate with ad-blocker software companies to show acceptable ads or to build a wall that requires users to whitelist the site for content access. However, there is lack of studies on the impact of these two counter-ad-blocking strategies on user behaviors. To address this issue, we conduct a randomized field experiment on the website of Forbes Media, a major US media publisher. The ad-blocker users are divided into a treatment group, which receives the wall strategy, and a control group, which receives the acceptable ads strategy. We utilize the difference-in-differences method to estimate the causal effects. Our study shows that the wall strategy has an overall negative impact on user engagements. However, it has no statistically significant effect on high-engaged users as they would view the pages no matter what strategy is used. It has a big impact on low-engaged users, who have no loyalty to the site. Our study also shows that revisiting behavior decreases over time, but the ratio of session whitelisting increases over time as the remaining users have relatively high loyalty and high engagement. The paper concludes with discussions of managerial insights for publishers when determining counter-ad-blocking strategies.

The fast increase in ad blocker usage results in large revenue loss for online publishers and advertisers. Many publishers initialize counter-ad-blocking strategies, where a user has to choose either whitelisting the publisher's web site in their ad blocker or leaving the site without accessing the content. This paper aims to predict the user whitelisting behavior, which can help online publishers to better assess users' interests and design corresponding strategies. We present several techniques for personalized whitelist prediction for a target user and a target web page. Our prediction models are evaluated on real-world data provided by a large online publisher, Forbes Media. The best prediction performance was achieved using the gradient boosting regression tree model, which also demonstrated robustness and efficiency.

The revenue of online display advertising in the U.S. is projected to be 7.9 billion U.S. dollars by 2022. One main way of display advertising is through real-time bidding (RTB). In RTB, an ad exchange runs a second price auction among multiple advertisers to sell each ad impression. Publishers usually set up a reserve price, the lowest price acceptable for an ad impression. If there are bids higher than the reserve price, then the revenue is the higher price between the reserve price and the second highest bid; otherwise, the revenue is zero. Thus, a higher reserve price can potentially increase the revenue, but with higher risks associated. In this paper, we study the problem of estimating the failure rate of a reserve price, i.e., the probability that a reserve price fails to be outbid. The solution to this problem have managerial implications to publishers to set appropriate reserve prices in order to minimizes the risks and optimize the expected revenue. This problem is highly challenging since most publishers do not know the historical highest bidding prices offered by RTB advertisers. To address this problem, we develop a parametric survival model for reserve price failure rate prediction. The model is further improved by considering user and page interactions, and header bidding information. The experimental results demonstrate the effectiveness of the proposed approach.

Display advertising is the most important revenue source for publishers in the online publishing industry. The ad pricing standards are shifting to a new model in which ads are paid only if they are viewed. Consequently, an important problem for publishers is to predict the probability that an ad at a given page depth will be shown on a user's screen for a certain dwell time. This paper proposes deep learning models based on Long Short-Term Memory (LSTM) to predict the viewability of any page depth for any given dwell time. The main novelty of our best model consists in the combination of bi-directional LSTM networks, encoder-decoder structure, and residual connections. The experimental results over a dataset collected from a large online publisher demonstrate that the proposed LSTM-based sequential neural networks outperform the comparison methods in terms of prediction performance.

Archiving graph data over history is demanded in many applications, such as social network and bibliographies. Typically, people are interested in querying temporal graphs. Existing keyword search approaches for graph-structured data are insufficient for querying temporal graphs. This paper initiates the study of supporting keyword-based queries on temporal graphs. We propose a search syntax that is an extension of keyword search, which allows casual users to easily search temporal graphs with temporal predicates and ranking functions. To generate results efficiently, we propose a best path iterator, which finds the "best" paths between two data nodes in each snapshot regarding to three ranking factors. We develop algorithms that efficiently generate top-k query results. Extensive experiments verified the efficiency and effectiveness of our approach.

Recommender systems are changing the way that people find information, products, and even other people. This paper studies the problem of leveraging the context of the items presented to the user in a user/system interaction session to improve the recommender system's ranking prediction. We propose a novel model that incorporates the opportunity cost of giving up the other items in the session and computes session‐specific relevance values for items for context‐aware recommendation. The model can work on a variety of different problems settings with emphasis on implicit user feedback as it supports varying levels of ordinal relevance. Experimental evaluation demonstrates the advantages of our new model with respect to the ranking quality.

Adverse Drug Reactions (ADRs) have become a serious health problem and even a leading cause of death in the United States. Pre‐marketing clinical trials and traditional post‐marketing surveillance using voluntary and spontaneous report systems are insufficient for ADR detection. On the other hand, online health forums provide valuable evidences in a large scale and in a timely fashion through the active participation of patients, caregivers, and doctors. In this article, we present patient‐centered and experience‐aware mining framework for effective ADR discovery using online health forum data. Our experimental evaluation with both an official ADR knowledge base and human‐annotated ground truth verifies the effectiveness of the proposed method for ADR discovery.

A half of online display ads are not rendered viewable because the users do not scroll deep enough or spend sufficient time at the page depth where the ads are placed. In order to increase the marketing efficiency and ad effectiveness, there is a strong demand for viewability prediction from both advertisers and publishers. This paper aims to predict the dwell time for a given triplet based on historic data collected by publishers. This problem is difficult because of user behavior variability and data sparsity. To solve it, we propose predictive models based on Factorization Machines and Field‐aware Factorization Machines in order to overcome the data sparsity issue and provide flexibility to add auxiliary information such as the visible area of a user's browser. In addition, we leverage the prior dwell time behavior of the user within the current page view, that is, time series information, to further improve the proposed models. Experimental results using data from a large web publisher demonstrate that the proposed models outperform comparison models. Also, the results show that adding time series information further improves the performance.

Social networks have become a vital mechanism to disseminate information to friends and colleagues. But the dynamic nature of information and user connectivity within these networks raised many new and challenging research problems. One of them is the query-related topic search in social networks. In this work, we investigate the important problem of the personalized influential topic search. There are two challenging questions that need to be answered: how to extract the social summarization of the social network so as to measure the topics' influence at the similar granularity scale? and how to apply the social summarization to the problem of personalized influential topic search. Based on the evaluation using real-world datasets, our proposed algorithms are proved to efficient and effective.

Archiving graph data over history is demanded in many applications, such as social network studies, collaborative projects, scientific graph databases, and bibliographies. Typically people are interested in querying temporal graphs. Existing keyword search approaches for graph-structured data are insufficient for querying temporal graphs. This paper initiates the study of supporting keyword-based queries on temporal graphs. We propose a search syntax that is a moderate extension of keyword search, which allows casual users to easily search temporal graphs with optional predicates and ranking functions related to timestamps. To generate results efficiently, we first propose a best path iterator, which finds the paths between two data nodes in each snapshot that is the “best” with respect to three ranking factors. It prunes invalid or inferior paths and maximizes shared processing among different snapshots. Then, we develop algorithms that efficiently generate top-k query results. Extensive experiments verified the efficiency and effectiveness of our approach.

Online display advertising has becomes a billion-dollar industry, and it keeps growing. Advertisers attempt to send marketing messages to attract potential customers via graphic banner ads on publishers' webpages. Advertisers are charged for each view of a page that delivers their display ads. However, recent studies have discovered that more than half of the ads are never shown on users' screens due to insufficient scrolling. Thus, advertisers waste a great amount of money on these ads that do not bring any return on investment. Given this situation, the Interactive Advertising Bureau calls for a shift toward charging by viewable impression, i.e., charge for ads that are viewed by users. With this new pricing model, it is helpful to predict the viewability of an ad. This paper proposes two probabilistic latent class models (PLC) that predict the viewability of any given scroll depth for a user-page pair. Using a real-life dataset from a large publisher, the experiments demonstrate that our models outperform comparison systems.

The amount of time spent by users at specific page depths within webpages, called dwell time, can be used by web publishers to decide where to place online ads and what type of ads to place at different depths within a webpage. This paper presents a model to predict the dwell time for a given "user, webpage, depth" triplet based on historic data collected by publishers. Dwell time prediction is difficult due to user behavior variability and data sparsity. We adopt the Factorization Machines model because it is able to capture the interaction between users and webpages, overcome the data sparsity issue, and provide flexibility to add auxiliary information such as the visible area of a user's browser. Experimental results using data from a large web publisher demonstrate that our model outperforms deterministic and regression-based comparison models.

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

As a massive industry, display advertising delivers advertisers' marketing messages to attract customers through graphic banners on webpages. Advertisers are charged by ad serving, where their ads are shown in web pages. However, recent studies show that about half of the ads were actually never seen by users because they do not scroll deep enough to bring the ads in-view. Thus, the ad pricing standards are shifting to a new model: ads are paid if they are in view, not just being served. To the best of our knowledge, this paper is the first to address the important problem of ad viewability prediction which can improve the performance of guaranteed ad delivery, real-time bidding, as well as recommender systems. We analyze a real-life dataset from a large publisher, identify a number of features that impact the scroll depth for a given user and a page, and propose a probabilistic latent class model that predicts the viewability of any given scroll depth for a user-page pair. The experiments demonstrate that our model outperforms comparison systems based on singular value decomposition and logistic regression, in terms of prediction quality and training time.

Recent efforts in data cleaning of structured data have focused exclusively on problems like data deduplication, record matching, and data standardization; none of these focus on fixing incorrect attribute values in tuples. Correcting values in tuples is typically performed by a minimum cost repair of tuples that violate static constraints like CFDs (which have to be provided by domain experts, or learned from a clean sample of the database). In this paper, we provide a method for correcting individual attribute values in a structured database using a Bayesian generative model and a statistical error model learned from the noisy database directly. We thus avoid the necessity for a domain expert or clean master data. We also show how to efficiently perform consistent query answering using this model over a dirty database, in case write permissions to the database are unavailable. We evaluate our methods over both synthetic and real data.

Decision support and knowledge discovery systems often compute aggregate values of interesting attributes by processing a huge amount of data in very large databases and/or warehouses. In particular, iceberg query is a special type of aggregation query that computes aggregate values above a user-provided threshold. Usually, only a small number of results will satisfy the threshold constraint. Yet, the results often carry very important and valuable business insights. Because of the small result set, iceberg queries offer many opportunities for deep query optimization. However, most existing iceberg query processing algorithms do not take advantage of the small-result-set property and rely heavily on the tuple-scan-based approach. This incurs intensive disk accesses and computation, resulting in long processing time especially when data size is large. Bitmap index, which builds one bitmap vector for each attribute value, is gaining popularity in both column-oriented and row-oriented databases in recent years. It occupies less space than the raw data and gives opportunities for more efficient query processing. In this paper, we exploited the property of bitmap index and developed a very effective bitmap pruning strategy for processing iceberg queries. Our index-pruning-based approach eliminates the need of scanning and processing the entire data set (table) and thus speeds up the iceberg query processing significantly. Experiments show that our approach is much more efficient than existing algorithms commonly used in row-oriented and column-oriented databases.

Information extraction systems are traditionally implemented as a pipeline of special-purpose processing modules targeting the extraction of a particular kind of information. A major drawback of such an approach is that whenever a new extraction goal emerges or a module is improved, extraction has to be reapplied from scratch to the entire text corpus even though only a small part of the corpus might be affected. In this paper, we describe a novel approach for information extraction in which extraction needs are expressed in the form of database queries, which are evaluated and optimized by database systems. Using database queries for information extraction enables generic extraction and minimizes reprocessing of data by performing incremental extraction to identify which part of the data is affected by the change of components or goals. Furthermore, our approach provides automated query generation components so that casual users do not have to learn the query language in order to perform extraction. To demonstrate the feasibility of our incremental extraction approach, we performed experiments to highlight two important aspects of an information extraction system: efficiency and quality of extraction results. Our experiments show that in the event of deployment of a new module, our incremental extraction approach reduces the processing time by 89.64 percent as compared to a traditional pipeline approach. By applying our methods to a corpus of 17 million biomedical abstracts, our experiments show that the query performance is efficient for real-time applications. Our experiments also revealed that our approach achieves high quality extraction results.

Studies show that about 50% of Web search is for information exploration purposes, where a user would like to investigate, compare, evaluate, and synthesize multiple relevant results. Due to the absence of general tools that can effectively analyze and differentiate multiple results, a user has to manually read and comprehend potential large results in an exploratory search. Such a process is time consuming, labor intensive and error prone. Interestingly, we find that the metadata information embedded in structured data provides a potential for automating or semi-automating the comparison of multiple results. In this article we present an approach for structured data search result differentiation. We define the differentiability of query results and quantify the degree of difference. Then we define the problem of identifying a limited number of valid features in a result that can maximally differentiate this result from the others, which is proved NP-hard. We propose two local optimality conditions, namely single-swap and multi-swap, and design efficient algorithms to achieve local optimality. We then present a feature type-based approach, which further improves the quality of the features identified for result differentiation. To show the usefulness of our approach, we implemented a system CompareIt, which can be used to compare structured search results as well as any objects. Our empirical evaluation verifies the effectiveness and efficiency of the proposed approach.

Database evolution is the process of updating the schema of a database or data warehouse (schema evolution) and evolving the data to the updated schema (data evolution). It is often desired or necessitated when changes occur to the data or the query workload, the initial schema was not carefully designed, or more knowledge of the database is known and a better schema is concluded. The Wikipedia database, for example, has had more than 170 versions in the past 5 years [8]. Unfortunately, although much research has been done on the schema evolution part, data evolution has long been a prohibitively expensive process, which essentially evolves the data by executing SQL queries and re-constructing indexes. This prevents databases from being flexibly and frequently changed based on the need and forces schema designers, who cannot afford mistakes, to be highly cautious. Techniques that enable efficient data evolution will undoubtedly make life much easier.

Empowering users to access databases using simple keywords can relieve users from the steep learning curve of mastering a structured query language and understanding complex and possibly fast-evolving data schemas. In this tutorial, we give an overview of the state-of-the-art techniques for supporting keyword-based search and exploration on databases. Several topics will be discussed, including query result definition, ranking functions, result generation and top-k query processing, snippet generation, result clustering, result comparison, query cleaning and suggestion, performance optimization, and search quality evaluation. Various data models will be discussed, including relational data, XML data, graph-structured data, data streams, and workflows. Finally we identify the challenges and opportunities for future research to advance the field.

Provenance in scientific workflows is a double-edged sword. On the one hand, recording information about the module executions used to produce a data item, as well as the parameter settings and intermediate data items passed between module executions, enables transparency and reproducibility of results. On the other hand, a scientific workflow often contains private or confidential data and uses proprietary modules. Hence, providing exact answers to provenance queries over all executions of the workflow may reveal private information. In this paper we discuss privacy concerns in scientific workflows -- data, module, and structural privacy - and frame several natural questions: (i) Can we formally analyze data, module, and structural privacy, giving provable privacy guarantees for an unlimited/bounded number of provenance queries? (ii) How can we answer search and structural queries over repositories of workflow specifications and their executions, providing as much information as possible to the user while still guaranteeing privacy? We then highlight some recent work in this area and point to several directions for future work.

Query expansion is a functionality of search engines that suggests a set of related queries for a user-issued keyword query. Typical corpus-driven keyword query expansion approaches return popular words in the results as expanded queries. Using these approaches, the expanded queries may correspond to a subset of possible query semantics, and thus miss relevant results. To handle ambiguous queries and exploratory queries, whose result relevance is difficult to judge, we propose a new framework for keyword query expansion: we start with clustering the results according to user specified granularity, and then generate expanded queries, such that one expanded query is generated for each cluster whose result set should ideally be the corresponding cluster. We formalize this problem and show its APX-hardness. Then we propose two efficient algorithms named iterative single-keyword refinement and partial elimination based convergence, respectively, which effectively generate a set of expanded queries from clustered results that provides a classification of the original query results. We believe our study of generating an optimal query based on the ground truth of the query results not only has applications in query expansion, but has significance for studying keyword search quality in general.

WITH the prevalence of Web search engines, keyword search has become the most popular way for users to retrieve information from text documents. On the other hand, there is an enormous amount of valuable information stored in structured form (relational or semistructured) in Internet, intranet, and enterprise databases. To query such data sources, users traditionally depended on specialized applications because for most users it is difficult to use structured or semistructured query languages. In recent years, enterprise search has gained popularity where a keyword-based search model is used for intranet data sources. However, in most of these systems, the structured data objects that can be retrieved via keyword search have to be predefined. The database research community has been focusing on developing some of the key technology that holds the promise of generalizing the reach of keyword search over structured and semistructured data beyond the state of the practice in commercial enterprise search engines. Some of the problems that have received attention include the task of automatically assembling a data object on the fly in response to a keyword search query over structured or semistructured data, designing an appropriate ranking function, and supporting top-k retrieval efficiently for the ranking functions. This special section of the IEEE Transactions on Knowledge and Data Engineering (TKDE) features a collection of four papers, selected from 16 submissions, representing recent advances in keyword search on structured data. These works present novel techniques for searching relational databases, text-rich databases, as well as XML data. The first paper, “SPARK2: Top-k Keyword Query in Relational Databases” by Yi Luo, Wei Wang, Xuemin Lin, Xiaofang Zhou, Jianmin Wang, ang Keqiu Li addresses the effectiveness and efficiency challenges of keyword search on relational databases. The authors propose a new ranking method that adapts the state-of-the-art IR ranking principles for keyword search over structured data. However, in generating top-k ranked results efficiently, the nonmonotonic nature of this ranking function renders known top-k query processing techniques inapplicable. To address the challenge, the authors propose a set of efficient top-k query processing algorithms for this ranking method that minimize database probing by leveraging novel score upper bounding functions. In the second paper, “Finding Top-k Answers in Keyword Search over Relational Databases Using Tuple Units,” Jianhua Feng, Guoliang Li, and Jianyong Wang use indexes to record joined tuples (named as tuple units) in the databases. In contrast to existing work where a query result is a single tuple unit, this paper allows multiple related tuple units to be leveraged to answer a keyword query to improve search quality. To enhance the performance, the authors propose two indexes that capture relationships between different tuple units, and then develop new ranking techniques and algorithms to progressively find the top-k query results. The third paper is “Efficient Keyword-Based Search for Top-K Cells in Text Cube” by Bolin Ding, Bo Zhao, Cindy Xide Lin, Jiawei Han, Chengxiang Zhai, Ashok Srivastava, and Nikunj C. Oza. It focuses on the scenario where the repository contains both structured and text data. Specifically, it studies the problem of keyword search in text cube, built on a multidimensional text database where each row is associated with a document and several structured dimensions. Unlike existing work where an individual document or a (joined) tuple is a query result, this work considers a cell as a query result. Given a keyword query, the goal of this paper is to find the top-k most relevant cells. The authors develop an IR-style relevance model for ranking cells, and then propose efficient algorithms to address the computational challenge due to the large number of cells in a text cube. The final paper in this special section, “Returning Clustered Results for Keyword Search on XML Documents” by Xiping Liu, Changxuan Wan, and Lei Chen, presents a new semantics for answering keyword queries on XML data and techniques to generate clustered search results. The authors propose an efficient algorithm that clusters results on-the-fly by first generating cluster labels and then clustered results. Furthermore, they propose a technique that constructs a cluster hierarchy that is interpretable and provides a general-to-specific view of the results. We would like to thank all of the authors who submitted papers to this special section for their high-quality contributions. We also thank the referees for their generous help and valuable suggestions. We are grateful to Professor Beng-Chin Ooi, the Editor-in-Chief of TKDE, for his strong support for this special section. IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 23, NO. 12, DECEMBER 2011 1761

Workflow views abstract groups of tasks in a workflow into high level composite tasks, in order to reuse subworkflows and facilitate provenance analysis. However, unless a view is carefully designed, it may not preserve the dataflow between tasks in the workflow, that is, it may not be sound . Unsound views can be misleading and cause incorrect provenance analysis. This article studies the problem of efficiently identifying and correcting unsound workflow views with minimal changes, and constructing minimal sound and elucidative workflow views with a set of user-specified relevant tasks. In particular, two related problems are investigated. First, given a workflow view, we wish to split each unsound composite task into the minimal number of tasks, such that the resulting view is sound. Second, given a workflow and a set of user specified relevant tasks, we generate a sound view, such that each composite task contains at most one relevant task, and the total number of tasks is minimized. We prove that both problems are NP-hard by reduction from independent set. We then propose two local optimality conditions (weak and strong) for each problem, and design polynomial time algorithms for both problems to meet these conditions. Experiments show that our proposed algorithms are reasonably effective and efficient. The proposed techniques are useful for view analysis/construction for not only workflows, but general networks as well.

Problem resolution is a key issue in the IT service industry. A large service provider handles, on daily basis, thousands of tickets that report various types of problems from its customers. The efficiency of this process highly depends on the effective interactions among various expert groups, in search of the resolver to the reported problem. In fact, ticket transfer decisions reflect the expertise awareness between groups, thus encoding a sophisticated resolution social network. In this paper, we propose a computational framework to quantitatively assess expertise awareness, i.e., how well a group knows the expertise of others. An accurate assessment of expertise awareness could identify the weakest components in a resolution system. The framework, built on our previously developed resolution engine, is able to calculate the performance difference caused by excluding a node from the network. The difference exposes the awareness of this node to other nodes in the network. To our best knowledge, this is the first study on this problem from a computational perspective. We tested the proposed framework on a large set of real-world problem tickets and validated our discovery by carefully analyzing the tickets that are incorrectly transferred. Experimental results show that our framework can successfully capture groups that do not know others' expertise very well.

With rapid development of web 2.0 technology and e-business, bloggers play significant roles in the blogosphere as well as the external world. In particular, influential bloggers can bring great business values to modern enterprise. Despite that several systems for mining influential bloggers are available, they measure the influence of bloggers in general rather than domain specific, which is not applicable for real application requirements, such as business advertisement, personalized recommendation and so on. In this paper, we propose an effective model to mine the top-k influential bloggers according to their interest domains, the impact and attitude of the comments to their posts, as well as their authority in the network of page links. In this demonstration, we present MASS, an effective system for mining influential bloggers. We will present the techniques in MASS, its experimental evaluation, as well as its applications.

This demo illustrates an XML search engine TargetSearch that addresses an open problem in XML keyword search: given relevant matches to keywords, how to compose query results properly so that they can be effectively ranked and easily digested by users. The approaches adopted in the literature generate either overwhelmingly large results or fragmentary results, both of which may cause the ranking schemes to be ineffective. Intuitively, each query has a search target and each result should contain exactly one instance of the search target along with its evidence. We developed TargetSearch which composes atomic and intact query results driven by users' search targets.

Information extraction systems are traditionally implemented as a pipeline of special-purpose processing modules. A major drawback of such an approach is that whenever a new extraction goal emerges or a module is improved, extraction has to be re-applied from scratch to the entire text corpus even though only a small part of the corpus might be affected. In this demonstration proposal, we describe a novel paradigm for information extraction: we store the parse trees output by text processing in a database, and then express extraction needs using queries, which can be evaluated and optimized by databases. Compared with the existing approaches, database queries for information extraction enable generic extraction and minimize reprocessing. However, such an approach also poses a lot of technical challenges, such as language design, optimization and automatic query generation. We will present the opportunities and challenges that we met when building GenerIE, a system that implements this paradigm.

Ticket resolution is a critical, yet challenging, aspect of the delivery of IT services. A large service provider needs to handle, on a daily basis, thousands of tickets that report various types of problems. Many of those tickets bounce among multiple expert groups before being transferred to the group with the right expertise to solve the problem. Finding a methodology that reduces such bouncing and hence shortens ticket resolution time is a long-standing challenge. In this paper, we present a unified generative model, the Optimized Network Model (ONM), that characterizes the lifecycle of a ticket, using both the content and the routing sequence of the ticket. ONM uses maximum likelihood estimation, to represent how the information contained in a ticket is used by human experts to make ticket routing decisions. Based on ONM, we develop a probabilistic algorithm to generate ticket routing recommendations for new tickets in a network of expert groups. Our algorithm calculates all possible routes to potential resolvers and makes globally optimal recommendations, in contrast to existing classification methods that make static and locally optimal recommendations. Experiments show that our method significantly outperforms existing solutions.

Database evolution is the process of updating the schema of a database or data warehouse (schema evolution) and evolving the data to the updated schema (data evolution). Database evolution is often necessitated in relational databases due to the changes of data or workload, the suboptimal initial schema design, or the availability of new knowledge of the database. It involves two steps: updating the database schema, and evolving the data to the new schema. Despite the capability of commercial RDBMSs to well optimize query processing, evolving the data during a database evolution through SQL queries is shown to be prohibitively costly. We designed and developed CODS, a platform for efficient data level data evolution in column oriented databases, which evolves the data to the new schema without materializing query results or unnecessary compression/decompression as occurred in traditional query level approaches. CODS ameliorates the efficiency of data evolution by orders of magnitude compared with commercial or open source RDBMSs.

Studies show that about 50% of web search is for information exploration purpose, where a user would like to investigate, compare, evaluate, and synthesize multiple relevant results. Due to the absence of general tools that can effectively analyze and differentiate multiple results, a user has to manually read and comprehend potentially large results in an exploratory search. Such a process is time consuming, labor intensive and error prone. With meta information embedded, keyword search on structured data provides the potential for automating or semi-automating the comparison of multiple results. In this demo we present a system XSACT for differentiating search results on structured data. XSACT takes as input a set of structured results, and outputs a Differentiation Feature Set (DFS) for each result to highlight their differences within a size bound. The problem of generating DFSs with maximal differences is proved to be NP-hard. XSACT adopts efficient algorithms for DFS generation, and features a user-friendly interface that effectively interacts with the users to help them compare search results.

Workflows are prevalent in diverse applications, which can be scientific experiments, business processes, web services, or recipes. With the dramatically growing number of workflows, there is an increasing need for people to search a workflow repository using keywords and to retrieve the relevant ones. A workflow hierarchy is a three dimensional object containing multiple abstraction views of different granularity on the same workflow. This unique structure poses a new set of challenges compared to keyword search on tree or graph structures typically found in relational or XML data. In this paper, we define an informative, self-contained and concise search result on workflows to be a projection of a workflow hierarchy on a two dimensional viewing plane inferred from user queries. We then design and develop an efficient keyword search engine for workflows. Experimental evaluation demonstrates the effectiveness of our approach.

Keyword search enables Web users to easily access XML data without the need to learn a structured query language and to study possibly complex data schemas. Existing work has addressed the problem of selecting qualified data nodes that match keywords and connecting them in a meaningful way, in the spirit of inferring the where clause in XQuery. However, how to infer the return clause for keyword searches is an open problem. To address this challenge, we present a keyword search engine for data-centric XML, XSeek, to infer the semantics of the search and identify return nodes effectively. XSeek recognizes possible entities and attributes inherently represented in the data. It also distinguishes between predicates and return specifications in query keywords. Then based on the analysis of both XML data structures and keyword patterns, XSeek generates return nodes. Furthermore, when the query is ambiguous and it is hard or impossible to determine the desirable return information, XSeek clusters the query results according to their semantics based on the user-specified granularity, and enables the user to easily browse and select the desired ones. Extensive experimental studies show the effectiveness and efficiency of XSeek.

Snippets are used by almost every text search engine to complement the ranking scheme in order to effectively handle user searches, which are inherently ambiguous and whose relevance semantics are difficult to assess. Despite the fact that XML is a standard representation format of Web data, research on generating result snippets for XML search remains limited. To tackle this important yet open problem, in this article, we present a system eXtract which generates snippets for XML search results. We identify that a good XML result snippet should be a meaningful information unit of a small size that effectively summarizes this query result and differentiates it from others, according to which users can quickly assess the relevance of the query result. We have designed and implemented a novel algorithm to satisfy these requirements. Furthermore, we propose to cluster the query results based on their snippets. Since XML result clustering can only be done at query time, snippet-based clustering significantly improves the efficiency while compromising little clustering accuracy. We verified the efficiency and effectiveness of our approach through experiments.

Workflows are widely used for representing business processes, Web services, scientific experiments, and activities in daily life, like recipes. There is an increasing need for people to search a workflow repository using keywords and retrieve the relevant ones according to their interests. A workflow hierarchy is a three dimensional object containing multi-resolution abstraction views on the same workflow. This unique structure poses a new set of challenges compared to keyword search on tree or graph structures which are typically found in XML or relational data. In this demonstration, we present an effective workflow search engine, WISE, which returns informative and concise search results, defined as the minimal views of the most specific workflow hierarchies containing matching keywords.

Empowering users to access databases using simple keywords can relieve the users from the steep learning curve of mastering a structured query language and understanding complex and possibly fast evolving data schemas. In this tutorial, we give an overview of the state-of-the-art techniques for supporting keyword search on structured and semi-structured data, including query result definition, ranking functions, result generation and top-k query processing, snippet generation, result clustering, query cleaning, performance optimization, and search quality evaluation. Various data models will be discussed, including relational data, XML data, graph-structured data, data streams, and workflows. We also discuss applications that are built upon keyword search, such as keyword based database selection, query generation, and analytical processing. Finally we identify the challenges and opportunities of future research to advance the field.

Workflow views abstract groups of tasks in a workflow into high level composite tasks, in order to reuse sub-workflows and facilitate provenance analysis. However, unless a view is carefully designed, it may not preserve the dataflow between tasks in the workflow, i.e., it may not be sound. Unsound views can be misleading and cause incorrect provenance analysis.

Studies show that about 50% of web search is for information exploration purpose, where a user would like to investigate, compare, evaluate, and synthesize multiple relevant results. Due to the absence of general tools that can effectively analyze and differentiate multiple results, a user has to manually read and comprehend potentially large results in an exploratory search. Such a process is time consuming, labor intensive and error prone. With meta information embedded, keyword search on structured data provides the potential for automating or semi-automating the comparison of multiple results. In this paper we present an approach for differentiating search results on structured data. We define the differentiability of query results and quantify the degree of difference. Then we define the problem of identifying a limited number of valid features in a result that can maximally differentiate this result from the others, which is proved to be NP-hard. We propose two local optimality conditions, namely single-swap and multi-swap. Efficient algorithms are designed to achieve local optimality. To show the applicability of our approach, we implemented a system XRed for XML result differentiation. Our empirical evaluation verifies the effectiveness and efficiency of the proposed approach.

Workflow views abstract groups of tasks in a workflow into composite tasks, and are used for simplifying provenance analysis, workflow sharing and reuse. An unsound view does not preserve the dataflow between tasks in the workflow, and can therefore cause incorrect provenance analysis. In this demo we present WOLVES, a system that efficiently identifies and corrects unsound workflow views with minimal changes ( view correction ). Since the view correction problem is NP-hard, WOLVES allows the user to choose between two forms of local optimality, strong and weak. Efficient time algorithms achieving these optimalities are implemented in WOLVES.

Answering queries using materialized views has been well studied in the context of structured queries and has shown significant performance benefits. Despite the popularity of keyword search over XML data, it is an open problem whether materialized views can be leveraged for query evaluation. In this paper, we investigate this problem and present techniques for answering keyword queries using a minimal number of materialized views. Experimental evaluation demonstrates the efficiency of the proposed techniques.

IT problem management calls for quick identification of resolvers to reported problems. The efficiency of this process highly depends on ticket routing---transferring problem ticket among various expert groups in search of the right resolver to the ticket. To achieve efficient ticket routing, wise decision needs to be made at each step of ticket transfer to determine which expert group is likely to be, or to lead to the resolver.

Snippets are used by almost every text search engine to complement ranking scheme in order to effectively handle user searches, which are inherently ambiguous and whose relevance semantics are difficult to assess. Despite the fact that XML is a standard representation format of web data, research on generating result snippets for XML search remains untouched.

Snippets are used by almost every text search engine to complement ranking schemes in order to effectively handle user keyword search. Despite the fact that XML is a standard representation format of web data, research on generating result snippets for XML search remains untouched. In this work, we present eXtract, a system that efficiently generates self-contained result snippets within a given size bound which effectively summarize the query results and differentiate them from one another, according to which users can quickly assess the relevance of the query results.

Keyword search is a user-friendly mechanism for retrieving XML data in web and scientific applications. An intuitively compelling but vaguely defined goal is to identify matches to query keywords that are relevant to the user. However, it is hard to directly evaluate the relevance of query results due to the inherent ambiguity of search semantics. In this work, we investigate an axiomatic framework that includes two intuitive and non-trivial properties that an XML keyword search technique should ideally satisfy: monotonicity and consistency , with respect to data and query. This is the first work that reasons about keyword search strategies from a formal perspective. Then we propose a novel semantics for identifying relevant matches, which, to the best of our knowledge, is the only existing algorithm that satisfies both properties. An efficient algorithm is designed for realizing this semantics. Extensive experimental studies have verified the intuition of the properties and shown the effectiveness of the proposed algorithm.

Managing problem tickets is a key issue in IT service industry. A large service provider may handle thousands of problem tickets from its customers on a daily basis. The efficiency of processing these tickets highly depends on ticket routing---transferring problem tickets among expert groups in search of the right resolver to the ticket. Despite that many ticket management systems are available, ticket routing in these systems is still manually operated by support personnel. In this demo, we introduce EasyTicket, a ticket routing recommendation engine that helps automate this process. By mining ticket history data, we model an enterprise social network that represents the functional relationships among various expert groups in ticket routing. Based on this network, our system then provides routing recommendations to new tickets. Our experimental studies on 1.4 million real-world problem tickets show that on average, EasyTicket can improve the efficiency of ticket routing by 35%.

Incompleteness due to missing attribute values (aka "null values") is very common in autonomous Web databases, on which user accesses are usually supported through mediators. Traditional query processing techniques that focus on the strict soundness of answer tuples often ignore tuples with critical missing attributes, even if they wind up being relevant to a user query. Ideally we would like the mediator to retrieve such relevant uncertain answers and gauge their relevance by accessing their likelihood of being relevant answers to the query. However, the autonomous nature of the databases poses several challenges, such as the restricted access privileges, limited query patterns, and sensitivity of database and network resource consumption in the Web environment. We introduce a novel query rewriting and optimization framework QPIAD that tackles these challenges to retrieve relevant uncertain answers. Our technique involves reformulating the user query based on approximate functional dependencies (AFDs) among the database attributes and ranking these queries using value distributions learned from naive Bayes classifiers. Empirical studies demonstrate the effectiveness of our approach in retrieving relevant uncertain answers with high precision, high recall and manageable cost.

There is an increasing need for an XML query engine that not only searches for exact matches to a query but also returns "query-like" structures. We have designed and developed XFinder, an efficient top K tree pattern query evaluation system, which reduces the problem of approximate tree structural matching to a simpler problem of subsequence matching. However, since not all subsequences correspond to valid tree structures, it is expensive to enumerate common subsequences between XML data and query and then filter the invalid ones. XFinder addresses this challenge by detecting and pruning structurally irrelevant subsequence matches as early as possible. Experiments show the efficiency of XFinder on various data and query sets.

Keyword search enables web users to easily access XML data without the need to learn a structured query language and to study possibly complex data schemas. Existing work has addressed the problem of selecting qualified data nodes that match keywords and connecting them in a meaningful way, in the spirit of inferring a where clause in XQuery. However, how to infer the return clause for keyword search is an open problem.

No abstract available.

Linguistic research and natural language processing employ large repositories of ordered trees. XML, a standard ordered tree model, and XPath, its associated language, are natural choices for linguistic data and queries. However, several important expressive features required for linguistic queries are missing or hard to express in XPath. In this paper, we motivate and illustrate these features with a variety of linguistic queries. Then we propose extensions to XPath to support linguistic queries, and design an efficient query engine based on a novel labeling scheme. Experiments demonstrate that our language is not only sufficiently expressive for linguistic trees but also efficient for practical usage.

Streaming XPath evaluation algorithms must record a potentially exponential number of pattern matches when both predicates and descendant axes are present in queries, and the XML data is recursive. In this paper, we use a compact data structure to encode these pattern matches rather than storing them explicitly. We then propose a polynomial time streaming algorithm to evaluate XPath queries by probing the data structure in a lazy fashion. Extensive experiments show that our approach not only has a good theoretical complexity bound but is also efficient in practice.

We present ViteX, an XPath processing system on XML streams with polynomial time complexity. ViteX uses a polynomial-space data structure to encode an exponential number of pattern matches (in the query size) which are required to process queries correctly during a single sequential scan of XML. Then ViteX computes query solutions by probing the data structure in a lazy fashion without enumerating pattern matches.

As XML becomes an increasingly popular format for information exchange, the efficient processing of broadcast XML data on a constrained device (for example, a cell phone or a PDA) becomes a critical task. In this paper we present the EXPedite system: a new model of data processing in an information exchange environment, which "migrates" the power of the data-sending server to receivers for efficient processing. It consists of a simple and general encoding scheme for servers, and streaming query processing algorithms on encoded XML stream for data receivers with constrained computing abilities. Experiments show the impressive performance of EXPedite.

We present BLAS, a Bi-LAbeling based System, for efficiently processing complex XPath queries over XML data. BLAS uses P-labeling to process queries involving consecutive child axes, and D-labeling to process queries involving descendant axes traversal. The XML data is stored in labeled form, and indexed to optimize descendent axis traversals. Three algorithms are presented for translating complex XPath queries to SQL expressions, and two alternate query engines are provided. Experimental results demonstrate that the BLAS system has a substantial performance improvement compared to traditional XPath processing using D-labeling.

The role of XML in data exchange is evolving from one of merely conveying the structure of data to one that also conveys its semantics. In particular, several proposals for key and foreign key constraints have recently appeared, and aspects of these proposals have been adopted within XMLSchema.In this paper, we examine the problem of checking keys and foreign keys in XML documents using a validator based on SAX. The algorithm relies on an indexing technique based on the paths found in key definitions, and can be used for checking the correctness of an entire document (bulk checking) as well as for checking updates as they are made to the document (incremental checking). The asymptotic performance of the algorithm is linear in the size of the document or update. Furthermore, experimental results demonstrate reasonable performance.