The ranked retrieval model has rapidly become the de facto way for search query processing in client-server databases, especially those on the web. Despite of the extensive efforts in the database community on designing better ranking functions/mechanisms, many such databases in practice still fail to address the diverse and sometimes contradicting preferences of users on tuple ranking, perhaps (at least partially) due to the lack of expertise and/or motivation for the database owner to design truly effective ranking functions. This project takes a different route on addressing the issue by defining a novel query reranking problem.
Structured hidden databases are widely prevalent on the Web. They provide restricted form-like search interfaces that allow users to execute search queries by specifying desired attribute values of the sought-after tuples, and the system responds by returning a few (e.g., top-k) tuples that satisfy the selection conditions, sorted by a suitable ranking function. The top-k output constraint prevents many interesting third-party (e.g., mashup) services from being developed over real-world web databases. This research involves developing effective techniques for retrieving more than top-k tuples for any query and support additional rank based analytics such as estimating the rank of a tuple or compare the rank of two arbitrary tuples to determine which of them is highly ranked. Our techniques access the hidden structured databases via their public interfaces and operate without any knowledge of the underlying static ranking function.
The objective of this project is to understand, evaluate, and contribute towards the suppression of sensitive aggregates over hidden databases. While owners of hidden databases would like to allow individual search queries, many also want to maintain a certain level of privacy for aggregates over their hidden databases. This has implications in the commercial domain (e.g., to prevent competitors from gaining strategic advantages) as well as in homeland-security related applications (e.g., to prevent potential terrorists from learning flight occupancy distributions). This project investigates techniques to suppress the sensitive aggregates while maintaining the usability of hidden databases for bona fide search users.
Structured hidden databases are widely prevalent on the Web. They provide restricted form-like search interfaces that allow users to execute search queries by specifying desired attribute values of the sought-after tuples, and the system responds by returning a few (e.g., top-k) tuples that satisfy the selection conditions, sorted by a suitable ranking function. Although search interfaces for hidden databases are designed with focused search queries in mind, for certain applications it may be advantageous to infer more aggregated views of the data from the returned results of search queries. This research involves developing effective techniques for performing data analytics, especially sampling, over hidden structured databases via their public interfaces. The outcomes include efficient algorithms for sampling hidden databases with a heterogeneous mix of data types, achievability results for sampling different types of search interfaces, and a prototypical toolset which demonstrates the sampling of real-world hidden databases.
The widespread use and growing popularity of online collaborative content sites today has created rich resources for users to consult in order to make purchasing decisions on various items such as movies, restaurants, e-commerce products, etc. It has also created new opportunities for content producers of such web items to design new improved items, compose eye-catching advertisement snippets, etc. in order to improve business. This project concerns developing data mining and exploration algorithms for performing aggregate analytics over user feedback (ratings, tags, likes, visits, etc.) available from collaborative content sites in order to benefit experience and decision making of both content producers and consumers. The key challenges exist in the form of information explosion and overload, besides user-item interaction intractability.
The ever-expanding volume and increasing complexity of information on the web has made recommendation systems essential tools for users in a variety of information seeking or e-commerce activities. Moreover, new research suggests that every digital comment made by users anywhere - a product review, social book-marking, tweets, blogs, activities on a social network site, e-mails can be mined for hints as to emotions and other thoughts. In this body of work, we intend to design novel query answering models considering the paradigm of recommendation. Our previous and ongoing works in that space consider novel recommendation problems, such as recommending items to a group of users, recommending composite items to a user, and so on. In the modeling of these problems, we tap into the latent social information sources and leverage that in a principled way to enhance query-answering tasks, and analyze that information for future learning and opportunities.
Crowdsourcing systems have gained popularity in a variety of domains. The next generation crowdsourcing systems will be collaborative and knowledge-intensive in nature. They need to treat the crowdsourcing problem not in optimization silos, but as an adaptive optimization problem by seamlessly handling the three main crowdsourcing processes (worker skill estimation, task assignment, task evaluation) and incorporating the uncertainty stemming from human factors. The main thrust behind this project is to develop algorithms for such an adaptive, knowledge-intensive crowdsourcing scenario by quantifying and incorporating the human factors into the three major crowdsourcing processes.
Faceted Search is an exploratory search interface that helps user to navigate and browse through a large information space through facets. A large number of information seeking and e-commerce applications benefit from such interface. We analyze the opportunities of adopting principles of the faceted search paradigm for tuple search. However, unlike past works on images and unstructured data such as text, here, the challenge is to dynamically determine the facets that are best suited for enabling a faceted search interface. Our proposed faceted search framework is dynamic and completely user interaction dependent as compared to existing faceted search systems where the facets and hierarchies are predefined and static. Our overall goal is to judiciously select the facet(s) dynamically based on user query that the user employs further to drill down in the results, such that user’s navigational cost during this exploration process is minimized. We investigate dynamic minimum effort driven faceted search in conjunction with structured and unstructured data (primarily Wikipedia).
In many OLAP and decision support environments, it is often desirable to answer complex long-running aggregate database queries approximately, provided some estimate of the error is also given. For example, when a sales manager asks give me the aggregate sales of Product X, grouped by the US states, she/he is probably not interested in getting answers to the nearest cent. We approach this difficult problem using statistical sampling-based techniques. Our objective is to propose practical solutions that require minimal changes to the underlying DBMS systems.
Ranking: Repositories such as relational databases - e.g., searching online databases of homes, used cars, and electronic goods. In many of these applications, the user often experiences "information overload", which occurs when the system responds to an under-specified user query by returning an overwhelming number of tuples, each displayed with a huge number of features (or attributes). We have developed a search and retrieval system that tackles this information overload problem from two angles. First, we show how to automatically rank and display the top-n most relevant tuples. Our ranking functions are either based on traditional distance-based metrics, or use probabilistic information retrieval principles that learn user preferences by exploiting past query workloads. Second, our system offers techniques for ordering the attributes of the returned tuples in decreasing order of "usefulness" and selects only a few of the most useful attributes to display. We have built demos of the system on used cars and a homes for sale dataset. User surveys have shown that our system improves the user's query experience.
Top-k: Top-k queries on large multi-attribute data sets are fundamental operations in information retrieval and ranking applications. In particular given specific top-k algorithms we were interested in studying their progress towards identification of the correct result at any point of the algorithms' execution. We adopted a probabilistic approach where we seek to report at any point the scores of the top-k results the algorithm has identified, as well as associate a confidence with this prediction. Such functionality can be a valuable asset when one is interested to reduce the runtime cost of top-k computations. We showed analytically that such probability and confidence are monotone in expectation. We presented a thorough experimental evaluation to validate our techniques using both synthetic and real data sets.
Attribute Recommendation: When advertising a product in the e-marketplace, it is very important to make sure that its content should be attractive to potential buyers, and that it beats the competitive products in the market. We wish to design methods which can assist the seller in deciding which attributes of the product (e.g., product features, keywords, etc) should be emphasized or recommended when preparing the advertisement. We have developed algorithms for several variants of the problem across different application domains, e.g., car/home sales, products advertising in newspapers, creating catchy titles for an article, discovering useless attributes of an object (e.g., a homebuilder can find out that 'adding a fireplace does not make the home more desirable in this market') and so on.