OpenRaiser/Intern-Atlas huggingface dataset:
Privacy preservation by independent component analysis and variance control
Authors: Chih-Ming Hsu, Ming-Syan Chen
Venue: CIKM
Year: 2011

The primary objective of privacy preservation is to protect an individual's confidential information in released data sets. In recent years, several simulation-based approaches for privacy preservation have been proposed. The idea is to generate a synthetic data set with the constraint that the probability distribution is as close as possible to that of the original set. In this paper, we propose two frameworks for simulation-based privacy preservation of multivariate numerical data. The first framework, called PRIMP (PRivacy preserving by Independent coMPonents), is based on independent component analysis (ICA). It is shown empirically that PRIMP outperforms other simulation-based approaches in terms of Spearman's rank correlation and Kendall's tau correlation. The second approach proposed is a hybrid method that combines PRIMP and Cholesky's decomposition technique. It is shown empirically that the hybrid method preserves the covariance matrix of the original data exactly. The method also resolves the problem of generating good seeds for the Cholesky-based approach. Although the empirical results show that the hybrid approach is not always better than the PRIMP in terms of Spearman's rank correlation and Kendall's tau correlation, in theory, the risk of information leakage under the hybrid approach is much less than that under PRIMP.
Enhancing accessibility of microblogging messages using semantic knowledge
Authors: Xia Hu, Lei Tang, Huan Liu
Venue: CIKM
Year: 2011

The volume of microblogging messages is increasing exponentially with the popularity of microblogging services. With a large number of messages appearing in user interfaces, it hinders user accessibility to useful information buried in disorganized, incomplete, and unstructured text messages. In order to enhance user accessibility, we propose to aggregate related microblogging messages into clusters and automatically assign them semantically meaningful labels. However, a distinctive feature of microblogging messages is that they are much shorter than conventional text documents. These messages provide inadequate term co occurrence information for capturing semantic associations. To address this problem, we propose a novel framework for organizing unstructured microblogging messages by transforming them to a semantically structured representation. The proposed framework first captures informative tree fragments by analyzing a parse tree of the message, and then exploits external knowledge bases (Wikipedia and WordNet) to enhance their semantic information. Empirical evaluation on a Twitter dataset shows that our framework significantly outperforms existing state-of-the-art methods.
Top-k most influential locations selection
Authors: Jin Huang, Zeyi Wen, Jianzhong Qi, Rui Zhang, Jian Chen, Zhen He
Venue: CIKM
Year: 2011

We propose and study a new type of facility location selection query, the top-k most influential location selection query. Given a set M of customers and a set F of existing facilities, this query finds k locations from a set C of candidate locations with the largest influence values, where the influence of a candidate location c (c in C) is defined as the number of customers in M who are the reverse nearest neighbors of c. We first present a naive algorithm to process the query. However, the algorithm is computationally expensive and not scalable to large datasets. This motivates us to explore more efficient solutions. We propose two branch and bound algorithms, the Estimation Expanding Pruning (EEP) algorithm and the Bounding Influence Pruning (BIP) algorithm. These algorithms exploit various geometric properties to prune the search space, and thus achieve much better performance than that of the naive algorithm. Specifically, the EEP algorithm estimates the distances to the nearest existing facilities for the customers and the numbers of influenced customers for the candidate locations, and then gradually refines the estimation until the answer set is found, during which distance metric based pruning techniques are used to improve the refinement efficiency. BIP only estimates the numbers of influenced customers for the candidate locations. But it uses the existing facilities to limit the space for searching the influenced customers and achieve a better estimation, which results in an even more efficient algorithm. Extensive experiments conducted on both real and synthetic datasets validate the efficiency of the algorithms.
Relevance weighting using within-document term statistics
Authors: Kai Hui, Ben He, Tiejian Luo, Bin Wang
Venue: CIKM
Year: 2011

With the rapid development of the information technology, there exists the difficulty in deploying state-of-the-art retrieval models in environments such as peer-to-peer networks and pervasive computing, where it is expensive or even infeasible to maintain the global statistics. To this end, this paper presents an investigation in the validity of different statistical assumptions of term distributions. Based on the findings in this investigation, a variety of weighting models, called NG (standing for "no global statistics") models, are derived from the Divergence from Randomness framework, in which only the within-document statistics are used in the relevance weighting. Compared to the state-of-the-art weighting models in extensive experiments on various standard TREC test collections, our proposed NG models can provide acceptable retrieval performance in ad-hoc search, without the use of global statistics.
Multiple keyword-based queries over XML streams
Authors: Felipe da C. Hummel, Altigran Soares da Silva, Mirella M. Moro, Alberto H. F. Laender
Venue: CIKM
Year: 2011

In this paper, we propose that various keyword-based queries be processed over XML streams in a multi-query processing way. Our algorithms rely on parsing stacks designed for simultaneously matching terms from several distinct queries and use new query indexes to speed up search operations when processing a large number of queries. Besides defining a new problem and novel solutions, we perform experiments in which aspects related to performance and scalability are examined.
Spreadsheet-based complex data transformation
Authors: Vu Hung, Boualem Benatallah, Régis Saint-Paul
Venue: CIKM
Year: 2011

Spreadsheets are used by millions of users as a routine all-purpose data management tool. It is now increasingly necessary for external applications and services to consume spreadsheet data. In this paper, we investigate the problem of transforming spreadsheet data to structured formats required by these applications and services. Unlike prior methods, we propose a novel approach in which transformation logic is embedded into a familiar and expressive spreadsheet-like formula mapping language. Popular transformation patterns provided by transformation languages and mapping tools, that are relevant to spreadsheet-based data transformation, are supported in the language via formulas. Consequently, the language avoids cluttering the source spreadsheets with transformations and turns out to be helpful when multiple schemas are targeted. We implemented a prototype and evaluated the benefits of our approach via experiments in a real application. The experimental results confirmed the benefits of our approach.
Provenance-based refresh in data-oriented workflows
Authors: Robert Ikeda, Semih Salihoglu, Jennifer Widom
Venue: CIKM
Year: 2011

We consider a general workflow setting in which input data sets are processed by a graph of transformations to produce output results. Our goal is to perform efficient selective refresh of elements in the output data, i.e., compute the latest values of specific output elements when the input data may have changed. We explore how data provenance can be used to enable efficient refresh. Our approach is based on capturing one-level data provenance at each transformation when the workflow is run initially. Then at refresh time provenance is used to determine (transitively) which input elements are responsible for given output elements, and the workflow is rerun only on that portion of the data needed for refresh. Our contributions are to formalize the problem setting and the problem itself, to specify properties of transformations and provenance that are required for efficient refresh, and to provide algorithms that apply to a wide class of transformations and workflows. We have built a prototype system supporting the features and algorithms presented in the paper. We report preliminary experimental results on the overhead of provenance capture, and on the crossover point between selective refresh and full workflow recomputation.
Tightly coupling visual and linguistic features for enriching audio-based web browsing experience
Authors: Muhammad Asiful Islam, Faisal Ahmed, Yevgen Borodin, I. V. Ramakrishnan
Venue: CIKM
Year: 2011

People who are blind use screen readers for browsing web pages. Since screen readers read out content serially, a naive readout tends to mix irrelevant and relevant content thereby disrupting the coherency of the material being read out and confusing the listener. To address this problem we can partition web pages into coherent segments and narrate each such piece separately. Extant methods to do segmentation use visual and structural cues without taking the semantics into account and consequently create segments containing irrelevant material. In this paper, we describe a new technique for creating coherent segments by tightly coupling visual, structural, and linguistic features present in the content. A notable aspect of the technique is that it produces segments with little irrelevant content. Preliminary experiments indicate that the technique is effective in creating highly coherent segments and the experiences of an early adopter who is blind suggest that it enriches the overall browsing experience.
Classification and annotation in social corpora using multiple relations
Authors: Yann Jacob, Ludovic Denoyer, Patrick Gallinari
Venue: CIKM
Year: 2011

We consider the problem of learning to annotate documents with concepts or keywords in content information networks, where the documents may share multiple relations. The concepts associated to a document will depend both on its content and on its neighbors in the network through the different relations. We formalize this problem as single and multi-label classification in a multi-graph, the nodes being the documents and the edges representing the different relations. The proposed algorithm learns to weight the different relations according to their importance for the annotation task. We perform experiments on different corpora corresponding to different annotation tasks on scientific articles, emails and Flickr images and show how the model may take advantage of the rich relational information.
An unsupervised ranking method based on a technical difficulty terrain
Authors: Shoaib Jameel, Wai Lam, Ching-man Au Yeung, Sheaujiun Chyan
Venue: CIKM
Year: 2011

Users look for information that can suit their level of expertise, but it often takes a mammoth effort to trace such information. One has to sift through multiple pages to look for one that fits the appropriate technical background. In this paper, a query-independent ranking system is proposed for technical web pages. The pages returned by the system are sorted by their relative technical difficulty in either ascending or descending order specified by the user. The technical difficulty of a document i.e. terms in sequence, is first computed by the combination of each individual term's geometry in the low-dimensional latent semantic indexing (LSI) space, which can be visualized as a conceptual terrain. Then the pages are ranked based on the expected cost to get over the terrain. Results indicate that our terrain based method outperforms traditional readability measures.
A linear-time approximation of the earth mover's distance
Authors: Min-Hee Jang, Sang-Wook Kim, Christos Faloutsos, Sunju Park
Venue: CIKM
Year: 2011

Color descriptors are one of the important features used in content-based image retrieval. The dominant color descriptor (DCD) represents a few perceptually dominant colors in an image through color quantization. For image retrieval based on DCD, the earth mover's distance and the optimal color composition distance are proposed to measure the dissimilarity between two images. Although providing good retrieval results, both methods are too time-consuming to be used in a large image database. To solve the problem, we propose a new distance function that calculates an approximate earth mover's distance in linear time. To calculate the dissimilarity in linear time, the proposed approach employs the space-filling curve for multidimensional color space. To improve the accuracy, the proposed approach uses multiple curves and adjusts the color positions. As a result, our approach achieves order-of-magnitude time improvement but incurs small errors. We have performed extensive experiments to show the effectiveness and efficiency of the proposed approach. The results reveal that our approach achieves almost the same results with the EMD in linear time.
Natural event summarization
Authors: Yexi Jiang, Chang-Shing Perng, Tao Li
Venue: CIKM
Year: 2011

Event mining is a useful way to understand computer system behaviors. The focus of recent works on event mining has been shifted to event summarization from discovering frequent patterns. Event summarization seeks to provide a comprehensible explanation of the event sequence on certain aspects. Previous methods have several limitations such as ignoring temporal information, generating the same set of boundaries for all event patterns, and providing a summary which is difficult for human to understand. In this paper, we propose a novel framework called natural event summarization that summarizes an event sequence using inter-arrival histograms to capture the temporal relationship among events. Our framework uses the minimum description length principle to guide the process in order to balance between accuracy and brevity. Also, we use multi-resolution analysis for pruning the problem space. We demonstrate how the principles can be applied to generate summaries with periodic patterns and correlation patterns in the framework. Experimental results on synthetic and real data show our method is capable of producing usable event summary, robust to noises, and scalable.
Relative effect of spam and irrelevant documents on user interaction with search engines
Authors: Timothy Jones, David Hawking, Paul Thomas, Ramesh S. Sankaranarayana
Venue: CIKM
Year: 2011

Meaningful evaluation of web search must take account of spam. Here we conduct a user experiment to investigate whether satisfaction with search engine result pages as a whole is harmed more by spam or by irrelevant documents. On some measures, search result pages are differentially harmed by the insertion of spam and irrelevant documents. Additionally we find that when users are given two documents of equal utility, the one with the lower spam score will be preferred; a result page without any spam documents will be preferred to one with spam; and an irrelevant document high in a result list is surprisingly more damaging to user satisfaction than a spam document. We conclude that web ranking and evaluation should consider both utility (relevance) and "spamminess" of documents.
Diversifying search results of controversial queries
Authors: Mouna Kacimi, Johann Gamper
Venue: CIKM
Year: 2011

Diversifying search results of queries seeking for different view points about controversial topics is key to improving satisfaction of users. The challenge for finding different opinions is how to maximize the number of discussed arguments without being biased against specific sentiments. This paper addresses the issue by first introducing a new model that represents the patterns occurring in documents about controversial topics. Second, proposing an opinion diversification model that uses (1) relevance of documents, (2) semantic diversification to capture different arguments and (3) sentiment diversification to identify positive, negative and neutral sentiments about the query topic. We have conducted our experiments using queries on various controversial topics and applied our diversification model on the set of documents returned by Google search engine. The results show that our model outperforms the native ranking of Web pages about controversial topics by a significant margin.
Fact-based question decomposition for candidate answer re-ranking
Authors: Aditya Kalyanpur, Siddharth Patwardhan, Branimir Boguraev, Adam Lally, Jennifer Chu-Carroll
Venue: CIKM
Year: 2011

Factoid questions often contain one or more assertions (facts) about their answers. However, existing question-answering (QA) systems have not investigated how the multiple facts may be leveraged to enhance system performance. We argue that decomposing complex factoid questions can benefit QA, as an answer candidate is more likely to be correct if multiple independent facts support it. We categorize decomposable questions as parallel or nested, depending on processing strategy required. We present a novel decomposition framework---for parallel and nested questions---which can be overlaid on top of traditional QA systems. It contains decomposition rules for identifying fact sub-questions, a question-rewriting component and a candidate re-ranker. In a particularly challenging domain for our baseline QA system, our framework shows a statistically significant improvement in end-to-end QA performance.
Discovering trending phrases on information streams
Authors: Krishna Yeswanth Kamath, James Caverlee
Venue: CIKM
Year: 2011

We study the problem of efficient discovery of trending phrases from high-volume text streams -- be they sequences of Twitter messages, email messages, news articles, or other time-stamped text documents. Most existing approaches return top-k trending phrases. But, this approach neither guarantees that the top-k phrases returned are all trending, nor that all trending phrases are returned. In addition, the value of k is difficult to set and is indifferent to stream dynamics. Hence, we propose an approach that identifies all the trending phrases in a stream and is flexible to the changing stream properties.
Creating user interfaces that entice people to manage better information
Authors: David R. Karger
Venue: CIKM
Year: 2011

Much research in information management begins by asking how to manage a given information corpus. But information management systems can only be as good as the information they manage. They struggle and often fail to correctly infer meaning from large blobs of text and the mysterious actions and demands of users. And they are useless for managing information that is never captured.
Improving retrieval accuracy of difficult queries through generalizing negative document language models
Authors: Maryam Karimzadehgan, ChengXiang Zhai
Venue: CIKM
Year: 2011

When a query topic is difficult and the search results are very poor, negative feedback is a very useful method to improve the retrieval accuracy and user experience. One challenge in negative feedback is that negative documents tend to be distracting in different ways, thus as training examples, negative examples are sparse. In this paper, we solve the problem of data sparseness in the language modeling framework. We propose an optimization framework, in which we learn from a few top-ranked non-relevant examples, and search in a large space of all language models to build a more general negative language model. This general negative language model has more power in pruning the non-relevant documents, thus potentially improving the performance for difficult queries. Experiment results on representative TREC collections show that the proposed optimization framework can improve negative feedback performance over the state-of-the-art negative feedback method through generalizing negative language models.
Evolving social search based on bookmarks and status messages from social networks
Authors: Bastian Karweg, Christian Hütter, Klemens Böhm
Venue: CIKM
Year: 2011

Social search is a variant of information retrieval where a document or website is considered relevant if individuals from the searcher's social network have interacted with it. Our ranking metric Social Relevance Score (SRS) is based on two factors. First, the engagement intensity quantifies the effort a user has made during an interaction. Second, users can assign a trust score to each person from their social network, which is then refined using social network analysis. We have tested our hypotheses with our search engine www.social-search.com, which extends the existing social bookmarking platform folkd.com. Our search engine integrates information the folkd.com users share through the popular social networks Twitter and Facebook. With permission of 2,385 testers, we have connected to their social graphs to generate a large-scale real-world dataset. Over the course of a two-month field study, 468,889 individuals have generated 24,854,281 website recommendations. We have used those links to enhance their search results while measuring the impact on the search behavior. We have found that social results are available for most queries and usually lead to more satisfying results.
BooksOnline'11: 4th workshop on online books, complementary social media, and crowdsourcing
Authors: Gabriella Kazai, Carsten Eickhoff, Peter Brusilovsky
Venue: CIKM
Year: 2011

The BooksOnline Workshop series aims to foster the discussion and exchange of research ideas towards addressing challenges and exploring opportunities around large collections of digital books and complementary media. The fourth workshop in the series, BooksOnline'11 pays special attention to the role of social media and the phenomena of crowdsourcing in the context of online books, which is expected to be key in defining new user experiences in digital libraries and on the Web. The workshop boasts a high quality program, including keynote addresses by Ville Miettinnen, CEO of Microtask and Adam Farquhar, Head of Digital Library Technology at The British Library. From the accepted papers two main themes became salient: 1) Information retrieval and information extraction methods focused on enhancing digital libraries, and 2) Studies and analyses of reading experience and behaviour. This paper provides an overview of the workshop and the accepted contributions.
Predicting document effectiveness in pseudo relevance feedback
Authors: Mostafa Keikha, Jangwon Seo, W. Bruce Croft, Fabio Crestani
Venue: CIKM
Year: 2011

Pseudo relevance feedback (PRF) is one of effective practices in Information Retrieval. In particular, PRF via the relevance model (RM) has been widely used due to the theoretical soundness and effectiveness. In a PRF scenario, an underlying relevance model is inferred by combining language models of the top retrieved documents where the contribution of each document is assumed to be proportional to its score for the initial query. However, it is not clear that selecting the top retrieved documents only by the initial retrieval scores is actually the optimal way for query expansion.