OpenRaiser/Intern-Atlas huggingface dataset:
Automatic image annotation using tag-related random search over visual neighbors
Authors: Zijia Lin, Guiguang Ding, Mingqing Hu, Jianmin Wang, Jiaguang Sun
Venue: CIKM
Year: 2012

In this paper, we propose a novel image auto-annotation model using tag-related random search over range-constrained visual neighbors of the to-be-annotated image. The proposed model, termed as TagSearcher, observes that the annotating performances of many previous visual-neighbor-based models are generally sensitive to the quantity setting of visual neighbors, and the probabilities for visual neighbors to be selected is better to be tag-dependent, meaning that each candidate tag can have its own trustworthy part of visual neighbors for score prediction. And thus TagSearcher uses a constrained range rather than an identical and fixed number of visual neighbors for auto-annotation. By performing a novel tag-related random search process over the graphical model made up of range-constrained visual neighbors, TagSearcher can find the trustworthy part for each candidate tag, and further utilize both visual similarities and tag correlations for score prediction. With the range constraint for visual neighbors and the tag-related random search process, TagSearcher can not only achieve satisfactory annotating performances, but also reduce the performance sensitivity. Experiments conducted on benchmark Corel5k well demonstrate its rationality and effectiveness.
TASE: a time-aware search engine
Authors: Sheng Lin, Peiquan Jin, Xujian Zhao, Lihua Yue
Venue: CIKM
Year: 2012

Most Web pages contain temporal information, which can be utilized by search engines to improve searching performance for users. However, traditional search engines have little support in processing temporal-textual Web queries. Aiming at solving this problem, in this paper we present and implement a prototype system for time-sensitive queries, which is called TASE (Time-Aware Search Engine). TASE extracts both the explicit and implicit temporal expressions for each Web page, and calculates the relevant score between the Web page and each temporal expression, and then re-rank search results based on the temporal-textual relevance between Web pages and the queries. It is demonstrated that TASE can improve the effectiveness of temporal-textual Web queries.
Effective and efficient?: bilingual sentiment lexicon extraction using collocation alignment
Authors: Zheng Lin, Songbo Tan, Xueqi Cheng, Xueke Xu, Weisong Shi
Venue: CIKM
Year: 2012

Bilingual sentiment lexicon is fundamental resource for cross-language sentiment analysis but its compilation remains a major bottleneck in computational linguistics. Traditional word alignment algorithm faces with the status of large alignment space, which may introduce redundant computations as well as alignment errors. In this paper, we use collocation alignment to extract bilingual sentiment lexicon overcoming the drawbacks of word alignment. The idea of collocation alignment is inspired by the strong cohesion between feature words and opinion words in sentiment corpus. Experimental results show that our approach not only decreases the computing time dramatically but also improves the precision of extracted bilingual word pairs due to the smaller alignment space.
Efficient algorithms for generalized subgraph query processing
Authors: Wenqing Lin, Xiaokui Xiao, James Cheng, Sourav S. Bhowmick
Venue: CIKM
Year: 2012

We study a new type of graph queries, which injectively maps its edges to paths of the graphs in a given database, where the length of each path is constrained by a given threshold specified by the weight of the corresponding matching edge. We give important applications of the new graph query and identify new challenges of processing such a query. Then, we devise the cost model of the branch-and-bound algorithm framework for processing the graph query, and propose an efficient algorithm to minimize the cost overhead. We also develop three indexing techniques to efficiently answer the queries online. Finally, we verify the efficiency of our proposed indexes with extensive experiments on large real and synthetic datasets.
PRemiSE: personalized news recommendation via implicit social experts
Authors: Chen Lin, Runquan Xie, Lei Li, Zhenhua Huang, Tao Li
Venue: CIKM
Year: 2012

A variety of news recommender systems based on different strategies have been proposed to provide news personalization services for online news readers. However, little research work has been reported on utilizing the implicit "social" factors (i.e., the potential influential experts in news reading community) among news readers to facilitate news personalization. In this paper, we investigate the feasibility of integrating content-based methods, collaborative filtering and information diffusion models by employing probabilistic matrix factorization techniques. We propose PRemiSE, a novel Personalized news Recommendation framework via implicit Social Experts, in which the opinions of potential influencers on virtual social networks extracted from implicit feedbacks are treated as auxiliary resources for recommendation. Empirical results demonstrate the efficacy and effectiveness of our method, particularly, on handling the so-called cold-start problem.
Utilizing common substructures to speedup tensor factorization for mining dynamic graphs
Authors: Wei Liu, Jeffrey Chan, James Bailey, Christopher Leckie, Kotagiri Ramamohanarao
Venue: CIKM
Year: 2012

In large and complex graphs of social, chemical/biological, or other relations, frequent substructures are commonly shared by different graphs or by graphs evolving through different time periods. Tensors are natural representations of these complex time-evolving graph data. A factorization of a tensor provides a high-quality low-rank compact basis for each dimension of the tensor, which facilitates the interpretation of frequent substructures of the original graphs. However, the high computational cost of tensor factorization makes it infeasible for conventional tensor factorization methods to handle large graphs that evolve frequently with time. To address this problem, in this paper we propose a novel iterative tensor factorization (ITF) method whose time complexity is linear in the cardinalities of all dimensions of a tensor. This low time complexity means that when using tensors to represent dynamic graphs, the computational cost of ITF is linear in the size (number of edges/vertices) of graphs and is also linear in the number of time periods over which the graph evolves. More importantly, an error estimation of ITF suggests that its factorization correctness is comparable to that of the standard factorization method. We empirically evaluate our method on publication networks and chemical compound graphs, and demonstrate that ITF is an order of magnitude faster than the conventional method and at the same time preserves factorization quality. To the best of our knowledge, this research is the first work that uses important frequent substructures to speed up tensor factorizations for mining dynamic graphs.
Entity centric query expansion for enterprise search
Authors: Xitong Liu, Hui Fang, Fei Chen, Min Wang
Venue: CIKM
Year: 2012

Enterprise search is important, and the search quality has a direct impact on the productivity of an enterprise. Many information needs of enterprise search center around entities. Intuitively, information related to the entities mentioned in the query, such as related entities, would be useful to reformulate the query and improve the retrieval performance. However, most existing studies on query expansion are term-centric. In this paper, we propose a novel entity-centric query expansion framework for enterprise search. Specifically, given a query containing entities, we first utilize both unstructured and structured information to find entities that are related to the ones in the query. We then discuss how to adapt existing feedback methods to use the related entities to improve search quality. Experiment results show that the proposed entity-centric query expansion strategy is more effective to improve the search performance than the state-of-the-art pseudo feedback methods on longer, natural language-like queries with entities.
Exploring and predicting search task difficulty
Authors: Jingjing Liu, Chang Liu, Michael J. Cole, Nicholas J. Belkin, Xiangmin Zhang
Venue: CIKM
Year: 2012

We report on an investigation of behavioral differences between users in difficult and easy search tasks. Behavioral factors that can be used in real-time to predict task difficulty are identified. User data was collected in a controlled lab experiment (n=38) where each participant completed four search tasks in the genomics domain. We looked at user behaviors that can be obtained by systems at three levels, distinguished by the time point when the measurements can be done. They are: 1) first-round level at the beginning of the search, 2) accumulated level during the search, and 3) whole-session level by the end of the search. Results show that a number of user behaviors at all three levels differed between easy and difficult tasks. Models predicting task difficulty at all three levels were developed and evaluated. A real-time model incorporating first-round and accumulated levels of behaviors (FA) had fairly good prediction performance (accuracy 83%; precision 88%), which is comparable with the model using the whole-session level behaviors which are not real-time (accuracy 75%; precision 92%). We also found that for efficiency purpose, using only a limited number of significant variables (FC_FA) can obtain a prediction accuracy of 75%, with a precision of 88%. Our findings can help search systems predict task difficulty and adapt search results to users.
Star-Join: spatio-textual similarity join
Authors: Sitong Liu, Guoliang Li, Jianhua Feng
Venue: CIKM
Year: 2012

Location-based services have attracted significant attention due to modern mobile phones equipped with GPS devices. These services generate large amounts of spatio-textual data which contain both spatial location and textual descriptions. Since a spatio-textual object may have different representations, possibly because of deviations of GPS or different user descriptions, it calls for efficient methods to integrate spatio-textual data from different sources. In this paper we study a new research problem called spatio-textual similarity join: given two sets of spatio-textual objects, we find the similar object pairs. To the best of our knowledge, we are the first to study this problem. We make the following contributions: (1) We develop a filter-and-refine framework and devise several efficient algorithms. We first generate spatial and textual signatures for the objects and build inverted index on top of these signatures. Then we generate candidate pairs using the inverted lists of signatures. Finally we refine the candidates and generate the final result. (2) We study how to generate high-quality signatures for spatial information. We develop an MBR-prefix based signature to prune large numbers of dissimilar object pairs. (3) Experimental results on real and synthetic datasets show that our algorithms achieve high performance and scale well.
Mining high utility itemsets without candidate generation
Authors: Mengchi Liu, Jun-Feng Qu
Venue: CIKM
Year: 2012

High utility itemsets refer to the sets of items with high utility like profit in a database, and efficient mining of high utility itemsets plays a crucial role in many real-life applications and is an important research issue in data mining area. To identify high utility itemsets, most existing algorithms first generate candidate itemsets by overestimating their utilities, and subsequently compute the exact utilities of these candidates. These algorithms incur the problem that a very large number of candidates are generated, but most of the candidates are found out to be not high utility after their exact utilities are computed. In this paper, we propose an algorithm, called HUI-Miner (High Utility Itemset Miner), for high utility itemset mining. HUI-Miner uses a novel structure, called utility-list, to store both the utility information about an itemset and the heuristic information for pruning the search space of HUI-Miner. By avoiding the costly generation and utility computation of numerous candidate itemsets, HUI-Miner can efficiently mine high utility itemsets from the utility-lists constructed from a mined database. We compared HUI-Miner with the state-of-the-art algorithms on various databases, and experimental results show that HUI-Miner outperforms these algorithms in terms of both running time and memory consumption.
An unsupervised method for author extraction from web pages containing user-generated content
Authors: Jing Liu, Xinying Song, Jingtian Jiang, Chin-Yew Lin
Venue: CIKM
Year: 2012

In this paper, we address the problem of author extraction (AE) from user generated content (UGC) pages. Most existing solutions for web information extraction, including AE, adopt supervised approaches, which require expensive manual annotation. We propose a novel unsupervised approach for automatically collecting and labeling training data based on two key observations of author names: (1) people tend to use a single name across sites if their preferred names are available; (2) people tend to create unique usernames to easily distinguish themselves from others, e.g. travelbug61. Our AE solution only requires features extracted from a single UGC page instead of relying on clues from multiple UGC pages. We conducted extensive experiments. (1) The evaluation of automatically labeled author field data shows 95.0% precision. (2) Our method achieves an F1 score of 96.1%, which significantly outperforms a state-of-the-art supervised approach with single page features (F1 score: 68.4%) and has a comparable performance to its multiple page solution (F1 score: 95.4%). (3) We also examine the robustness of our approach on various UGC pages from forums and review sites, and achieve promising results as well.
On the connections between explicit semantic analysis and latent semantic analysis
Authors: Chao Liu, Yi-Min Wang
Venue: CIKM
Year: 2012

Semantic analysis tries to solve problems arising from polysemy and synonymy that are abundant in natural languages. Recently, Gabrilovich and Markovitch propose the Explicit Semantic Analysis (ESA) technique, which complements the well-known Latent Semantic Analysis (LSA) technique. In this paper, we show that the two techniques are not as distinct as their names suggest; instead, we find that ESA is equivalent to a LSA variant, and this equivalence generalizes to all kernel methods using kernels arising from the canonical dot product. Effectively, this result guarantees that ESA would not outperform the peak efficacy of LSA for any applications using the above kernel methods. In short, this paper for the first time establishes the connections between ESA and LSA, quantifies their relative efficacy, and generalizes the result to a big category of kernel methods.
Modeling UIMA type system using web ontology language: towards interoperability among UIMA-based NLP tools
Authors: Hongfang Liu, Stephen T. Wu, Cui Tao, Christopher G. Chute
Venue: CIKM
Year: 2012

With the recent development and adoption of NLP framework architectures, NLP modules/tools developed independently in the research community can be adopted as integrated applications. Development of wrappers and interfaces required to adopt NLP modules/tools, however, still requires huge amount of efforts. In this paper, we focus on one NLP framework architecture, UIMA (Unstructured Information Management Architecture), which defines annotations as types described in a type system and can achieve direct interoperability if a common type system is used. We explore the use of ontology to model UIMA types and argue existing ontology development or reasoning tools can be utilized to understand types (we use types and annotations interchangeably) from existing NLP systems developed under UIMA, define equivalent annotations in different NLP systems, and apply the practice in the ontology community to draw agreements on the definition of common NLP types, thereby achieving better interoperability among NLP modules/tools.
Full-text citation analysis: enhancing bibliometric and scientific publication ranking
Authors: Xiaozhong Liu, Jinsong Zhang, Chun Guo
Venue: CIKM
Year: 2012

The goal of this paper is to use innovative text and graph mining algorithms along with full-text citation analysis and topic modeling to enhance classical bibliometric analysis and publication ranking. By utilizing citation contexts extracted from a large number of full-text publications, each citation or publication is represented by a probability distribution over a set of predefined topics, where each topic is labeled by an author contributed keyword. We then used publication/citation topic distribution to generate a citation graph with vertex prior and edge transitioning probability distributions. The publication importance score for each given topic is calculated by PageRank with edge and vertex prior distributions. Based on 104 topics (labeled with keywords) and their review papers, the cited publications of each review paper are assumed as "important publications" for ranking evaluation. The result shows that full text citation and publication content prior topic distribution along with the PageRank algorithm can significantly enhance bibliometric analysis and scientific publication ranking performance for academic IR system.
Similarity search in 3D object-based video data
Authors: Jakub Lokoc, Jürgen Wünschmann, Tomás Skopal, Albrecht Rothermel
Venue: CIKM
Year: 2012

In this paper, we present the vision of the usage of an object-based video data storage format for similarity search. The efficient (fast) and effective (accurate) search in video streams is an ongoing and still unsolved problem. Using an object-based format of multimedia data, all the information that is needed to answer queries is already available in a machine accessible format. This way, the process of creating (video) descriptors as well as the similarity search becomes easier, because the data is already organized in a manner that allows fast access to specific information. To demonstrate the concept of similarity search process using the object-based 3D video format, we present experiments conducted on generated clouds of points (an abstraction of 3D video data).
TCSST: transfer classification of short & sparse text using external data
Authors: Guodong Long, Ling Chen, Xingquan Zhu, Chengqi Zhang
Venue: CIKM
Year: 2012

Short & sparse text is becoming more prevalent on the web, such as search snippets, micro-blogs and product reviews. Accurately classifying short & sparse text has emerged as an important while challenging task. Existing work has considered utilizing external data (e.g. Wikipedia) to alleviate data sparseness, by appending topics detected from external data as new features. However, training a classifier on features concatenated from different spaces is not easy considering the features have different physical meanings and different significance to the classification task. Moreover, it exacerbates the "curse of dimensionality" problem. In this study, we propose a transfer classification method, TCSST, to exploit the external data to tackle the data sparsity issue. The transfer classifier will be learned in the original feature space. Considering that the labels of the external data may not be readily available or sufficiently enough, TCSST further exploits the unlabeled external data to aid the transfer classification. We develop novel strategies to allow TCSST to iteratively select high quality unlabeled external data to help with the classification. We evaluate the performance of TCSST on both benchmark as well as real-world data sets. Our experimental results demonstrate that the proposed method is effective in classifying very short & sparse text, consistently outperforming existing and baseline methods.
A simple approach to the design of site-level extractors using domain-centric principles
Authors: Chong Long, Xiubo Geng, Chang Xu, Sathiya Keerthi
Venue: CIKM
Year: 2012

We consider the problem of extracting, in a domain-centric fashion, a given set of attributes from a large number of semi-structured websites. Previous approaches [7, 5] to solve this problem are based on page level inference. We propose a distinct new approach that directly chooses attribute extractors for a site using a scoring mechanism that is designed at the domain level via simple classification methods using a training set from a small number of sites. To keep the number of candidate extractors in each site manageably small we use two observations that hold in most domains: (a) imprecise annotators can be used to identify a small set of candidate extractors for a few attributes (anchors); and (b) non-anchor attributes lie in close proximity to the anchor attributes. Experiments on three domains (Events, Books and Restaurants) show that our approach is very effective in spite of its simplicity.
Designing the reconciled schema for a pharmacovigilance data warehouse through a temporally-enhanced ER model
Authors: Riccardo Lora, Alberto Sabaini, Carlo Combi, Ugo Moretti
Venue: CIKM
Year: 2012

Pharmacovigilance is the activity related to the collection, analysis, and prevention of adverse reactions induced by drugs. The spontaneous reporting of adverse drug reactions is a system for identifying and sending reports about unexpected reactions to the regulatory authority. In Italy the information needed for properly carrying out the pharmacovigilance activities is scattered in different databases, which often contain the same information but encoded in different and temporally evolving ways. The data contained in the mentioned archives need to be integrated with information contained in other databases. In this paper we describe the construction of a data warehousing system, called VigiSegn, for the national center of pharmacovigilance; in particular, we focus on the data sources analysis and the design of the reconciled database. The (temporal) schema of reconciled data has been designed by using the TimeER conceptual data model.
Fast top-k similarity queries via matrix compression
Authors: Yucheng Low, Alice X. Zheng
Venue: CIKM
Year: 2012

In this paper, we propose a novel method to efficiently compute the top-K most similar items given a query item, where similarity is defined by the set of items that have the highest vector inner products with the query. The task is related to the classical k-Nearest-Neighbor problem, and is widely applicable in a number of domains such as information retrieval, online advertising and collaborative filtering. Our method assumes an in-memory representation of the dataset and is designed to scale to query lengths of 100,000s of terms. Our algorithm uses a generalized Holder's inequality to upper bound the inner product with the norms of the constituent vectors. We also propose a novel compression scheme that computes bounds for groups of candidate items, thereby speeding up computation and minimizing memory requirements per query. We conduct extensive experiments on the publicly available Wikipedia dataset, and demonstrate that, with a memory overhead of 21%, our method can provide 1-3 orders of magnitude improvement in query run-time compared to naive methods and state of the art competing methods. Our median top-10 word query time is 25 us on 7.5 million words and 2.3 million documents.