410602
Using self-supervised word segmentation in Chinese information retrieval
We propose a self-supervised word-segmentation technique for Chinese information retrieval. This method combines the advantages of traditional dictionary based approaches with character based approaches, while overcoming many of their shortcomings. Experiments on TREC data show comparable performance to both the dictionary based and the character based approaches. However, our method is language independent and unsupervised, which provides a promising avenue for constructing accurate multilingual information retrieval systems that are flexible and adaptive.
11235220
Probability-Based Chinese Text Processing and Retrieval
We discuss the use of probability-based natural language processing for Chinese text retrieval. We focus on comparing different text extraction methods and probabilistic weighting methods. Several docu- ment processing methods and probabilistic weighting functions are presented. A number of experiments have been conducted on large standard text collections. We present the experimental results that com- pare a word-based text processing method with a character-based method. The experimental results also compare a number of term-weighting functions including both single-unit weighting and compound-unit weighting functions. Modern information retrieval (IR) systems should be able to take natural language queries and retrieve documents written in natural languages. One way to process nat- ural language texts in IR is statistical. In this approach, linguistic units are extracted from the documents and queries. Those units extracted from the documents are used to index the documents. Those extracted from a query are weighted according to their degrees of importance. The most important units are chosen as query terms. An infor- mation retrieval system takes the selected query terms, matches the terms with the indexes of documents, calculates a retrieval status value for each matched document using a term-weighting method, and presents the user with potentially relevant docu- ments from a collection of documents. The performance of the information retrieval system in identifying relevant documents greatly depends on the text processing method used. We investigate the effectiveness of different text extraction methods and different term weighting methods in the context of Chinese information retrieval. It is a well- known problem that there is no separator between Chinese words, so Chinese words cannot be used easily to index or search texts as is possible in English. Therefore, some people use characters or n-grams as searchable tokens instead of words. We discuss two text extraction methods. One extraction method uses words, compound words, and phrases in the document and query texts as indexing terms to represent the texts. We refer to this method as the word-based approach. For this approach, text segmentation, which divides both document and query texts into linguistic units, is regarded not only as a necessary precursor but also as a bottleneck of this kind of system (Wu and Tseng 1993). The other extraction method is based on single Chinese characters, in which texts are indexed by the characters appearing in the texts (Chen 1992). By using sin- gle character approaches, a search could be conducted for any multi-character word or phrase identified at search time, no matter whether this word or phrase is in the dic- tionary. Both word-based and character-based methods have been used in information
921552
Dynamic Web log session identification with statistical language models
We present a novel session identification method based on statistical language modeling. Unlike standard time-out methods, which use fixed time thresholds for session identification, we use an information theoretic approach that yields more robust results for identifying session boundaries. We evaluate our new approach by learning interesting association rules from the segmented session files. We then compare the performance of our approach to three standard session identification method--the standard timeout method, the reference length method, and the maximal forward reference method--and find that our statistical language modeling approach generally yields superior results. However, as with every method, the performance of our technique varies with changing parameter settings. Therefore, we also analyze the influence of the two key factors in our language-modeling-based approach: the choice of smoothing technique and the language model order. We find that all standard smoothing techniques, save one, perform well, and that performance is robust to language model order.
9414412
Concept-based biomedical text retrieval
One challenging problem for biomedical text retrieval is to find accurate synonyms or name variants for biomedical entities. In this paper, we propose a new concept-based approach to tackle this problem. In this approach, a set of concepts instead of keywords will be extracted from a query first. Then these concepts will be used for retrieval purpose. The experiment results show that the proposed approach can boost the retrieval performance and it generates very good results on 2005 TREC Genomics data sets.
28835634
A Distance-Based Algorithm for Clustering Database User Sessions
In this paper, we present a distance-based clustering algorithm for grouping database user sessions. The algorithm considers both local and global similarities between sessions and incorporates three distance metrics in the computation of the distance between two sessions. We describe the three metrics and discuss the rational for combining them. The algorithm is evaluated on two datasets. One is a clinic OLTP workload file and the other is the TPC-W benchmark. The evaluation results are reported.
14449557
Evaluation and automatic selection of methods for handling missing data
Real-world data often contain missing values. In this paper, nine different methods for handling missing data are described and compared. Thirty real-world datasets are used as input data in our experiment. Nine different missing levels are implemented in each training data set to investigate the performance of the methods at different missing levels. For evaluation, two different classification techniques, C4.5 and ELEM2, are applied to obtain the classification error rates. The experimental results show that different methods can have different effects on a data set. Based on the experimental results, we also propose a meta-learning approach to selecting a method for handling missing data. The evaluation results show that the meta-learning approach is effective in selecting a suitable method for handling missing data.
15814097
Language Independent Text Categorization
Text categorization is defined as the task of assigning pre-defined category labels to new documents. This paper proposes a language-independent text categorization model based on machine learning, and describes the feature extraction, classifier and evaluation method in detail. This model has been implemented on two news corpus of Chinese and Japanese and satisfactory categorization effectiveness has been achieved.
329318
The garbage collection advantage: improving program locality
As improvements in processor speed continue to outpace improvements in cache and memory speed, poor locality increasingly degrades performance. Because copying garbage collectors move objects, they have an opportunity to improve locality. However, no static copying order is guaranteed to match program traversal orders. This paper introduces <i>online object reordering</i> (OOR) which includes a new dynamic, online class analysis for Java that detects program traversal patterns and exploits them in a copying collector. OOR uses run-time method sampling that drives just-in-time (JIT) compilation. For each <i>hot</i> (frequently executed) method, OOR analysis identifies the hot field accesses. At garbage collection time, the OOR collector then copies referents of hot fields together with their parent. Enhancements include static analysis to exclude accesses in cold basic blocks, heuristics that decay heat to respond to phase changes, and a separate space for hot objects. The overhead of OOR is on average negligible and always less than 2% on Java benchmarks in Jikes RVM with MMTk. We compare program performance of OOR to static class-oblivious copying orders (e.g., breadth and depth first). Performance variation due to static orders is often low, but can be up to 25%. In contrast, OOR matches or improves upon the best static order since its history-based copying tunes memory layout to program traversal.
10668543
Parameterized Computation of LCS for Two Sequences
The problem of finding the longest common subsequence is a well-known optimization problem because of its applications, especially in bioinformatics. In this paper, by applying the techniques developed in parameterized computation, an efficient approach for the problem of finding the longest common subsequence of two sequences is presented. The parameterized approach is compared with the well-known dynamic programming approach for the problem. The parameterized approach is much more efficient, as is shown by the experimental results.
18862916
Clustering graphs for visualization via node similarities
Graph visualization is commonly used to visually model relations in many areas. Examples include Web sites, CASE tools, and knowledge representation. When the amount of information in these graphs becomes too large, users, however, cannot perceive all elements at the same time. A clustered graph can greatly reduce visual complexity by temporarily replacing a set of nodes in clusters with abstract nodes. This paper proposes a new approach to clustering graphs. The approach constructs the node similarity matrix of a graph that is derived from a novel metric of node similarity. The linkage pattern of the graph is thus encoded into the similarity matrix, and then one obtains the hierarchical abstraction of densely linked subgraphs by applying the k-means algorithm to the matrix. A heuristic method is developed to overcome the inherent drawbacks of the k-means algorithm. For clustered graphs we present a multilevel multi-window approach to hierarchically drawing them in different abstract level views with the purpose of improving their readability. The proposed approaches demonstrate good results in our experiments. As application examples, visualization of part of Java class diagrams and Web graphs are provided. We also conducted usability experiments on our algorithm and approach. The results have shown that the hierarchically clustered graph used in our system can improve user performance for certain types of tasks.
121152
Dynamic programming algorithms for restriction map comparison
For most sequence comparison problems there is a corresponding map comparison algorithm. While map data may appear to be incompatible with dynamic programming, we show in this paper that the rigor and efficiency of dynamic programming algorithms carry over to the map comparison algorithms. We present algorithms for restriction map comparison that deal with two types of map errors: (i) closely spaced sites for different enzymes can be ordered incorrectly, and (ii) closely spaced sites for the same enzyme can be mapped as a single site. The new algorithms are a natural extension of a previous map comparison model. Dynamic programming algorithms for computing optimal global and local alignments under the new model are described. The new algorithms take about the same order of time as previous map comparison algorithms. Programs implementing some of the new algorithms are used to find similar regions within the Escherichia coli restriction map of Kohara et al.