OpenRaiser/Intern-Atlas huggingface dataset:
Unsupervised Feature Selection on Data Streams
Authors: Hao Huang, Shinjae Yoo, Shiva Prasad Kasiviswanathan
Venue: CIKM
Year: 2015

Massive data streams are continuously being generated from sources such as social media, broadcast news, etc., and typically these datapoints lie in high-dimensional spaces (such as the vocabulary space of a language). Timely and accurate feature subset selection in these massive data streams has important applications in model interpretation, computational/storage cost reduction, and generalization enhancement. In this paper, we introduce a novel unsupervised feature selection approach on data streams that selects important features by making only one pass over the data while utilizing limited storage. The proposed algorithm uses ideas from matrix sketching to efficiently maintain a low-rank approximation of the observed data and applies regularized regression on this approximation to identify the important features. We theoretically prove that our algorithm is close to an expensive offline approach based on global singular value decompositions. The experimental results on a variety of text and image datasets demonstrate the excellent ability of our approach to identify important features even in presence of concept drifts and also its efficiency over other popular scalable feature selection algorithms.
A Unified Posterior Regularized Topic Model with Maximum Margin for Learning-to-Rank
Authors: Shoaib Jameel, Wai Lam, Steven Schockaert, Lidong Bing
Venue: CIKM
Year: 2015

While most methods for learning-to-rank documents only consider relevance scores as features, better results can often be obtained by taking into account the latent topic structure of the document collection. Existing approaches that consider latent topics follow a two-stage approach, in which topics are discovered in an unsupervised way, as usual, and then used as features for the learning-to-rank task. In contrast, we propose a learning-to-rank framework which integrates the supervised learning of a maximum margin classifier with the discovery of a suitable probabilistic topic model. In this way, the labelled data that is available for the learning-to-rank task can be exploited to identify the most appropriate topics. To this end, we use a unified constrained optimization framework, which can dynamically compute the latent topic similarity score between the query and the document. Our experimental results show a consistent improvement over the state-of-the-art learning-to-rank models.
A Structured Query Model for the Deep Relational Web
Authors: Hasan M. Jamil, H. V. Jagadish
Venue: CIKM
Year: 2015

The deep web is very large and diverse and queries evaluated against the deep web can provide great value. While there have been attempts at accessing the data in the deep web, these are clever "one-of'' systems and techniques. In this paper, we describe an ongoing research of a generic structured query model that can be used against the deep web. Using this query model, the contributions of a community of researchers can be combined freely, leading to a system that can be improved incrementally each time someone develops a specific novel technique to improve a particular operator.
A Flash-aware Buffering Scheme using On-the-fly Redo
Authors: Kyo-Sung Jeong, Sang-Wook Kim, Sungchae Lim
Venue: CIKM
Year: 2015

In this paper, we address how to reduce the amount of page updates in flash-based DBMS equipped with SSD (Solid State Drive). We propose a novel buffering scheme that evicts a dirty page X without flushing it into SSD, and restores the right image of X when X is requested for later access. The restoration of X having previous flushing-less eviction is performed through our online redo actions on X. We call this page-restoring online redo the on-the-fly redo. Although our on-the-fly redo mechanism has some overhead of increasing the number of page reads, this can be compensated by infrequent page updates. Additionally, since the proposed buffering scheme with the on-the-fly redo can easily support the no-steal policy in buffer management, we can enjoy the advantages of smaller logging overhead and faster recovery. Through the TPC-C benchmarks using a Berkeley DB, we show that our scheme shortens the transaction processing times by up to 53%.
Improving Ranking Consistency for Web Search by Leveraging a Knowledge Base and Search Logs
Authors: Jyun-Yu Jiang, Jing Liu, Chin-Yew Lin, Pu-Jen Cheng
Venue: CIKM
Year: 2015

In this paper, we propose a new idea called ranking consistency in web search. Relevance ranking is one of the biggest problems in creating an effective web search system. Given some queries with similar search intents, conventional approaches typically only optimize ranking models by each query separately. Hence, there are inconsistent rankings in modern search engines. It is expected that the search results of different queries with similar search intents should preserve ranking consistency. The aim of this paper is to learn consistent rankings in search results for improving the relevance ranking in web search. We then propose a re-ranking model aiming to simultaneously improve relevance ranking and ranking consistency by leveraging knowledge bases and search logs. To the best of our knowledge, our work offers the first solution to improving relevance rankings with ranking consistency. Extensive experiments have been conducted using the Freebase knowledge base and the large-scale query-log of a commercial search engine. The experimental results show that our approach significantly improves relevance ranking and ranking consistency. Two user surveys on Amazon Mechanical Turk also show that users are sensitive and prefer the consistent ranking results generated by our model.
Message Clustering based Matrix Factorization Model for Retweeting Behavior Prediction
Authors: Bo Jiang, Jiguang Liang, Ying Sha, Lihong Wang
Venue: CIKM
Year: 2015

Retweeting is an important mechanism for information diffusion in social networks. Through retweeting, message is reshared from one user to another user, forming large cascades of message forwarding. Most existing researches of predicting retweeting utilize user social relationships for modeling which leads to vast calculating amount. In this paper, we propose two message clustering based matrix factorization models for retweeting prediction. Unlike previous approaches, our models exploit the clustering relationships of messages instead of social relationships. Our models are quite general because we do not need any auxiliary information except for message content. Several experiments on real datasets show that our models are effective and outperform the state-of-the-art methods.
Heterogeneous Multi-task Semantic Feature Learning for Classification
Authors: Xin Jin, Fuzhen Zhuang, Sinno Jialin Pan, Changying Du, Ping Luo, Qing He
Venue: CIKM
Year: 2015

Multi-task Learning (MTL) aims to learn multiple related tasks simultaneously instead of separately to improve generalization performance of each task. Most existing MTL methods assumed that the multiple tasks to be learned have the same feature representation. However, this assumption may not hold for many real-world applications. In this paper, we study the problem of MTL with heterogeneous features for each task. To address this problem, we first construct an integrated graph of a set of bipartite graphs to build a connection among different tasks. We then propose a multi-task nonnegative matrix factorization (MTNMF) method to learn a common semantic feature space underlying different heterogeneous feature spaces of each task. Finally, based on the common semantic features and original heterogeneous features, we model the heterogenous MTL problem as a multi-task multi-view learning (MTMVL) problem. In this way, a number of existing MTMVL methods can be applied to solve the problem effectively. Extensive experiments on three real-world problems demonstrate the effectiveness of our proposed method.
Efficient Sparse Matrix Multiplication on GPU for Large Social Network Analysis
Authors: Yong-Yeon Jo, Sang-Wook Kim, Duck-Ho Bae
Venue: CIKM
Year: 2015

As a number of social network services appear online recently, there have been many attempts to analyze social networks for extracting valuable information. Most existing methods first represent a social network as a quite sparse adjacency matrix, and then analyze it through matrix operations such as matrix multiplication. Due to the large scale and high complexity, efficient processing multiplications is an important issue in social network analysis. In this paper, we propose a GPU-based method for efficient sparse matrix multiplication through the parallel computing paradigm. The proposed method aims at balancing the amount of workload both at fine- and coarse-grained levels for maximizing the degree of parallelism in GPU. Through extensive experiments using synthetic and real-world datasets, we show that the proposed method outperforms previous methods by up to three orders-of-magnitude.
PIKM 2015: The 8th ACM Workshop for Ph.D. Students in Information and Knowledge Management
Authors: Mouna Kacimi, Nicoleta Preda, Maya Ramanath
Venue: CIKM
Year: 2015

The PIKM workshop offers Ph.D. students the opportunity to bring their work to an international and interdisciplinary research community, and create a network of young researchers to exchange and develop new and promising ideas. Similar to the CIKM, the PIKM workshop covers a wide range of topics in the areas of databases, information retrieval and knowledge management.
Scalable Clustering Algorithm via a Triangle Folding Processing for Complex Networks
Authors: Ying Kang, Xiaoyan Gu, Weiping Wang, Dan Meng
Venue: CIKM
Year: 2015

Facing up to the incessant growth of complex networks, more and more researchers start turning to a multilevel computing paradigm with high scalability for clustering. By virtue of iterative coarsening level by level, the clustering results which are obtained from the coarsest network and then projected to the original network, is superior to the ones from mining the original complex network explicitly. Empirical works reflect that the local-aggregation characteristic is a key point for multilevel clustering algorithms, thus techniques like modularity, label propagation etc. are used to discover the micro-clusters for coarsening. In this paper, we propose a scalable clustering algorithm via a triangle folding processing for complex networks(SCAFT). Based on the strong cluster property of triangle, we fold each traversed triangle of the network into a superverex to realize coarsening. And each generated coarsened network by iteration is capable of reserving the cluster structures of last level network, or even the intrinsic cluster structures of original complex network, improving the computational accuracy. What's more, a streaming algorithm is embedded in our novel approach to generate a serial input sequence of vertices, reducing the heavy burdens of memory usage of system. Experimental results on real-world complex networks show that, SCAFT outperforms the state-of-the-art multilevel clustering algorithms in terms of clustering accuracy, running time, especially in memory usage.
Cross-Modal Similarity Learning: A Low Rank Bilinear Formulation
Authors: Cuicui Kang, Shengcai Liao, Yonghao He, Jian Wang, Wenjia Niu, Shiming Xiang, Chunhong Pan
Venue: CIKM
Year: 2015

The cross-media retrieval problem has received much attention in recent years due to the rapid increasing of multimedia data on the Internet. A new approach to the problem has been raised which intends to match features of different modalities directly. In this research, there are two critical issues: how to get rid of the heterogeneity between different modalities and how to match the cross-modal features of different dimensions. Recently metric learning methods show a good capability in learning a distance metric to explore the relationship between data points. However, the traditional metric learning algorithms only focus on single-modal features, which suffer difficulties in addressing the cross-modal features of different dimensions. In this paper, we propose a cross-modal similarity learning algorithm for the cross-modal feature matching. The proposed method takes a bilinear formulation, and with the nuclear-norm penalization, it achieves low-rank representation. Accordingly, the accelerated proximal gradient algorithm is successfully imported to find the optimal solution with a fast convergence rate O(1/t2). Experiments on three well known image-text cross-media retrieval databases show that the proposed method achieves the best performance compared to the state-of-the-art algorithms.
Query Relaxation across Heterogeneous Data Sources
Authors: Verena Kantere, George Orfanoudakis, Anastasios Kementsietsidis, Timos K. Sellis
Venue: CIKM
Year: 2015

The fundamental assumption for query rewriting in heterogeneous environments is that the mappings used for the rewriting are complete, i.e., every relation and attribute mentioned in the query is associated, through mappings, to relations and attributes in the schema of the source that the query is rewritten. In reality, it is rarely the case that such complete sets of mappings exist between sources, and the presence of partial mappings is the norm rather than the exception. So, practically, existing query answering algorithms fail to generate any rewriting in the majority of cases. The question is then whether we can somehow relax queries that cannot be rewritten as such (due to insufficient mappings), and whether we can identify the interesting query relaxations, given the mappings at hand.
Top-k Reliable Edge Colors in Uncertain Graphs
Authors: Arijit Khan, Francesco Gullo, Thomas Wohler, Francesco Bonchi
Venue: CIKM
Year: 2015

We study the fundamental problem of finding the set of top-k edge colors that maximizes the reliability between a source node and a destination node in an uncertain and edge-colored graph. Our top-k reliable color set problem naturally arises in a variety of real-world applications including pathway finding in biological networks, topic-aware influence maximization, and team formation in social networks, among many others. In addition to the #P-completeness of the classical reliability finding problem between a source and a destination node over an uncertain graph, we prove that our problem is also NP-hard, and neither sub-modular, nor super-modular. To this end, we aim at designing effective and scalable solutions for the top-k reliable color set problem. We first introduce two baselines following the idea of repetitive inclusion of the next best edge colors, and we later develop a more efficient and effective algorithm that directly finds the highly-reliable paths while maintaining the budget on the number of edge-colors. An extensive empirical evaluation on various large-scale and real-world graph datasets illustrates that our proposed techniques are both scalable and highly accurate.
Generalized Team Draft Interleaving
Authors: Eugene Kharitonov, Craig Macdonald, Pavel Serdyukov, Iadh Ounis
Venue: CIKM
Year: 2015

Interleaving is an online evaluation method that compares two ranking functions by mixing their results and interpreting the users' click feedback. An important property of an interleaving method is its sensitivity, i.e. the ability to obtain reliable comparison outcomes with few user interactions. Several methods have been proposed so far to improve interleaving sensitivity, which can be roughly divided into two areas: (a) methods that optimize the credit assignment function (how the click feedback is interpreted), and (b) methods that achieve higher sensitivity by controlling the interleaving policy (how often a particular interleaved result page is shown).
External Knowledge and Query Strategies in Active Learning: a Study in Clinical Information Extraction
Authors: Mahnoosh Kholghi, Laurianne Sitbon, Guido Zuccon, Anthony N. Nguyen
Venue: CIKM
Year: 2015

This paper presents a new active learning query strategy for information extraction, called Domain Knowledge Informativeness (DKI). Active learning is often used to reduce the amount of annotation effort required to obtain training data for machine learning algorithms. A key component of an active learning approach is the query strategy, which is used to iteratively select samples for annotation. Knowledge resources have been used in information extraction as a means to derive additional features for sample representation. DKI is, however, the first query strategy that exploits such resources to inform sample selection. To evaluate the merits of DKI, in particular with respect to the reduction in annotation effort that the new query strategy allows to achieve, we conduct a comprehensive empirical comparison of active learning query strategies for information extraction within the clinical domain. The clinical domain was chosen for this work because of the availability of extensive structured knowledge resources which have often been exploited for feature generation. In addition, the clinical domain offers a compelling use case for active learning because of the necessary high costs and hurdles associated with obtaining annotations in this domain. Our experimental findings demonstrated that (1) amongst existing query strategies, the ones based on the classification model's confidence are a better choice for clinical data as they perform equally well with a much lighter computational load, and (2) significant reductions in annotation effort are achievable by exploiting knowledge resources within active learning query strategies, with up to 14% less tokens and concepts to manually annotate than with state-of-the-art query strategies.
Building Effective Query Classifiers: A Case Study in Self-harm Intent Detection
Authors: Ashiqur R. KhudaBukhsh, Paul N. Bennett, Ryen W. White
Venue: CIKM
Year: 2015

Query-based triggers play a crucial role in modern search systems, e.g., in deciding when to display direct answers on result pages. We address a common scenario in designing such triggers for real-world settings where positives are rare and search providers possess only a small seed set of positive examples to learn query classification models. We choose the critical domain of self-harm intent detection to demonstrate how such small seed sets can be expanded to create meaningful training data with a sizable fraction of positive examples. Our results show that with our method, substantially more positive queries can be found compared to plain random sampling. Additionally, we explored the effectiveness of traditional active learning approaches on classification performance and found that maximum uncertainty performs the best among several other techniques that we considered.
Behavioral Dynamics from the SERP's Perspective: What are Failed SERPs and How to Fix Them?
Authors: Julia Kiseleva, Jaap Kamps, Vadim Nikulin, Nikita Makarov
Venue: CIKM
Year: 2015

Web search is always in a state of flux: queries, their intent, and the most relevant content are changing over time, in predictable and unpredictable ways. Modern search technology has made great strides in keeping up to pace with these changes, but there remain cases of failure where the organic search results on the search engine result page (SERP) are outdated, and no relevant result is displayed. Failing SERPs due to temporal drift are one of the greatest frustrations of web searchers, leading to search abandonment or even search engine switch. Detecting failed SERPs timely and providing access to the desired out-of-SERP results has huge potential to improve user satisfaction. Our main findings are threefold: First, we refine the conceptual model of behavioral dynamics on the web by including the SERP and defining (un)successful SERPs in terms of observable behavior. Second, we analyse typical patterns of temporal change and propose models to predict query drift beyond the current SERP, and ways to adapt the SERP to include the desired results. Third, we conduct extensive experiments on real world search engine traffic demonstrating the viability of our approach. Our analysis of behavioral dynamics at the SERP level gives new insight in one of the primary causes of search failure due to temporal query intent drifts. Our overall conclusion is that the most detrimental cases in terms of (lack of) user satisfaction lead to the largest changes in information seeking behavior, and hence to observable changes in behavior we can exploit to detect failure, and moreover not only detect them but also resolve them.
Querying Temporal Drifts at Multiple Granularities
Authors: Sofia Kleisarchaki, Sihem Amer-Yahia, Ahlame Douzal Chouakria, Vassilis Christophides
Venue: CIKM
Year: 2015

There exists a large body of work on online drift detection with the goal of dynamically finding and maintaining changes in data streams. In this paper, we adopt a query-based approach to drift detection. Our approach relies on a drift index, a structure that captures drift at different time granularities and enables flexible drift queries. We formalize different drift queries that represent real-world scenarios and develop query evaluation algorithms that use different materializations of the drift index as well as strategies for online index maintenance. We describe a thorough study of the performance of our algorithms on real-world and synthetic datasets with varying change rates.
Probabilistic Non-negative Inconsistent-resolution Matrices Factorization
Authors: Masahiro Kohjima, Tatsushi Matsubayashi, Hiroshi Sawada
Venue: CIKM
Year: 2015

In this paper, we tackle with the problem of analyzing datasets with different resolution such as a pair of user's individual data and user group's data, for example "userA visited shopA 5 times" and "users whose attributes are men purchased itemA 80 times in total". In order to establish a basic approach to this problem, we focus on the simplified scenario and propose a new probabilistic model called probabilistic non-negative inconsistent-resolution matrices factorization (pNimf). pNimf is rigorously derived from the data generative process using latent high-resolution data which underlie low-resolution data. We conduct experiments on real purchase log data and confirm that the proposed model provides superior performance, and that the performance improves as the number of low-resolution data increases. These results imply that our way of modeling using latent high-resolution data can become the basic approach to the problem of analyzing dataset with different resolution.