OpenRaiser/Intern-Atlas huggingface dataset:
Efficient term proximity search with term-pair indexes
Authors: Hao Yan, Shuming Shi, Fan Zhang, Torsten Suel, Ji-Rong Wen
Venue: CIKM
Year: 2010

There has been a large amount of research on early termination techniques in web search and information retrieval. Such techniques return the top-k documents without scanning and evaluating the full inverted lists of the query terms. Thus, they can greatly improve query processing efficiency. However, only a limited amount of efficient top-k processing work considers the impact of term proximity, i.e., the distance between term occurrences in a document, which has recently been integrated into a number of retrieval models to improve effectiveness.
Online learning for multi-task feature selection
Authors: Haiqin Yang, Irwin King, Michael R. Lyu
Venue: CIKM
Year: 2010

Multi-task feature selection (MTFS) is an important tool to learn the explanatory features across multiple related tasks. Previous MTFS methods fulfill this task in batch-mode training. This makes them inefficient when data come in sequence or when the number of training data is so large that they cannot be loaded into the memory simultaneously. To tackle these problems, we propose the first online learning framework for MTFS. A main advantage of the online algorithms is the efficiency in both time complexity and memory cost due to the closed-form solutions in updating the model weights at each iteration. Experimental results on a real-world dataset attest to the merits of the proposed algorithms.
Language pyramid and multi-scale text analysis
Authors: Shuang-Hong Yang, Hongyuan Zha
Venue: CIKM
Year: 2010

The classical Bag-of-Word (BOW) model represents a document as a histogram of word occurrence, losing the spatial information that is invaluable for many text analysis tasks. In this paper, we present the Language Pyramid (LaP) model, which casts a document as a probabilistic distribution over the joint semantic-spatial space and motivates a multi-scale 2D local smoothing framework for nonparametric text coding. LaP efficiently encodes both semantic and spatial contents of a document into a pyramid of matrices that are smoothed both semantically and spatially at a sequence of resolutions, providing a convenient multi-scale imagic view for natural language understanding. The LaP representation can be used in text analysis in a variety of ways, among which we investigate two instantiations in the current paper: (1) multi-scale text kernels for document categorization, and (2) multi-scale language models for ad hoc text retrieval. Experimental results illustrate that: for classification, LaP outperforms BOW by (up to) 4% on moderate-length texts (RCV1 text benchmark) and 15% on short texts (Yahoo! queries); and for retrieval, LaP gains 12% MAP improvement over uni-gram language models on the OHSUMED data set.
On top-k social web search
Authors: Peifeng Yin, Wang-Chien Lee, Ken C. K. Lee
Venue: CIKM
Year: 2010

To enhance the quality of document search, recent research studies have started to exploit the social networks of users by considering social influence (SI), measurement of the affinity between a query user and the publisher of a retrieved document, in addition to the commonly used textual relevance (TR). We refer to such document search that considers social networks as social web search. In this paper, we focus on efficient top-k social web search and propose two search strategies: (i) TR-based search and (ii) SI-based search that tailor document examination orders upon TR and SI, respectively. We evaluate the proposed strategies through experimentation.
RankSVR: can preference data help regression?
Authors: Hwanjo Yu, Sungchul Kim, Seung-Hoon Na
Venue: CIKM
Year: 2010

In some regression applications (e.g., an automatic movie scoring system), a large number of ranking data is available in addition to the original regression data. This paper studies whether and how the ranking data can improve the accuracy of regression task. In particular, this paper first proposes an extension of SVR (Support Vector Regression), RankSVR, which incorporates ranking constraints in the learning of regression function. Second, this paper proposes novel sampling methods for RankSVR, which selectively choose samples of ranking data for training of regression functions in order to maximize the performance of RankSVR. While it is relatively easier to acquire ranking data than regression data, incorporating all the ranking data in the learning of regression doest not always generate the best output. Moreoever, adding too many ranking constraints into the regression problem substantially lengthens the training time. Our proposed sampling methods find the ranking samples that maximize the regression performance. Experimental results on synthetic and real data sets show that, when the ranking data is additionally available, RankSVR significantly performs better than SVR by utilizing ranking constraints in the learning of regression, and also show that our sampling methods improve the RankSVR performance better than the random sampling.
Web search solved?: all result rankings the same?
Authors: Hugo Zaragoza, Berkant Barla Cambazoglu, Ricardo Baeza-Yates
Venue: CIKM
Year: 2010

The objective of this work is to derive quantitative statements about what fraction of web search queries issued to the state-of-the-art commercial search engines lead to excellent results or, on the contrary, poor results. To be able to make such statements in an automated way, we propose a new measure that is based on lower and upper bound analysis over the standard relevance measures. Moreover, we extend this measure to carry out comparisons between competing search engines by introducing the concept of disruptive sets, which we use to estimate the degree to which a search engine solves queries that are not solved by its competitors. We report empirical results on a large editorial evaluation of the three largest search engines in the US market.
CasJoin: a cascade chain for text similarity joins
Authors: Xiaoxun Zhang, Zhili Guo, Honglei Guo, Huijia Zhu, Zhong Su
Venue: CIKM
Year: 2010

We are concerned with the problem of similarity joins of text data, where the task is to find all pairs of documents above an expected similarity. Such a problem often serves as an indispensable step in many web applications. A crucial issue is to preclude unnecessary candidate pairs as many as possible ahead of expensive similarity evaluation. In this paper, we initiate an idea of adopting a cascade structure in text joins for a large speedup, where a latter stage can exclude a considerable number of invalid pairs survived in former stages. The proposed algorithm is shortly referred to as CasJoin. We further adopt a prefix filter to build the stage of CasJoin by introducing a novel vision to the dynamic generation of document vector. Specifically, a vector is partitioned into a chain of multiple prefixes that are appended one by one for cascade joining. We evaluate our CasJoin on a typical web corpus, ODP. Experiments indicate that, comparing to the state-of-the-art prefix algorithms, CasJoin can achieve a drastic reduction of candidates by as much as 98.15% and a dramatic speedup of joining by up to 13.34x.
SUMMA: subgraph matching in massive graphs
Authors: Shijie Zhang, Shirong Li, Jiong Yang
Venue: CIKM
Year: 2010

Graphs can represent a large number of data types, e.g., online social networks, internet links, procedure dependency graphs, etc. The need for indexing massive graphs is an urgent research problem of great practical importance. The main challenge is the size. Each graph may contain at least tens of millions vertices. The working memory may not be able to store the database graph due to its large size, which increases the processing time significantly.
Formal approach and automated tool for constructing ontology from object-oriented database model
Authors: Fu Zhang, Zong Min Ma, Xing Wang, Yu Wang
Venue: CIKM
Year: 2010

Extracting domain knowledge from databases can facilitate the development of Web ontologies. In this paper, a formal approach and an automated tool for constructing ontologies from Object-oriented database models (OODMs) are developed. The approach and tool can automatically translate an OODM and its corresponding database instances into the ontology structure and ontology instances, respectively. Case studies show that the approach is feasible and the automated construction tool is efficient.
PTM: probabilistic topic mapping model for mining parallel document collections
Authors: Duo Zhang, Jimeng Sun, ChengXiang Zhai, Abhijit Bose, Nikos Anerousis
Venue: CIKM
Year: 2010

Many applications generate a large volume of parallel document collections. A parallel document collection consists of two sets of documents where the documents in each set correspond to each other and form semantic pairs (e.g., pairs of problem and solution descriptions in a help-desk setting). Although much work has been done on text mining, little previous work has attempted to mine such a novel kind of text data. In this paper, we propose a new probabilistic topic model, called Probabilistic Topic Mapping (PTM) model, to mine parallel document collections to simultaneously discover latent topics in both sets of documents as well as the mapping of topics in one set to those in the other. We evaluate the PTM model on one real parallel document collection in IT service domain. We show that PTM can effectively discover meaningful topics, as well as their mappings, and it's also useful for improving text matching and retrieval when there's a vocabulary gap.
Learning click models via probit bayesian inference
Authors: Yuchen Zhang, Dong Wang, Gang Wang, Weizhu Chen, Zhihua Zhang, Botao Amber Hu, Li Zhang
Venue: CIKM
Year: 2010

Recent advances in click models have positioned them as an effective approach to the improvement of interpreting click data, and some typical works include UBM, DBN, CCM, etc. After formulating the knowledge of user search behavior into a set of model assumptions, each click model developed an inference method to estimate its parameters. The inference method plays a critical role in terms of accuracy in interpreting clicks, and we observe that different inference methods for a click model can lead to significant accuracy differences. In this paper, we propose a novel Bayesian inference approach for click models. This approach regards click model under a unified framework, which has the following characteristics and advantages:
Discriminative factored prior models for personalized content-based recommendation
Authors: Lanbo Zhang, Yi Zhang
Venue: CIKM
Year: 2010

Most existing content-based filtering approaches including Rocchio, Language Models, SVM, Logistic Regression, Neural Networks, etc. learn user profiles independently without capturing the similarity among users. The Bayesian hierarchical models learn user profiles jointly and have the advantage of being able to borrow information from other users through a Bayesian prior. The standard Bayesian hierarchical model assumes all user profiles are generated from the same prior. However, considering the diversity of user interests, this assumption might not be optimal. Besides, most existing content-based filtering approaches implicitly assume that each user profile corresponds to exactly one user interest and fail to capture a user's multiple interests (information needs).
SKIF: a data imputation framework for concept drifting data streams
Authors: Peng Zhang, Xingquan Zhu, Jianlong Tan, Li Guo
Venue: CIKM
Year: 2010

Missing data commonly occurs in many applications. While many data imputation methods exist to handle the missing data problem for large scale databases, when applied to concept drifting data streams, these methods face some common difficulties. First, due to large and continuous data volumes, we are unable to maintain all stream records to form a candidate pool and estimate missing values, as most existing methods commonly do. Second, even if we could maintain all complete stream records using a summary structure, the concept drifting problem would make some information obsolete, and thus deteriorate the imputation accuracy. Third, in data streams, it is necessary to develop a fast yet accurate algorithm to find the most similar data for imputation. Fourth, due to the dynamic and sophisticated data collection environments, the missing rate of most stream data may be much higher than that in generic static databases, so the imputation method should be able to accommodate high missing rate in the data. To tackle these challenges, we propose, in this paper, a Streaming k-Nearest-Neighbors Imputation Framework (SKIF) for concept drifting data streams. To handle concept drifting and large volume problems in data streams, SKIF first summarizes historical complete records in some micro-resources (which are high-level statistical data structures), and maintains these micro-resources in a candidate pool as benchmark data. After that, SKIF employs a novel hybrid-kNN imputation procedure, which uses a hybrid similarity search mechanism, to find the most similar micro-resources from the large scale candidate pool efficiently. Experimental results demonstrate the effectiveness of the proposed SKIF framework for data stream imputation tasks.
On wavelet decomposition of uncertain time series data sets
Authors: Yuchen Zhao, Charu C. Aggarwal, Philip S. Yu
Venue: CIKM
Year: 2010

In this paper, we will explore the construction of wavelet decompositions of uncertain data. Uncertain representations of data sets require significantly more space, and it is therefore even more important to construct compressed representations for such cases. We will use a hierarchical optimization technique in order to construct the most effective partitioning for our wavelet representation. We explore two different schemes which optimize the uncertainty in the resulting representation. We will show that the incorporation of uncertainty into the design of the wavelet representations significantly improves the compression rate of the representation. We present experimental results illustrating the effectiveness of our approach.
Learning a user-thread alignment manifold for thread recommendation in online forum
Authors: Jun Zhao, Jiajun Bu, Chun Chen, Ziyu Guan, Can Wang, Cheng Zhang
Venue: CIKM
Year: 2010

People are more and more willing to participate in online forums to share their knowledge and experience. However, it may not be easy for them to find their desired threads in online forums due to the information overload problem. Traditional recommendation approaches can not be directly applied to online forums due to two reasons. First, unlike traditional movie or music recommendation problem, there is no rating information in online forums. Second, the sparsity problem is more severe since the users may only read threads but take no actions. To address these limitations, in this paper we propose to make use of the reply relationships among users, as well as thread contents. A learning algorithm is introduced to infer a user-thread alignment manifold in which both users and thread contents can be well represented. Thus, the relatedness between users and threads can be measured on this alignment manifold, and the closest threads which can best meet the corresponding user's information needs are recommended. Experiments on a dataset crawled from digg.com have demonstrated the superiority of our algorithm over traditional recommendation algorithms.
Context modeling for ranking and tagging bursty features in text streams
Authors: Wayne Xin Zhao, Jing Jiang, Jing He, Dongdong Shan, Hongfei Yan, Xiaoming Li
Venue: CIKM
Year: 2010

Bursty features in text streams are very useful in many text mining applications. Most existing studies detect bursty features based purely on term frequency changes without taking into account the semantic contexts of terms, and as a result the detected bursty features may not always be interesting or easy to interpret. In this paper we propose to model the contexts of bursty features using a language modeling approach. We then propose a novel topic diversity-based metric using the context models to find newsworthy bursty features. We also propose to use the context models to automatically assign meaningful tags to bursty features. Using a large corpus of a stream of news articles, we quantitatively show that the proposed context language models for bursty features can effectively help rank bursty features based on their newsworthiness and to assign meaningful tags to annotate bursty features.
A topical link model for community discovery in textual interaction graph
Authors: Guoqing Zheng, Jinwen Guo, Lichun Yang, Shengliang Xu, Shenghua Bao, Zhong Su, Dingyi Han, Yong Yu
Venue: CIKM
Year: 2010

This paper is concerned with community discovery in textual interaction graph, where the links between entities are indicated by textual documents. Specifically, we propose a Topical Link Model(TLM), which leverages Hierarchical Dirichlet Process(HDP) to introduce hidden topical variable of the links. Other than the use of links, TLM can look into the documents on the links in detail to recover sound communities. Moreover, TLM is a nonparametric model, which is able to learn the number of communities from the data. Extensive experiments on two real world corpora show TLM outperforms two state-of-the-art baseline models, which verify the effectiveness of TLM in determining the proper number of communities and generating sound communities.
Rough sets based reasoning and pattern mining for a two-stage information filtering system
Authors: Xujuan Zhou, Yuefeng Li, Peter Bruza, Yue Xu, Raymond Y. K. Lau
Venue: CIKM
Year: 2010

This paper presents a novel two-stage information filtering model which combines the merits of term-based and pattern- based approaches to effectively filter sheer volume of infor- mation. In particular, the first filtering stage is supported by a novel rough analysis model which efficiently removes a large number of irrelevant documents, thereby addressing the overload problem. The second filtering stage is empow- ered by a semantically rich pattern taxonomy mining model which effectively fetches incoming documents according to the specific information needs of a user, thereby addressing the mismatch problem. The experiments have been conducted to compare the proposed two-stage filtering (T-SM) model with other possible "term-based + pattern-based" or "term-based + term-based" IF models. The results based on the RCV1 corpus show that the T-SM model significantly outperforms other types of "two-stage" IF models.
A late fusion approach to cross-lingual document re-ranking
Authors: Dong Zhou, Séamus Lawless, Jinming Min, Vincent Wade
Venue: CIKM
Year: 2010

The field of information retrieval still strives to develop models which allow semantic information to be integrated in the ranking process to improve performance in comparison to standard bag-of-words based models. Cross-lingual information retrieval is an example of where such a model is required, as content or concepts often need to be matched across languages. To overcome this problem, a conceptual model has been adopted in ranking an entire corpus which normally exploits latent/implicit features of the text. One of the drawbacks of this model is that the computational cost is significant and often intractable in modern test collections. Therefore, approaches utilizing concept-based models for re-ranking initial retrieval results have attracted a considerable amount of study, in particular the latent concept model. However, fitting such a model to a smaller collection is less meaningful than fitting it into the whole corpus. This paper proposes a late fusion method which incorporates scores generated by using external knowledge to enhance the space produced by the latent concept method. This method is further demonstrated to be suitable for multilingual re-ranking purposes. To illustrate the effectiveness of the proposed method, experiments were conducted over test collections across three languages. The results demonstrate that the method can comfortably achieve improvements in retrieval performance over several re-ranking methods.
Transfer incremental learning for pattern classification
Authors: Zhenfeng Zhu, Xingquan Zhu, Yue-Fei Guo, Xiangyang Xue
Venue: CIKM
Year: 2010

Traditional machine learning methods, such as Support Vector Machines (SVMs), usually assume that training and test data share the same distributions. Due to the inherent dynamic data nature, it is often observed that (1) the volumes of the training data may gradually grow; and (2) the existing and the newly arrived samples may be subject to different distributions or learning tasks. In this paper, we propose a Transfer Incremental Support Vector Machine(TrISVM), with the objective of tackling changes in data volumes and learning tasks at the same time. By using new updating rules to calculate the inverse matrix, TrISVM solves the existing incremental learning problem more efficiently, especially for high dimensional data. Furthermore, when using new samples to update the existing models, TrISVM employs sample-based weight adjustment procedures to ensure that the concept transferring between auxiliary and target samples can be leveraged to fulfill the transfer learning goal. Experimental results on real-world data sets demonstrate that TrISVM achieves better efficiency and prediction accuracy than both incremental-learning and transfer-learning based methods. In addition, the results also show that TrISVM is able to achieve bidirectional knowledge transfer between two similar tasks.
Estimating selectivity for joined RDF triple patterns
Authors: Hai Huang, Chengfei Liu
Venue: CIKM
Year: 2011

A fundamental problem related to RDF query processing is selectivity estimation, which is crucial to query optimization for determining a join order of RDF triple patterns. In this paper we focus research on selectivity estimation for SPARQL graph patterns. The previous work takes the join uniformity assumption when estimating the joined triple patterns. This assumption would lead to highly inaccurate estimations in the cases where properties in SPARQL graph patterns are correlated. We take into account the dependencies among properties in SPARQL graph patterns and propose a more accurate estimation model. Since star and chain query patterns are common in SPARQL graph patterns, we first focus on these two basic patterns and propose to use Bayesian network and chain histogram respectively for estimating the selectivity of them. Then, for estimating the selectivity of an arbitrary SPARQL graph pattern, we design algorithms for maximally using the precomputed statistics of the star paths and chain paths. The experiments show that our method outperforms existing approaches in accuracy.
DESIRE 2011: first international workshop on data infrastructures for supporting information retrieval evaluation
Authors: Maristella Agosti, Nicola Ferro, Costantino Thanos
Venue: CIKM
Year: 2011

The workshop focuses on the three areas of interest to CIKM to discuss how to envisage and design evaluation infrastructures able to store, manage, and make accessible the scientific data and knowledge of interest for advancing the evaluation of information retrieval and access tools.