Many applications that process social data, such as tweets, must extract entities from tweets (e.g., "Obama" and "Hawaii" in "Obama went to Hawaii"), link them to entities in a knowledge base (e.g., Wikipedia), classify tweets into a set of predefined topics, and assign descriptive tags to tweets. Few solutions exist today to solve these problems for social data, and they are limited in important ways. Further, even though several industrial systems such as OpenCalais have been deployed to solve these problems for text data, little if any has been published about them, and it is unclear if any of the systems has been tailored for social media. In this paper we describe in depth an end-to-end industrial system that solves these problems for social data. The system has been developed and used heavily in the past three years, first at Kosmix, a startup, and later at WalmartLabs. We show how our system uses a Wikipedia-based global "real-time" knowledge base that is well suited for social data, how we interleave the tasks in a synergistic fashion, how we generate and use contexts and social signals to improve task accuracy, and how we scale the system to the entire Twitter firehose. We describe experiments that show that our system outperforms current approaches. Finally we describe applications of the system at Kosmix and WalmartLabs, and lessons learned.

Many applications increasingly employ information extraction and integration (IE/II) programs to infer structures from unstructured data. Automatic IE/II are inherently imprecise. Hence such programs often make many IE/II mistakes, and thus can significantly benefit from user feedback. Today, however, there is no good way to automatically provide and process such feedback. When finding an IE/II mistake, users often must alert the developer team (e.g., via email or Web form) about the mistake, and then wait for the team to manually examine the program internals to locate and fix the mistake, a slow, error-prone, and frustrating process.

A common criticism of database systems is that they are hard to query for users uncomfortable with a formal query language. To address this problem, form-based interfaces and keyword search have been proposed; while both have benefits, both also have limitations. In this paper, we investigate combining the two with the hopes of creating an approach that provides the best of both. Specifically, we propose to take as input a target database and then generate and index a set of query forms offline. At query time, a user with a question to be answered issues standard keyword search queries; but instead of returning tuples, the system returns forms relevant to the question. The user may then build a structured query with one of these forms and submit it back to the system for evaluation. In this paper, we address challenges that arise in form generation, keyword search over forms, and ranking and displaying these forms. We explore techniques to tackle these challenges, and present experimental results suggesting that the approach of combining keyword search and form-based interfaces is promising.

The rapid growth of Web communities has motivated many solutions for building community data portals. These solutions follow roughly two approaches. The first approach (e.g., Libra, Citeseer, Cimple) employs semi-automatic methods to extract and integrate data from a multitude of data sources. The second approach (e.g., Wikipedia, Intellipedia) deploys an initial portal in wiki format, then invites community members to revise and add material. In this paper we consider combining the above two approaches to building community portals. The new hybrid machine-human approach brings significant benefits. It can achieve broader and deeper coverage, provide more incentives for users to contribute, and keep the portal more up-to-date with less user effort. In a sense, it enables building "community wikipedias", backed by an underlying structured database that is continuously updated using automatic techniques. We outline our ideas for the new approach, describe its challenges and opportunities, and provide initial solutions. Finally, we describe a real-world implementation and preliminary experiments that demonstrate the utility of the new approach.

Data integration systems often provide a uniform query interface, called amediated schema, to a multitude of data sources. To answer user queries, such systems employ a set ofsemantic matchesbetween the mediated schema and the data-source schemas. Finding such matches is well known to be difficult. Hence much work has focused on developing semi-automatic techniques to efficiently find the matches. In this paper we consider the complementary problem ofimproving the mediated schema, to make finding such matches easier. Specifically, a mediated schemaSwill typically be matched with many source schemas. Thus,can the developer of S analyze and revise S in a way that preserves S's semantics, and yet makes it easier to match with in the future? In this paper we provide an affirmative answer to the above question, and outline a promising solution direction, calledmSeer. Given a mediated schemaSand a matching toolM,mSeerfirst computes a matchability score that quantifies how wellScan be matched against usingM. Next,mSeeruses this score to generate a matchability report that identifies the problems in matchingS.Finally,mSeeraddresses these problems by automatically suggesting changes toS(e.g., renaming an attribute, reformatting data values, etc.) that it believes will preserve the semantics ofSand yet make it more amenable to matching. We present extensive experiments over several real-world domains that demonstrate the promise of the proposed approach.

In this paper, we introduce PLACE*, a distributed spatio-temporal data stream management system for moving objects. PLACE* supports continuous spatio-temporal queries that hop among a network of regional servers. To minimize the execution cost, a new Query-Track- Participate (QTP) query processing model is proposed inside PLACE*. In the QTP model, a query is continuously answered by a querying server, a tracking server, and a set of participating servers. In this paper, we focus on query plan generation, execution and update algorithms for continuous range queries in PLACE* using QTP. An extensive experimental study demonstrates the effectiveness of the proposed algorithms in PLACE*.

WLAN location estimation based on 802.11 signal strength is becoming increasingly prevalent in today's pervasive computing applications. Among the well-established location determination approaches, probabilistic techniques show good performance and, thus, become increasingly popular. For these techniques to achieve a high level of accuracy, however, a large number of training samples are usually required for calibration, which incurs a great amount of offline manual effort. In this paper, we aim to solve the problem by reducing both the sampling time and the number of locations sampled in constructing a radio map. We propose a novel learning algorithm that builds location-estimation systems based on a small fraction of the calibration data that traditional techniques require and a collection of user traces that can be cheaply obtained. When the number of sampled locations is reduced, an interpolation method is developed to effectively patch a radio map. Extensive experiments show that our proposed methods are effective in reducing the calibration effort. In particular, unlabeled user traces can be used to compensate for the effects of reducing the calibration effort and can even improve the system performance. Consequently, manual effort can be reduced substantially while a high level of accuracy is still achieved

An important goal of indoor location estimation systems is to increase the estimation accuracy while reducing the power consumption. In this paper, we present a novel algorithm known as CaDet for power-efficient location estimation by intelligently selecting the number of access points (APs) used for location estimation. We show that by employing machine learning techniques, CaDet is able to use a small subset of the APs in the environment to detect a client's location with high accuracy. CaDet uses a combination of information theory, clustering analysis, and a decision tree algorithm. By collecting data and testing our algorithms in a realistic WLAN environment in the computer science department area of the Hong Kong University of Science and Technology, we show that CaDet (clustering and decision tree-based method) can be much higher in accuracy as compared to other methods. We also show through experiments that, by intelligently selecting APs, we are able to save the power on the client device while achieving the same level of accuracy.

In the area of cost-sensitive learning, inductive learning algorithms have been extended to handle different types of costs to better represent misclassification errors. Most of the previous works have only focused on how to deal with misclassification costs. In this paper, we address the equally important issue of how to handle the test costs associated with querying the missing values in a test case. When an attribute contains a missing value in a test case, it may or may not be worthwhile to take the extra effort in order to obtain a value for that attribute, or attributes, depending on how much benefit the new value bring about in increasing the accuracy. In this paper, we consider how to integrate test-cost-sensitive learning with the handling of missing values in a unified framework that includes model building and a testing strategy. The testing strategies determine which attributes to perform the test on in order to minimize the sum of the classification costs and test costs. We show how to instantiate this framework in two popular machine learning algorithms: decision trees and naive Bayesian method. We empirically evaluate the test-cost-sensitive methods for handling missing values on several data sets.

WLAN location estimation based on 802.11 signal strength is becoming increasingly prevalent in today’s pervasive computing applications. As an alternative to the well-established deterministic approaches, probabilistic location determination techniques show good performance and thus become increasingly popular. For these techniques to achieve a high level of accuracy, however, adequate training samples should be collected offline for calibration. As a result, a great amount of manual effort is incurred. In this paper, we aim to solve the problem by reducing both the sampling time and the number of locations sampled in constructing the radio map. A learning algorithm is proposed to build location estimation systems based on a small fraction of the calibration data that traditional techniques require and a collection of user traces that can be cheaply obtained. Our experiments show that unlabeled user traces can be used to compensate for the effects of reducing calibration effort and can even improve the system performance. Consequently, manual effort can be significantly reduced while a high level of accuracy is still achieved.

Inductive learning techniques such as the naive Bayes and decision tree algorithms have been extended in the past to handle different types of costs mainly by distinguishing different costs of classification errors. However, it is an equally important issue to consider how to handle the test costs associated with querying the missing values in a test case. When the value of an attribute is missing in a test case, it may or may not be worthwhile to take the effort to obtain its missing value, depending on how much the value results in a potential gain in the classification accuracy. In this paper, we show how to obtain a test-cost sensitive naive Bayes classifier (csNB) by including a test strategy which determines how unknown attributes are selected to perform test on in order to minimize the sum of the mis-classification costs and test costs. We propose and evaluate several potential test strategies including one that allows several tests to be done at once. We empirically evaluate the csNB method, and show that it compares favorably with its decision tree counterpart.