Abstract We study the Revenue Maximization (RM) problem in a two-phase marketing scenario consisting of a presale phase and an official sale phase. In the presale phase, users are influenced through social diffusion and are offered discounts. In the official phase, mass-media influence is modeled as a community-based stochastic process, incorporating conformity effects within communities. This scenario better reflects real-world marketing practices. However, the resulting RM problem is NP-hard and non-submodular, rendering traditional greedy approaches ineffective. To address this, we employ the sandwich approximation (SA) strategy to provide theoretical guarantees. Furthermore, we propose the Community-Based Greedy Algorithm (CBGA), which incorporates a general improvement strategy applicable to greedy selection methods based on Monte Carlo simulation or Reverse Influence Sampling. CBGA adopts a divide-and-conquer approach by performing greedy selection within each community, thereby improving the runtime efficiency. The integration of CBGA with the SA strategy yields a structure-dependent theoretical guarantee, with the approximation quality determined by the number of boundary nodes between communities. We further extend our model to more general settings. We experimentally validate that CBGA matches the performance of all baselines but runs faster on six real-world datasets.

To maintain popularity on social media over the long term, users need to shift to a new topic instead of sticking to one topic. When selecting a new topic, a user needs to consider both its popularity on the entire social media and its popularity among the current followers. The former affects the expected number of new followers, and the latter affects the expected ratio of the current followers the user can retain after the topic change. The timing is also important. The user should change to a new topic before the current topic becomes less popular and the user loses many of the current followers. If the user change the topic after losing the followers, it is more difficult to obtain new followers. In this paper, we introduce a new task based on these observations: recommending appropriate new topics for currently popular social media users at appropriate timing. As an example of opportunities in the research on this task, we also propose a simple method of predicting the popularity a given user would gain after shifting to a given new topic. Our method predicts it based on the similarity between the user’s current topic and the given new topic. In our experiment with data collected from X (formerly Twitter), our method improves the prediction accuracy compared with a baseline method.

We propose a method of evaluating exclusion queries in keywordbased image retrieval.Image retrieval based on the presence of search terms in the associated text can achieve high precision, while its recall is often low because of the incompleteness of available text data.Low recall is rarely a serious problem in Web search because Web search is usually precision-oriented.By contrast, keywordbased exclusion queries for image retrieval, which include negative terms specifying what to exclude, often have low precision because of the incomplete exclusion based on the presence of the negative terms in incomplete text data.To avoid that, we exclude unwanted images not based on the presence of the negative terms, but based on the content-based similarity to images retrieved by the negative terms.Our experiment shows that our method improves the precision of exclusion queries in keyword-based image retrieval.

Many existing spammer detection methods uses dependency between workers’ answers and the true answers. These methods may regard a diligent but low-skilled worker as a spammer. Our method uses correlation between workers’ task completion time and the difficulty of the tasks. Our experimental result suggests that this approach is potentially useful, but the selection of tasks seems a key for success.

In this paper, we introduce a new recipe dataset MIRecipe (Multimedia-Instructional Recipe). It has both text and image data for every cooking step, while the conventional recipe datasets only contain final dish images, and/or images only for some of the steps. It consists of 26,725 recipes, which include 239,973 steps in total. The recognition of ingredients in images associated with cooking steps poses a new challenge: Since ingredients are processed during cooking, the appearance of the same ingredient is very different in the beginning and finishing stages of the cooking. The general object recognition methods, which assume the constant appearance of objects, do not perform well for such objects. To solve the problem, we propose two stage-aware techniques: stage-wise model learning, which trains a separate model for each stage, and stage-aware curriculum learning, which starts with the training data from the beginning stage and proceeds to the later stages. Our experiment with our dataset shows that our method achieves higher accuracy than the model trained using all the data without considering the stages. Our dataset is available at our GitHub repository.

This paper proposes a method of suggesting expanded queries that disambiguate the original Web query which has multiple interpretations. In order to produce a diverse set of queries including those corresponding to infrequent query intents, our method produces queries by extracting phrases connecting given query terms from a corpus. We use a corpus because infrequent query intents may not appear in query logs. We use phrase queries because we need sufficiently specific queries for retrieving pages corresponding to infrequent query intents out of many pages corresponding to popular query intents. Phrase queries usually have high accuracy but low recall. In order to also achieve high recall, we use a disjunction of many phrase queries as a query. Our method first produces many phrase queries by using term expansion and phrase extraction from a corpus, then group semantically similar phrases into clusters, and use each cluster as a disjunctive set of phrase queries.

In this paper, we propose a method of improving accuracy of multiclass classification tasks in crowdsourcing. In crowdsourcing, it is important to assign appropriate workers to appropriate tasks. In multiclass classification, different workers are good at different subcategories. In our method, we reorganize a given flat classification task into a hierarchical classification task consisting of several subtasks, and assign each worker to an appropriate subtask. In this approach, it is important to choose a good hierarchy. In our method, we first post a flat classification task with a part of data and collect statistics on each worker's ability. Based on the obtained statistics, we simulate all candidate hierarchical schemes, estimate their expected accuracy, choose the best scheme, and post it with the rest of data. In our method, it is also important to allocate workers to appropriate subtasks. We designed several greedy worker allocation algorithms. The results of our experiments show that our method improves the accuracy of multiclass classification tasks.

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.

In this paper, we report our experience in constructing a cooking recipe text corpus. We describe problems we found and explain how we managed them. One of the problems we faced in the construction of our recipe corpus is the difficulty of establishing a clear, stable, and complete guideline instructing annotators how to annotate. During the annotation, we found many unexpected cases for which the pre-defined guideline is not clear enough, and even cases for which the pre-defined guideline provides no guidance at all. As a result, we needed to update the guideline twice during the annotation, and also needed to revise annotations we have done before the updates. During that process, we have several trade-offs, and it is not easy to decide when and how often we should revise the annotations. It is even unclear whether we should revise them or should instead use the human resource for annotating more data. We show an experiment, whose result suggests that we should revise the old annotations. Another problem we had is the management of versions of the guideline, sets of annotations corresponding to them, and communication between participants.

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.

In this paper, we propose a method of retrieving posts on social networking services (SNSs) by specifying a pair of queries: a topic query and an entity query. A topic query specifies the topic of the posts to retrieve (e.g., "iPhone") and an entity query specifies the type of users who posted them (e.g., "students"). In the existing search systems for SNS posts, we can specify topics of posts by keywords, but we cannot specify types of users. Even if we include keywords specifying types of users in a query, such keywords are not usually included in tweets or user profile data. In our method, we estimate types of users by learning vocabulary whose appearance is correlated with specific types of users. We learn it from the datasets obtained through Web search. We retrieve Web documents through the search with a keyword specifying the type of users (e.g., "student"), and we also retrieve Web documents by using a keyword specifying its opposite (e.g., "adult"). We regard the documents retrieved by these queries as positive and negative examples of documents describing the target type, and we train a model for recognizing users of the given type. We recognize users of the target type by inputting their posts and their profile data into the model. We use Web documents instead of SNS posts for training the model because the Web has more documents describing types of people.

In this paper, we propose a method to support book search tasks where users issue a query describing the story in a book to a database storing brief descriptions of books. Such a query may include extraneous words that do not appear in the brief description of the book in the database. In addition, queries by users who only have vague memories of the stories may even include wrong keywords. In order to find books with such queries, we need a query relaxation scheme. In the scheme we propose in this paper, we classify words in a user query describing a book into four types based on their roles in the description, and for each type, we estimate the probability of their appearance in the description in the database. We estimate it based on statistics we obtained through an analysis of an archive of queries and answers in the past. We then generate relaxed queries by using every subset of the words in the user query, and rank the queries based on the expected ranking of the target book in their results. The expected ranking of the target book in a query result is estimated by using appearance probabilities of words in the query and the number of books matching the query. We conducted an experiment for comparing various ranking schemes by their MRR, and our ranking scheme that uses both the word appearance probabilities and the number of matching books showed a good performance.

In this paper, we propose a method of improving accuracy of multiclass classification tasks in crowdsourcing. In order to improve quality of outputs in crowdsourcing, it is important to assign workers to tasks they are good at. In multiclass classification tasks, which are common in crowdsourcing, sometimes different workers are good at different subcategories. It suggests that we can improve the accuracy of a multiclass classification task by reorganizing the task into a hierarchical classification task, and assigning workers to appropriate sub-tasks in the hierarchy. We experimentally show that we can actually improve the accuracy of a classification task by this approach. We collected performance data of workers in a flat multiclass classification task on Amazon Mechanical Turk, and simulated the process of the reorganization and the worker allocation. We confirmed that the output in the simulation achieves higher accuracy than that of the original flat classification task.

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.

In this paper, we propose a method of ranking recently created Twitter accounts according to their prospective popularity. Early detection of new promising accounts is useful for trend prediction, viral marketing, user recommendation, and so on. New accounts are, however, difficult to evaluate because they have not yet established the reputation they deserve, and we cannot apply existing link-based or other popularity-based account evaluation methods. Our method first finds early adopters, i.e., users who often find new good information sources earlier than others. Our method then regards new accounts followed by good early adopters as promising, even if they do not have many followers now. In order to find good early adopters, we estimate the frequency of link propagation from each account, i.e., how many times the follow links from the account have been copied by its followers. If the frequency is high, the account must be a good early adopter who often find good information sources earlier than its followers. We develop a method of inferring which links are created by copying which links. One important advantage of our method is that our method only uses information that can be easily obtained only by crawling neighbors of the target accounts in the current Twitter graph. We evaluated our method by an experiment on Twitter data. We chose then-new accounts from an old snapshot of Twitter, compute their ranking by our method, and compare it with the ranking based on the number of followers the accounts currently have. The result shows that our method produces better rankings than various baseline methods, especially for very new accounts that have only a few followers.

We propose a method for extracting logical hierarchical structure of HTML documents. Because mark-up structure in HTML documents does not necessarily coincide with logical hierarchical structure, it is not trivial how to extract logical structure of HTML documents. Human readers, however, easily understand their logical structure. The key information used by them is headings in the documents. Human readers exploit the following properties of headings: (1) headings appear at the beginning of the corresponding blocks, (2) headings are given prominent visual styles, (3) headings of the same level share the same visual style, and (4) headings of higher levels are given more prominent visual styles. Our method also exploits these properties for extracting hierarchical headings and their associated blocks. Our experiment shows that our method outperforms existing methods. In addition, our method extracts not only hierarchical blocks but also their associated headings.

Many microblog messages remain useful only within a short time, and users often find such a message after its informational value has vanished. Users also sometimes miss old but still useful messages buried among outdated ones. To solve these problems, we develop a method of classifying messages into the following three categories: (1) messages that users should read now because their value will diminish soon, (2) messages that users may read later because their value will not largely change soon, and (3) messages that are not useful anymore because their value has vanished. Our method uses an error correcting output code consisting of binary classifiers each of which determines whether a given message has value at specific time point. Our experiments on Twitter data confirmed that it outperforms naive methods.

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.

Nowadays the Web and Web browsers have become the most important and universal platform for people to search, view, process, and exchange various kinds of information. Consequently, today's users usually open many Web pages simultaneously in order to perform multiple tasks in parallel, which makes Web browsers crucial in our daily task management. However, no existing Web browser provides users with sufficient support for the management of many tabs or windows of opened pages. On the other hand, wide displays have become more affordable and prevalent, while extra space on those displays is not utilized effectively in Web browsing. In this paper, we propose a new Web browser interface aiming to support efficient task management in Web browsing on wide displays. In order to help users switch between opened Web pages, we show thumbnails of the pages in the extra space around the currently focused page. In the page thumbnails, we emphasize distinctive elements in each page in order to make the selection of the thumbnails easier. In addition, we calculate the relevance between pages based on users' switching history, and emphasize pages relevant to the current page by adjusting the size or opacity of the thumbnails. This further helps users find the thumbnails of needed pages, and also helps users get the overview of the page set related to the current task.

Distributed SOA computing environments usually use SOAP intermediaries that sit between senders and receivers to mediate SOAP messages. The intermediaries may add support services to the SOAP message exchange, such as routing, logging, and security. The typical processing by a SOAP intermediary is parsing the incoming SOAP messages, checking the data in each message, and then serializing the messages to put them back into the network. DOM is one of the popular interfaces to navigate an XML tree. Existing DOM implementations are not efficient for SOAP intermediary processing. Existing DOM implementations parse XML data to create tree data and traverse the tree data for serialization. Typically, a SOAP intermediary rarely modifies the tree data. In such situations, creating the tree data and serializing it back into XML data is computationally expensive. We propose a DOM implementation based on a hybrid data representation that uses both literal XML and DOM objects. In our implementation, a SOAP intermediary stores the original literal XML representation and reuses it to avoid traversing all of the tree data during serialization. We prototyped the DOM implementation and evaluated its performance.

We propose new interaction techniques that support better browsing of large HTML tables on small screen devices, such as mobile phones. We propose three modes for browsing tables: normal mode, record mode, and cell mode. Normal mode renders tables in the ordinary way, but provides various useful functions for browsing large tables, such as hiding unnecessary rows and columns. Record mode regards each row (or column) as the basic information unit and displays it in a record-like format with column (or row) headers, while cell mode regards each cell as the basic unit and displays each cell together with its corresponding row and column headers. For these table presentations, we need to identify row and column headers that explain the meaning of rows and columns. To provide users with both row and column headers even when the tables have attributes for only one of them, we introduce the concept of keys and develop a method of automatically discovering attributes and keys in tables. Another issue in these presentations is how to handle composite cells spanning multiple rows or columns. We determine the semantics of such composite cells and render them in appropriate ways in accordance with their semantics.

Web services use an interoperable and loosely coupled data exchange architecture. Web services processing can cause significant runtime overhead, especially when the number of fine-grained transactions becomes large. Although some best-practice guidelines recommend coarse-grained messages to improve the performance of web services, coarse-grained services may interfere with the componentization of the services. Service granularity should be designed for reusability and modularity. In this paper, we propose a SOAP message bundling framework. This framework enables bundling multiple messages into one message. With this framework, application developers do not have to consider the service granularity. Instead, the framework bundles some fine-grained messages into a single coarse-grained message. To support this framework, we provide for service providers (1) a WSDL conversion tool and (2) a skeleton wrapper generator. These tools let service providers receive bundled messages without modifying existing service implementations. We also provide (3) a stub wrapper generator that allows service requesters to use bundled services easily. The existing message exchanges are not influenced by this framework. We evaluated the performance gain in experiments using the Google SOAP API. The results showed that our approach improves the performance of web services.

This paper shows a scheme for incremental evaluation of XPath queries. Here, we focus on a monotone fragment of XPath, i.e., when a data is deleted from (or inserted to) the database, only deletion (insertion, resp.) may occur to query answers. For efficiently processing deletions, we store information on partial matchings, i.e., which elements were participating in matchings for which query answers, and also store counters showing how many matchings each query answer had. We use the information on the partial matchings also for skipping a part of computation upon data insertion. We investigate properties of the XPath fragment in order to keep the amount of information we store as small as possible.

In this paper, we address the problem of cache replacement for transcoding proxy caching. First, an efficient cache replacement algorithm is proposed. Our algorithm considers both the aggregate effect of caching multiple versions of the same multimedia object and cache consistency. Second, a complexity analysis is presented to show the efficiency of our algorithm. Finally, some preliminary simulation experiments are conducted to compare the performance of our algorithm with some existing algorithms. The results show that our algorithm outperforms others in terms of the various performance metrics.

Archiving is important for scientific data, where it is necessary to record all past versions of a database in order to verify findings based upon a specific version. Much scientific data is held in a hierachical format and has a key structure that provides a canonical identification for each element of the hierarchy. In this article, we exploit these properties to develop an archiving technique that is both efficient in its use of space and preserves the continuity of elements through versions of the database, something that is not provided by traditional minimum-edit-distance diff approaches. The approach also uses timestamps. All versions of the data are merged into one hierarchy where an element appearing in multiple versions is stored only once along with a timestamp. By identifying the semantic continuity of elements and merging them into one data structure, our technique is capable of providing meaningful change descriptions, the archive allows us to easily answer certain temporal queries such as retrieval of any specific version from the archive and finding the history of an element. This is in contrast with approaches that store a sequence of deltas where such operations may require undoing a large number of changes or significant reasoning with the deltas. A suite of experiments also demonstrates that our archive does not incur any significant space overhead when contrasted with diff approaches. Another useful property of our approach is that we use XML format to represent hierarchical data and the resulting archive is also in XML. Hence, XML tools can be directly applied on our archive. In particular, we apply an XML compressor on our archive, and our experiments show that our compressed archive outperforms compressed diff-based repositories in space efficiency. We also show how we can extend our archiving tool to an external memory archiver for higher scalability and describe various index structures that can further improve the efficiency of some temporal queries on our archive.

We present an archiving technique for hierarchical data with key structure. Our approach is based on the notion of timestamps whereby an element appearing in multiple versions of the database is stored only once along with a compact description of versions in which it appears. The basic idea of timestamping was discovered by Driscoll et. al. in the context of persistent data structures where one wishes to track the sequences of changes made to a data structure. We extend this idea to develop an archiving tool for XML data that is capable of providing meaningful change descriptions and can also efficiently support a variety of basic functions concerning the evolution of data such as retrieval of any specific version from the archive and querying the temporal history of any element. This is in contrast to diff-based approaches where such operations may require undoing a large number of changes or significant reasoning with the deltas. Surprisingly, our archiving technique does not incur any significant space overhead when contrasted with other approaches. Our experimental results support this and also show that the compacted archive file interacts well with other compression techniques. Finally, another useful property of our approach is that the resulting archive is also in XML and hence can directly leverage existing XML tools.

While a query result in a traditional database is a subset of the database, in a video database, it is a set of subintervals extracted from the raw video sequence. It is very hard, if not impossible, to predetermine all the queries that will be issued in the future, and all the subintervals that will become necessary to answer them. As a result, conventional query frameworks are not applicable to video databases. We propose a new video query model that computes query results by dynamically synthesizing needed subintervals from fragmentary indexed intervals in the database. We introduce new interval operations required for that computation. We also propose methods to compute relative relevance of synthesized intervals to a given query. A query result is a list of synthesized intervals sorted in the order of their degree of relevance.

This paper presents an equational formulation of an object-oriented data model. In this model, a database is represented as a system of equations over a set of oid's, and a database query is a transformation of a system of equations into another system of equations. During the query processing, our model maintains an equivalence relation over oid's that relates oid's corresponding to the same "real-world entity." By this mechanism, the model achieves a declarative set-based query language and views for objects with identity. Moreover, the query primitives are designed so that queries including object traversal can be evaluated in a data-parallel fashion.

Access control in function granularity is one of the features of many object-oriented databases. In those systems, the users are granted rights to invoke composed functions instead of rights to invoke primitive operations. Although primitive operations are invoked inside composed functions, the users can invoke them only through the granted functions. This achieves access control in abstract operation level. Access control utilizing encapsulated functions, however, easily causes many "security flaws" through which malicious users can bypass the encapsulation and can abuse the primitive operations inside the functions. In this paper, we develop a technique to statically detect such security flaws. First, we design a framework to describe security requirements that should be satisfied. Then, we develop an algorithm that syntactically analyzes program code of the functions and determines whether given security requirements are satisfied or not. This algorithm is sound, that is, whenever there is a security flaw, it detects it.

We present a typed polymorphic calculus that supports a general mechanism for view definition and object sharing among classes. In this calculus, a class can contain inclusion specifications of objects from other classes. Each such specification consists of a predicate determining the subset of objects to be included and a viewing function under which those included objects are manipulated. Both predicates and viewing functions can be any type consistent programs definable in the polymorphic calculus. Inclusion specifications among classes can be cyclic, allowing mutually recursive class definitions. These features achieve flexible view definitions and wide range of class organizations in a compact and elegant way. Moreover, the calculus provides a suitable set of operations for views and classes so that the programmer can manipulate views and classes just the same way as one deals with ordinary records and sets.