OpenRaiser/Intern-Atlas huggingface dataset:
Shine: search heterogeneous interrelated entities
Authors: Xuanhui Wang, Jian-Tao Sun, Zheng Chen
Venue: CIKM
Year: 2007

Heterogeneous entities or objects are very common and are usually interrelated with each other in many scenarios. For example, typical Web search activities involve multiple types of interrelated entities such as end users, Web pages, and search queries. In this paper, we define and study a novel problem: <UL>S</UL>earch <UL>H</UL>eterogeneous <UL>IN</UL>terrelated <UL>E</UL>ntities (SHINE). Given a SHINE-query which can be any type(s) of entities, the task of SHINE is to retrieve multiple types of related entities to answer this query. This is in contrast to the traditional search,which only deals with a single type of entities (e.g., Web pages). The advantages of SHINE include: (1) It is feasible for end users to specify their information need along different dimensions by accepting queries with different types. (2) Answering a query by multiple types of entities provides informative context for users to better understand the search results and facilitate their information exploration. (3) Multiple relations among heterogeneous entities can be utilized to improve the ranking of any particular type of entities. To attain the goal of SHINE, we propose to represent all entities in a unified space through utilizing their interaction relationships. Two approaches, M-LSA and E-VSM, are discussed and compared in this paper. The experiments on 3 data sets (i.e., a literature data set, a search engine log data set, and a recommendation data set) show the effectiveness and flexibility of our proposed methods.
An architecture for xml information retrieval in a peer-to-peer environment
Authors: Judith Winter, Oswald Drobnik
Venue: CIKM
Year: 2007

XML has become a widely accepted standard for modelling, storing, and exchanging structured documents. Taking advantage of the document structure can result in improving the retrieval performance of XML-documents notably. A growing number of these documents are stored in Peer-to-Peer networks, which are promising self-organizing infrastructures. Documents are distributed over the Peer-to-Peer network by either being stored locally on individual peers or by being assigned to collections such as Digital Libraries. Current search methods for XML-documents in Peer-to-Peer networks lack the use of Information Retrieval techniques for vague queries and relevance detection.
Mining redundancy in candidate-bearing snippets to improve web question answering
Authors: Youzheng Wu, Xinhui Hu, Hideki Kashioka
Venue: CIKM
Year: 2007

Conventional question answering (QA) techniques independently process candidate-bearing snippets to select an exact answer to a question from candidate answers. This paper presents two novel ways of utilizing redundancy in candidate-bearing snippets to help select an exact answer to a question in our Web QA system, i.e., cluster-based language model (CLM-M) and unsupervised SVM classifier (U-SVM) techniques. The comparative experiments demonstrate that the proposed methods significantly outperform the language model-based (LM-M) and supervised SVM-based (S-SVM) techniques that do not utilize this redundancy in the candidate-bearing snippets. Using the CLM-M, the top_1 score is increased from 36.03% (LM-M) to 46.96%; and the top_1 improvement in the U-SVM over the S-SVM is about 23%. Moreover, a cross-model comparison shows that the performance ranking of these models is: U-SVM > CLM-LM > LM-M > S-SVM > R-M (the retrieval-based model).
Mutually beneficial learning with application to on-line news classification
Authors: Lei Wu, Zhiwei Li, Mingjing Li, Wei-Ying Ma, Nenghai Yu
Venue: CIKM
Year: 2007

There are three common challenges in real-world classification applications, i.e. how to use domain knowledge, how to resist noisy samples and how to use unlabeled data. To address these problems, a novel classification framework called Mutually Beneficial Learning (MBL) is proposed in this paper. MBL integrates two learning steps together. In the first step, the underlying local structures of feature space are discovered through a learning process. The result provides necessary capability to resist noisy samples and prepare better input for the second step where a consecutive classification process is further applied to the result. These two steps are iteratively performed until a stop condition is met. Different from traditional classifiers, the output of MBL consists of two components: a common classifier and a set of rules corresponding to local structures. In application, a test sample is first matched with the discovered rules. If a matched rule is found, the label of the rule is assigned to the sample; otherwise, the common classifier will be utilized to classify the sample. We applied the MBL to online news classification, and our experimental results showed that MBL is significantly better than Naive Bayes and SVM, even when the data is noisy or partially labeled.
Using social annotations to improve language model for information retrieval
Authors: Shengliang Xu, Shenghua Bao, Yunbo Cao, Yong Yu
Venue: CIKM
Year: 2007

This poster is concerned with the problem of exploring the use of social annotations for improving language models for information retrieval (denoted as LMIR). Two properties of social annotations, namely keyword property and structure property are studied for this aim. The keyword property improves LMIR by concatenating all the annotations of a document to generate a summary of the document. The structure property can boost LMIR further when similarity among annotations and similarity among documents are taken into consideration simultaneously. The two properties of social annotations are leveraged for the use of language modeling with a mixture model named as "Language Annotation Model" (denoted as LAM). Evaluations using del.icio.us data show that LAM outperforms the traditional LMIR approaches significantly.
Generating concise association rules
Authors: Yue Xu, Yuefeng Li
Venue: CIKM
Year: 2007

Association rule mining has made many achievements in the area of knowledge discovery. However, the quality of the extracted association rules is a big concern. One problem with the quality of the extracted association rules is the huge size of the extracted rule set. As a matter of fact, very often tens of thousands of association rules are extracted among which many are redundant thus useless. Mining non-redundant rules is a promising approach to solve this problem. The Min-max exact basis proposed by Pasquier et al [Pasquier05] has showed exciting results by generating only non-redundant rules. In this paper, we first propose a relaxing definition for redundancy under which the Min-max exact basis still contains redundant rules; then we propose a condensed representation called Reliable exact basis for exact association rules. The rules in the Reliable exact basis are not only non-redundant but also more succinct than the rules in Min-max exact basis. We prove that the redundancy eliminated by the Reliable exact basis does not reduce the belief to the Reliable exact basis. The size of the Reliable exact basis is much smaller than that of the Min-max exact basis. Moreover, we prove that all exact association rules can be deduced from the Reliable exact basis. Therefore the Reliable exact basis is a lossless representation of exact association rules. Experimental results show that the Reliable exact basis significantly reduces the number of non-redundant rules.
Efficient LCA based keyword search in xml data
Authors: Yu Xu, Yannis Papakonstantinou
Venue: CIKM
Year: 2007

Keyword search in XML documents based on the notion of lowest common ancestors (LCAs) and modifications of it has recently gained research interest [2, 3, 4]. In this paper we propose an efficient algorithm called Indexed Stack to find answers to keyword queries based on XRank's semantics to LCA [2]. The complexity of the Indexed Stack algorithm is O(kd|S1|\log|S|) where k is the number of keywords in the query, d is the depth of the tree and |S1 | (|S|) is the occurrence of the least (most) frequent keyword in the query. In comparison, the best worst case complexity of the core algorithms in [2] is O(kd|S|). We analytically and experimentally evaluate the Indexed Stack algorithm and the two core algorithms in [2]. The results show that the Indexed Stack algorithm outperforms in terms of both CPU and I/O costs other algorithms by orders of magnitude when the query contains at least one low frequency keyword along with high frequency keywords.
Query expansion using probabilistic local feedback with application to multimedia retrieval
Authors: Rong Yan, Alexander G. Hauptmann
Venue: CIKM
Year: 2007

As one of the most effective query expansion approaches, local feedback is able to automatically discover new query terms and improve retrieval accuracy for different retrieval models. However, the performance of local feedback is heavily dependent on the assumption that most top-ranked documents are relevant to the query topic. Although this assumption might be sensible for ad-hoc text retrieval, it is usually violated in many other retrieval tasks such as multimedia retrieval. In this paper, we develop a robust local analysis approach called probabilistic local feedback (PLF) based on a discriminative probabilistic retrieval framework. The proposed model is effective for improving retrieval accuracy without assuming the most top-ranked documents are relevant. It also provides a sound probabilistic interpretation and a convergence guarantee on the iterative result updating process. Although derived from variational techniques, this approach only involves an iterative process of simple operations on ranking features and thus can be computed efficiently in practice. Our multimedia retrieval experiments on TRECVID'03-'05 collections have demonstrated the advantage of the proposed PLF approaches which can achieve noticeable gains in terms of mean average precision over various baseline methods and PRF-augmented results.
Link analysis using time series of web graphs
Authors: Lei Yang, Lei Qi, Yan-Ping Zhao, Bin Gao, Tie-Yan Liu
Venue: CIKM
Year: 2007

Link analysis is a key technology in contemporary web search engines. Most of the previous work on link analysis only used information from one snapshot of web graph. Since commercial search engines crawl the Web periodically, they will naturally obtain time series data of web graphs. The historical information contained in the series of web graphs can be used to improve the performance of link analysis. In this paper, we argue that page importance should be a dynamic quantity, and propose defining page importance as a function of both PageRank of the current web graph and accumulated historical page importance from previous web graphs. Specifically, a novel algorithm named TemporalRank is designed to compute the proposed page importance. We try to use a kinetic model to interpret this page importance and show that it can be regarded as the solution to an ordinary differential equation. Experiments on link analysis using web graph data in five snapshots show that the proposed algorithm can outperform PageRank in many measures, and can effectively filter out newly appeared link spam websites.
Nugget discovery in visual exploration environments by query consolidation
Authors: Di Yang, Elke A. Rundensteiner, Matthew O. Ward
Venue: CIKM
Year: 2007

Queries issued by casual users or specialists exploring a dataset often point us to important subsets of the data, be it clusters, outliers or other meaningful features. Capturing and caching such queries (henceforth called nuggets) has many potential benefits, including the optimization of the system performance and the search experience of users. Unfortunately, current visual exploration systems have not yet tapped into this potential resource of identifying and sharing important queries. In this paper, we introduce a query consolidation strategy aimed at solving the general problem of isolating important queries from the potentially huge amount of queries submitted. Our solution clusters redundant queries caused by exploration-style query specification, which is prevalent in data exploration systems. To measure the similarity between queries, we designed an effective distance metric that incorporates both the query specification and the actual query result. To overcome its high complexity when comparing queries with large result sets, we designed an approximation method, which is efficient while still providing excellent accuracy. A user study conducted on multivariate data sets comparing our proposed technique to others in the literature confirms that the proposed distance metric indeed matches well with users' intuition. As proof of feasibility, we integrated our proposed query consolidation solution into the Nugget Management System (NMS) framework [22], which is based on a visual exploration system XmdvTool. A second user study indicates that both the efficiency and accuracy of users' visual exploration are enhanced when supported by NMS.
Ranking very many typed entities on wikipedia
Authors: Hugo Zaragoza, Henning Rode, Peter Mika, Jordi Atserias, Massimiliano Ciaramita, Giuseppe Attardi
Venue: CIKM
Year: 2007

We discuss the problem of ranking very many entities of different types. In particular we deal with a heterogeneous set of types, some being very generic and some very specific. We discuss two approaches for this problem: i) exploiting the entity containment graph and ii) using a Web search engine to compute entity relevance. We evaluate these approaches on the real task of ranking Wikipedia entities typed with a state-of-the-art named-entity tagger. Results show that both approaches can greatly increase the performance of methods based only on passage retrieval.
Recognition and classification of noun phrases in queries for effective retrieval
Authors: Wei Zhang, Shuang Liu, Clement T. Yu, Chaojing Sun, Fang Liu, Weiyi Meng
Venue: CIKM
Year: 2007

It has been shown that using phrases properly in the document retrieval leads to higher retrieval effectiveness. In this paper, we define four types of noun phrases and present an algorithm for recognizing these phrases in queries. The strengths of several existing tools are combined for phrase recognition. Our algorithm is tested using a set of 500 web queries from a query log, and a set of 238 TREC queries. Experimental results show that our algorithm yields high phrase recognition accuracy. We also use a baseline noun phrase recognition algorithm to recognize phrases from the TREC queries. A document retrieval experiment is conducted using the TREC queries (1) without any phrases, (2) with the phrases recognized from a baseline noun phrase recognition algorithm, and (3) with the phrases recognized from our algorithm respectively. The retrieval effectiveness of (3) is better than that of (2), which is better than that of (1). This demonstrates that utilizing phrases in queries does improve the retrieval effectiveness, and better noun phrase recognition yields higher retrieval performance.
An efficient algorithm for approximate biased quantile computation in data streams
Authors: Qi Zhang, Wei Wang
Venue: CIKM
Year: 2007

We propose an efficient algorithm for approximate biased quantile computation in large data streams. Our algorithm computes decomposable biased quantile summaries on fixed sized blocks and dynamically maintains the biased quantile summary for the entire stream as the exponential histogram over the block-wise quantile summaries. The algorithm is computationally efficient and achieves an amortized computational cost of O(log(1⁄∈log(∈n))) and a space requirement of O(log3∈n↬∈). Our algorithm does not assume prior knowledge of the stream sizes or the range of data values in the streams. In practice, our algorithm is able to efficiently maintain summaries over large data streams with over tens of millions of observations and achieves significant performance improvement over prior algorithms.
Boolean representation based data-adaptive correlation analysis over time series streams
Authors: Tiancheng Zhang, Dejun Yue, Yu Gu, Ge Yu
Venue: CIKM
Year: 2007

Correlation analysis is a basic problem in the field of data stream mining. Typical approaches add sliding window to data streams to get the recent results, but the window length defined by users is always fixed which is not suitable for the changing stream environment. We propose a Boolean representation based data-adaptive method for correlation analysis among a large number of time series streams. The periodical trends of each stream series to are monitored to choose the most suitable window size and group the series with the same trends together. Instead of adopting complex pair-wise calculation, we can also quickly get the correlation pairs of series at the optimal window sizes. All the processing is realized by simple Boolean operations. Both the theory analysis and the experimental evaluations show that our method has good computation efficiency with high accuracy.
Effective top-k computation in retrieving structured documents with term-proximity support
Authors: Mingjie Zhu, Shuming Shi, Mingjing Li, Ji-Rong Wen
Venue: CIKM
Year: 2007

Modern web search engines are expected to return top-k results efficiently given a query. Although many dynamic index pruning strategies have been proposed for efficient top-k computation, most of them are prone to ignore some especially important factors in ranking functions, e.g. term proximity (the distance relationship between query terms in a document). The inclusion of term proximity breaks the monotonicity of ranking functions and therefore leads to additional challenges for efficient query processing. This paper studies the performance of some existing top-k computation approaches using term-proximity-enabled ranking functions. Our investigation demonstrates that, when term proximity is incorporated into ranking functions, most existing index structures and top-k strategies become quite inefficient. According to our analysis and experimental results, we propose two index structures and their corresponding index pruning strategies: Structured and Hybrid, which performs much better on the new settings. Moreover, the efficiency of index building and maintenance would not be affected too much with the two approaches.
The benefit of additional semantics in folksonomy systems
Authors: Fabian Abel
Venue: CIKM
Year: 2008

With the advent of Web 2.0 folksonomy systems like Flickr, del.icio.us, etc. have become very popular. They enable users to annotate resources (images, websites, etc.) with freely chosen keywords, so-called tags. The evolving set of such tag assignments, which are generally user-tag-resource bindings, are called folksonomies. Folksonomies embody valuable information that can be exploited by search and ranking algorithms.
Ranking in folksonomy systems: can context help?
Authors: Fabian Abel, Nicola Henze, Daniel Krause
Venue: CIKM
Year: 2008

Folksonomy systems have shown to contribute to the quality of Web search ranking strategies. In this paper, we analyze and compare different graph-based ranking algorithms, namely FolkRank, SocialPageRank, and SocialSimRank. We enhance these algorithms by exploiting the context of tag assignmets, and evaluate the results on the GroupMe! dataset. In GroupMe!, users can organize and maintain arbitrary Web resources in self-defined groups. When users annotate resources in GroupMe!, this can be interpreted in context of a certain group. The grouping activity delivers valuable semantic information about resources and their context. We show how to use this information to improve the detection of relevant search results, and compare different strategies for ranking result lists in folksonomy systems.
A spam resistant family of concavo-convex ranks for link analysis
Authors: Sreangsu Acharyya, Joydeep Ghosh
Venue: CIKM
Year: 2008

A parameterized family of non-linear, link analytic ranking functions is proposed that includes Pagerank as a special case and uses the convexity property of those functions to be more resistant to link spam attacks. A contribution of the paper is the construction of such a scheme with provable uniqueness and convergence guarantees. The paper also demonstrates that even in an unlabelled scenario this family can have spam resistance comparable to Trustrank [3] that uses labels of spam or nat-spam on a training set. The proposed method can use labels, if available, to improve its performance to provide state of the art level of link spam protection.
Humane data mining
Authors: Rakesh Agrawal
Venue: CIKM
Year: 2008

Data Mining has made tremendous strides in the last decade. It is time to take data mining to the next level of contributions, while continuing to innovate for the current mainstream market. We postulate that a fruitful future direction could be humane data mining: applications to benefit individuals. The potential applications include personal data mining (e.g. personal health), enable people to get a grip on their world (e.g. dealing with the long tail of search), enable people to become creative (e.g. inventions arising from linking non-interacting scientific literature), enable people to make contributions to society (e.g. education collaboration networks), and data-driven science (e.g. study ecological disasters, brain disorders). Rooting our future work in these (and similar) applications, will lead to new data mining abstractions, algorithms, and systems.
Pairwise statistical significance of local sequence alignment using multiple parameter sets
Authors: Ankit Agrawal, Xiaoqiu Huang
Venue: CIKM
Year: 2008

Accurate estimation of statistical significance of a pairwise alignment is an important problem in sequence comparison. Recently, a comparative study of pairwise statistical significance with database statistical significance was conducted. In this paper, we extend the earlier work on pairwise statistical significance by incorporating with it the use of multiple parameter sets. Preliminary results for a knowledge discovery application such as homology detection reveal that using multiple parameter sets for pairwise statistical significance estimates gives significantly better coverage than using a single parameter set, at least at some error levels. Also, the fact that the performance does not degrade when using multiple parameter sets is a strong evidence that the assumption that the score distribution follows an extreme value distribution is valid even when using multiple parameter sets. Results of pairwise statistical significance using multiple parameter sets are further shown to be significantly better than database statistical significance estimates reported by BLAST and PSI-BLAST, and comparable and at times significantly better than SSEARCH.
Exploiting pipeline interruptions for efficient memory allocation
Authors: Josep Aguilar-Saborit, Mohammad Jalali, Dave Sharpe, Victor Muntés-Mulero
Venue: CIKM
Year: 2008

Efficiency of memory-intensive operations is a key factor in obtaining good performance during multi-join query processing. The pipelined execution of these queries forces the operations in the query plan to be processed concurrently. Making a wrong decision regarding the amount of memory allocated for such operations can have a drastic impact on the response time. However, some of the execution algorithms used at run time interrupt the pipelined execution, ensuring that some operations are never executed concurrently. Because of this, it is essential to explore new approaches in order to improve memory exploitation.