OpenRaiser/Intern-Atlas huggingface dataset:
A signal-to-noise approach to score normalization
Authors: Avi Arampatzis, Jaap Kamps
Venue: CIKM
Year: 2009

Score normalization is indispensable in distributed retrieval and fu-sion or meta-search where merging of result-lists is required. Dis-tributional approaches to score normalization with reference to rel-evance, such as binary mixture models like the normal-exponential, suffer from lack of universality and troublesome parameter estima-tion especially under sparse relevance. We develop a new approach which tackles both problems by using aggregate score distributions without reference to relevance, and is suitable for uncooperative engines. The method is based on the assumption that scores pro-duced by engines consist of a signal and a noise component which can both be approximated by submitting well-defined sets of arti-ficial queries to each engine. We evaluate in a standard distributed retrieval testbed and show that the signal-to-noise approach yields better results than other distributional methods. As a significant by-product, we investigate query-length distributions.
Improvements that don't add up: ad-hoc retrieval results since 1998
Authors: Timothy G. Armstrong, Alistair Moffat, William Webber, Justin Zobel
Venue: CIKM
Year: 2009

The existence and use of standard test collections in information retrieval experimentation allows results to be compared between research groups and over time. Such comparisons, however, are rarely made. Most researchers only report results from their own experiments, a practice that allows lack of overall improvement to go unnoticed. In this paper, we analyze results achieved on the TREC Ad-Hoc, Web, Terabyte, and Robust collections as reported in SIGIR (1998--2008) and CIKM (2004--2008). Dozens of individual published experiments report effectiveness improvements, and often claim statistical significance. However, there is little evidence of improvement in ad-hoc retrieval technology over the past decade. Baselines are generally weak, often being below the median original TREC system. And in only a handful of experiments is the score of the best TREC automatic run exceeded. Given this finding, we question the value of achieving even a statistically significant result over a weak baseline. We propose that the community adopt a practice of regular longitudinal comparison to ensure measurable progress, or at least prevent the lack of it from going unnoticed. We describe an online database of retrieval runs that facilitates such a practice.
On the feasibility of multi-site web search engines
Authors: Ricardo Baeza-Yates, Aristides Gionis, Flavio Junqueira, Vassilis Plachouras, Luca Telloli
Venue: CIKM
Year: 2009

Web search engines are often implemented as centralized systems. Designing and implementing a Web search engine in a distributed environment is a challenging engineering task that encompasses many interesting research questions. However, distributing a search engine across multiple sites has several advantages, such as utilizing less compute resources and exploiting data locality. In this paper we investigate the cost-effectiveness of building a distributed Web search engine. We propose a model for assessing the total cost of a distributed Web search engine that includes the computational costs and the communication cost among all distributed sites. We then present a query-processing algorithm that maximizes the amount of queries answered locally, without sacrificing the quality of the results compared to a centralized search engine. We simulate the algorithm on real document collections and query workloads to measure the actual parameters needed for our cost model, and we show that a distributed search engine can be competitive compared to a centralized architecture with respect to real cost.
Supervised semantic indexing
Authors: Bing Bai, Jason Weston, David Grangier, Ronan Collobert, Kunihiko Sadamasa, Yanjun Qi, Olivier Chapelle, Kilian Q. Weinberger
Venue: CIKM
Year: 2009

In this article we propose Supervised Semantic Indexing (SSI), an algorithm that is trained on (query, document) pairs of text documents to predict the quality of their match. Like Latent Semantic Indexing (LSI), our models take account of correlations between words (synonymy, polysemy). However, unlike LSI our models are trained with a supervised signal directly on the ranking task of interest, which we argue is the reason for our superior results. As the query and target texts are modeled separately, our approach is easily generalized to different retrieval tasks, such as online advertising placement. Dealing with models on all pairs of words features is computationally challenging. We propose several improvements to our basic model for addressing this issue, including low rank (but diagonal preserving) representations, and correlated feature hashing (CFH). We provide an empirical study of all these methods on retrieval tasks based on Wikipedia documents as well as an Internet advertisement task. We obtain state-of-the-art performance while providing realistically scalable methods.
Multi-task learning for learning to rank in web search
Authors: Jing Bai, Ke Zhou, Gui-Rong Xue, Hongyuan Zha, Gordon Sun, Belle L. Tseng, Zhaohui Zheng, Yi Chang
Venue: CIKM
Year: 2009

Both the quality and quantity of training data have significant impact on the performance of ranking functions in the context of learning to rank for web search. Due to resource constraints, training data for smaller search engine markets are scarce and we need to leverage existing training data from large markets to enhance the learning of ranking function for smaller markets. In this paper, we present a boosting framework for learning to rank in the multi-task learning context for this purpose. In particular, we propose to learn non-parametric common structures adaptively from multiple tasks in a stage-wise way. An algorithm is developed to iteratively discover super-features that are effective for all the tasks. The estimation of the functions for each task is then learned as a linear combination of those super-features. We evaluate the performance of this multi-task learning method for web search ranking using data from a search engine. Our results demonstrate that multi-task learning methods bring significant relevance improvements over existing baseline methods.
Collaborative filtering using random neighbours in peer-to-peer networks
Authors: Arno Bakker, Elth Ogston, Maarten van Steen
Venue: CIKM
Year: 2009

Traditionally, collaborative filtering (CF) algorithms used for recommendation operate on complete knowledge. This makes these algorithms hard to employ in a decentralized context where not all users' ratings can be available at all locations. In this paper we investigate how the well-known neighbourhood-based CF algorithm by Herlocker et al. operates on partial knowledge; that is, how many similar users does the algorithm actually need to produce good recommendations for a given user, and how similar must those users be. We show for the popular MovieLens 1,000,000 and Jester datasets that sufficiently good recommendations can be made based on the ratings of a neighbourhood consisting of a relatively small number of randomly selected users.
Interpretable and reconfigurable clustering of document datasets by deriving word-based rules
Authors: Vipin Balachandran, Deepak P, Deepak Khemani
Venue: CIKM
Year: 2009

Clusters of text documents output by clustering algorithms are often hard to interpret. We describe motivating real-world scenarios that necessitate reconfigurability and high interpretability of clusters and outline the problem of generating clusterings with interpretable and reconfigurable cluster models. We develop a clustering algorithm toward the outlined goal of building interpretable and reconfigurable cluster models; it works by generating rules with disjunctions and conditions on the frequencies of words, to decide on the membership of a document to a cluster. Each cluster is comprised of precisely the set of documents that satisfy the corresponding rule. We show that our approach outperforms the unsupervised decision tree approach by huge margins. We show that the purity and f-measure losses to achieve interpretability are as little as 5% and 3% respectively using our approach.
User interests in social media sites: an exploration with micro-blogs
Authors: Nilanjan Banerjee, Dipanjan Chakraborty, Koustuv Dasgupta, Sumit Mittal, Anupam Joshi, Seema Nagar, Angshu Rai, Sameer Madan
Venue: CIKM
Year: 2009

Recent technological advances in mobile-based access to social networking platforms and facilities to update information in real{time (e.g. in Facebook) have allowed an individual's online presence to be as ephemeral and dynamic in nature, as her very thoughts and interests. In this context, micro-blogging has been widely adopted by users as an effective means to capture and disseminate their thoughts and actions to a larger audience on a daily basis. Interestingly, daily chatters of a user obtained from her micro-blogs offer a unique information source to analyze and interpret her context in real-time - i.e. interests, intentions,and activities. In this paper, we gather data from the public timeline of Twitter spanning across ten worldwide cities over a period of four weeks. We use this dataset to (a) explore how users express interests in real-time through micro-blogs, and (b) understand how text mining techniques can be applied to interpret real-time context of a user based on her tweets. Initial findings reported herein suggest that social media sites like Twitter constitute a promising source for extracting user context that can be exploited by novel social networking applications.
Improving retrievability of patents with cluster-based pseudo-relevance feedback documents selection
Authors: Shariq Bashir, Andreas Rauber
Venue: CIKM
Year: 2009

High findability of documents within a certain cut-off rank is considered an important factor in recall-oriented application domains such as patent or legal document retrieval. Findability is hindered by two aspects, namely the inherent bias favoring some types of documents over others introduced by the retrieval model, and the failure to correctly capture and interpret the context of conventionally rather short queries. In this paper, we analyze the bias impact of different retrieval models and query expansion strategies. We furthermore propose a novel query expansion strategy based on document clustering to identify dominant relevant documents. This helps to overcome limitations of conventional query expansion strategies that suffer strongly from the noise introduced by imperfect initial query results for pseudo-relevance feedback documents selection. Experiments with different collections of patent documents suggest that clustering based document selection for pseudo-relevance feedback is an effective approach for increasing the findability of individual documents and decreasing the bias of a retrieval system.
Boosting KNN text classification accuracy by using supervised term weighting schemes
Authors: Iyad Batal, Milos Hauskrecht
Venue: CIKM
Year: 2009

The increasing availability of digital documents in the last decade has prompted the development of machine learning techniques to automatically classify and organize text documents. The majority of text classification systems rely on the vector space model, which represents the documents as vectors in the term space. Each vector component is assigned a weight that reflects the importance of the term in the document. Typically, these weights are assigned using an information retrieval (IR) approach, such as the famous tf-idf function. In this work, we study two weighting schemes based on information gain and chi-square statistics. These schemes take advantage of the category label information to weight the terms according to their distributions across the different categories. We show that using these supervised weights instead of conventional unsupervised weights can greatly improve the performance of the k-nearest neighbor (KNN) classifier. Experimental evaluations, carried out on multiple text classification tasks, demonstrate the benefits of this approach in creating accurate text classifiers.
What happens after an ad click?: quantifying the impact of landing pages in web advertising
Authors: Hila Becker, Andrei Z. Broder, Evgeniy Gabrilovich, Vanja Josifovski, Bo Pang
Venue: CIKM
Year: 2009

Unbeknownst to most users, when a query is submitted to a search engine two distinct searches are performed: the organic or algorithmic search that returns relevant Web pages and related data (maps, images, etc.), and the sponsored search that returns paid advertisements. While an enormous amount of work has been invested in understanding the user interaction with organic search, surprisingly little research has been dedicated to what happens after an ad is clicked, a situation we aim to correct.
Pure spreading activation is pointless
Authors: Michael R. Berthold, Ulrik Brandes, Tobias Kötter, Martin Mader, Uwe Nagel, Kilian Thiel
Venue: CIKM
Year: 2009

Almost every application of spreading activation is accompanied by its own set of often heuristic restrictions on the dynamics. We show that in constraint-free scenarios spreading activation would actually yield query-independent results, so that the specific choice of restrictions is not only a pragmatic computational issue, but crucially determines the outcome.
Generating synopses for document-element search
Authors: Sumit Bhatia, Shibamouli Lahiri, Prasenjit Mitra
Venue: CIKM
Year: 2009

Scientists often search for document-elements like tables, figures, or algorithm pseudo-codes. Domain scientists and researchers report important data, results and algorithms using these document-elements; readers want to compare the reported results with their findings. Some document-element search engines have been proposed (especially to search for tables and figures) to make this task easier. While searching for document-elements today, the end-user is presented with the caption of the document-element and a sentence in the document text that refers to the document-element. Oftentimes, the caption and the reference text do not contain enough information to interpret the document-element. In this paper, we present the first set of methods to extract this useful information (synopsis) related to document-elements automatically. We also investigate the problem of choosing the optimum synopsis-size that strikes a balance between information content and size of the generated synopses.
Towards non-directional Xpath evaluation in a RDBMS
Authors: Sourav S. Bhowmick, Curtis E. Dyreson, Erwin Leonardi, Zhifeng Ng
Venue: CIKM
Year: 2009

XML query languages use directional path expressions to locate data in an XML data collection. They are tightly coupled to the structure of a data collection, and can fail when evaluated on the same data in a different structure. This paper extends path expressions with a new non-directional axis called the rank-distance axis. Given a context node and two positive integers α and β, the rank-distance axis returns those nodes that are ranked between α and β in terms of closeness from the context node in any direction. This paper shows how to evaluate the rank-distance axis in a tree-unaware XML database. A tree-unaware implementation does not invade the database kernel to support XML queries, instead it uses an existing RDBMS such as Microsoft's SQL server as a back-end and provides a front-end layer to translate XML queries to SQL. This paper presents an overview of an algorithm that translates queries with a rank-distance axis to SQL.
Collaborative resource discovery in social tagging systems
Authors: Bin Bi, Lifeng Shang, Ben Kao
Venue: CIKM
Year: 2009

Social tagging systems which allow users to create, edit and share collections of internet resources associated with tags in a collaborative fashion are growing in popularity in recent years. The rapidly growing amount of shared data in these folksonomies, i.e., taxonomies created by the folk, presents new technical challenges involved with discovering resources which are likely of interest to the user. Social tags which reflect the meaning of resources from the user's points of view provide an opportunity to enhance the quality of retrieval. In this paper, we introduce a novel framework to search relevant resources to the user query by incorporating information obtained from folksonomies' underlying data structures consisting of a set of user/tag/resource triplets. In contrast to traditional retrieval and recommendation techniques which represent a collection by a matrix, we represent our data as a third-order tensor on which a novel Cube Latent Semantic Indexing (CubeLSI) technique is proposed to capture latent semantic associations between tags. With the latent semantic representation we show how to rank relevant resources according to their relevance to user queries. The excellent performance of the method is demonstrated by an experimental evaluation on the deli.cio.us dataset. Copyright 2009 ACM.
Inverted indexes vs. bitmap indexes in decision support systems
Authors: Truls Amundsen Bjørklund, Nils Grimsmo, Johannes Gehrke, Øystein Torbjørnsen
Venue: CIKM
Year: 2009

Bitmap indexes are widely used in Decision Support Systems (DSSs) to improve query performance. In this paper, we evaluate the use of compressed inverted indexes with adapted query processing strategies from Information Retrieval as an alternative. In a thorough experimental evaluation on both synthetic data and data from the Star Schema Benchmark, we show that inverted indexes are more compact than bitmap indexes in almost all cases. This compactness combined with efficient query processing strategies results in inverted indexes outperforming bitmap indexes for most queries, often significantly.
Probabilistic skyline queries
Authors: Christian Böhm, Frank Fiedler, Annahita Oswald, Claudia Plant, Bianca Wackersreuther
Venue: CIKM
Year: 2009

The ability to deal with uncertain information is becoming increasingly important for modern database applications. Whereas a conventional (certain) object is usually represented by a vector from a multidimensional feature space, an uncertain object is represented by a multivariate probability density function (PDF). This PDF can be defined either discretely (e.g. by a histogram) or continuously in parametric form (e.g. by a Gaussian Mixture Model). For a database of uncertain objects, the users expect similar data analysis techniques as for a conventional database of certain objects. An important analysis technique for certain objects is the skyline operator which finds maximal or minimal vectors with respect to any possible attribute weighting. In this paper, we propose the concept of probabilistic skylines, an extension of the skyline operator for uncertain objects. In addition, we propose efficient and effective methods for determining the probabilistic skyline of uncertain objects which are defined by a PDF in parametric form (e.g. a Gaussian function or a Gaussian Mixture Model). To further accelerate the search, we elaborate how the computation of the probabilistic skyline can be supported by an index structure for uncertain objects. An extensive experimental evaluation demonstrates both the effectiveness and the efficiency of our technique.
Voting in social networks
Authors: Paolo Boldi, Francesco Bonchi, Carlos Castillo, Sebastiano Vigna
Venue: CIKM
Year: 2009

A voting system is a set of rules that a community adopts to take collective decisions. In this paper we study voting systems for a particular kind of community: electronically mediated social networks. In particular, we focus on delegative democracy (a.k.a. proxy voting) that has recently received increased interest for its ability to combine the benefits of direct and representative systems, and that seems also perfectly suited for electronically mediated social networks. In such a context, we consider a voting system in which users can only express their preference for one among the people they are explicitly connected with, and this preference can be propagated transitively, using an attenuation factor. We present this system and we study its properties. We also take into consideration the problem of missing votes, which is particularly relevant in online networks, as some recent case shows. Our experiments on real-world networks provide interesting insight into the significance and stability of the results obtained with the suggested voting system.
A new framework to automate constrained microaggregation
Authors: Isaac Cano, Guillermo Navarro-Arribas, Vicenç Torra
Venue: CIKM
Year: 2009

Data protection methods from privacy preserving data mining and statistical disclosure control can introduce perturbation in the data. While this perturbation helps to protect the privacy of the respondents, it can introduce inconsistencies and errors. Moreover, the data are normally edited after collection to ensure its correctness and fix inconsistencies, and perturbation methods can introduce new errors in such data. In this paper we present a framework to automate the protection of data with a perturbative method, microaggregation, while at the same time ensuring that no inconsistencies and errors are introduced. That is, the data are microaggregated preserving a set of given constraints (edit constraints).
The use of categorization information in language models for question retrieval
Authors: Xin Cao, Gao Cong, Bin Cui, Christian S. Jensen, Ce Zhang
Venue: CIKM
Year: 2009

Community Question Answering (CQA) has emerged as a popular type of service meeting a wide range of information needs. Such services enable users to ask and answer questions and to access existing question-answer pairs. CQA archives contain very large volumes of valuable user-generated content and have become important information resources on the Web. To make the body of knowledge accumulated in CQA archives accessible, effective and efficient question search is required. Question search in a CQA archive aims to retrieve historical questions that are relevant to new questions posed by users. This paper proposes a category-based framework for search in CQA archives. The framework embodies several new techniques that use language models to exploit categories of questions for improving question-answer search. Experiments conducted on real data from Yahoo! Answers demonstrate that the proposed techniques are effective and efficient and are capable of outperforming baseline methods significantly.
Enhancing recommender systems under volatile userinterest drifts
Authors: Huanhuan Cao, Enhong Chen, Jie Yang, Hui Xiong
Venue: CIKM
Year: 2009

This paper presents a systematic study of how to enhance recommender systems under volatile user interest drifts. A key development challenge along this line is how to track user interests dynamically. To this end, we first define four types of interest patterns to understand users' rating behaviors and analyze the properties of these patterns. We also propose a rating graph and rating chain based approach for detecting these interest patterns. For each users' rating series, a rating graph and a rating chain are constructed based on the similarities between rated items. The type of a given user's interest pattern is identified through the density of the corresponding rating graph and the continuity of the corresponding rating chain. In addition, we propose a general algorithm framework for improving recommender systems by exploiting these identified patterns. Finally, experimental results on a real-world data set show that the proposed rating graph based approach is effective for detecting user interest patterns, which in turn help to improve the performance of recommender systems.