OpenRaiser/Intern-Atlas huggingface dataset:
Annotating scientific papers for mathematical formula search
Authors: Giovanni Yoko Kristianto, Goran Topic, Minh-Quoc Nghiem, Akiko N. Aizawa
Venue: CIKM
Year: 2012

In recent years, growing numbers of scientific papers have been published in XML format generating a large published base of MathML-style formulas. Although these formulas can be indexed and searched based on their XML tree structures, they generally lack sufficient information for semantic interpretation. We propose an annotation design for linking mathematical formulas to natural language descriptions in the surrounding text. We also introduce potential applications for this annotation framework.
Generating facets for phone-based navigation of structured data
Authors: Krishna Kummamuru, Ajith Jujjuru, Mayuri Duggirala
Venue: CIKM
Year: 2012

Designing interactive voice systems that have optimum cognitive load on callers has been an active research topic for quite some time. There have been many studies comparing the user preferences on navigation trees with higher depths over higher breadths. In this paper, we consider the navigation of structured data containing various types of attributes using phone-based interactions. This problem is particularly relevant to emerging economies in which innovative voice-based applications are being built to address semi-literate population. We address the problem of identifying the right sequence of facets to be presented to the user for phone-based navigation of the data in two stages. Firstly, we perform extensive user studies in the target population to understand the relation between the nature of facets (attributes) of the data and the cognitive load. Secondly, we propose an algorithm to design optimum navigation trees based on the inferences made in the first phase. We compare the proposed algorithm with the traditional facet generation algorithms with respect to various factors and discuss the optimality of the proposed algorithm.
Session-based query performance prediction
Authors: Andrey Kustarev, Yury Ustinovsky, Anna Mazur, Pavel Serdyukov
Venue: CIKM
Year: 2012

Search sessions are known to be a rich source of diverse valuable information for individual query analysis. In this paper, we address the problem of query performance prediction by utilizing the entire logical search sessions containing the given query. Guided by the intuitions based on the observations made after the analysis of the search sessions' properties and performance of the queries they contain, we propose a number of features that significantly advance the existing query performance prediction models. Some of them specifically allow to focus on tail queries with sparse click-through statistics.
Daily-deal selection for revenue maximization
Authors: Theodoros Lappas, Evimaria Terzi
Venue: CIKM
Year: 2012

Daily-Deal Sites (DDS) like Groupon, LivingSocial, Amazon's Goldbox, and many more, have become particularly popular over the last three years, providing discounted offers to customers for restaurants, ticketed events, services etc. In this paper, we study the following problem: among a set of candidate deals, which are the ones that a DDS should feature as daily-deals in order to maximize its revenue? Our first contribution lies in providing two combinatorial formulations of this problem. Both formulations take into account factors like the diversification of daily deals and the limited consuming capacity of the userbase. We prove that our problems are NP-hard and devise pseudopolynomial -- time approximation algorithms for their solution. We also propose a set of heuristics, and demonstrate their efficiency in our experiments. In the context of deal selection and scheduling, we acknowledge the importance of the ability to estimate the expected revenue of a candidate deal. We explore the nature of this task in the context of real data, and propose a framework for revenue-estimation. We demonstrate the effectiveness of our entire methodology in an experimental evaluation on a large dataset of daily-deals from Groupon.
Customizing search results for non-native speakers
Authors: Theodoros Lappas, Michail Vlachos
Venue: CIKM
Year: 2012

Blog posts, news articles and other webpages are present on the web in multiple languages. Standard search engines evaluate the relevance of the candidate documents to the given query. However, when considering documents with overlapping content, many of them written in a foreign language other than the user's own native tongue, it is beneficial to promote documents that are easy enough for the user to read. Here, we show how to rank a collection of foreign documents based on both: a) relevance to the query, and b) the comprehension difficulty of the document. We design effective ranking operators that evaluate the difficulty of a foreign document with respect to the user's native language. We show that existing search engines can easily augment their scoring function by incorporating the proposed comprehensibility metrics. Finally, we provide extensive experimental evidence that the comprehensibility-aware ranking model significantly improves the standard relevance-based ranking paradigm.
Robust distributed indexing for locality-skewed workloads
Authors: Mu-Woong Lee, Seung-won Hwang
Venue: CIKM
Year: 2012

Multidimensional indexing is crucial for enabling a fast search over large-scale data. Owing to the unprecedented scale of data, extending such indexing technology has recently gained attention in distributed environments. The goal of existing efforts in distributed indexing has been the localization of queries to data residing at a small number of nodes (i.e., locality-preserving indexing) to minimize communication cost. However, considering that workloads often correlate with data locality, such indexing often generates hotspots. Location-based queries are typically skewed to disaster areas during certain periods of time, e.g., during Hurricane Irene, search traffic increased by more than 2000%. To alleviate such hotspots, we propose workload-balancing as an optimization goal. A cost model analytically supporting the need for load balancing is first developed, then a distributed index that evenly distributes the workload is presented. Our empirical study suggests that hotspots degrading search performance can be effectively alleviated. Specifically, when deployed to Amazon EC2, our proposed scheme showed maximum speed-up of 127.7%. Even in hostile settings where workload is not at all correlated with the search criteria, the proposed scheme's performance is comparable to existing approaches optimized for such settings.
PathRank: a novel node ranking measure on a heterogeneous graph for recommender systems
Authors: Sangkeun Lee, Sungchan Park, Minsuk Kahng, Sang-goo Lee
Venue: CIKM
Year: 2012

In this paper, we present a novel random-walk based node ranking measure, PathRank, which is defined on a heterogeneous graph by extending the Personalized PageRank algorithm. Not only can our proposed measure exploit the semantics behind the different types of nodes and edges in a heterogeneous graph, but also it can emulate various recommendation semantics such as collaborative filtering, content-based filtering, and their combinations. The experimental results show that PathRank can produce more various and effective recommendation results compared to existing approaches.
A comprehensive analysis of parameter settings for novelty-biased cumulative gain
Authors: Teerapong Leelanupab, Guido Zuccon, Joemon M. Jose
Venue: CIKM
Year: 2012

In the TREC Web Diversity track, novelty-biased cumulative gain (α-NDCG) is one of the official measures to assess retrieval performance of IR systems. The measure is characterised by a parameter, α, the effect of which has not been thoroughly investigated. We find that common settings of α, i.e. α=0.5, may prevent the measure from behaving as desired when evaluating result diversification. This is because it excessively penalises systems that cover many intents while it rewards those that redundantly cover only few intents. This issue is crucial since it highly influences systems at top ranks. We revisit our previously proposed threshold, suggesting α be set on a query-basis. The intuitiveness of the measure is then studied by examining actual rankings from TREC 09-10 Web track submissions. By varying α according to our query-based threshold, the discriminative power of α-NDCG is not harmed and in fact, our approach improves α-NDCG's robustness. Experimental results show that the threshold for α can turn the measure to be more intuitive than using its common settings.
Applying weighted queries on probabilistic databases
Authors: Sebastian Lehrack
Venue: CIKM
Year: 2012

Relational queries applied on probabilistic databases have been established as a powerful tool for accessing huge data sets of uncertain data. Often various parts of such queries have different significances for a specific user. Thus, a query language should allow us to give subqueries different weights to quantify the individual user preferences. In this work we introduce a theoretical foundation for weighted algebra operators on probabilistic databases within a SQL-like query language.
Supporting factual statements with evidence from the web
Authors: Chee Wee Leong, Silviu Cucerzan
Venue: CIKM
Year: 2012

Fact verification has become an important task due to the increased popularity of blogs, discussion groups, and social sites, as well as of encyclopedic collections that aggregate content from many contributors. We investigate the task of automatically retrieving supporting evidence from the Web for factual statements. Using Wikipedia as a starting point, we derive a large corpus of statements paired with supporting Web documents, which we employ further as training and test data under the assumption that the contributed references to Wikipedia represent some of the most relevant Web documents for supporting the corresponding statements. Given a factual statement, the proposed system first transforms it into a set of semantic terms by using machine learning techniques. It then employs a quasi-random strategy for selecting subsets of the semantic terms according to topical likelihood. These semantic terms are used to construct queries for retrieving Web documents via a Web search API. Finally, the retrieved documents are aggregated and re-ranked by employing additional measures of their suitability to support the factual statement. To gauge the quality of the retrieved evidence, we conduct a user study through Amazon Mechanical Turk, which shows that our system is capable of retrieving supporting Web documents comparable to those chosen by Wikipedia contributors.
An evaluation and enhancement of densitometric fragmentation for content slicing reuse
Authors: Killian Levacher, Séamus Lawless, Vincent Wade
Venue: CIKM
Year: 2012

Content slicing addresses the need of adaptive systems to reuse open corpus material by converting it into re-composable information objects. However this conversion is highly dependent upon the ability to correctly fragment pages into structurally sound atomic pieces. A recently suggested approach to fragmentation, which relies on densitometric page representation, claims to achieve high accuracy and time performance. Although it has been well received within the research community, a full evaluation of this approach and identification of strengths and weaknesses across a range of characteristics hasn't been performed. This paper proposes an independent evaluation of the approach with respect to granularity control, accuracy, time performance, content diversity and linguistic dependency. Moreover, this paper also provides a significant contribution to address important weaknesses discovered during the analysis, in order to improve the suitability and impact of the original algorithm within the context of content slicing.
On skyline groups
Authors: Chengkai Li, Nan Zhang, Naeemul Hassan, Sundaresan Rajasekaran, Gautam Das
Venue: CIKM
Year: 2012

We formulate and investigate the novel problem of finding the skyline k-tuple groups from an n-tuple dataset - i.e., groups of k tuples which are not dominated by any other group of equal size, based on aggregate-based group dominance relationship. The major technical challenge is to identify effective anti-monotonic properties for pruning the search space of skyline groups. To this end, we show that the anti-monotonic property in the well-known Apriori algorithm does not hold for skyline group pruning. We then identify order-specific property which applies to SUM, MIN, and MAX and weak candidate-generation property which applies to MIN and MAX only. Experimental results on both real and synthetic datasets verify that the proposed algorithms achieve orders of magnitude performance gain over a baseline method.
Relational co-clustering via manifold ensemble learning
Authors: Ping Li, Jiajun Bu, Chun Chen, Zhanying He
Venue: CIKM
Year: 2012

Co-clustering targets on grouping the samples and features simultaneously. It takes advantage of the duality between the samples and features. In many real-world applications, the data points or features usually reside on a submanifold of the ambient Euclidean space, but it is nontrivial to estimate the intrinsic manifolds in a principled way. In this study, we focus on improving the co-clustering performance via manifold ensemble learning, which aims to maximally approximate the intrinsic manifolds of both the sample and feature spaces. To achieve this, we develop a novel co-clustering algorithm called Relational Multi-manifold Co-clustering (RMC) based on symmetric nonnegative matrix tri-factorization, which decomposes the relational data matrix into three matrices. This method considers the inter-type relationship revealed by the relational data matrix and the intra-type information reflected by the affinity matrices. Specifically, we assume the intrinsic manifold of the sample or feature space lies in a convex hull of a group of pre-defined candidate manifolds. We hope to learn an appropriate convex combination of them to approach the desired intrinsic manifold. To optimize the objective, the multiplicative rules are utilized to update the factorized matrices and the entropic mirror descent algorithm is exploited to automatically learn the manifold coefficients. Experimental results demonstrate the superiority of the proposed algorithm.
Incorporating word correlation into tag-topic model for semantic knowledge acquisition
Authors: Fang Li, Tingting He, Xinhui Tu, Xiaohua Hu
Venue: CIKM
Year: 2012

This paper presents a tag-topic model with Dirichlet Forest prior (TTM-DF) for semantic knowledge acquisition from blog. The TTM-DF model extends the tag-topic model (TTM) by replacing the Dirichlet prior with the Dirichlet Forest prior over the topic-word multinomial. The correlation between words are calculated to generate a set of Must-Links and Cannot-Links, then the structures of Dirichlet trees are obtained though encoding the constraints of Must-Links and Cannot-Links. Words under the same subtrees are expected to be more correlated than words under different subtrees. We conduct experiments on a synthetic and a blog dataset. Both of the experimental results show that the TTM-DF model performs much better than the TTM model. It can improve the coherence of the underlying topics and the tag-topic distributions, and capture semantic knowledge effectively.
DQR: a probabilistic approach to diversified query recommendation
Authors: Ruirui Li, Ben Kao, Bin Bi, Reynold Cheng, Eric Lo
Venue: CIKM
Year: 2012

Web search queries issued by casual users are often short and with limited expressiveness. Query recommendation is a popular technique employed by search engines to help users refine their queries. Traditional similarity-based methods, however, often result in redundant and monotonic recommendations. We identify five basic requirements of a query recommendation system. In particular, we focus on the requirements of redundancy-free and diversified recommendations. We propose the DQR framework, which mines a search log to achieve two goals: (1) It clusters search log queries to extract query concepts, based on which recommended queries are selected. (2) It employs a probabilistic model and a greedy heuristic algorithm to achieve recommendation diversification. Through a comprehensive user study we compare DQR against five other recommendation methods. Our experiment shows that DQR outperforms the other methods in terms of relevancy, diversity, and ranking performance of the recommendations. © 2012 ACM.
Collective intelligence in the online social network of yahoo!answers and its implications
Authors: Ze Li, Haiying Shen, Joseph Edward Grant
Venue: CIKM
Year: 2012

Question and Answer (Q&A) websites such as Yahoo!Answers provide a platform where users can post questions and receive answers. These systems take advantage of the collective intelligence of users to find information. In this paper, we analyze the online social network (OSN) in Yahoo!Answers. Based on a large amount of our collected data, we studied the OSN's structural properties, which reveals strikingly distinct properties such as low link symmetry and weak correlation between indegree and outdegree. After studying the knowledge base and behaviors of the users, we find that a small number of top contributors answer most of the questions in the system. Also, each top contributor focuses on only a few knowledge categories. In addition, the knowledge categories of the users are highly clustered. We also study the knowledge base in a user's social network, which reveals that the members in a user's social network share only a few knowledge categories. Based on the findings, we provide guidance in the design of spammer detection algorithms and distributed Q&A systems. We also propose a friendship-knowledge oriented Q&A framework that synergically combines current OSN-based Q&A and web Q&A. We believe that the results presented in this paper are crucial in understanding the collective intelligence in the web Q&A OSNs and lay a cornerstone for the evolution of next-generation Q&A systems.
Spatial-aware interest group queries in location-based social networks
Authors: Yafei Li, Dingming Wu, Jianliang Xu, Byron Choi, Weifeng Su
Venue: CIKM
Year: 2012

Location-based social networks, such as Foursquare and Facebook Places, are bridging the gap between the physical world and online social networking services through acquired user locations. Some social networks released check-in services that allow users to share their visiting locations with their friends. In this paper, users' interests are modeled by check-in actions. We propose a new spatial-aware interest group (SIG) query that retrieves a user group of size k where every user is highly interested in the query keyword and also spatially close to each other. An efficient algorithm AIR based on the IR-tree is proposed for the processing of SIG queries. Furthermore, an optimization is developed and achieves a much better performance than the baseline algorithm.
Keyword-based k-nearest neighbor search in spatial databases
Authors: Guoliang Li, Jing Xu, Jianhua Feng
Venue: CIKM
Year: 2012

With the ever-increasing number of spatio-textual objects, many applications require to find objects close to a given query point in spatial databases. In this paper, we study the problem of keyword-based k-nearest neighbor search in spatial databases, which, given a query point and a set of keywords, finds k-nearest neighbors of the query point that contain all query keywords. To efficiently answer such queries, we propose a new indexing framework by integrating a spatial component and a textual component, which can efficiently prune search space in terms of both spatial information and textual descriptions. We develop effective index structures and pruning techniques to improve query performance. Experimental results show that our approach significantly outperforms state-of-the-art methods.
Measuring robustness of complex networks under MVC attack
Authors: Rong-Hua Li, Jeffrey Xu Yu, Xin Huang, Hong Cheng, Zechao Shang
Venue: CIKM
Year: 2012

Measuring robustness of complex networks is a fundamental task for analyzing the structure and function of complex networks. In this paper, we study the network robustness under the maximal vertex coverage (MVC) attack, where the attacker aims to delete as many edges of the network as possible by attacking a small fraction of nodes. First, we present two robustness metrics of complex networks based on MVC attack. We then propose an efficient randomized greedy algorithm with near-optimal performance guarantee for computing the proposed metrics. Finally, we conduct extensive experiments on 20 real datasets. The results show that P2P and co-authorship networks are extremely robust under the MVC attack while both the online social networks and the Email communication networks exhibit vulnerability under the MVC attack. In addition, the results demonstrate the efficiency and effectiveness of our proposed algorithms for computing the corresponding robustness metrics.
Density index and proximity search in large graphs
Authors: Nan Li, Xifeng Yan, Zhen Wen, Arijit Khan
Venue: CIKM
Year: 2012

Given a large real-world graph where vertices are associated with labels, how do we quickly find interesting vertex sets according to a given query? In this paper, we study label-based proximity search in large graphs, which finds the top-k query-covering vertex sets with the smallest diameters. Each set has to cover all the labels in a query. Existing greedy algorithms only return approximate answers, and do not scale well to large graphs. We propose a novel framework, called gDensity, which uses density index and likelihood ranking to find vertex sets in an efficient and accurate manner. Promising vertices are ordered and examined according to their likelihood to produce answers, and the likelihood calculation is greatly facilitated by density indexing. Techniques such as progressive search and partial indexing are further proposed. Experiments on real-world graphs show the efficiency and scalability of gDensity.
A collective synchronous behavior model on social media
Authors: Victor C. Liang, Vincent T. Y. Ng
Venue: CIKM
Year: 2012

Collective synchronous behavior is a pervasive phenomenon that we can discover in nature and virtual social media. Traditional data mining methods, however, mainly concentrate on analysis of individual behavior. In sociology, many well-known models are not suitable for the social media environment as well, in which huge amounts of data are generated everyday. In this paper, we proposed an innovative model that consists of multiple hidden Markov chains. By learning from the observations from a group of people, our model can not only predict the steady future state of a collective, but also measure the dependency property, reactive factor, of individuals. Experiment result shows that our model has ability to distinguish the behaviors of different persons.
An efficient and simple under-sampling technique for imbalanced time series classification
Authors: Guohua Liang, Chengqi Zhang
Venue: CIKM
Year: 2012

Imbalanced time series classification (TSC) involving many real-world applications has increasingly captured attention of researchers. Previous work has proposed an intelligent-structure preserving over-sampling method (SPO), which the authors claimed achieved better performance than other existing over-sampling and state-of-the-art methods in TSC. The main disadvantage of over-sampling methods is that they significantly increase the computational cost of training a classification model due to the addition of new minority class instances to balance data-sets with high dimensional features. These challenging issues have motivated us to find a simple and efficient solution for imbalanced TSC. Statistical tests are applied to validate our conclusions. The experimental results demonstrate that this proposed simple random under-sampling technique with SVM is efficient and can achieve results that compare favorably with the existing complicated SPO method for imbalanced TSC.