OpenRaiser/Intern-Atlas huggingface dataset:
Sort-based query-adaptive loading of R-trees
Authors: Daniar Achakeev, Bernhard Seeger, Peter Widmayer
Venue: CIKM
Year: 2012

Bulk-loading of R-trees has been an important problem in academia and industry for more than twenty years. Current algorithms create R-trees without any information about the expected query profile. However, query profiles are extremely useful for the design of efficient indexes. In this paper, we address this deficiency and present query-adaptive algorithms for building R-trees optimally designed for a given query profile. Since optimal R-tree loading is NP-hard (even without tuning the structure to a query profile), we provide efficient, easy to implement heuristics. Our sort-based algorithms for query-adaptive loading consist of two steps: First, sorting orders are identified resulting in better R-trees than those obtained from standard space-filling curves. Second, for a given sorting order, we propose a dynamic programming algorithm for generating R-trees in linear runtime. Our experimental results confirm that our algorithms generally create significantly better R-trees than the ones obtained from standard sort-based loading algorithms, even when the query profile is unknown.
Multi-faceted ranking of news articles using post-read actions
Authors: Deepak Agarwal, Bee-Chung Chen, Xuanhui Wang
Venue: CIKM
Year: 2012

Personalized article recommendation is important for news portals to improve user engagement. Existing work quantifies engagement primarily through click rates. We suggest that quality of recommendations may be improved by exploiting different types of "post-read" engagement signals like sharing, commenting, printing and e-mailing article links. Specifically, we propose a multi-faceted ranking problem for recommending articles, where each facet corresponds to a ranking task that seeks to maximize actions of a particular post-read type (e.g., ranking articles to maximize sharing actions). Our approach is to predict the probability that a user would take a post-read action on an article, so that articles can be ranked according to such probabilities. However, post-read actions are rare events --- enormous data sparsity makes the problem challenging. We meet the challenge by exploiting correlations across different post-read action types through a novel locally augmented tensor (LAT) model, so that the ranking performance of a particular action type can be improved by leveraging data from all other action types. Through extensive experiments, we show that our LAT model significantly outperforms a variety of state-of-the-art factor models, logistic regression and IR models.
Learning to rank for robust question answering
Authors: Arvind Agarwal, Hema Raghavan, Karthik Subbian, Prem Melville, Richard D. Lawrence, David Gondek, James Fan
Venue: CIKM
Year: 2012

This paper aims to solve the problem of improving the ranking of answer candidates for factoid based questions in a state-of-the-art Question Answering system. We first provide an extensive comparison of 5 ranking algorithms on two datasets -- from the Jeopardy quiz show and a medical domain. We then show the effectiveness of a cascading approach, where the ranking produced by one ranker is used as input to the next stage. The cascading approach shows sizeable gains on both datasets. We finally evaluate several rank aggregation techniques to combine these algorithms, and find that Supervised Kemeny aggregation is a robust technique that always beats the baseline ranking approach used by Watson for the Jeopardy competition. We further corroborate our results on TREC Question Answering datasets.
First international workshop on information and knowledge management for developing region
Authors: Rakesh Agrawal, Douglas W. Oard, Nitendra Rajput
Venue: CIKM
Year: 2012

Several issues arise with management of content that is generated in developing regions. Some result from linguistic diversity (as in India and Africa), some result from content being available only in forms that are more difficult to computationally manipulate (e.g., handwriting, speech, and legacy digital text in nonstandard encodings), some result from underinvestment in language resources for the languages of these regions, and some result from increased contact between cultures that have different views regarding the proper use of information and information artifacts. Such issues warrant focused attention if we are to optimally leverage information and knowledge management to the advantage of populations in developing regions. That is the purpose of this workshop.
Fast and reliable anomaly detection in categorical data
Authors: Leman Akoglu, Hanghang Tong, Jilles Vreeken, Christos Faloutsos
Venue: CIKM
Year: 2012

Spotting anomalies in large multi-dimensional databases is a crucial task with many applications in finance, health care, security, etc. We introduce COMPREX, a new approach for identifying anomalies using pattern-based compression. Informally, our method finds a collection of dictionaries that describe the norm of a database succinctly, and subsequently flags those points dissimilar to the norm---with high compression cost---as anomalies.
Survival analysis for freshness in microblogging search
Authors: Gianni Amati, Giuseppe Amodeo, Carlo Gaibisso
Venue: CIKM
Year: 2012

Freshness of information in real-time search is central in social networks, news, blogs and micro-blogs. Nevertheless, there is not a clear experimental evidence that shows what principled approach effectively combines time and content.
Mining sentiment terminology through time
Authors: Hadi Amiri, Tat-Seng Chua
Venue: CIKM
Year: 2012

The correspondence between sentiment terminology and the active language used for expressing opinions is a crucial prerequisite for effective sentiment analysis. Mining sentiment terminology includes the detection of new opinion words as well as inferring their polarities. In this paper, we first propose a novel approach based on the interchangeability characteristic of words to detect new opinion words through time. We then show that the current non-time-based polarity inference approaches may assign opposite polarity to the same opinion word at different times. To tackle this issue, we consider the polarity scores computed at different times as polarity evidences (with the possibility of flawed evidences) and combine them to compute a globally correct polarity score for each opinion word. The experiments show that our approach is effective both in terms of the quality of the discovered new opinion words as well as its ability in inferring their polarities through time. Furthermore, we show the application of mining sentiment terminology through time in the sentiment classification (SC) task. The experiments show that mining more recent new opinion words leads to greater improvement in the performance of SC. To the best of our knowledge, this is the first work that investigates "time" as an important factor in mining sentiment terminology.
Learning to discover complex mappings from web forms to ontologies
Authors: Yuan An, Xiaohua Hu, Il-Yeol Song
Venue: CIKM
Year: 2012

In order to realize the Semantic Web, various structures on the Web including Web forms need to be annotated with and mapped to domain ontologies. We present a machine learning-based automatic approach for discovering complex mappings from Web forms to ontologies. A complex mapping associates a set of semantically related elements on a form to a set of semantically related elements in an ontology. Existing schema mapping solutions mainly rely on integrity constraints to infer complex schema mappings. However, it is difficult to extract rich integrity constraints from forms. We show how machine learning techniques can be used to automatically discover complex mappings between Web forms and ontologies. The challenge is how to capture and learn the complicated knowledge encoded in existing complex mappings. We develop an initial solution that takes a naive Bayesian approach. We evaluated the performance of the solution on various domains. Our experimental results show that the solution returns the expected mappings as the top-1 results usually among several hundreds candidate mappings for more than 80% of the test cases. Furthermore, the expected mappings are always returned as the top-k results with k<4. The experiments have demonstrated that the approach is effective and has the potential to save significant human efforts.
Dynamic covering for recommendation systems
Authors: Ioannis Antonellis, Anish Das Sarma, Shaddin Dughmi
Venue: CIKM
Year: 2012

In this paper, we identify a fundamental algorithmic problem that we term succinct dynamic covering (SDC), arising in many modern-day web applications, including ad-serving and online recommendation systems such as in eBay, Netflix, and Amazon. Roughly speaking, SDC applies two restrictions to the well-studied Max-Coverage problem [14]: Given an integer k, X={1,2,...,n}and I={S_1,...,S_m}, S_i subseteq X, find |J| subseteq I, such that |J| < k and (union_S_in_J S) is as large as possible. The two restrictions applied by SDC are: (1)Dynamic: At query-time, we are given a query Q subseteq X, and our goal is to find J such that Q bigcap (union_S_J S) is as large as possible; Space-constrained: We don't have enough space to store (and process) the entire input; specifically, we have o(mn), and maybe as little as O((m+n)polylog(mn))space. A solution to SDC maintains a small data structure, and uses this datastructure to answer most dynamic queries with high accuracy. We call such a scheme a Coverage Oracle.
The effect of aggregated search coherence on search behavior
Authors: Jaime Arguello, Robert Capra
Venue: CIKM
Year: 2012

Aggregated search is the task of blending results from different specialized search services, or verticals, into the web search results. Aggregated search coherence refers to the degree to which results from different systems focus on similar senses of the query. While cross-component coherence has been cited as an important criterion for whole-page evaluation, its effect on search behavior has not been deeply investigated in prior research. In this work, we focus on the coherence between two aggregated search components: images and web results. In particular, we investigate whether the query-senses associated with the blended image results can influence user interaction with the web results. For example, if a user wants web results about "jaguar" the animal, are they more likely to examine the web results if the image results contain pictures of the animal instead of pictures of the car? Based on two large user studies, our results show that the image results can systematically affect user interaction with the web results. If the web results are largely consistent with the search task, then the effect of the image results is small. However, if the web results are only marginally consistent with the search task, such as when they are highly diversified across query-senses, the image results have a significant effect on user interaction with the web results. Our findings have implications on current research in whole-page evaluation, aggregated search, and diversity ranking.
Efficient influence-based processing of market research queries
Authors: Anastasios Arvanitis, Antonios Deligiannakis, Yannis Vassiliou
Venue: CIKM
Year: 2012

The rapid growth of social web has contributed vast amounts of user preference data. Analyzing this data and its relationships with products could have several practical applications, such as personalized advertising, market segmentation, product feature promotion etc. In this work we develop novel algorithms for efficiently processing two important classes of queries involving user preferences, i.e. potential customers identification and product positioning. With regards to the first problem, we formulate product attractiveness based on the notion of reverse skyline queries. We then present a new algorithm, termed as RSA, that significantly reduces the I/O cost, as well as the computation cost, when compared to the state-of-the-art reverse skyline algorithm, while at the same time being able to quickly report the first results. Several real-world applications require processing of a large number of queries, in order to identify the product characteristics that maximize the number of potential customers. Motivated by this problem, we also develop a batched extension of our RSA algorithm that significantly improves upon processing multiple queries individually, by grouping contiguous candidates, exploiting I/O commonalities and enabling shared processing. Our experimental study using both real and synthetic data sets demonstrates the superiority of our proposed algorithms for the studied classes of queries.
Fast candidate generation for two-phase document ranking: postings list intersection with bloom filters
Authors: Sebastian Bruch, Jimmy Lin
Venue: CIKM
Year: 2012

Most modern web search engines employ a two-phase ranking strategy: a candidate list of documents is generated using a "cheap" but low-quality scoring function, which is then reranked by an "expensive" but high-quality method (usually machine-learned). This paper focuses on the problem of candidate generation for conjunctive query processing in this context. We describe and evaluate a fast, approximate postings list intersection algorithms based on Bloom filters. Due to the power of modern learning-to-rank techniques and emphasis on early precision, significant speedups can be achieved without loss of end-to-end retrieval effectiveness. Explorations reveal a rich design space where effectiveness and efficiency can be balanced in response to specific hardware configurations and application scenarios.
Modeling browsing behavior for click analysis in sponsored search
Authors: Azin Ashkan, Charles L. A. Clarke
Venue: CIKM
Year: 2012

Clickthrough rate provides a fundamental measure of advertising quality, which is widely used in ad selection strategies. However, ads placed in contexts where they are rarely viewed, or where users are unlikely to be interested in commercial results, may receive few clicks regardless of their quality. In this paper, we gain insight into user browsing and click behavior for the purpose of click analysis in sponsored search domain. The list of ads displayed on a page, the user's initial motivation to browse this list, and the persistence of the user are among the contextual factors considered in this paper. We propose a probabilistic model for user's browsing and click behavior using these contextual factors. To evaluate the performance of the model, we compare it with state-of-the-art methods. The experimental results confirm that these contextual factors can better reflect user browsing and click behavior in sponsored search.
PolariCQ: polarity classification of political quotations
Authors: Rawia Awadallah, Maya Ramanath, Gerhard Weikum
Venue: CIKM
Year: 2012

We consider the problem of automatically classifying quotations about political debates into both topic and polarity. These quotations typically appear in news media and online forums. Our approach maps quotations onto one or more topics in a category system of political debates, containing more than a thousand fine-grained topics. To overcome the difficulty that pro/con classification faces due to the brevity of quotations and sparseness of features, we have devised a model of quotation expansion that harnesses antonyms from thesauri like WordNet. We developed a suite of statistical language models, judiciously customized to our settings, and use these to define similarity measures for unsupervised or supervised classifications. Experiments show the effectiveness of our method.
On empirical tradeoffs in large scale hierarchical classification
Authors: Rohit Babbar, Ioannis Partalas, Éric Gaussier, Cécile Amblard
Venue: CIKM
Year: 2012

While multi-class categorization of documents has been of research interest for over a decade, relatively fewer approaches have been proposed for large scale taxonomies in which the number of classes range from hundreds of thousand as in Directory Mozilla to over a million in Wikipedia. As a result of ever increasing number of text documents and images from various sources, there is an immense need for automatic classification of documents in such large hierarchies. In this paper, we analyze the tradeoffs between the important characteristics of different classifiers employed in the top down fashion. The properties for relative comparison of these classifiers include, (i) accuracy on test instance, (ii) training time (iii) size of the model and (iv) test time required for prediction. Our analysis is motivated by the well known error bounds from learning theory, which is also further reinforced by the empirical observations on the publicly available data from the Large Scale Hierarchical Text Classification Challenge. We show that by exploiting the data heterogenity across the large scale hierarchies, one can build an overall classification system which is approximately 4 times faster for prediction, 3 times faster to train, while sacrificing only 1% point in accuracy.
Outlier detection using centrality and center-proximity
Authors: Duck-Ho Bae, Seo Jeong, Sang-Wook Kim, Minsoo Lee
Venue: CIKM
Year: 2012

An outlier is an object that is considerably dissimilar with the remainder of the dataset. In this paper, we first propose the notion of centrality and center-proximity as novel outlierness measures which can be considered to represent the characteristics of all of the objects in the dataset. We then propose a graph-based outlier detection method which can solve the problems of local density, micro-cluster, and fringe objects. Finally, through extensive experiments, we show the effectiveness of the proposed method.
An effective category classification method based on a language model for question category recommendation on a cQA service
Authors: Kyoungman Bae, Youngjoong Ko
Venue: CIKM
Year: 2012

Classiying user's question into several topics helps respondents answering the question in a cQA service. The word weighting method must estimate the appropriate weight of a word to improve the category (or topic) classification. In this paper, we propose a novel effective word weighting method based on a language model for automatic category classification in the cQA service. We first calculate the occurrence probability of a word in each category by using a language model and then the final weight of each word is estimated by ratio of the occurrence probability of the word on a category to the occurrence probability of the word on the other categories. As a result, the proposed method significantly improves the performance of the category classification.
User engagement: the network effect matters!
Authors: Ricardo Baeza-Yates, Mounia Lalmas
Venue: CIKM
Year: 2012

In the online world, user engagement refers to the quality of the user experience that emphasizes the positive aspects of the interaction with a web application and, in particular, the phenomena associated with wanting to use that application longer and frequently. This definition is motivated by the observation that successful web applications are not just used, but they are engaged with. Users invest time, attention, and emotion into them.
The twitaholic next door.: scalable friend recommender system using a concept-sensitive hash function
Authors: Patrick Bamba, Julien Subercaze, Christophe Gravier, Nabil Benmira, Jimi Fontaine
Venue: CIKM
Year: 2012

In this paper we present a Friend Recommender System for micro-blogging. Traditional batch processing of massive amounts of data makes it difficult to provide a near-real time friend recommender system or even a system that can properly scale to millions of users. In order to overcome these issues, we have designed a solution that represents user-generated micro posts as a set of pseudo-cliques. These graphs are assigned a hash value using an original Concept-Sensitive Hash function, a new sub-kind of Locally-Sensitive Hash functions. Finally, since the user profiles are represented as a binary footprint, the pairwise comparison of footprints using the Hamming distance provides scalability to the recommender system. The paper goes with an online application relying on a large Twitter dataset, so that the reader can freely experiment the system.
Hierarchical image annotation using semantic hierarchies
Authors: Hichem Bannour, Céline Hudelot
Venue: CIKM
Year: 2012

Semantic hierarchies have been introduced recently to improve image annotation. They was used as a framework for hierarchical image classification, and thus to improve classifiers accuracy and reduce the complexity of managing large scale data. In this paper, we investigate the contribution of semantic hierarchies for hierarchical image classification. We propose first a new method based on the hierarchy structure to train efficiently hierarchical classifiers. Our method, named One-Versus-Opposite-Nodes, allows decomposing the problem in several independent tasks and therefore scales well with large database. We also propose two methods for computing a hierarchical decision function that serves to annotate new image samples. The former is performed by a top-down classifiers voting, while the second is based on a bottom-up score fusion. The experiments on Pascal VOC'2010 dataset showed that our methods improve well the image annotation results.
Gumshoe quality toolkit: administering programmable search
Authors: Zhuowei Bao, Benny Kimelfeld, Yunyao Li, Sriram Raghavan, Huahai Yang
Venue: CIKM
Year: 2012

Enterprise search is challenging due to various reasons, notably the dynamic terminology and domain structure that are specific to the enterprise, combined with the fact that search deployments are typically managed by domain experts who are not necessarily search experts. To address that, it has been proposed to design search architectures that feature two principles: comprehensibility of the ranking mechanism and customizability of the search engine by means of intuitive runtime rules. The proposed demonstration operates on top of an engine implementation based on this search philosophy, and provides an administrator toolkit to realize the two principles. In particular, the toolkit provides a complete visualization of the provenance (hence ranking) of search results, embeds an editor for programming runtime rules, facilitates the investigation of (the cause of) missing or low-ranked desired results, and provides suggestions of rewrite rules to handle such results.
Efficient provenance storage for relational queries
Authors: Zhifeng Bao, Henning Köhler, Liwei Wang, Xiaofang Zhou, Shazia Sadiq
Venue: CIKM
Year: 2012

Provenance information is vital in many application areas as it helps explain data lineage and derivation. However, storing fine-grained provenance information can be expensive. In this paper, we present a framework for storing provenance information relating to data derived via database queries. In particular, we first propose a provenance tree data structure which matches the query structure and thereby presents a possibility to avoid redundant storage of information regarding the derivation process. Then we investigate two approaches for reducing storage costs. The first approach utilizes two ingenious rules to achieve reduction on provenance trees. The second one is a dynamic programming solution, which provides a way of optimizing the selection of query tree nodes where provenance information should be stored. The optimization algorithm runs in polynomial time in the query size and is linear in the size of the provenance information, thus enabling provenance tracking and optimization without incurring large overheads. Experiments show that our approaches guarantee significantly lower storage costs than existing approaches.