Information Extraction (IE)-the problem of extracting structured information from unstructured text - has become the key enabler for many enterprise applications such as semantic search, business analytics and regulatory compliance. While rule-based IE systems are widely used in practice due to their well-known "explainability," developing high-quality information extraction rules is known to be a labor-intensive and time-consuming iterative process.

Rule-based information extraction from text is increasingly being used to populate databases and to support structured queries on unstructured text. Specification of suitable information extraction rules requires considerable skill and standard practice is to refine rules iteratively, with substantial effort. In this paper, we show that techniques developed in the context of data provenance, to determine the lineage of a tuple in a database, can be leveraged to assist in rule refinement. Specifically, given a set of extraction rules and correct and incorrect extracted data, we have developed a technique to suggest a ranked list of rule modifications that an expert rule specifier can consider. We implemented our technique in the SystemT information extraction system developed at IBM Research -- Almaden and experimentally demonstrate its effectiveness.

A spreadsheet-like "direct manipulation" interface is more intuitive for many non-technical database users compared to traditional alternatives, such as visual query builders. The construction of such a direct manipulation interface may appear straightforward, but there are some significant challenges. First, individual direct manipulation operations cannot be too complex, so expressive power has to be achieved through composing (long) sequences of small operations. Second, all intermediate results are visible to the user, so grouping and ordering are material after every small step. Third, users often find the need to modify previously specified queries. Since manipulations are specified one step at a time, there is no actual queryexpression to modify. Suitable means must be provided to address this need. Fourth, the order in which manipulations are performed by the user should not affect the results obtained, to avoid user confusion. We address the aforementioned challenges by designing a new spreadsheet algebra that: i) operates on recursively grouped multi-sets, ii) contains a selectively designed set of operators capable of expressing at least all single-block SQL queries and can be intuitively implemented in a spreadsheet, iii) enables query modification by the notion of modifiable query state, and iv) requires no ordering in unary data manipulation operators since they are all designed to commute. We built a prototype implementation of the spreadsheet algebra and show, through user studies with non-technical subjects, that the resultant query interface is easier to use than a standard commercial visual query builder.

When a database query has a large number of results, the user can only be shown one page of results at a time. One popular approach is to rank results such that the "best" results appear first. This approach is well-suited for information retrieval, and for some database queries, such as similarity queries or under-specified (or keyword) queries with known (or guessable) user preferences. However, standard database query results comprise a set of tuples, with no associated ranking. It is typical to allow users the ability to sort results on selected attributes, but no actual ranking is defined.

When a database query has a large number of results, the user can only be shown one page of results at a time. One popular approach is to rank results such that the "best" results appear first. However, standard database query results comprise a set of tuples, with no associated ranking. It is typical to allow users the ability to sort results on selected attributes, but no actual ranking is defined. An alternative approach to the first page is not to try to show the best results, but instead to help users learn what is available in the whole result set and direct them to finding what they need. In this paper, we demonstrate through a user study that a page comprising one representative from each of k clusters (generated through a k -medoid clustering) is superior to multiple alternative candidate methods for generating representatives of a data set. Users often refine query specifications based on returned results. Traditional clustering may lead to completely new representatives after a refinement step. Furthermore, clustering can be computationally expensive. We propose a tree-based method for efficiently generating the representatives, and smoothly adapting them with query refinement. Experiments show that our algorithms outperform the state-of-the-art in both result quality and efficiency.

Queries posed to database systems often involve Universal Quantification. Such queries are typically expensive to evaluate. While they can be handled by basic access methods, for selection, grouping, etc., new access methods specifically tailored to evaluate universal quantification can greatly decrease the computational cost. In this paper, we study the efficient evaluation of universal quantification in an XML database. Specifically, we develop a small taxonomy of universal quantification types, and define a family of algorithms suitable for handling each. We experimentally demonstrate the performance benefits of the new family of algorithms.

More and more applications require peer-to-peer (P2P) systems to support complex queries over multi-dimensional data. For example, a P2P auction network for real estate frequently needs to answer queries such as "select five available buildings closest to the airport". Such queries are not efficiently supported in current P2P systems. Towards an efficient and scalable P2P system capable of processing complex multi-dimensional queries, we first propose a comprehensive framework for sharing, indexing, and querying multi-dimensional data, where (i) peers with more computational power coordinate indexing and query processing, and (ii) other peers participate in part of the computation in order to achieve scalability and load-balance. Based on this framework, we propose Network-R-tree (NR-tree), a P2P adaptation of the dominant spatial index - R*-tree. NR-tree, indexing spatial data at clustered peers, is capable of processing complex queries such as range queries and k-nearest neighbor queries. We propose query processing algorithms for range and k-nearest neighbor queries and experimentally prove the effectiveness of proposed techniques with real data.

Caching has been an important technique for saving network traffic and reducing response time, especially in mobile environments where bandwidth is often a scarce resource. In this paper, we propose a novel approach for caching multidimensional data in a cluster of mobile devices. In particular, we focus on the most common types of multi-dimensional queries, namely range and k-nearest neighbor queries, by computing a cacheable region for every query, caching the result at the client, and indexing it in an R*-tree at the cluster gateway. Subsequent queries are first issued to the R*-tree and only remainder queries or queries that cannot be guaranteed exact answers are sent to the remote data server. To the best of our knowledge, our work is the first to study caching results from complex multi-dimensional queries (e.g., kNN query) and propose to build an R*-tree on previously fetched query results in a cluster of mobile devices. Rigorous experiments show that our approach significantly reduces network traffic and response time.

Moving objects (e.g., vehicles in road networks) continuously generate large amounts of spatio-temporal information in the form of data streams. Efficient management of such streams is a challenging goal due to the highly dynamic nature of the data and the need for fast, online computations. We present a novel approach for approximate query processing about the present, past, or the future in spatio-temporal databases. In particular, we first propose an incrementally updateable, multidimensional histogram for present-time queries. Second, we develop a general architecture for maintaining and querying historical data. Third, we implement a stochastic approach for predicting the results of queries that refer to the future. Finally, we experimentally prove the effectiveness and efficiency of our techniques using a realistic simulation.

Existing methods for peediction spatio-temporal databases assume that objects move according to linear functions. This severely limits their applicability, since in practice movement is more complex, and individual objects may follow drastically diffferent motion patterns. In order to overcome these problems, we first introduce a general framework for monitoring and indexing moving objects, where (i) each boject computes individually the function that accurately captures its movement and (ii) a server indexes the object locations at a coarse level and processes queries using a filter-refinement mechanism. Our second contribution is a novel recursive motion function that supports a broad class of non-linear motion patterns. The function does not presume any a-priori movement but can postulate the particular motion of each object by examining its locations at recent timestamps. Finally. we propse an efficient indexing scheme that faciliates the processing of predicitive queries without false misses.