Abstract Large-scale crowdsourcing with high-quality results, such as online surveys and data labeling tasks, is in wide demand. Existing techniques on task assignment result quality optimization, however, have addressed only a part of optimization space that does not necessarily reflect the real-world problem. For example, in reality, the proper worker set for task assignment and the workers’ submissions to the task are non-obvious in advance, which is not considered by existing techniques. Hence, this paper discusses a task assignment algorithm that dynamically probes the proper worker set(s) and worker submission models for the task to optimize task assignments in terms of quality, time, and expense. Specifically, we introduce CrowdBwO (Crowd Bandit with Optimization), a novel multi-armed bandit algorithm that is based on batched bandits and bandits with Knapsack and incorporates worker submission models. CrowdBwO dynamically determines and utilizes proper worker set(s) and worker submission models for each task under uncertainty to achieve high-performance crowdsourcing. We conducted extensive experiments with synthetic workers and real workers to evaluate CrowdBwO in two specific problem settings. Our extensive experimental results demonstrate that CrowdBwO is significant for real-world crowdsourcing and has a high performance.

With the rising awareness of the critical role sleep plays in both health and social well-being, the demand for sleep studies is rapidly increasing.Automatic sleep stage classification is a fundamental part of sleep measurement, and machine learning models have been developed to assist in this process. These models achieve accuracy comparable to that of technicians when using data from healthy individuals. However, sleep patterns in individuals with sleep disorders, such as sleep apnea syndrome (SAS), one of the most common sleep disorders, differ from those of healthy individuals. As a result, existing models trained on healthy individuals’ data do not achieve sufficient accuracy when applied to SAS patients. This is a barrier to clinical application.A recent study using in-home EEG devices showed that technicians can accurately classify sleep stages in SAS cases by considering surrounding epochs. Based on this, we developed a model dedicated to SAS patients that incorporates the temporal context of relevant epochs.We found that this context-aware model significantly improved classification accuracy compared to models that only focused on the target epoch. In the training process using data from 76 severe SAS cases, the model based solely on single-epoch data achieved an accuracy of 71.5%, while the model considering the surrounding epochs achieved an accuracy of 73.7%. The classification accuracy improved across all stages except N3.This approach appears to capture the frequent sleep stage transitions characteristic of SAS.

Predicting how social networks change in the future is important in many applications. Results in social network research have shown that the change in the network can be explained by a small number of concepts, such as "homophily" and "transitivity". However, existing prediction methods require many latent features that are not connected to such concepts, making the methods' black boxes and their prediction results difficult to interpret, making them harder to derive scientific knowledge about social networks. In this study, we propose NetEvolve a novel multi-agent reinforcement learning-based method that predicts changes in a given social network. Given a sequence of changes as training data, NetEvolve learns the characteristics of the nodes with interpretable features, such as how the node feels rewards for connecting with similar people and the cost of the connection itself. Based on the learned feature, NetEvolve makes a forecast based on multi-agent simulation. The method achieves comparable or better accuracy than existing methods in predicting network changes in real-world social networks while keeping the prediction results interpretable.

Nowadays, it is a common practice for crowd workers to develop ML models that classify data items. We envision the Human+AI crowd where crowd programmers develop "AI workers," which are black-box software agents that work among other human workers. The problem here is evaluating such AI workers is different from evaluating human workers in that they may not be spam workers, although they have low accuracy at the beginning of their learning process or for a particular label. Therefore, existing work evaluates the output from AI workers every time they output the task results. Obviously, such a naive evaluation does not scale because there are a tremendous number of task results to be evaluated. This paper addresses the problem of how to efficiently evaluate AI worker outputs by skipping the AI evaluation when the AI is unlikely to satisfy the expected accuracy. We conducted an experiment to compare two strategies and found that both reduce the number of evaluations by orders of magnitude while keeping the number of task assignments to AI workers.

Identifying the location where a photo was taken is an important operation in many applications such as the disaster response if it is not associated with the location information. This process usually is done by experts who are familiar with the geolocation. However it is not guaranteed that we can find such expert workers. In this paper, we explore an approach to improve the quality of image geolocation with an workflow implement experts’ strategy for the image geolocations. The result of preliminary experiment suggested that our approach is effective in improving the accuracy of non-expert geolocation.

Many existing optimization approaches deal with task assignments on one single crowdsourcing platform. This paper addresses the difficulties of the optimal platform selection for qualification tasks on one single platform. We proposed a novel approach about assigning qualification tasks to workers iteratively on multiple platforms to maximize the total number of collected qualified workers on a limited budget. We applied Multi-Armed Bandit (MAB) algorithms to create strategies for the platform selections to achieve this goal. The conducted experiments revealed that (1) the optimal platform is not always trivial, and (2) the strategies created by MAB algorithms can achieve high-quality assignments under different settings which also satisfied different requesters’ needs.

When selecting workers in microtask crowdsourcing platforms, requesters select qualified workers by looking at the evaluation results for the tasks in the past or by conducting qualifying tests for the tasks. As a result, they choose workers whose skill levels are above some threshold. This sometimes limits the number of workers who perform the tasks, which has a negative effect for both of requesters and workers. In this paper, we explore an approach to increasing the work opportunities for many workers, by finding task assignment based on the estimated skill level of workers and the difficulty level of tasks. We show the result of a preliminary experiment to discuss the potential and limitation of this approach.

Entity matching is an issue of interest in information integration and data cleaning. Since the representations of the same entity vary, it is often impossible to fully automate the entity matching and require human inputs. However, to guarantee high-quality entity matching, how to integrate human resources into the entity matching while minimizing the cost of human resources? In this paper, we propose BUBBLE, a novel human-in-the-loop entity matching framework hybridizing Bayesian inference and crowdsourcing. To guarantee entity matching quality, Bayesian inference is conducted to determine whether the matching requires crowdsourcing. We show that we can define Bayesian error rate for this problem. For optimization, we use metric learning to select the candidate matching pairs by nearest-neighbor search in the learned embedding space, and we construct a k-nearest neighbor graph to avoid the redundant matching. We applied BUBBLE to a bibliographic data matching problem on the National Diet Library. The experimental results show that BUBBLE can assign tasks to humans with higher quality results compared to those of the same number of task assignments to humans. The result also shows that our optimization scheme is effective without sacrificing the quality.

The coronavirus disease 2019 (COVID-19) pandemic has spread across the globe from the beginning of 2020 and people worldwide have been receiving news about the same from government offices, press conferences and various other media outlets. The COVID-19 Information Watcher Project started in 2020 to collect and organize reliable information sources worldwide. However, it is difficult to automatically identify reliable information sources in foreign countries for several reasons. First, what kind of information sources are reliable heavily depend on each county situation. In some countries people trust their government’s official information but in other countries they do not. Secondly, such reliable information sources often provide information in their local languages. Reliable information sources are not necessarily top-ranked by search engines. Crowdsourcing is a promising way to deal with such a case. However, crowd-sourcing platforms do not cover crowds in all countries. In this study, we report some results of our attempt to collect local information regarding COVID-19 from several countries through multi-hop crowdsourcing, in which we allow crowd workers on a crowdsourcing platform to use other platforms in other countries. We show two case studies, Russia and Afghanistan. Our results show that the multi-hop crowdsourcing is a promising way to collect COVID-19 information from different countries.

This paper addresses the problem of dynamically assigning tasks to a crowd consisting of AI and human workers. Currently, crowdsourcing the creation of AI programs is a common practice. To apply such kinds of AI programs to the set of tasks, we often take the ``all-or-nothing'' approach that waits for the AI to be good enough. However, this approach may prevent us from exploiting the answers provided by the AI until the process is completed, and also prevents the exploration of different AI candidates. Therefore, integrating the created AI, both with other AIs and human computation, to obtain a more efficient human-AI team is not trivial. In this paper, we propose a method that addresses these issues by adopting a ``divide-and-conquer'' strategy for AI worker evaluation. Here, the assignment is optimal when the number of task assignments to humans is minimal, as long as the final results satisfy a given quality requirement. This paper presents some theoretical analyses of the proposed method and an extensive set of experiments conducted with open benchmarks and real-world datasets. The results show that the algorithm can assign many more tasks than the baselines to AI when it is difficult for AIs to satisfy the quality requirement for the whole set of tasks. They also show that it can flexibly change the number of tasks assigned to multiple AI workers in accordance with the performance of the available AI workers.

Understanding the current situation of natural disaster damages is a critical step for an effective natural disaster responses, and many pictures uploaded after natural disasters are valuable resources for this purpose. However, many pictures are not associated with location information and it is not easy to connect the image content to locations on a map. There are two reasons for this difficulty. First, pictures are different in terms of directions and heights. Second, the situation of damaged areas in the picture may differ from before the natural disaster. Therefore, there is a mismatch between map fragments and the pictures taken after a disaster. This paper explores the potential of human computation to solve this problem. For this study, we asked people to draw a birds-eye view map of the place in a picture and compared the map with the correct map fragments to see the characteristics of such drawn maps.

How to develop AI systems that can explain how they made decisions is one of the important and hot topics today. Inspired by the dual-process theory in psychology, this paper proposes a human-in-the-loop approach to develop System-2 AI that makes an inference logically and outputs interpretable explanation. Our proposed method first asks crowd workers to raise understandable features of objects of multiple classes and collect training data from the Internet to generate classifiers for the features. Logical decision rules with the set of generated classifiers can explain why each object is of a particular class. In our preliminary experiment, we applied our method to an image classification of Asian national flags and examined the effectiveness and issues of our method. In our future studies, we plan to combine the System-2 AI with System-1 AI (e.g., neural networks) to efficiently output decisions.

In a data labeling process for building machine learning, the choice of labeling data instances is known to have a significant impact on the performance of classifiers. So far, the study of active learning has addressed the issue of how to choose the subset by prioritizing the data instances based on the state of the current classifier. However, the active learning approach has two drawbacks that (i) require a training loop to update the priorities of labeling tasks and (ii) require us to choose a specific active learner while we do not know the optimal classification model. In this paper, we propose a new framework of priority-aware labeling system that allows a parallel task assignment to crowd workers without assuming a particular classifier, which is based on novel methods called “batch prioritization” and “label expansion”. We conducted experiments with multiple datasets to examine the effectiveness of the approach and found that the proposed method improves the performance of the final classifiers more quickly than the active learning approach despite that the labeling tasks can be processed in a fully parallel manner.

The most typical approach today to data processing which does not have proven algorithms is to first request humans to provide labels to a small set of data and then develop artificial intelligences (AIs) with the data to perform all the remaining tasks. This development is sometimes crowdsourced through platforms such as Kaggle. The approach, however, is not always effective; if the AI does not meet the quality requirement, we may have to give up the development and all the data items have to be done manually. In order to avoid this all-or-nothing situation, “selective” AI programs that perform tasks which they are confident to do will be effective. This study addresses the problem of designing an incentive structure for crowdsourcing the development of such selective AI programs. This paper shows the results of our real-world experiment with a stair-step incentive structure and the behavior of a worker who developed the AI agent under the incentive. This paper also discusses the limitations of the proposed incentive design.

Peer learning is a known effective method of education, which involves people teaching each other. Usually, peer learning requires dedicated facilitators, but it is not always possible to have them in some situations such as in classes with a large number of students and in crowdsourcing settings. This paper addresses the question whether there is a way through which people can teach each other without dedicated facilitators. A key issue is to allow people to identify their own incomprehension. We applied a microtask approach to the problem and verified that the developed workflow was effective. The result of our preliminary experiment suggests that the approach is effective for identifying students' incomprehension. We also show that the identified incomprehensible parts allow people to teach each other.

This paper reports the result of a preliminary experiment on active learning strategies for the hierarchical labeling microtasks. A typical example of hierarchical labeling microtask consists of a set of labeling tasks for partitions of a large image; starting from the whole image, the workers choose to give a label or divide it into smaller ones. This paper shows the result of an experiment to compare several strategies for active learning in the setting. The result suggests that the difference in the strategies affects the performance in the early stage.

In this paper, we show preliminary results on the quality assessment of crowdworker output based on the movements of the mouse and the eyes while the task is performed. We assume that the mouse and the eyes stop longer if the quality is lower due to the lack of knowledge, or confidence, etc. Because the mouse- and eye-stopping duration follows lognormal distribution, we estimate its parameters (mean and standard deviation) to evaluate the quality. Results of preliminary experiments with 10 participants show that the parameters of correct outputs are different from those of incorrect ones. As compared to the task duration, which is often used as a feature for assessment, we have found that the mouse-and the eyestopping duration is advantageous and complementary for the assessment.

Recent evolution in cloud computing platforms have attracted the largest amount of data than ever before. Today, even the most sensitive data are being outsourced, thus, protection is essential to ensure that privacy is not traded for the convenience provided by cloud platforms. Traditional symmetric encryption schemes provide good protection; however, they ruin the merits of cloud computing. Attempts have been made to obtain a scheme where both functionality and protection can be achieved. However, features provided in existing searchable encryption schemes tend to be left behind the latest findings in the information retrieval (IR) area.

Task assignment is one of the important issues in crowdsourcing. Most existing schemes consider both of task-centric measures (e.g., required abilities) and worker-centric measures (e.g., worker preference) at local (each task) assignment level, but consider only task-centric measures at the global (the whole workflow) assignment level, such as productivity and throughput. This paper proposes to introduce Inclusiveness and Activity Degree as the worker-centric measures at the global level. It is not trivial whether we can find assignment that are good in terms of all of the two task-centric measures (productivity and throughput) and the two worker-centric measures (Inclusiveness and Activity Degree) at the global level. This paper explains five assignments that are expected to increase some measures and shows Activity Degree Conscious Assignment can produce high Inclusiveness and Activity Degree and not significantly reduce the productivity and throughput assignment through a simulation.

Can people learn from machines behavior in microtask based crowdsourcing? Can we train the machines as our mentor even without domain expertise? In this paper, we investigate how the task results improve concerning quality during and after presenting machine prediction as a reference answer in self-correction. Four reference types were examined in the experiment; Correct, Random, Machine prediction trained by correct answers, and that trained by human answers. Learning effects were observed only in presenting machine prediction, although those accuracy rates were far from correct (100%). Moreover, there were no learning effects in "Correct" and "Random". This suggests the following hypothesis: Since machine learners make some "models" for the problem, it is easier for humans to interpret the outputs of machine learners than the results without via them; it is more difficult to interpret not only random answers but also the correct answers in a case where the perfect interpretation of the problem is difficult. Furthermore, some workers answered with higher accuracy rate than machines in the post-test. Therefore, this strategy can be expected to be useful for bootstrapping solutions in the situation where unknown problems occur without expertise or at a low cost.

One of the problems in crowdsourcing is the development of appropriate instructions for workers. To improve task instructions, we must find typical mistake patterns. However, manually identifying these patterns is a cumbersome task. This study shows that a relatively simple approach classifying workers in terms of their understanding of task instructions is promising for addressing this issue. The verification results by domain experts suggest that the output is useful for improving task instructions.

At times, a composite dataflow needs rerunning in crowdsourcing for various reasons, even when the dataflow may be half complete. Rerunning the dataflow requires more time and incurs monetary costs for the additional work that would need to be completed by crowd workers. This time and cost may be reduced by reusing complete or intermediate results in the previous run. However, at times, such results cannot be used as is (e.g., when the dataflow has been changed), and some additional tasks need to be completed in the old dataflow in order to make them reusable in the new dataflow. The benefit of reusing these results in the previous run may or may not be worth the cost of these additional tasks. This paper gives a general framework for formulating this problem, and proposed a method to estimate the additional costs. The simulation result shows that it is worth devising optimization techniques to identify feasible (namely, cost-effective) plans.

Crowdsourcing is a promising tool involving multiple people in completing tasks that are difficult to complete by an individual, a small team or a computer. Ensuring the quality of the results is also one of the primary problems in crowdsourcing. One of the major approaches to improve the data quality to aggregate answers from more than one workers. This study explores a different approach - we ask workers to prove facts. We devise a general framework for collecting and ranking evidence-based proofs. The experiments results show that the proposed framework works and how diverse the collected proofs are. Our results clearly indicate that the crowd-based approach to prove facts is promising.

People have become increasingly dependent on the Web. However, it is difficult for visually impaired individuals to understand the content, especially if the web page contains images. The images can be more accessible by adding alt text, but it is known that alt text added through the current automation techniques are not necessarily helpful. Crowdsourcing is a promising approach for it, but adding alt text to all the images on the Web requires a tremendous amount of effort. In addition, too many alt texts of images also increase the difficulty of reading. Therefore, it is crucial to select important images for understanding web pages. This paper presents the results of our preliminary experiments to identify important images for understanding web pages. We adopted a crowdsourcing approach with two microtask designs. The results of our study demonstrated that (1) there are several types of images that are difficult to automatically assess the importance; thus, human-in-the-loop can be a promising approach to identify important ones in the types of images; and (2) there are microtask designs that can result in the similar results but different to each other in terms of other criteria. The results suggested that the identification of important images for understanding web pages is an interesting problem to address.

This paper addresses the pipeline processing of sequential workflows in crowdsourcing. Sequential workflows consisting of several subtasks are ubiquitous in crowdsourcing. Our approach is to control the budget distribution to subtasks in order to balance the execution speed of the subtasks and to improve throughput of overall sequential workflows. As we cannot control the price for earlier steps retrospectively in the stepwise batch execution, we explore pipeline processing schemes. Our experimental results show that our pipeline processing scheme with price control achieves significantly higher throughput of sequential workflows.

Self-correction for crowdsourced tasks is a two-stage setting that allows a crowd worker to review the task results of other workers; the worker is then given a chance to update his/her results according to the review.Self-correction was proposed as an approach complementary to statistical algorithms in which workers independently perform the same task. It can provide higher-quality results with few additional costs. However, thus far, the effects have only been demonstrated in simulations, and empirical evaluations are needed. In addition, as self-correction gives feedback to workers, an interesting question arises: whether perceptual learning is observed in self-correction tasks. This paper reports our experimental results on self-corrections with a real-world crowdsourcing service.The empirical results show the following: (1) Self-correction is effective for making workers reconsider their judgments. (2) Self-correction is more effective if workers are shown task results produced by higher-quality workers during the second stage. (3) Perceptual learning effect is observed in some cases. Self-correction can give feedback that shows workers how to provide high-quality answers in future tasks.The findings imply that we can construct a positive loop to improve the quality of workers effectively.We also analyze in which cases perceptual learning can be observed with self-correction in crowdsourced microtasks.

Worker-task assignments represent one of the critical issues in crowdsourcing, as they affect the quality of task results. This study addresses the problem of forming worker groups assigned to the same task in a task stream that requires more than one worker. We introduce a worker-group queue model that covers practical and common scenarios for task-stream crowdsourcing, and compare three strategies in terms of the skill balance among worker groups, the quality of the final outputs, the number of worker re-assignments of workers, and psychological stress felt by workers. We found that one of the compared strategies that employs multiple worker queues yields good results based on these measures.

We demonstrate CrowdSheet, a spreadsheet interface for implementing complex crowdsourcing. Despite its appeal, adoption of the spreadsheet paradigm is associated with two nontrivial problems: (1) how to design the interface, which must be a natural extension of existing spreadsheets, while guaranteeing a reasonable expressive power, and (2) how to incorporate techniques for improving data quality without sacrificing the spreadsheet's easy-to-use feature. In this demo, we show three things. First, CrowdSheet allows non IT experts to easily implement crowdsourcing applications with complex workflows. Second, CrowdSheet adopts only new two spreadsheet functions to implement a fairly wide range of real-world applications. Third, its modular architecture gives CrowdSheet a declarative feature that lets users choose alternative plans for improving data quality, while keeping the CrowdSheet description simple.

Determining numbers is a fundamental operation in many applications. Although the main objective is to determine the exact number, a complete enumeration is not always possible. Therefore, different methods have been employed depending on the situation, such as Fermi estimation and complete enumeration. This paper introduces a method for crowd-based best-effort number estimation, which seamlessly integrates Fermi estimation and complete enumeration. The principle underlying of the method is defining a table called the Fermi-estimation table, which represents both task decomposition and Fermi estimation. This paper also shows our preliminary results and discusses some of the future prospects.

Creating session programs for large-scale academic conferences is a cumbersome task for program committees. Our goal is to establish a crowd-in-the-loop method for creating session programs. In the proposed method, crowd workers are both paper authors and PC members. In contrast to existing approaches, our method is unique in that we use microtasks as much as possible to minimize interactions between workers. This paper presents an overview of our approach, as well as the results of a preliminary experiment on the bidding tasks for sessions by authors. We found that authors do not necessarily bid for appropriate sessions, meaning we need a mechanism to properly modify the bidding results.

Since over one million tourists annually visit the Angkor ruins, the effect on the buildings from the vibrations caused by these tourists is a huge problem for maintaining them. Such organisms as bryophytes, which adhere to the surface of the stones of the ruins, is another factor that damages them. Using crowdsourcing and 3D reconstruction technology, we are organizing a proactive preservation project for the Angkor Thom Bayon Temple, which is a world cultural heritage site. We evaluated its damaged parts and visualized the damaged state.

A common workflow to perform a continuous human task stream is to divide workers into groups, have one group perform the newly-arrived task, and rotate the groups. Usually, more than one worker belongs to each group for improving the quality of task results. We call this type of workflow the group rotation. This paper addresses the problem of how to manage Group Rotation Type Crowdsourcing, the group rotation in a crowdsourcing setting. In the group-rotation type crowdsourcing, we must change the group structure dynamically because workers come in and leave frequently. However, changing the group structure will give workers psychological stress, such as surprise, confusion or irritation. This paper explores a design space for group restructuring algorithms in the group rotation type crowdsourcing and compares implemented strategies in terms of the evaluation results on psychological stress with real-world crowd workers.

In order to realize smooth communication between people with or without difficulty in hearing, we aim to implement an information support system based on crowdsourcing, a problem-solving model, in which numerous people cooperate to accomplish a job. More specifically, we implement a crowdsourced captioning system that enables groups of deaf and hard-of-hearing people to collaboratively interpret a speech or lecture given by sign language to text in real-time. Deaf and hard-of-hearing people are generally considered as the ones who receive support from others, but our proposal helps them become the ones who offer support to others. In this paper, we explore the issues that need be resolved for the practical use of the proposed system through several experiments and succeed in verifying its feasibility.

Collaborative crowdsourcing is an emerging paradigm where a set of workers, often with diverse and complementary skills, form groups and work together to complete complex tasks. While crowdsourcing has been used successfully in many applications, collaboration is essential for achieving a high quality outcome for a number of emerging applications such as text translation, citizen journalism and surveillance tasks. However, no crowdsourcing platform today enables the end-to-end deployment of collaborative tasks. We demonstrate Crowd4U, a volunteer-based system that enables the deployment of diverse crowdsourcing tasks with complex data-flows, in a declarative manner. In addition to treating workers and tasks as rich entities, Crowd4U also provides an easy-to-use form-based task UI. Crowd4U implements worker-to-task assignment algorithms that are appropriate for each kind of task. Once workers are assigned to tasks, appropriate worker collaboration schemes are enforced in order to enable effective result coordination.

We propose a method for obtaining and ranking paraphrased questions from crowds to be used as a part of instructions in microtask-based crowdsourcing. With our method, we are able to obtain questions that differ in expression yet have the same semantics with respect to the crowdsourcing task. This is done by generating tasks that give hints and elicit instructions from workers. We conducted experiments with data used for a real set of gold standard questions submitted to a commercial crowdsourcing platform and compared the results with those from a direct-rewrite method.

We describe the Crowd4U initiative, which aims at constructing an all-academic open and generic platform for microvolunteering and crowdsourcing worldwide. Crowd4U provides a microtask-based platform in which most workers are volunteers at universities and other research institutions. Crowd4U is open in the sense that the platform can interact with other platforms, researchers can register their tasks, and the underlying code is not a black box. It is generic as it allows to register virtually any task. Crowd4U has already been used by several projects for public and academic purposes.

Data integrity constraints are fundamental in various applications, such as data management, integration, cleaning, and schema extraction. In this paper, we address the problem of finding inclusion dependencies on the Web. The problem is important because (1) applications of inclusion dependencies, such as data quality management, are beneficial in the Web context, and (2) such dependencies are not explicitly given in general. In our approach, we enumerate pairs of HTML/XML elements that possibly represent inclusion dependencies and then rank the results for verification. First, we propose a bit-based signature scheme to efficiently select candidates (element pairs) in the enumeration process. The signature scheme is unique in that it supports Jaccard containment to deal with the incomplete nature of data on the Web, and preserves the semiorder inclusion relationship among sets of words. Second, we propose a ranking scheme to support a user in checking whether each enumerated pair actually suggests inclusion dependencies. The ranking scheme sorts the enumerated pairs so that we can examine a small number of pairs for simultaneously verifying many pairs.

This demo presents a principled approach to the problems of data-centric human/machine computations with Crowd4U, a crowdsourcing platform equipped with a suite of tools for rapid development of crowdsourcing applications. Using the demo, we show that declarative database abstraction can be used as a powerful tool to design, implement, and analyze data-centric crowdsourcing applications. The power of Crowd4U comes from CyLog, a database abstraction that handles complex data-centric human/machine computations. CyLog is a Datalog-like language that incorporates a principled feedback system for humans at the language level so that the semantics of the computation not closed in machines can be defined based on the game theory. We believe that the demo clearly shows that database abstraction can be a promising basis for designing complex data-centric applications requiring human/machine computations.

There are many applications in which users interactively access huge tree data by repeating set-based navigations. In this paper, we focus on label-specific/wildcard children/ descendant navigations. For efficient processing of these operations in huge data stored on a disk, we need a node ordering scheme that clusters nodes that are accessed together by these operations. In this paper, (1) we show there is no node order that is optimal for all these operations, (2) we propose two schemes, each of which is optimal only for some subset of them, and (3) we show that one of the proposed schemes can process all these operations with access to a constant-bounded number of regions on the disk without accessing irrelevant nodes.

This paper addresses the problem of finding new locations of moved Web pages. We discuss why the content-based approach has a limitation in solving the problem and why it is important to exploit the knowledge on where to search for the pages.

PageChaser is a system that monitors links between Web pages and searches for the new locations of moved Web pages when it finds broken links. The problem of searching for moved pages is different from typical information retrieval problems. First, it is impossible to identify the final destination until the page is actually moved, so the index-server approach is not necessarily effective. Secondly, there is a large bias about where the new address is likely to be and crawler-based solutions can be effectively implemented, avoiding the need to search the entire Web. PageChaser incorporates a comprehensive set of heuristics, some of which are novel, in a single unified framework. This paper explains the underlying ideas behind the design and development of PageChaser.

We focus on the problem of data transformations, i.e., how to transform data to another structure to adapt it to new application requirements or given environments. Here, we define data transformation as the process of taking as input two schemas A and B and an instance of A, and producing an instance of B. Today, data transformations are required in many situations: to integrate multiple information sources, to construct and receive data for Web services, and to migrate data from legacy systems to new systems, from local databases to data warehouses. This demonstration focuses on XML transformations, since XML is the de facto standard for data exchange.

We present XLearner, a novel tool that helps the rapid development of XML mapping queries written in XQuery. XLearner is novel in that it learns XQuery queries consistent with given examples (fragments) of intended query results. XLearner combines known learning techniques, incorporates mechanisms to cope with issues specific to the XQuery learning context, and provides a systematic way for the semiautomatic development of queries. We describe the XLearner system. It presents algorithms for learning various classes of XQuery, shows that a minor extension gives the system a practical expressive power, and reports experimental results to demonstrate how XLearner outputs reasonably complicated queries with only a small number of interactions with the user.

XML is the "lingua franca" for data exchange between interenterprise applications. In this work, we describe SilkRoute, a framework for publishing relational data in XML. In SilkRoute, relational data is published in three steps: the relational tables are presented to the database administrator in a canonical XML view; the database administrator defines in the XQuery query language a public, virtual XML view over the canonical XML view; and an application formulates an XQuery query over the public view. SilkRoute composes the application query with the public-view query, translates the result into SQL, executes this on the relational engine, and assembles the resulting tuple streams into an XML document. This work makes some key contributions to XML query processing. First, it describes an algorithm that translates an XQuery expression into SQL. The translation depends on a query representation that separates the structure of the output XML document from the computation that produces the document's content. The second contribution addresses the optimization problem of how to decompose an XML view over a relational database into an optimal set of SQL queries. We define formally the optimization problem, describe the search space, and propose a greedy, cost-based optimization algorithm, which obtains its cost estimates from the relational engine. Experiments confirm that the algorithm produces queries that are nearly optimal.

We address the problem of efficiently constructing materialized XML views of relational databases. In our setting, the XML view is specified by a query in the declarative query language of a middle-ware system, called SilkRoute. The middle-ware system evaluates a query by sending one or more SQL queries to the target relational database, integrating the resulting tuple streams, and adding the XML tags. We focus on how to best choose the SQL queries, without having control over the target RDBMS.

This paper explains a novel manipulation framework for XML. The key idea is to choose some example XML elements existing in the database and show the system how to manipulate them. The system then infers how to manipulate the whole collection of XML documents. The framework is unique in that while other approaches require users to write (or draw) explicit query specifications in their own query languages, ours needs implicit specifications through example operations. The problem is challenging, because XML documents can be semistructured data and inferring the intended operation is not trivial. Our algorithm is based on tree-style object modeling and path-expressions with wild-cards to infer the user's intention. The paper presents the object modeling, its inference mechanism, and some results of our preliminary experiments.