OpenRaiser/Intern-Atlas huggingface dataset:
Coupling feature selection and machine learning methods for navigational query identification
Authors: Yumao Lu, Fuchun Peng, Xin Li, Nawaaz Ahmed
Venue: CIKM
Year: 2006

It is important yet hard to identify navigational queries in Web search due to a lack of sufficient information in Web queries, which are typically very short. In this paper we study several machine learning methods, including naive Bayes model, maximum entropy model, support vector machine (SVM), and stochastic gradient boosting tree (SGBT), for navigational query identification in Web search. To boost the performance of these machine techniques, we exploit several feature selection methods and propose coupling feature selection with classification approaches to achieve the best performance. Different from most prior work that uses a small number of features, in this paper, we study the problem of identifying navigational queries with thousands of available features, extracted from major commercial search engine results, Web search user click data, query log, and the whole Web's relational content. A multi-level feature extraction system is constructed.Our results on real search data show that 1) Among all the features we tested, user click distribution features are the most important set of features for identifying navigational queries. 2) In order to achieve good performance, machine learning approaches have to be coupled with good feature selection methods. We find that gradient boosting tree, coupled with linear SVM feature selection is most effective. 3) With carefully coupled feature selection and classification approaches, navigational queries can be accurately identified with 88.1% F1 score, which is 33% error rate reduction compared to the best uncoupled system, and 40% error rate reduction compared to a well tuned system without feature selection.
Structure-based querying of proteins using wavelets
Authors: Keith Marsolo, Srinivasan Parthasarathy, Kotagiri Ramamohanarao
Venue: CIKM
Year: 2006

The ability to retrieve molecules based on structural similarity has use in many applications, from disease diagnosis and treatment to drug discovery and design. In this paper, we present a method to represent protein molecules that allows for the fast, flexible and efficient retrieval of similar structures, based on either global or local attributes. We begin by computing the pair-wise distance between amino acids, transforming each 3D structure into a 2D distance matrix. We normalize this matrix to a specific size and apply a 2D wavelet decomposition to generate a set of approximation coefficients, which serves as our global feature vector. This transformation reduces the overall dimensionality of the data while still preserving spatial features and correlations. We test our method by running queries on three different protein data sets that have been used previously in the literature, basing our comparisons on labels taken from the SCOP database. We find that our method significantly outperforms existing approaches, in terms of retrieval accuracy, memory utilization and execution time. Specifically, using a k-d tree and running a 10-nearest-neighbor search on a dataset of 33,000 proteins against itself, we see an average accuracy of 89% at the SCOP SuperFamily level and a total query time that is up to 350 times faster than previously published techniques. In addition to processing queries based on global similarity, we also propose innovative extensions to effectively match proteins based solely on shared local substructures, allowing for a more flexible query interface.
Estimation, sensitivity, and generalization in parameterized retrieval models
Authors: Donald Metzler
Venue: CIKM
Year: 2006

In this work we investigate three important aspects of parameterized retrieval models: estimation, sensitivity, and generalization. Since all parameterized models, even those based on heuristics, have inherent uncertainty, we study these issues using statistical tools.
Discovering and exploiting keyword and attribute-value co-occurrences to improve P2P routing indices
Authors: Sebastian Michel, Matthias Bender, Nikos Ntarmos, Peter Triantafillou, Gerhard Weikum, Christian Zimmer
Venue: CIKM
Year: 2006

Peer-to-Peer (P2P) search requires intelligent decisions for query routing: selecting the best peers to which a given query, initiated at some peer, should be forwarded for retrieving additional search results. These decisions are based on statistical summaries for each peer, which are usually organized on a per-keyword basis and managed in a distributed directory of routing indices. Such architectures disregard the possible correlations among keywords. Together with the coarse granularity of per-peer summaries, which are mandated for scalability, this limitation may lead to poor search result quality.This paper develops and evaluates two solutions to this problem, sk-STAT based on single-key statistics only, and mk-STAT based on additional multi-key statistics. For both cases, hash sketch synopses are used to compactly represent a peer's data items and are efficiently disseminated in the P2P network to form a decentralized directory. Experimental studies with Gnutella and Web data demonstrate the viability and the trade-offs of the approaches.
Collaborative filtering in dynamic usage environments
Authors: Olfa Nasraoui, Jeff Cerwinske, Carlos Rojas, Fabio A. González
Venue: CIKM
Year: 2006

The increasing expansion of websites and their web usage necessitates increasingly scalable techniques for Web usage mining that can be better cast within the framework of mining evolving data streams [1, 5]. Despite recent developments in mining evolving Web clickstreams [3, 6], there has not been any investigation of the performance of collaborative filtering [2] in the demanding environment of evolving data streams. In this paper, we study limited memory collaborative filtering based recommendations in evolving scenarios using a systematic validation methodology.
Investigating the exhaustivity dimension in content-oriented XML element retrieval evaluation
Authors: Paul Ogilvie, Mounia Lalmas
Venue: CIKM
Year: 2006

INEX, the evaluation initiative for content-oriented XML retrieval, has since its establishment defined the relevance of an element according to two graded dimensions, exhaustivity and specificity. The former measures how exhaustively an XML element discusses the topic of request, whereas specificity measures how focused the element is on the topic of request. The reason for having two dimensions was to provide a more stable measure of relevance than if assessors were asked to rate the relevance of an element on a single scale. However, obtaining relevance assessments is a costly task. as each document must be assessed for relevance by a human assessor. In XML retrieval this problem is exacerbated as the elements of the document must also be assessed with respect to the exhaustivity and specificity dimensions. A continuous discussion in INEX has been whether such a sophisticated definition of relevance, and in particular the exhaustivity dimension, was needed. This paper attempts to answer this question through extensive statistical tests to compare the conclusions about system performance that could be made under different assessment scenarios.
Window join approximation over data streams with importance semantics
Authors: Adegoke A. Ojewole, Qiang Zhu, Wen-Chi Hou
Venue: CIKM
Year: 2006

Load shedding techniques generate approximate sliding window join results when memory constraints prevent exact computation. The previously proposed random load shedding method drops input tuples without consideration for the number of outputs created, while the recently proposed semantic load shedding technique aims to produce the largest possible result set. We consider a new model in which data stream tuples contain numerical importance values relevant to the query source and seek to maximize the importance of the approximate join result. We show that both random load shedding and semantic load shedding are sub-optimal in this situation, while the techniques presented in this paper satisfy the objective function by considering both tuple importance and join attribute distributions. We extend the existing offline semantic approximation technique to make it compatible with our objective function and show that it is less space and time efficient than our new optimal offline algorithm for small and large join memory allotments. We also introduce four efficient online algorithms, which are quite promising in maximizing the importance of the approximate join result without foreknowledge of input streams.
Combining feature selectors for text classification
Authors: J. Scott Olsson, Douglas W. Oard
Venue: CIKM
Year: 2006

We introduce several methods of combining feature selectors for text classification. Results from a large investigation of these combinations are summarized. Easily constructed combinations of feature selectors are shown to improve peak R-precision and F1 at statistically significant levels.
Vector and matrix operations programmed with UDFs in a relational DBMS
Authors: Carlos Ordonez, Javier García-García
Venue: CIKM
Year: 2006

In general, a relational DBMS provides limited capabilities to perform multidimensional statistical analysis, which requires manipulating vectors and matrices. In this work, we study how to extend a DBMS with basic vector and matrix operators by programming User-Defined Functions (UDFs). We carefully analyze UDF features and limitations to implement vector and matrix operations commonly used in statistics, machine learning and data mining, paying attention to DBMS, operating system and computer architecture constraints. UDFs represent a C programming interface that allows the definition of scalar and aggregate functions that can be used in SQL. UDFs have several advantages and limitations. A UDF allows fast evaluation of arithmetic expressions, memory manipulation, using multidimensional arrays and exploiting all C language control statements. Nevertheless, a UDF cannot perform disk I/O, the amount of heap and stack memory that can be allocated is small and the UDF code must consider specific architecture characteristics of the DBMS. We experimentally compare UDFs and SQL with respect to performance, ease of use, flexibility and scalability. We profile UDFs based on call overhead, memory management and interleaved disk access. We show UDFs are faster than standard SQL aggregations and as fast as SQL arithmetic expressions.
Robust periodicity detection algorithms
Authors: Srinivasan Parthasarathy, Sameep Mehta, S. Srinivasan
Venue: CIKM
Year: 2006

Periodicity detection is an important pre-processing step for many time series algorithms. It provides important information about the structural properties of a time series. Feature vectors based on periodicity can be used for clustering, classification, abnormality detection, and human motion understanding. The periodicity detection task is not difficult in case of simple and uncontaminated signal. Unfortunately, most of the real datasets exhibit one or more of the following properties: i) non-stationarity, ii) interlaced cyclic patterns and iii) data contamination, which makes the period detection extremely challenging. A seemingly straightforward solution is to develop individual specialized algorithms for handling each case separately. However, determining if a time series is non-stationary or is contaminated in itself is an extremely difficult task. In this article, we propose generic algorithms which can detect periods in complex, noisy and incomplete datasets. The algorithm leverages the frequency characterization and autocorrelation structure inherent in a time series to estimate its periodicity. We extend the methods to handle non-stationary time series by tracking the candidate periods using a Kalman filter. We also address the interesting problem of finding multiple interlaced periodicities.
POLESTAR: collaborative knowledge management and sensemaking tools for intelligence analysts
Authors: Nicholas J. Pioch, John O. Everett
Venue: CIKM
Year: 2006

In this paper, we describe POLESTAR (POLicy Explanation using STories and ARguments), an integrated suite of knowledge management and collaboration tools for intelligence analysts.POLESTAR provides built-in support for analyst workflow, including collection of textual facts from source documents, structured argumentation, and automatic citation in analytic product documents. Underlying POLESTAR is a scalable dependency repository, which provides traceability from product documents to source snippets. The repository's notification engine allows POLESTAR to alert analysts when dependent sources are discredited and aid them in repairing affected arguments. The paper then discusses recent extensions to POLESTAR to support collaborative analysis through community-of-interest finding, portfolio sharing, and peer review of arguments. We conclude with a preview of future research and summary of POLESTAR's primary benefits from the point of view of its deployed users.
Amnesic online synopses for moving objects
Authors: Michalis Potamias, Kostas Patroumpas, Timos K. Sellis
Venue: CIKM
Year: 2006

We present a hierarchical tree structure for online maintenance of time-decaying synopses over streaming data. We exemplify such an amnesic behavior over streams of locations taken from numerous moving objects in order to obtain reliable trajectory approximations as well as affordable estimates regarding distinct count spatiotemporal queries.
Knowing a web page by the company it keeps
Authors: Xiaoguang Qi, Brian D. Davison
Venue: CIKM
Year: 2006

Web page classification is important to many tasks in information retrieval and web mining. However, applying traditional textual classifiers on web data often produces unsatisfying results. Fortunately, hyperlink information provides important clues to the categorization of a web page. In this paper, an improved method is proposed to enhance web page classification by utilizing the class information from neighboring pages in the link graph. The categories represented by four kinds of neighbors (parents, children, siblings and spouses) are combined to help with the page in question. In experiments to study the effect of these factors on our algorithm, we find that the method proposed is able to boost the classification accuracy of common textual classifiers from around 70% to more than 90% on a large dataset of pages from the Open Directory Project, and outperforms existing algorithms. Unlike prior techniques, our approach utilizes same-host links and can improve classification accuracy even when neighboring pages are unlabeled. Finally, while all neighbor types can contribute, sibling pages are found to be the most important.
Adapting association patterns for text categorization: weaknesses and enhancements
Authors: Tieyun Qian, Hui Xiong, Yuanzhen Wang, Enhong Chen
Venue: CIKM
Year: 2006

The use of association patterns for text categorization has attracted great interest and a variety of useful methods have been developed. However, the key characteristics of pattern-based text categorization remain unclear. Indeed, there are still no concrete answers for the following two questions: First, what kind of association patterns are the best candidate for pattern-based text categorization? Second, what is the most desirable way to use patterns for text categorization? In this paper, we focus on answering the above two questions. Specifically, we show that hyperclique patterns are more desirable than frequent patterns for text categorization. Along this line, we develop an algorithm for text categorization using hyperclique patterns. The experimental results show that our method provides better performance than state-of-the-art methods in terms of both computational performance and classification accuracy.
Semi-automatic annotation and MPEG-7 authoring of dance videos
Authors: Balakrishnan Ramadoss, Rajkumar Kannan
Venue: CIKM
Year: 2006

This paper presents a system (DanVideo) that is implemented using J2SE and JMF to annotate manually the macro and micro features of the dance videos by the dance experts. As MPEG-7 has reached a matured state for the description of the multimedia structure and semantics through the Descriptors and Description Schemes, DanVideo generates a MPEG-7 instance that conforms to the MPEG-7 schema, semi-automatically and effortlessly from the dance annotations.
Information retrieval from relational databases using semantic queries
Authors: Anand Ranganathan, Zhen Liu
Venue: CIKM
Year: 2006

Relational databases are widely used today as a mechanism for providing access to structured data. They, however, are not suitable for typical information finding tasks of end users. There is often a semantic gap between the queries users want to express and the queries that can be answered by the database. In this paper, we propose a system that bridges this semantic gap using domain knowledge contained in ontologies. Our system extends relational databases with the ability to answer semantic queries that are represented in SPARQL, an emerging Semantic Web query language. Users express their queries in SPARQL, based on a semantic model of the data, and they get back semantically relevant results. We define different categories of results that are semantically relevant to the users' query and show how our system retrieves these results. We evaluate the performance of our system on sample relational databases, using a combination of standard and custom ontologies.
Concept frequency distribution in biomedical text summarization
Authors: Lawrence H. Reeve, Hyoil Han, Saya V. Nagori, Jonathan C. Yang, Tamara A. Schwimmer, Ari D. Brooks
Venue: CIKM
Year: 2006

Text summarization is a data reduction process. The use of text summarization enables users to reduce the amount of text that must be read while still assimilating the core information. The data reduction offered by text summarization is particularly useful in the biomedical domain, where physicians must continuously find clinical trial study information to incorporate into their patient treatment efforts. Such efforts are often hampered by the high-volume of publications. Our contribution is two-fold: 1) to propose the frequency of domain concepts as a method to identify important sentences within a full-text; and 2) propose a novel frequency distribution model and algorithm for identifying important sentences based on term or concept frequency distribution. An evaluation of several existing summarization systems using biomedical texts is presented in order to determine a performance baseline. For domain concept comparison, a recent high-performing frequency-based algorithm using terms is adapted to use concepts and evaluated using both terms and concepts. It is shown that the use of concepts performs closely with the use of terms for sentence selection. Our proposed frequency distribution model and algorithm outperforms a state-of-the-art approach.
Incremental hierarchical clustering of text documents
Authors: Nachiketa Sahoo, Jamie Callan, Ramayya Krishnan, George T. Duncan, Rema Padman
Venue: CIKM
Year: 2006

Incremental hierarchical text document clustering algorithms are important in organizing documents generated from streaming on-line sources, such as, Newswire and Blogs. However, this is a relatively unexplored area in the text document clustering literature. Popular incremental hierarchical clustering algorithms, namely Cobweb and Classit, have not been widely used with text document data. We discuss why, in the current form, these algorithms are not suitable for text clustering and propose an alternative formulation that includes changes to the underlying distributional assumption of the algorithm in order to conform with the data. Both the original Classit algorithm and our proposed algorithm are evaluated using Reuters newswire articles and Ohsumed dataset.
Performance thresholding in practical text classification
Authors: Hinrich Schütze, Emre Velipasaoglu, Jan O. Pedersen
Venue: CIKM
Year: 2006

In practical classification, there is often a mix of learnable and unlearnable classes and only a classifier above a minimum performance threshold can be deployed. This problem is exacerbated if the training set is created by active learning. The bias of actively learned training sets makes it hard to determine whether a class has been learned. We give evidence that there is no general and efficient method for reducing the bias and correctly identifying classes that have been learned. However, we characterize a number of scenarios where active learning can succeed despite these difficulties.
A probabilistic relevance propagation model for hypertext retrieval
Authors: Azadeh Shakery, ChengXiang Zhai
Venue: CIKM
Year: 2006

A major challenge in developing models for hypertext retrieval is to effectively combine content information with the link structure available in hypertext collections. Although several link-based ranking methods have been developed to improve retrieval results, none of them can fully exploit the discrimination power of contents as well as fully exploit all useful link structures. In this paper, we propose a general relevance propagation framework for combining content and link information. The framework gives a probabilistic score to each document defined based on a probabilistic surfing model. Two main characteristics of our framework are our probabilistic view on the relevance propagation model and propagation through multiple sets of neighbors. We compare eight different models derived from the probabilistic relevance propagation framework on two standard TREC Web test collections. Our results show that all the eight relevance propagation models can outperform the baseline content only ranking method for a wide range of parameter values, indicating that the relevance propagation framework provides a general, effective and robust way of exploiting link information. Our experiments also show that using multiple neighbor sets outperforms using just one type of neighbors significantly and taking a probabilistic view of propagation provides guidance on setting propagation parameters.
Filtering or adapting: two strategies to exploit noisy parallel corpora for cross-language information retrieval
Authors: Lixin Shi, Jian-Yun Nie
Venue: CIKM
Year: 2006

Noisy parallel corpora have been widely used for Cross-language information retrieval (CLIR). However, the previous studies only focus on truly parallel corpus. In this paper, we examine two possible approaches to exploit noisy corpora: filtering out noise from the corpora or adapting the training process of translation model to the noise corpora. Our experiments show that the second approach is better suited to CLIR.
Pseudo-anchor text extraction for searching vertical objects
Authors: Shuming Shi, Fei Xing, Mingjie Zhu, Zaiqing Nie, Ji-Rong Wen
Venue: CIKM
Year: 2006

This paper examines the problem of utilizing pseudo-anchor text to help ranking Web objects in vertical search. We adopt a machine learning based approach to extract pseudo-anchor text for a vertical object from its candidate anchor blocks. Experiments in academic search domain indicate that our approach is able to dramatically improve search performance.
Maximizing the sustained throughput of distributed continuous queries
Authors: Ioana Stanoi, George A. Mihaila, Themis Palpanas, Christian A. Lang
Venue: CIKM
Year: 2006

Monitoring systems today often involve continuous queries over streaming data, in a distributed collaborative system. The distribution of query operators over a network of processors, and their processing sequence, form a query configuration with inherent constraints on the throughput it can support. In this paper we propose to optimize stream queries with respect to a version of throughput measure, the profiled input throughput. This measure is focused on matching the expected behavior of the input streams. To prune the search space we used hill-climbing techniques that proved to be efficient and effective.