OpenRaiser/Intern-Atlas huggingface dataset:
BioDIFF: an effective fast change detection algorithm for genomic and proteomic data
Authors: Yang Song, Sourav S. Bhowmick
Venue: CIKM
Year: 2004

A key issue in biological data integration is how to detect changes to the underlying biological data sources. In this poster, we present an algorithm called BioDiff for detecting exact changes to genomic and proteomic data. In our approach we transform heterogeneous genomic and proteomic data to XML format and then detect changes between two versions of XML representation of biological data. Our algorithm extends X-Diff [2], a published XML change detection algorithm. X-Diff algorithm can detect the optimum differences between two unordered XML documents in a polynomial time. It works for any type of XML data. However, we believe that it is not efficient to apply X-Diff directly to detect changes to XML representation of biological data. Since the min-cost max-flow algorithm for computing the bipartite mapping between two XML trees is the most time consuming part, it is desirable to reduce the size of data set during mapping. However, X-Diff fails to do so for biological data as it ignores the semantics of the XML elements. 2. ALGORITHM BIODIFF
Grammar-based task analysis of web logs
Authors: Savitha Srinivasan, Arnon Amir, Prasad M. Deshpande, Vladimir Zbarsky
Venue: CIKM
Year: 2004

The daily use of Internet-based services is involved with hundreds of different tasks being performed by multiple users. A single task is typically involved with a sequence of Web URLs invocation. We study the problem of pattern detection in Web logs to identify tasks performed by users, and analyze task trends over time using a grammar-based framework. Our results are demonstrated on a corporate Intranet portal application with 7000 users over a 6 week period and demonstrate compelling business value from this high-level task analysis.
Associative document retrieval by query subtopic analysis and its application to invalidity patent search
Authors: Toru Takaki, Atsushi Fujii, Tetsuya Ishikawa
Venue: CIKM
Year: 2004

We propose an associative document retrieval method, in which a document is used as a query to search for other similar documents. Because a long document usually includes more than one topic, we first analyze a query document to extract multiple subtopics. For each subtopic element, a sub-query is produced and similar documents are retrieved with a relevance score. The relevance scores are weighted by the importance of each subtopic element and are integrated to determine the final relevant documents. In the calculation of the subtopic importance, the specificity of a query term is evaluated using entropy, which is the deviation degree of the appearances of the term in each subtopic element. We apply this method to an invalidity patent search. By exploiting certain unique features of Japanese patent claims, we use features distinguishing the preamble and the essential portion in a query patent claim. To demonstrate the effectiveness of our method, we experimentally evaluated our associative document retrieval method on five years of patent documents.
Calculating similarity between texts using graph-based text representation model
Authors: Junji Tomita, Hidekazu Nakawatase, Megumi Ishii
Venue: CIKM
Year: 2004

Knowledge discovery from a large volumes of texts usually requires many complex analysis steps. The graph-based text representation model has been proposed to simplify the steps. The model represents texts in a formal manner, Subject Graphs, and provides text handling operations whose inputs and outputs are identical in form, i.e. a set of subject graphs, so they can be combined in any order. A subject graph uses node weight to represent the significance of each term, and link weight to represent that of each term-term association. This paper concentrates on the algorithms for making subject graphs and calculating the similarity between them. An evaluation shows that Subject Graphs can calculate the similarity between texts more precisely than term vectors, since they incorporate the significance of association between terms.
Feature selection with conditional mutual information maximin in text categorization
Authors: Gang Wang, Frederick H. Lochovsky
Venue: CIKM
Year: 2004

Feature selection is an important component of text categorization. This technique can both increase a classifier's computation speed, and reduce the overfitting problem. Several feature selection methods, such as information gain and mutual information, have been widely used. Although they greatly improve the classifier's performance, they have a common drawback, which is that they do not consider the mutual relationships among the features. In this situation, where one feature's predictive power is weakened by others, and where the selected features tend to bias towards major categories, such selection methods are not very effective. In this paper, we propose a novel feature selection method for text categorization called <i>conditional mutual information maximin</i> (CMIM). It can select a set of individually discriminating and weakly dependent features. The experimental results show that CMIM can perform much better than traditional feature selection methods.
Web page clustering enhanced by summarization
Authors: Xuanhui Wang, Dou Shen, Hua-Jun Zeng, Zheng Chen, Wei-Ying Ma
Venue: CIKM
Year: 2004

Traditional Web page clustering algorithms use the full-text in the documents to generate feature vectors. Such methods often produce unsatisfactory results because there is much noisy information, such as decoration, interaction, and advertisement, in Web pages. The varying-length problem of the Web pages is also a significant negative factor affecting the performance. In this paper, we investigate the use of several summarization techniques to tackle these issues when clustering Web pages. Compared with the full-text representation of the Web pages, our experimental results indicate that our proposed approach effectively solves the problems of noisy information and varying-length, and thus significantly boosts the clustering performance.
Scalable sequential pattern mining for biological sequences
Authors: Ke Wang, Yabo Xu, Jeffrey Xu Yu
Venue: CIKM
Year: 2004

Biosequences typically have a small alphabet, a long length, and patterns containing gaps (i.e., "don't care") of arbitrary size. Mining frequent patterns in such sequences faces a different type of explosion than in transaction sequences primarily motivated in market-basket analysis. In this paper, we study how this explosion affects the classic sequential pattern mining, and present a scalable two-phase algorithm to deal with this new explosion. The <i>Segment Phase</i> first searches for short patterns containing no gaps, called <i>segments</i>. This phase is efficient. The <i>Pattern Phase</i> searches for long patterns containing multiple segments separated by variable length gaps. This phase is time consuming. The purpose of two phases is to exploit the information obtained from the first phase to speed up the pattern growth and matching and to prune the search space in the second phase. We evaluate this approach on synthetic and real life data sets.
Distance-function design and fusion for sequence data
Authors: Yi Wu, Edward Y. Chang
Venue: CIKM
Year: 2004

Sequence-data mining plays a key role in many scientific studies and real-world applications such as bioinformatics, data stream, and sensor networks, where sequence data are processed and their semantics interpreted. In this paper we address two relevant issues: sequence-data representation, and representation-to-semantics mapping. For representation, since the best one is dependent upon the application being used and even the type of query, we propose representing sequence data in multiple views. For each representation, we propose methods to construct a <i>valid kernel</i> as the distance function to measure <i>similarity</i> between sequences. For mapping, we then find the best combination of the individual distance functions, which measure similarity of different views, to depict the target semantics. We propose a <i>super-kernel function-fusion</i> scheme to achieve the optimal mapping. Through theoretical analysis and empirical studies on UCI and real world datasets, we show our approach of multi-view representation and fusion to be mathematically valid and very effective for practical purposes.
Interval query indexing for efficient stream processing
Authors: Kun-Lung Wu, Shyh-Kwei Chen, Philip S. Yu
Venue: CIKM
Year: 2004

A large number of continual range queries can be issued against a data stream. Usually, a main memory-based query index with a small storage cost and a fast search time is needed, especially if the stream is rapid. In this paper, we present a CEI-based query index that meets both criteria for efficient processing of continual interval queries in a streaming environment. This new query index is centered around a set of predefined virtual <i>containment-encoded intervals</i>, or CEIs. The CEIs are used to first decompose query intervals and then perform efficient search operations. The CEIs are defined and labeled such that containment relationships among them are encoded in their IDs. The containment encoding makes decomposition and search operations efficient because integer additions and logical shifts can be used to carry out most of the operations. Simulations are conducted to evaluate the effectiveness of the CEI-based query index and to compare it with alternative approaches. The results show that the CEI-based query index significantly outperforms existing approaches in terms of both storage cost and search time.
MRSSA: an iterative algorithm for similarity spreading over interrelated objects
Authors: Gui-Rong Xue, Hua-Jun Zeng, Zheng Chen, Yong Yu, Wei-Ying Ma, Wensi Xi, Edward A. Fox
Venue: CIKM
Year: 2004

We introduce the Multiple Relationship Similarity Spreading Algorithm (MRSSA) to enhance IR effectiveness. This method has similarity computed in an iterative "spreading" fashion for multiple object types, combining both inter- and intra-object relationships. We demonstrate the value of this approach in the context of the WWW, where the key objects are web pages and queries, Relationships considered are derived from hyperlinks (in- and out-links) and click-through logs.
Virtual cursors for XML joins
Authors: Beverly Yang, Marcus Fontoura, Eugene J. Shekita, Sridhar Rajagopalan, Kevin S. Beyer
Venue: CIKM
Year: 2004

Structural joins are a fundamental operation in XML query processing and a large body of work has focused on index-based algorithms for executing them. In this paper, we describe how two well-known index features -- path indices and ancestor information -- can be combined in a novel way to replace one or more of the physical index cursors in a structural join with <i>virtual cursors</i>. The position of a virtual cursor is derived from the path and ancestor information of a physical cursor. Implementation results are provided to show that, by eliminating index I/O, virtual cursors can improve the performance of structural joins by an order of magnitude or more.
Weakly-supervised relation classification for information extraction
Authors: Zhu Zhang
Venue: CIKM
Year: 2004

This paper approaches the relation classification problem in information extraction framework with bootstrapping on top of Support Vector Machines. A new bootstrapping algorithm is proposed and empirically evaluated on the ACE corpus. We show that the supervised SVM classifier using various lexical and syntactic features can achieve promising classification accuracy. More importantly, the proposed <i>BootProject</i> algorithm based on random feature projection can significantly reduce the need for labeled training data with only limited sacrifice of performance.
Combining structural and citation-based evidence for text classification
Authors: Baoping Zhang, Marcos André Gonçalves, Weiguo Fan, Yuxin Chen, Edward A. Fox, Pável Calado, Marco Cristo
Venue: CIKM
Year: 2004

This paper discusses how citation-based information and structural content (e.g., title, abstract) can be combined to improve classification of text documents into predefined categories. We evaluate different measures of similarity derived from the citation structure and the structural content of the collection, and determine how they can be fused to improve classification effectiveness. To discover the best fusion framework, we apply Genetic Programming (GP) techniques. Our empirical experiments using documents from the ACM Digital Library and the ACM Computing Classification System show that we can discover similarity functions that work better than using evidence in isolation and whose combined performance through a simple majority voting is comparable to that of Support Vector Machine classifiers.
InfoAnalyzer: a computer-aided tool for building enterprise taxonomies
Authors: Li Zhang, Shixia Liu, Yue Pan, Liping Yang
Venue: CIKM
Year: 2004

In this paper we study the problem of collecting training samples for building enterprise taxonomies. We develop a computer-aided tool named InfoAnalyzer, which can effectively assist the enterprise to prepare large set of samples used for machine learning in text categorization. In our system, the enterprise category tree is initially defined by some keywords, then the Google search engine is used to construct a small set of labeled documents, and topic tracking algorithm based on document length normalization is applied to enlarge the training corpus on the bases of the seed stories. Furthermore, we design a method to check the consistency of the training corpus. Experiments show that the training corpus is good enough for statistical classification methods and meets human's requirements as well.
Discovering frequently changing structures from historical structural deltas of unordered XML
Authors: Qiankun Zhao, Sourav S. Bhowmick, Mukesh K. Mohania, Yahiko Kambayashi
Venue: CIKM
Year: 2004

Recently, a large amount of work has been done in XML data mining. However, we observed that most of the existing works focus on the snapshot XML data, while XML data is dynamic in real applications. To the best of our knowledge, none of the existing works has addressed the issue of mining the history of changes to XML documents. Such mining results can be useful in many applications such as XML change detection, XML indexing, association rule mining, and classification etc. In this paper, we propose a novel approach to discover the <i>frequently changing structures</i> from the sequence of historical <i>structural deltas</i> of unordered XML. To make the structure discovering process efficient, an expressive and compact data model, <b>H</b>istorical-<b>D</b>ocument <b>O</b>bject <b>M</b>odel (<b>H-DOM</b>), is proposed. Using this model, two basic algorithms, which can discover all the <i>frequently changing structures</i> with only two scans of the XML sequence, are presented. Experimental results show that our algorithms, together with the optimization techniques, are efficient and scalable.
Internet scale string attribute publish/subscribe data networks
Authors: Ioannis Aekaterinidis, Peter Triantafillou
Venue: CIKM
Year: 2005

With this work we aim to make a three-fold contribution. We first address the issue of supporting efficiently queries over string-attributes involving prefix, suffix, containment, and equality operators in large-scale data networks. Our first design decision is to employ distributed hash tables (DHTs) for the data network's topology, harnessing their desirable properties. Our next design decision is to derive DHT-independent solutions, treating DHT as a black box. Second, we exploit this infrastructure to develop efficient content based publish/subscribe systems. The main contribution here are algorithms for the efficient processing of queries (subscriptions) and events (publications). Specifically, we show that our subscription processing algorithms require O(logN) messages for a N-node network, and our event processing algorithms require O(l x logN) messages (with l being the average string length).Third, we develop algorithms for optimizing the processing of multi-dimensional events, involving several string attributes. Further to our analysis, we provide simulation-based experiments showing promising performance results in terms of number of messages, required bandwidth, load balancing, and response times.
Answering aggregation queries on hierarchical web sites using adaptive sampling
Authors: Foto N. Afrati, Paraskevas V. Lekeas, Chen Li
Venue: CIKM
Year: 2005

We study how to answer aggregation queries over hierarchical Web sites using adaptive sampling.
Predicting accuracy of extracting information from unstructured text collections
Authors: Eugene Agichtein, Silviu Cucerzan
Venue: CIKM
Year: 2005

Exploiting lexical and semantic relationships in large unstructured text collections can significantly enhance managing, integrating, and querying information locked in unstructured text. Most notably, named entities and relations between entities are crucial for effective question answering and other information retrieval and knowledge management tasks. Unfortunately, the success in extracting these relationships can vary for different domains, languages, and document collections. Predicting extraction performance is an important step towards scalable and intelligent knowledge management, information retrieval and information integration. We present a general language modeling method for quantifying the difficulty of information extraction tasks. We demonstrate the viability of our approach by predicting performance of real world information extraction tasks, Named Entity recognition and Relation Extraction.
Mining all maximal frequent word sequences in a set of sentences
Authors: Helena Ahonen-Myka
Venue: CIKM
Year: 2005

We present an efficient algorithm for finding all maximal frequent word sequences in a set of sentences. A word sequence s is considered frequent, if all its words occur in at least σ sentences and the words occur in each of these sentences in the same order as in s, given a frequency threshold σ. Hence, the words of a sequence s do not have to occur consecutively in the sentences.
Model-guided information discovery for intelligence analysis
Authors: Rafael Alonso, Hua Li
Venue: CIKM
Year: 2005

Intelligence analysis can be aided and guided by models of the analysts' interests and priorities. This paper describes our approach to analyst modeling as part of the Ant CAFÉ project, in which analyst models are used to guide the searching behavior of a swarm of intelligent agents. Structural elements of our analyst model include concepts and relations, both of which help to capture the analyst's current interest and concerns. In addition, the concepts and relationships have associated scalar parameters to provide a quantitative measure of the user's level of interest. We have developed algorithms for dynamically adapting the weights and evolving the elements of the model itself. To evaluate these algorithms we have built an Analyst Modeling Environment workbench. We have tested our approach on this workbench using traces generated by human analysts, and have demonstrated improvements over current state of the art search engines.
Learning to summarise XML documents using content and structure
Authors: Massih-Reza Amini, Anastasios Tombros, Nicolas Usunier, Mounia Lalmas, Patrick Gallinari
Venue: CIKM
Year: 2005

Documents formatted in eXtensible Markup Language (XML) are becoming increasingly available in collections of various document types. In this paper, we present an approach for the summarisation of XML documents. The novelty of this approach lies in that it is based on features not only from the content of documents, but also from their logical structure. We follow a machine learning like, sentence extraction-based summarisation technique. To find which features are more effective for producing summaries this approach views sentence extraction as an ordering task. We evaluated our summarisation model using the INEX dataset. The results demonstrate that the inclusion of features from the logical structure of documents increases the effectiveness of the summariser, and that the learnable system is also effective and well-suited to the task of summarisation in the context of XML documents.
Generalized contextualization method for XML information retrieval
Authors: Paavo Arvola, Marko Junkkari, Jaana Kekäläinen
Venue: CIKM
Year: 2005

A general re-weighting method, called contextualization, for more efficient element ranking in XML retrieval is introduced. Re-weighting is based on the idea of using the ancestors of an element as a context: if the element appears in a good context -- good interpreted as probability of relevance -- its weight is increased in relevance scoring; if the element appears in a bad context, its weight is decreased. The formal presentation of contextualization is given in a general XML representation and manipulation frame, which is based on utilization of structural indices. This provides a general approach independent of weighting schemas or query languages.Contextualization is evaluated with the INEX test collection. We tested four runs: no contextualization, parent, root and tower contextualizations. The contextualization runs were significantly better than no contextualization. The root contextualization was the best among the re-weighted runs.
A geometric interpretation and analysis of R-precision
Authors: Javed A. Aslam, Emine Yilmaz
Venue: CIKM
Year: 2005

Average precision and R-precision are two of the most commonly cited measures of overall retrieval performance, but their correlation, though well-known, has defied explanation. We recently devised a geometric interpretation of R-precision which suggests that under a reasonable set of assumptions, R-precision approximates the area under the precision-recall curve, as does average precision, thus explaining their correlation. In this paper, we consider these assumptions and our geometric interpretation of R-precision in order to further understand, and make reasonable use of, the information that R-precision provides. Given our geometric interpretation of R-precision, we show that R-precision is highly informative by demonstrating that it can be used to (1) accurately infer precision-recall curves, (2) accurately infer other measures of retrieval performance, and (3) devise new measures of retrieval performance. Through our analysis, we also state the conditions under which R-precision is informative.
Redundant documents and search effectiveness
Authors: Yaniv Bernstein, Justin Zobel
Venue: CIKM
Year: 2005

The web contains a great many documents that are content-equivalent, that is, informationally redundant with respect to each other. The presence of such mutually redundant documents in search results can degrade the user search experience. Previous attempts to address this issue, most notably the TREC novelty track, were characterized by difficulties with accuracy and evaluation. In this paper we explore syntactic techniques --- particularly document fingerprinting --- for detecting content equivalence. Using these techniques on the TREC GOV1 and GOV2 corpora revealed a high degree of redundancy; a user study confirmed that our metrics were accurately identifying content-equivalence. We show, moreover, that content-equivalent documents have a significant effect on the search experience: we found that 16.6% of all relevant documents in runs submitted to the TREC 2004 terabyte track were redundant.