OpenRaiser/Intern-Atlas huggingface dataset:
A diversity measure leveraging domain specific auxiliary information
Authors: Narayan Bhamidipati, Nagaraj Kota
Venue: CIKM
Year: 2011

This article deals with the notion of reduction in uncertainty when the probability mass is distributed over similar values than dissimilar values. Shannon's entropy is a frequently used information theoretic measure of the uncertainty associated with random variables, but it depends solely on the set of values the probability mass function assumes, and does not take into consideration whether the mass is distributed among extreme values or not. A similarity structure, possibly obtained through domain knowledge, on the values assumed by the random variable may reduce the associated uncertainty. More the similarity, less the uncertainty. A novel measure named Similarity Adjusted Entropy (or Sim-adjusted Entropy for short), that generalizes Shannon's entropy, is then proposed to capture the effects of this similarity structure. Sim-adjusted entropy provides a mechanism for incorporating the domain expertise into an entropy based framework for solving various data mining tasks. Applications highlighted in this manuscript include clustering of categorical data and measuring audience diversity. Experiments performed on Yahoo! Answers data set demonstrate the ability of the proposed method to obtain more cohesive clusters. Another set of experiments confirm the utility of the proposed measure for measuring audience diversity.
A taxonomy of local search: semi-supervised query classification driven by information needs
Authors: Jiang Bian, Yi Chang
Venue: CIKM
Year: 2011

Local search service (e.g. Yelp, Yahoo! Local) has emerged as a popular and effective paradigm for a wide range of information needs for local businesses; it now provides a viable and even more effective alternative to general purpose web search for queries on local businesses. However, due to the diversity of information needs behind local search, it is necessary to use different information retrieval strategies for different query types in local search. In this paper, we explore a taxonomy of local search driven by users' information needs, which categorizes local search queries into three types: business category, chain business, and non-chain business. To decide which search strategy to use for each category in this taxonomy without placing the burden on the web users, it is indispensable to build an automatic local query classifier. However, since local search queries yield few online features and it is expensive to obtain editorial labels, it is insufficient to use only a supervised learning approach. In this paper, we address these problems by developing a semi-supervised approach for mining information needs from a vast amount of unlabeled data from local query logs to boost local query classification. Results of a large scale evaluation over queries from a commercial local search site illustrate that the proposed semi-supervised method allow us to accurately classify a substantially larger proportion of local queries than the supervised learning approach.
Ranking support for keyword search on structured data using relevance models
Authors: Veli Bicer, Thanh Tran, Radoslav Nedkov
Venue: CIKM
Year: 2011

Keyword query processing over structured data has gained a lot of interest as keywords have proven to be an intuitive mean for accessing complex results in databases. While there is a large body of work that provides different mechanisms for computing keyword search results efficiently, a recent study has shown that the problem of ranking is much neglected. Existing strategies employ heuristics that perform only in ad-hoc experiments but fail to consistently and repeatedly deliver results across different information needs. We provide a principled approach for ranking that focuses on a well-established notion of what constitutes relevant keyword search results. In particular, we adopt relevance-based language models to consider the structure and semantics of keyword search results, and introduce novel strategies for smoothing probabilities in this structured data setting. Using a standardized evaluation framework, we show that our work largely and consistently outperforms all existing systems across datasets and various information needs.
Towards a unified solution: data record region detection and segmentation
Authors: Lidong Bing, Wai Lam, Yuan Gu
Venue: CIKM
Year: 2011

Although the task of data record extraction from Web pages has been studied extensively, yet it fails to handle many pages due to their complexity in format or layout. In this paper, we propose a unified method to tackle this task by addressing several key issues in a uniform manner. A new search structure, named as Record Segmentation Tree (RST), is designed, and several efficient search pruning strategies on the RST structure are proposed to identify the records in a given Web page. Another characteristic of our method which is significantly different from previous works is that it can effectively handle complicated and challenging data record regions. It is achieved by generating subtree groups dynamically from the RST structure during the search process. Furthermore, instead of using string edit distance or tree edit distance, we propose a token-based edit distance which takes each DOM node as a basic unit in the cost calculation. Extensive experiments are conducted on four data sets, including flat, nested, and intertwine records. The experimental results demonstrate that our method achieves higher accuracy compared with three state-of-the-art methods.
Using query log and social tagging to refine queries based on latent topics
Authors: Lidong Bing, Wai Lam, Tak-Lam Wong
Venue: CIKM
Year: 2011

An important way to improve users' satisfaction in Web search is to assist them to issue more effective queries. One such approach is query refinement (reformulation), which generates new queries according to the current query issued by users. A common procedure for conducting refinement is to generate some candidate queries first, and then a scoring method is designed to assess the quality of these candidates. Currently, most of the existing methods are context based. They rely heavily on the context relation of terms in the historical queries, and cannot detect and maintain the semantic consistency of queries. In this paper, we propose a graphical model to score queries. The proposed model exploits a latent topic space, which is automatically derived from the query log, to assess the semantic dependency of terms in a query. In the graphical model, both term context dependency and topic context dependency are considered. This also makes it feasible to score some queries which do not have much available historical term context information. We also utilize social tagging data in the candidate query generation process. Based on the observation that different users may tag the same resource with different tags of similar meaning, we propose a method to mine these term pairs for new candidate query construction.
Assigning documents to master sites in distributed search
Authors: Roi Blanco, Berkant Barla Cambazoglu, Flavio Paiva Junqueira, Ivan Kelly, Vincent Leroy
Venue: CIKM
Year: 2011

An appealing solution to scale Web search with the growth of the Internet is the use of distributed architectures. Distributed search engines rely on multiple sites deployed in distant regions across the world, where each site is specialized to serve queries issued by the users of its region. This paper investigates the problem of assigning each document to a master site. We show that by leveraging similarities between a document and the activity of the users, we can accurately detect which site is the most relevant to place a document. We conduct various experiments using two document assignment approaches, showing performance improvements of up to 20.8% over a baseline technique which assigns the documents to search sites based on their language.
Data-thirsty business analysts need SODA: search over data warehouse
Authors: Lukas Blunschi, Claudio Jossen, Donald Kossmann, Magdalini Mori, Kurt Stockinger
Venue: CIKM
Year: 2011

Querying large data warehouses is very hard for non-tech savvy business users. Deep technical knowledge of both SQL as well as the schema of the database is required in order to build correct queries and to come up with new business insights. In this paper we introduce a novel system called SODA (Search Over DAta Warehouse) that bridges the gap between the business world and the IT world by enabling extended keyword search in a data warehouse. SODA uses metadata information, DBpedia entries as well as base data to generate SQL to allow intuitive exploration of the data. The process of query classification, query graph generation and SQL generation is visualized to provide the analysts with information on how the query results are produced. Experiments with real data of a global financial institution comprising around 300 tables showed promising results.
Managing interoperability and complexity inhealth systems: MIXHS'11 workshop summary
Authors: Matt-Mouley Bouamrane, Cui Tao
Venue: CIKM
Year: 2011

Managing Interoperability and Complexity in Health Systems, MIXHS'11, aims to be a forum focussing on recent research and technical results in knowledge management and information systems in bio-medical and electronic health systems. The workshop will provide an opportunity for sharing practical experiences and best practices in e-Health information infrastructure development and management. Of particular interest to the workshop themes are technical solutions to recurring practical systems deployment issues, including harnessing the complexity of bio-medical domain knowledge and the interoperability of heterogeneous health systems. The workshop will gather experts, researchers, system developers, practitioners and policymakers designing and implementing solutions for managing clinical data and integrating existing and future electronic health systems infrastructures.
Diversification for multi-domain result sets
Authors: Alessandro Bozzon, Marco Brambilla, Piero Fraternali, Marco Tagliasacchi
Venue: CIKM
Year: 2011

Multi-domain search answers to queries spanning multiple entities, like "Find an affordable house in a city with low criminality index, good schools and medical services", by producing ranked sets of entity combinations that maximize relevance, measured by a function expressing the user's preferences. Due to the combinatorial nature of results, good entity instances (e.g., inexpensive houses) tend to appear repeatedly in top-ranked combinations. To improve the quality of the result set, it is important to balance relevance (i.e., high values of the ranking function) with diversity, which promotes different, yet almost equally relevant, entities in the top-k combinations. This paper explores two different notions of diversity for multi-domain result sets, compares experimentally alternative algorithms for the trade-off between relevance and diversity, and performs a user study for evaluating the utility of diversification in multi-domain queries.
Implementation techniques for large-scale latent semantic indexing applications
Authors: Roger B. Bradford
Venue: CIKM
Year: 2011

The technique of latent semantic indexing (LSI) has wide applicability in information retrieval and data mining tasks. To date, however, most applications of LSI have addressed relatively small collections of data. This has been due partly to hardware and software limitations and partly to overly pessimistic estimates of the processing requirements of the singular value decomposition (SVD) process. In recent years, advances in hardware capabilities and software implementations have enabled much larger LSI applications. Moreover, experience with large LSI indexes has shown that the SVD is not the limitation on scalability that it was long thought to be. This paper describes techniques applicable to creating large-scale (multi-million document) LSI indexes. Detailed data regarding the LSI index creation process is presented for collections of up to 100 million documents. Four key factors are shown to contribute to the scalability of LSI. First, in most situations, the time required for calculation of the singular value decomposition (SVD) of the term-document matrix is not the dominant factor determining the overall time required to build an LSI index. Second, the time required to calculate the SVD in LSI is linear in the number of objects indexed. Third, incremental index creation greatly facilitates use of LSI in dynamic environments. Fourth, distributed query processing can be employed to support large numbers of users. It is shown that LSI is well-suited for implementation in modern distributed computing environments. This paper provides the first measurements of the execution time for large-scale LSI build processes in a cloud environment.
Enabling information extraction by inference of regular expressions from sample entities
Authors: Falk Brauer, Robert Rieger, Adrian Mocan, Wojciech M. Barczynski
Venue: CIKM
Year: 2011

Regular expressions are the dominant technique to extract business relevant entities (e.g., invoice numbers or product names) from text data (e.g., invoices), since these entity types often follow a strict underlying syntactical pattern. However, the manual construction of regular expressions that guarantee a high recall and precision is a tedious manual task and requires expert knowledge. In this paper, we propose an approach that automatically infers regular expressions from a set of (positive) sample entities, which in turn can be derived either from enterprise databases (e.g., a product catalog) or annotated documents (e.g., historical invoices). The main innovation of our approach is that it learns effective regular expressions that can be easily interpreted and modified by a user. The effectiveness is obtained by a novel method that weights dependent entity features of different granularity (i.e. on character and token level) against each other and selects the most suitable ones to form a regular expression.
Local computation of PageRank: the ranking side
Authors: Marco Bressan, Luca Pretto
Venue: CIKM
Year: 2011

Imagine you are a social network user who wants to search, in a list of potential candidates, for the best candidate for a job on the basis of their PageRank-induced importance ranking. Is it possible to compute this ranking for a low cost, by visiting only small subnetworks around the nodes that represent each candidate? The fundamental problem underpinning this question, i.e. computing locally the PageRank ranking of k nodes in an $n$-node graph, was first raised by Chen et al. (CIKM 2004) and then restated by Bar-Yossef and Mashiach (CIKM 2008). In this paper we formalize and provide the first analysis of the problem, proving that any local algorithm that computes a correct ranking must take into consideration Ω(√(kn)) nodes -- even when ranking the top $k$ nodes of the graph, even if their PageRank scores are "well separated", and even if the algorithm is randomized (and we prove a stronger Ω(n) bound for deterministic algorithms). Experiments carried out on large, publicly available crawls of the web and of a social network show that also in practice the fraction of the graph to be visited to compute the ranking may be considerable, both for algorithms that are always correct and for algorithms that employ (efficient) local score approximations.
Efficient resource attribute retrieval in RDF triple stores
Authors: Andreas Brodt, Oliver Schiller, Bernhard Mitschang
Venue: CIKM
Year: 2011

The W3C Resource Description Framework (RDF) is gaining popularity for its ability to manage semi-structured data without a predefined database schema. So far, most RDF query processors have concentrated on finding complex graph patterns in RDF, which typically involves a high number of joins. This works very well to query resources by the relations between them. Yet, obtaining a record-like view on the attributes of resources, as natively supported by RDBMS, imposes unnecessary performance burdens, as the individual attributes must be joined to assemble the final result records. We present an approach to retrieve the attributes of resources efficiently. We first determine the resources in question and then retrieve all their attributes efficiently at once, exploiting contiguous storage in RDF indexes. In addition, we present an index structure which is specifically designed for RDF attribute retrieval. Our measurements show that our approach is clearly superior for larger numbers of attributes.
Improving k-nearest neighbors algorithms: practical application of dataset analysis
Authors: Fidel Cacheda, Victor Carneiro, Diego Fernández, Vreixo Formoso
Venue: CIKM
Year: 2011

In the last years, recommender systems have achieved a great popularity. Many different techniques have been developed and applied to this field. However, in many cases the algorithms do not obtain the expected results. In particular, when the applied model does not fit the real data the results are especially bad. This happens because many times models are directly applied to a domain without a previous analysis of the data. In this work we study the most popular datasets in the movie recommendation domain, in order to understand how the users behave in this particular context. We have found some remarkable facts that question the utility of the similarity measures traditionally used in k-Nearest Neighbors (kNN) algorithms. These findings can be useful in order to develop new algorithms. In particular, we modify traditional kNN algorithms by introducing a new similarity measure specially suited for sparse contexts, where users have rated very few items. Our experiments show slight improvements in prediction accuracy, which proves the importance of a thorough dataset analysis as a previous step to any algorithm development.
Large-scale question classification in cQA by leveraging Wikipedia semantic knowledge
Authors: Li Cai, Guangyou Zhou, Kang Liu, Jun Zhao
Venue: CIKM
Year: 2011

With the flourishing of community-based question answering (cQA) services like Yahoo! Answers, more and more web users seek their information need from these sites. Understanding user's information need expressed through their search questions is crucial to information providers. Question classification in cQA is studied for this purpose. However, there are two main difficulties in applying traditional methods (question classification in TREC QA and text classification) to cQA: (1) Traditional methods confine themselves to classify a text or question into two or a few predefined categories. While in cQA, the number of categories is much larger, such as Yahoo! Answers, there contains 1,263 categories. Our empirical results show that with the increasing of the number of categories to moderate size, the performance of the classification accuracy dramatically decreases. (2) Unlike the normal texts, questions in cQA are very short, which cannot provide sufficient word co-occurrence or shared information for a good similarity measure due to the data sparseness. In this paper, we propose a two-stage approach for question classification in cQA that can tackle the difficulties of the traditional methods. In the first stage, we preform a search process to prune the large-scale categories to focus our classification effort on a small subset. In the second stage, we enrich questions by leveraging Wikipedia semantic knowledge to tackle the data sparseness. As a result, the classification model is trained on the enriched small subset. We demonstrate the performance of our proposed method on Yahoo! Answers with 1,263 categories. The experimental results show that our proposed method significantly outperforms the baseline method (with error reductions of 23.21%).
Skynets: searching for minimum trees in graphs with incomparable edge weights
Authors: Huiping Cao, K. Selçuk Candan, Maria Luisa Sapino
Venue: CIKM
Year: 2011

Query processing over weighted data graphs often involves searching for a minimum weighted subgraph --a tree-- which covers the nodes satisfying the given query criteria (such as a given set of keywords). Existing works often focus on graphs where the edges have scalar valued weights. In many applications, however, edge weights need to be represented as ranges (or intervals) of possible values. In this paper, we introduce the problem of skynets, for searching minimum weighted subgraphs, covering the nodes satisfying given query criteria, over interval-weighted graphs. The key challenge is that, unlike scalars which are often totally ordered, depending on the application specific semantics of the ≤ operator, intervals may be partially ordered. Naturally, the need to maintain alternative, incomparable solutions can push the computational complexity of the problem (which is already high for the case with totally ordered scalar edge weights) even higher. In this paper, we first provide alternative definitions of the ≤ operator for intervals and show that some of these lend themselves to efficient solutions. To tackle the complexity challenge in the remaining cases, we propose two optimization criteria that can be used to constrain the solution space. We also discuss how to extend existing approximation algorithms for Steiner trees to discover solutions to the skynet problem. For efficient calculation of the results, we introduce a novel skyline union operator. Experiments show that the proposed approach achieves significant gains in efficiency, while providing close to optimal results.
Google, bing and a new perspective on ranking similarity
Authors: Bruno Cardoso, João Magalhães
Venue: CIKM
Year: 2011

In this paper, we propose a framework to characterize and compare two search engine results. Typical user-queries are ambiguous and, consequentially, each search engine will compute ranks in different manners, attempting to answer them in the best possible way. Thus, each search engine will have its own bias. Given the importance of the first page results in Web Search Engines, in this paper we propose a framework to assess the information presented in the first page by measuring the information entropy and the correlations between two ranks. Employing the recently proposed Rank-Biased Overlap measure [2] we compare to which extent do Bing and Google rankings in fact differ. We also extend this measure and propose a measure for comparing the information entropy present in two ranks. The proposed measure is based on the correlation of two ranks and the application of Jensen-Shannon's divergence among two document sets. Our methodology starts with 40,000 user queries and crawls the search results for these queries on both search engines. The results allow us to determine the search engines correlations, crawling coverage, information overlap, and information entropy.
Folksonomy-based term extraction for word cloud generation
Authors: David Carmel, Erel Uziel, Ido Guy, Yosi Mass, Haggai Roitman
Venue: CIKM
Year: 2011

In this work we study the task of term extraction for word cloud generation. We present a folksonomy-based term extraction method, called tag-boost, which boosts terms that are frequently used by the public to tag content. Our experiments with tag-boost-based term extraction over different domains demonstrate tremendous improvement in word cloud quality, as reflected by the agreement between extracted terms and manually assigned tags of the testing items. Additionally, we show that tag-boost can be effectively applied even in non-tagged domains, by using an external rich folksonomy borrowed from a well-tagged domain.