OpenRaiser/Intern-Atlas huggingface dataset:
Mining noisy tagging from multi-label space
Authors: Zhongang Qi, Ming Yang, Zhongfei (Mark) Zhang, Zhengyou Zhang
Venue: CIKM
Year: 2012

In this paper we study the problem of mining noisy tagging. Most of the existing discriminative classification methods to this problem only consider one tag at a time as the classification target, and completely ignore the rest of the given tags at the same time. In this paper we argue that all the given multiple tags can be utilized simultaneously as an additional feature and the information contained in the multi-label space can be taken advantage of to improve the performance of the classification. We first propose a novel distance measure to compute the distance between instances in the multi-label space. Then we propose several novel methods to incorporate the information of the multi-label space into the discriminative classification methods in one view learning or in two views learning to solve a general multi-label classification problem and to mitigate the influence of the noise in the classification. We apply the proposed solutions to the problem with a more specific context - noisy image annotation, and evaluate the proposed methods on a standard dataset from the related literature. Experiments show that they are superior to the peer methods in the existing literature on solving the problem of mining noisy tagging.
Optimizing data migration for cloud-based key-value stores
Authors: Xiulei Qin, Wenbo Zhang, Wei Wang, Jun Wei, Xin Zhao, Tao Huang
Venue: CIKM
Year: 2012

As one database offloading strategy, elastic key-value stores are often introduced to speed up the application performance with dynamic scalability. Since the workload is varied, efficient data migration with minimal impact in service is critical for the issue of elasticity and scalability. However, due to the new virtualization technology, real-time and low-latency requirements, data migration within cloud-based key-value stores has to face new challenges: effects of VM interference, and the need to trade off between the two ingredients of migration cost, namely migration time and performance impact. To fulfill these challenges, in this paper we explore a new approach to optimize the data migration. Explicitly, we build two interference-aware models to predict the migration time and performance impact for each migration action using statistical machine learning, and then create a cost model to strike a balance between the two ingredients. Using the load rebalancing scenario as a case study, we have designed one cost-aware migration algorithm that utilizes the cost model to guide the choice of possible migration actions. Finally, we demonstrate the effectiveness of the approach using Yahoo! Cloud Serving Benchmark (YCSB).
CoNet: feature generation for multi-view semi-supervised learning with partially observed views
Authors: Brian Quanz, Jun Huan
Venue: CIKM
Year: 2012

Multi-view semi-supervised learning methods try to exploit the combination of multiple views along with large amounts of unlabeled data in order to learn better predictive functions when limited labeled data is available. However, lack of complete view data limits the applicability of multi-view semi-supervised learning to real world data. Commonly, one data view is readily and cheaply available, but additionally views may be costly or only available in some cases. This work aims to make multi-view semi-supervised learning approaches more applicable to real world data specifically by addressing the issue of missing views.
Extraction and analysis of the structure of labels in biomedical ontologies
Authors: Manuel Quesada-Martínez, Jesualdo Tomás Fernández-Breis, Robert Stevens
Venue: CIKM
Year: 2012

The increasing interest in biomedical ontologies has provoked the development of a significant number of ontologies, and many more are expected to be produced in the near future. A significant proportion of such ontologies have not been created by computer scientists or ontology engineers, but by domain experts. Many such ontologies are rich in implicit knowledge, but are really just plain taxonomies and controlled vocabularies, with little axiomatization.
Short-text domain specific key terms/phrases extraction using an n-gram model with wikipedia
Authors: Muhammad Atif Qureshi, Colm O&apos, Riordan, Gabriella Pasi
Venue: CIKM
Year: 2012

Finding domain specific key terms/phrases from a given set of documents is a challenging task. A domain may be defined as an area of interest over a collection of documents which may not be explicitly defined but implicitly observable in those documents. When considering a collection of documents related to academic research, examples of key terms/phrases may be Information Retrieval", "Marine Biology", etc. In this paper a technique for extracting important key terms/phrases in a considered topical domain is proposed using external evidence from the titles of Wikipedia articles and the Wikipedia category graph. We performed some experiments over the document collection of Web sites of different post-graduate schools. Our preliminary evaluations show promising results for the detection of domain specific key terms/phrases from the given set of domain focused Web pages.
GRAFT: an approximate graphlet counting algorithm for large graph analysis
Authors: Mahmudur Rahman, Mansurul Bhuiyan, Mohammad Al Hasan
Venue: CIKM
Year: 2012

Graphlet frequency distribution (GFD) is an analysis tool for understanding the variance of local structure in a graph. Many recent works use GFD for comparing, and characterizing real-life networks. However, the main bottleneck for graph analysis using GFD is the excessive computation cost for obtaining the frequency of each of the graphlets in a large network. To overcome this, we propose a simple, yet powerful algorithm, called GRAFT, that obtains the approximate graphlet frequency for all graphlets that have upto 5 vertices. Comparing to an exact counting algorithm, our algorithm achieves a speedup factor between 10 and 100 for a negligible counting error, which is, on average, less than 5%; For example, exact graphlet counting for ca-AstroPh takes approximately 3 days; but, GRAFT runs for 45 minutes to perform the same task with a counting accuracy of 95.6%.
Exploring the cluster hypothesis, and cluster-based retrieval, over the web
Authors: Fiana Raiber, Oren Kurland
Venue: CIKM
Year: 2012

We present a study of the cluster hypothesis, and of the performance of cluster-based retrieval methods, performed over large scale Web collections. Among the findings we present are (i) the cluster hypothesis can hold, as determined by a specific test, for large scale Web corpora to the same extent it does for newswire corpora; (ii) while spam documents do not affect the extent to which the cluster hypothesis holds, they considerably affect the performance of cluster based, as well as that of document-based, retrieval methods; and, (iii) as is the case for newswire corpora, cluster-based methods can yield better performance than document-based methods for Web corpora.
Content-based relevance estimation on the web using inter-document similarities
Authors: Fiana Raiber, Oren Kurland, Moshe Tennenholtz
Venue: CIKM
Year: 2012

In adversarial and noisy search settings as the Web, the document-query surface level similarity can be a highly misleading relevance signal. Thus, devising content-based relevance estimation (ranking) approaches becomes highly challenging. We address this challenge using two methods that utilize inter-document similarities in an initially retrieved list. The first removes documents from the list that exhibit high query similarity, but for which there is insufficient additional support for relevance that is based on inter-document similarities. The method is based on a probabilistic model that decouples document-query similarities from relevance estimation. The second method re-ranks the list by "rewarding" documents that exhibit high similarity both to the query and to other documents in the list. Both methods incorporate, in addition, at the model level, query-independent document quality estimates. Extensive empirical evaluation demonstrates the merits of our methods.
Constructing test collections by inferring document relevance via extracted relevant information
Authors: Shahzad Rajput, Matthew Ekstrand-Abueg, Virgiliu Pavlu, Javed A. Aslam
Venue: CIKM
Year: 2012

The goal of a typical information retrieval system is to satisfy a user's information need---e.g., by providing an answer or information "nugget"---while the actual search space of a typical information retrieval system consists of documents---i.e., collections of nuggets. In this paper, we characterize this relationship between nuggets and documents and discuss applications to system evaluation.
A word-order based graph representation for relevance identification
Authors: Lakshmi Ramachandran, Edward F. Gehringer
Venue: CIKM
Year: 2012

In this paper we propose a new word-order based graph representation for text. In our graph representation vertices represent words or phrases and edges represent relations between contiguous words or phrases. The graph representation also includes dependency information. Our text representation is suitable for applications involving the identification of relevance or paraphrases across texts, where word-order information would be useful. We show that this word-order based graph representation performs better than a dependency tree representation while identifying the relevance of one piece of text to another.
Learning from mistakes: towards a correctable learning algorithm
Authors: Karthik Raman, Krysta M. Svore, Ran Gilad-Bachrach, Christopher J. C. Burges
Venue: CIKM
Year: 2012

Many learning algorithms generate complex models that are difficult for a human to interpret, debug, and extend. In this paper, we address this challenge by proposing a new learning paradigm called correctable learning, where the learning algorithm receives external feedback about which data examples are incorrectly learned. We define a set of metrics which measure the correctability of a learning algorithm. We then propose a simple and efficient correctable learning algorithm which learns local models for different regions of the data space. Given an incorrect example, our method samples data in the neighborhood of that example and learns a new, more correct local model over that region. Experiments over multiple classification and ranking datasets show that our correctable learning algorithm offers significant improvements over the state-of-the-art techniques.
Metaphor: a system for related search recommendations
Authors: Azarias Reda, Yubin Park, Mitul Tiwari, Christian Posse, Sam Shah
Venue: CIKM
Year: 2012

Search plays an important role in online social networks as it provides an essential mechanism for discovering members and content on the network. Related search recommendation is one of several mechanisms used for improving members' search experience in finding relevant results to their queries. This paper describes the design, implementation, and deployment of Metaphor, the related search recommendation system on LinkedIn, a professional social networking site with over 175~million members worldwide. Metaphor builds on a number of signals and filters that capture several dimensions of relatedness across member search activity. The system, which has been in live operation for over a year, has gone through multiple iterations and evaluation cycles. This paper makes three contributions. First, we provide a discussion of a large-scale related search recommendation system. Second, we describe a mechanism for effectively combining several signals in building a unified dataset for related search recommendations. Third, we introduce a query length model for capturing bias in recommendation click behavior. We also discuss some of the practical concerns in deploying related search recommendations.
Topic based pose relevance learning in dance archives
Authors: Reede Ren, John P. Collomosse, Joemon M. Jose
Venue: CIKM
Year: 2012

This paper improves spatial pyramid kernel (SPK) and proposes a relevance learning approach to compare performer's poses in a large dance archive, the NRCD collection1. Domain knowledge of Choreutics is exploited to define pose topics and a selection operator is developed for pose topic matching. The visual structure descriptor of self similarity (SSF) is extended to hierarchical self similarity (HSSF) to keep shape context. The framework of Bag-of-Visual Words (BOVW) is applied to encode as well as to speed up the matching on pose topics/topic combinations. This alleviates the complexity in limb allocation which is infeasible in our data. Extensive experiments show that the new approach outperforms the original SPK in both precision and robustness.
The efficient imputation method for neighborhood-based collaborative filtering
Authors: Yongli Ren, Gang Li, Jun Zhang, Wanlei Zhou
Venue: CIKM
Year: 2012

As each user tends to rate a small proportion of available items, the resulted Data Sparsity issue brings significant challenges to the research of recommender systems. This issue becomes even more severe for neighborhood-based collaborative filtering methods, as there are even lower numbers of ratings available in the neighborhood of the query item. In this paper, we aim to address the Data Sparsity issue in the context of the neighborhood-based collaborative filtering. Given the (user, item) query, a set of key ratings are identified, and an auto-adaptive imputation method is proposed to fill the missing values in the set of key ratings. The proposed method can be used with any similarity metrics, such as the Pearson Correlation Coefficient and Cosine-based similarity, and it is theoretically guaranteed to outperform the neighborhood-based collaborative filtering approaches. Results from experiments prove that the proposed method could significantly improve the accuracy of recommendations for neighborhood-based Collaborative Filtering algorithms.
Preprocessing of informal mathematical discourse in context ofcontrolled natural language
Authors: Raúl Ernesto Gutiérrez de Piñerez Reyes, Juan Francisco Díaz-Frías
Venue: CIKM
Year: 2012

Informal Mathematical Discourse (IMD) is characterized by the mixture of natural language and symbolic expressions in the context of textbooks, publications in mathematics and mathematical proof. We focused the IMD processing at the low level of discourse. In this paper, we proposed the preprocessing phase before the IMD structure analysis within the context of Controlled Natural Language (CNL). Our contribution is defined in context of the IMD processing and the use of machine learning; first, we present a CNL, a pure corpus and Matemathical Treebank for processing IMD; second, we present a preprocessing phase for IMD analysis with connectives disambiguation and verbs treatment, finally, we found a satisfactory result on input text parsing using a statistical parsing model. We will propagate these results for classification of argumentative informal practices via the low level discourse in IMD processing.
PARMA: a parallel randomized algorithm for approximate association rules mining in MapReduce
Authors: Matteo Riondato, Justin A. DeBrabant, Rodrigo Fonseca, Eli Upfal
Venue: CIKM
Year: 2012

Frequent Itemsets and Association Rules Mining (FIM) is a key task in knowledge discovery from data. As the dataset grows, the cost of solving this task is dominated by the component that depends on the number of transactions in the dataset. We address this issue by proposing PARMA, a parallel algorithm for the MapReduce framework, which scales well with the size of the dataset (as number of transactions) while minimizing data replication and communication cost. PARMA cuts down the dataset-size-dependent part of the cost by using a random sampling approach to FIM. Each machine mines a small random sample of the dataset, of size independent from the dataset size. The results from each machine are then filtered and aggregated to produce a single output collection. The output will be a very close approximation of the collection of Frequent Itemsets (FI's) or Association Rules (AR's) with their frequencies and confidence levels. The quality of the output is probabilistically guaranteed by our analysis to be within the user-specified accuracy and error probability parameters. The sizes of the random samples are independent from the size of the dataset, as is the number of samples. They depend on the user-chosen accuracy and error probability parameters and on the parallel computational model. We implemented PARMA in Hadoop MapReduce and show experimentally that it runs faster than previously introduced FIM algorithms for the same platform, while 1) scaling almost linearly, and 2) offering even higher accuracy and confidence than what is guaranteed by the analysis.
Workshop on multimodal crowd sensing (CrowdSens 2012)
Authors: Haggai Roitman, Iván Cantador, Miriam Fernández
Venue: CIKM
Year: 2012

This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in CIKM '12 Proceedings of the 21st ACM international conference on Information and knowledge management, http://dx.doi.org/10.1145/2396761.2398760.
On the foundations of probabilistic information integration
Authors: Fereidoon Sadri
Venue: CIKM
Year: 2012

Information integration has been a subject of research for several decades and still remains a very active research area. Many new applications depend or benefit from large scale integration. Examples include large research projects in life sciences, need for data sharing among government agencies, reliance of corporations on business intelligence (which requires data integration from many heterogeneous sources), and integration of information on the web. The importance of information integration with uncertainty has been observed in recent years. Frequently, information from multiple sources are uncertain and possibly inconsistent. Further the process of integration often depends on approximate schema mappings, another source of uncertainty. An integration system is useful only to the extent that the information it produces can be trusted. Hence, providing a measure of certainty for integrated information is of crucial importance in many important applications.
G-SPARQL: a hybrid engine for querying large attributed graphs
Authors: Sherif Sakr, Sameh Elnikety, Yuxiong He
Venue: CIKM
Year: 2012

We propose a SPARQL-like language, G-SPARQL, for querying attributed graphs. The language expresses types of queries which of large interest for applications which model their data as large graphs such as: pattern matching, reachability and shortest path queries. Each query can combine both of structural predicates and value-based predicates (on the attributes of the graph nodes and edges). We describe an algebraic compilation mechanism for our proposed query language which is extended from the relational algebra and based on the basic construct of building SPARQL queries, the Triple Pattern. We describe a hybrid Memory/Disk representation of large attributed graphs where only the topology of the graph is maintained in memory while the data of the graph is stored in a relational database. The execution engine of our proposed query language splits parts of the query plan to be pushed inside the relational database while the execution of other parts of the query plan are processed using memory-based algorithms, as necessary. Experimental results on real datasets demonstrate the efficiency and the scalability of our approach and show that our approach outperforms native graph databases by several factors.
A unified optimization framework for auction and guaranteed delivery in online advertising
Authors: Konstantin Salomatin, Tie-Yan Liu, Yiming Yang
Venue: CIKM
Year: 2012

This paper proposes a new unified optimization framework combining pay-per-click auctions and guaranteed delivery in sponsored search. Advertisers usually have different (and sometimes mixed) marketing goals: brand awareness and direct response. Different mechanisms are good at addressing different goals, e.g., guaranteed delivery was often used to build brand awareness and pay-per-click auctions was widely used for direct marketing. Our new method accommodates both in a unified framework, with the search engine revenue as an optimization objective. In this way, we can target a guaranteed number of ad clicks (or impressions) per campaign for advertisers willing to pay a premium and enable keyword auctions for all others. Specifically, we formulate this joint optimization problem using linear programming and a column generation strategy for efficiency. To select the best column (a ranked list of ads) given a query, we propose a novel dynamic programming algorithm that takes the special structure of the ad allocation and pricing mechanisms into account. We have tested the proposed framework and the algorithms on real ad data obtained from a commercial search engine. The results demonstrate that our proposed approach can outperform several baselines in guaranteeing the number of clicks for the given advertisers, and in increasing the total revenue for the search engine.
Differences in effectiveness across sub-collections
Authors: Mark Sanderson, Andrew Turpin, Ying Zhang, Falk Scholer
Venue: CIKM
Year: 2012

The relative performance of retrieval systems when evaluated on one part of a test collection may bear little or no similarity to the relative performance measured on a different part of the collection. In this paper we report the results of a detailed study of the impact that different sub-collections have on retrieval effectiveness, analyzing the effect over many collections, and with different approaches to sub-dividing the collections. The effect is shown to be substantial, impacting on comparisons between retrieval runs that are statistically significant. Some possible causes for the effect are investigated, and the implications of this work are examined for test collection design and for the strength of conclusions one can draw from experimental results.
An automatic blocking mechanism for large-scale de-duplication tasks
Authors: Anish Das Sarma, Ankur Jain, Ashwin Machanavajjhala, Philip Bohannon
Venue: CIKM
Year: 2012

De-duplication - identification of distinct records referring to the same real-world entity - is a well-known challenge in data integration. Since very large datasets prohibit the comparison of every pair of records, blocking has been identified as a technique of dividing the dataset for pairwise comparisons, thereby trading off recall of identified duplicates for efficiency. Traditional de-duplication tasks, while challenging, typically involved a fixed schema such as Census data or medical records. However, with the presence of large, diverse sets of structured data on the web and the need to organize it effectively on content portals, de-duplication systems need to scale in a new dimension to handle a large number of schemas, tasks and data sets, while handling ever larger problem sizes. In addition, when working in a map-reduce framework it is important that canopy formation be implemented as a hash function, making the canopy design problem more challenging. We present CBLOCK, a system that addresses these challenges. CBLOCK learns hash functions automatically from attribute domains and a labeled dataset consisting of duplicates. Subsequently, CBLOCK expresses blocking functions using a hierarchical tree structure composed of atomic hash functions. The application may guide the automated blocking process based on architectural constraints, such as by specifying a maximum size of each block (based on memory requirements), impose disjointness of blocks (in a grid environment), or specify a particular objective function trading off recall for efficiency. As a post-processing step to automatically generated blocks, CBLOCK rolls-up smaller blocks to increase recall. We present experimental results on two large-scale de-duplication datasets from a commercial search engine - consisting of over 140K movies and 40K restaurants respectively - and demonstrate the utility of CBLOCK.