Abstract Many successful retrieval models are derived based on or conform to the probability ranking principle (PRP). We present a new derivation of a document ranking function given by the probability of relevance of a document, conforming to the PRP. Our formulation yields a family of retrieval models, called probabilistic binary relevance (PBR) models, with various instantiations obtained by different probability estimations. By extensive experiments on a range of TREC collections, improvement of the PBR models over some established baselines with statistical significance is observed, especially in the large Clueweb09 Cat‐B collection.

In Information Retrieval, numerous retrieval models or document ranking functions have been developed in the quest for better retrieval effectiveness. Apart from some formal retrieval models formulated on a theoretical basis, various recent works have applied heuristic constraints to guide the derivation of document ranking functions. While many recent methods are shown to improve over established and successful models, comparison among these new methods under a common environment is often missing. To address this issue, we perform an extensive and up-to-date comparison of leading term-independence retrieval models implemented in our own retrieval system. Our study focuses on the following questions: (RQ1) Is there a retrieval model that consistently outperforms all other models across multiple collections; (RQ2) What are the important features of an effective document ranking function? Our retrieval experiments performed on several TREC test collections of a wide range of sizes (up to the terabyte-sized Clueweb09 Category B) enable us to answer these research questions. This work also serves as a reproducibility study for leading retrieval models. While our experiments show that no single retrieval model outperforms all others across all tested collections, some recent retrieval models, such as MATF and MVD, consistently perform better than the common baselines.

In this article, we present a novel principled approach to passage-based (document) retrieval using fuzzy set theory. The approach formulates passage score combination according to general relevance decision principles. By operationalizing these principles using aggregation operators of fuzzy set theory, our approach justifies the common heuristics of taking the maximum constituent passage score as the overall document score. Experiments show that this heuristics is only the near best, with some fuzzy set aggregation operators stipulated in our approach being better methods. The significance of our principled approach is the applicability of many passage score combination methods, potentially bringing further performance enhancement. Experiments on several text retrieval conference collections demonstrate that our approach performs significantly better than document-based retrieval. While recent works in the literature mostly employ document-based rather than passage-based retrieval due to the common conception that document length normalization solves the problem of varying document lengths, our results show that document length normalization alone is not sufficient, especially in pseudo-relevance feedback retrieval.

Feature engineering is one aspect of knowledge engineering. Besides feature selection, the appropriate assignment of feature values is also crucial to the performance of many software applications, such as text categorization (TC) and speech recognition. In this work, we develop a general method to enhance TC performance by the use of context-dependent feature values (aka term weights), which are obtained by a novel adaptation of a context-dependent adjustment procedure previously shown to be effective in information retrieval. The motivation of our approach is that the general method can be used with different text representations and in combination of other TC techniques. Experiments on several test collections show that our context-dependent feature values can improve TC over traditional context-independent unigram feature values, using a strong classifier like Support Vector Machine (SVM), which past works have found to be hard to improve. We also show that the relative performance improvement of our method over the context-independent baseline is comparable to the levels attained by recent word embedding methods in the literature, while an advantage of our approach is that it does not require the substantial training needed to learn word embedding representations.

Model construction is a kind of knowledge engineering, and building retrieval models is critical to the success of search engines. This article proposes a new (retrieval) language model, called binary independence language model (BILM). It integrates two document-context based language models together into one by the log-odds ratio where these two are language models applied to describe document-contexts of query terms. One model is based on relevance information while the other is based on the non-relevance information. Each model incorporates link dependencies and multiple query term dependencies. The probabilities are interpolated between the relative frequency and the background probabilities. In a simulated relevance feedback environment of top 20 judged documents, our BILM performed statistically significantly better than the other highly effective retrieval models at 95% confidence level across four TREC collections using fixed parameter values for the mean average precision. For the less stable performance measure (i.e. precision at the top 10), no statistical significance is shown between the different models for the individual test collections although numerically our BILM is better than two other models with a confidence level of 95% based on a paired sign test across the test collections of both relevance feedback and retrospective experiments.

Numerous past studies have demonstrated the effectiveness of therelevance model(RM) for information retrieval (IR). This approach enables relevance or pseudo‐relevance feedback to be incorporated within the language modeling framework ofIR. In the traditionalRM, the feedback information is used to improve the estimate of thequerylanguage model. In this article, we introduce an extension ofRMin the setting of relevance feedback. Our method provides an additional way to incorporate feedback via the improvement of thedocumentlanguage models. Specifically, we make use of the context information of known relevant and nonrelevant documents to obtain weighted counts of query terms for estimating the document language models. The context information is based on the words (unigrams or bigrams) appearing within a text window centered on query terms. Experiments on several Text REtrieval Conference (TREC)collections show that our context‐dependent relevance model can improve retrieval performance over the baselineRM. Together with previous studies within theBM25 framework, our current study demonstrates that the effectiveness of our method for using context information inIRis quite general and not limited to any specific retrieval model.

The inverted index is the dominant indexing method in information retrieval systems. It enables fast return of the list of all documents containing a given query term. However, for retrieval schemes involving query expansion, as in pseudo-relevance feedback (PRF), the retrieval time based on an inverted index increases linearly with the number of expansion terms. In this regard, we have examined the use of a forward index , which consists of the mapping of each document to its constituent terms. We propose a novel forward index-based reranking scheme to shorten the PRF retrieval time. In our method, a first retrieval of the original query is performed using an inverted index, and then a forward index is employed for the PRF part. We have studied several new forward indexes, including using a novel spstring data structure and the weighted variable bit-block compression (wvbc) signature. With modern hardware such as solid-state drives (SSDs) and sufficiently large main memory, forward index methods are particularly promising. We find that with the whole index stored in main memory, PRF retrieval using a spstring or wvbc forward index excels in time efficiency over an inverted index, being able to obtain the same levels of performance measures at shorter times.

While term independence is a widely held assumption in most of the established information retrieval approaches, it is clearly not true and various works in the past have investigated a relaxation of the assumption. One approach is to use n‐grams in document representation instead of unigrams. However, the majority of early works on n‐grams obtained only modest performance improvement. On the other hand, the use of information based on supporting terms or “contexts” of queries has been found to be promising. In particular, recent studies showed that using new context‐dependent term weights improved the performance of relevance feedback (RF) retrieval compared with using traditional bag‐of‐words BM25 term weights. Calculation of the new term weights requires an estimation of the local probability of relevance of each query term occurrence. In previous studies, the estimation of this probability was based on unigrams that occur in the neighborhood of a query term. We explore an integration of the n‐gram and context approaches by computing context‐dependent term weights based on a mixture of unigrams and bigrams. Extensive experiments are performed using the title queries of the Text Retrieval Conference (TREC)‐6, TREC‐7, TREC‐8, and TREC‐2005 collections, for RF with relevance judgment of either the top 10 or top 20 documents of an initial retrieval. We identify some crucial elements needed in the use of bigrams in our methods, such as proper inverse document frequency (IDF) weighting of the bigrams and noise reduction by pruning bigrams with large document frequency values. We show that enhancing context‐dependent term weights with bigrams is effective in further improving retrieval performance.

Abstract We studied the effectiveness of a new class of context‐dependent term weights for information retrieval. Unlike the traditional term frequency–inverse document frequency (TF–IDF), the new weighting of a term t in a document d depends not only on the occurrence statistics of t alone but also on the terms found within a text window (or “document‐context”) centered on t. We introduce a Boost and Discount (B&D) procedure which utilizes partial relevance information to compute the context‐dependent term weights of query terms according to a logistic regression model. We investigate the effectiveness of the new term weights compared with the context‐independent BM25 weights in the setting of relevance feedback. We performed experiments with title queries of the TREC‐6, ‐7, ‐8, and 2005 collections, comparing the residual Mean Average Precision (MAP) measures obtained using B&D term weights and those obtained by a baseline using BM25 weights. Given either 10 or 20 relevance judgments of the top retrieved documents, using the new term weights yields improvement over the baseline for all collections tested. The MAP obtained with the new weights has relative improvement over the baseline by 3.3 to 15.2%, with statistical significance at the 95% confidence level across all four collections.

Given a set of clusters, we consider an optimization problem which seeks a subset of clusters that maximizes the microaverage F-measure. This optimal value can be used as an evaluation measure of the goodness of clustering. For arbitrarily overlapping clusters, finding the optimal value is NP-hard. We claim that a greedy approximation algorithm yields the global optimal solution for clusters that overlap only by nesting. We present a mathematical proof of this claim by induction. For a family of n clusters containing a total of N objects, this algorithm has an {\rm O}(n;{2}) time complexity and O(N) space complexity.

A new principles framework is presented for retrieval evaluation of ranked outputs. It applies decision theory to model relevance decision preferences and shows that the Probability Ranking Principle (PRP) specifies optimal ranking. It has two new components, namely a probabilistic evaluation model and a general measure of retrieval effectiveness. Its probabilities may be interpreted as subjective or objective ones. Its performance measure is the expected weighted rank which is the weighted average rank of a retrieval list. Starting from this measure, the expected forward rank and some existing retrieval effectiveness measures (e.g., top n precision and discounted cumulative gain) are instantiated using suitable weighting schemes after making certain assumptions. The significance of these instantiations is that the ranking prescribed by PRP is shown to be optimal simultaneously for all these existing performance measures. In addition, the optimal expected weighted rank may be used to normalize the expected weighted rank of retrieval systems for (summary) performance comparison (across different topics) between systems. The framework also extends PRP and our evaluation model to handle graded relevance, thereby generalizing the discussed, existing measures (e.g., top n precision) and probabilistic retrieval models for graded relevance.

Abstract We propose a new optimal clustering effectiveness measure, called CS1, based on a combination of clusters rather than selecting a single optimal cluster as in the traditional MK1 measure. For hierarchical clustering, we present an algorithm to compute CS1, defined by seeking the optimal combinations of disjoint clusters obtained by cutting the hierarchical structure at a certain similarity level. By reformulating the optimization to a 0‐1 linear fractional programming problem, we demonstrate that an exact solution can be obtained by a linear time algorithm. We further discuss how our approach can be generalized to more general problems involving overlapping clusters, and we show how optimal estimates can be obtained by greedy algorithms.

Abstract A dialogue‐based interface for information systems is considered a potentially very useful approach to information access. A key step in computer processing of natural‐language dialogues is dialogue‐act (DA) recognition. In this paper, we apply a feature‐based classification approach for DA recognition, by using the maximum entropy (ME) method to build a classifier for labeling utterances with DA tags. The ME method has the advantage that a large number of heterogeneous features can be flexibly combined in one classifier, which can facilitate feature selection. A unique characteristic of our approach is that it does not need to model the prior probability of DAs directly, and thus avoids the use of a discourse grammar. This simplifies the implementation of the classifier and improves the efficiency of DA recognition, without sacrificing the classification accuracy. We evaluate the classifier using a large data set based on the Switchboard corpus. Encouraging performance is observed; the highest classification accuracy achieved is 75.03%. We also propose a heuristic to address the problem of sparseness of the data set. This problem has resulted in poor classification accuracies of some DA types that have very low occurrence frequencies in the data set. Preliminary evaluation shows that the method is effective in improving the macroaverage classification accuracy of the ME classifier.

In an ad-hoc retrieval task, the query is usually short and the user expects to find the relevant documents in the first several result pages. We explored the possibilities of using Wikipedia's articles as an external corpus to expand ad-hoc queries. Results show promising improvements over measures that emphasize on weak queries.

This paper presents a new perspective of the probability ranking principle (PRP) by defining retrieval effectiveness in terms of our novel expected rank measure of a set of documents for a particular query. This perspective is based on preserving decision preferences, and it imposes weaker conditions on PRP than the utility-theoretic perspective of PRP.

This paper presents a pilot study of query-specific clustering that uses our novel document-context based similarity scores as compared with document similarity scores. Clustering is applied to the top 1000 retrieved documents for a given query. Clustering effectiveness is evaluated based on the MK1 score for TREC-2, TREC-6 and TREC-7 test collections. Encouraging results were obtained whereby document-context clustering produces better MK1 scores than document clustering with a 95% confidence level if precision and recall are equally important.

This paper presents our novel relevance feedback (RF) algorithm that uses the probabilistic document-context based retrieval model with limited relevance judgments for document re-ranking. Probabilities of the document-context based retrieval model are estimated from the top N (=20) documents in the initial retrieval. We use document-context based cosine similarity measure to find similar data for better probability estimation in order to reduce the data scarcity problem and the negative weighting problem. Our RF algorithm is promising because its mean average precision is statistically significantly better than the baseline using TREC-6 and TREC-7 data collections.

The vector space model (VSM) is one of the most widely used information retrieval (IR) models in both academia and industry. It was less effective at the Chinese ad hoc retrieval tasks than other retrieval models in the NTCIR-3 evaluation workshop, but comparable to those in the NTCIR-4 and NTCIR-5 workshops. We do not know whether the lower level performance was due to the VSM's inherent deficiencies or to a less effective normalization of document length. Hence we evaluated the VSM with various pivoted normalizations of document length using the NTCIR-3 collection for confirmation. We found that VSM's retrieval effectiveness with pivoted normalization was comparable to other competitive retrieval models (for example, 2-Poisson), and that VSM's retrieval speed with pivoted normalization was similar to competitive retrieval models (2-Poisson). We proposed a novel adaptive scheme that automatically estimates the (near) best parameters for pivoted document-length normalization based on query size; the new normalization is called adaptive pivoted document-length normalization . This scheme achieved good retrieval effectiveness, sometimes for short (title) queries and sometimes for long queries, without manually adjusting parameter values. We found that unique, adaptive pivoted normalization can enhance fixed pivoted normalizations for different test collections (TREC-5 and TREC-6). We also evaluated the VSM with the adaptive pivoted normalization using the pseudo-relevance feedback (PRF) and found that this type of VSM performs similarly to the competitive retrieval models (2-Poisson) with PRF. Hence, we conclude that the VSM with unique (adaptive) pivoted document-length normalization is effective for Chinese IR and that its retrieval effectiveness is comparable to that of other competitive retrieval models with or without PRF for the reference test collections used in this evaluation.

SB-Tree is a binary tree data structure proposed to represent time series according to the importance of data points. Its use in stock data management is distinguished by preserving the critical data points' attribute values, retrieving time series data according to the importance of data points and facilitating multi-resolution time series retrieval. As new stock data are available continuously, an effective updating mechanism for SB-Tree is needed. In this paper, a study of different updating approaches is reported. Three families of updating methods are proposed. They are periodic rebuild, batch update and point-by-point update. Their efficiency, effectiveness and characteristics are compared and reported.

We propose a novel probabilistic retrieval model which weights terms according to their contexts in documents. The term weighting function of our model is similar to the language model and the binary independence model. The retrospective experiments (i.e., relevance information is present) illustrate the potential of our probabilistic context-based retrieval where the precision at the top 30 documents is about 43% for TREC-6 data and 52% for TREC-7 data.

Language modeling is a current research topic in many domains including speech recognition, optical character recognition, handwriting recognition, machine translation and spelling correction. There are two main types of language models, the mathematical and the linguistic. The most widely used mathematical language model is the n-gram model inferred from statistics. This model has three problems: long distance restriction, recursive nature and partial language understanding. Language models based on linguistics present many difficulties when applied to large scale real texts. We present here a new hybrid language model that combines the advantages of the n-gram statistical language model with those of a linguistic language model which makes use of grammatical or semantic rules. Using suitable rules, this hybrid model can solve problems such as long distance restriction, recursive nature and partial language understanding. The new language model has been effective in experiments and has been incorporated in Chinese sentence input products for Windows and Macintosh OS.

A load balancing scheme is presented which allows HTTP requests to be dynamically migrated between clustered back-end Web servers based on the loading condition of the system. We adopt a nearest neighborhood clustering algorithm whereby an adaptive number of requests are migrated as determined by the real-time distribution of load among the servers. Experiment results demonstrate that our proposed algorithm yields the best performance when compared with several other common approaches.

Beside their original functions, mobile devices are now enabled with increasing computational power and wireless communication technology that can facilitate many different applications. One valuable application is about the mobile access of financial data and a major task involved is to provide the historical stock price movement so that the market players can make appropriate investment decisions. However, due to the limitations of this new environment (e.g. screen size, bandwidth for data exchange, storage and computational power), adaptation is needed for time series visualization. In this paper, a progressive time series visualization method, with additional compression ability, for the mobile environment is proposed. The proposed method is based on a perceptually important point (PIP) identification scheme so that the time series data points can be disseminated in the order of importance for the changing (data access) requirements. The application of the proposed method to stock price time series visualization in mobile devices is demonstrated.

Time series data, due to their numerical and continuous nature, are difficult to process, analyze, and mine. However, these tasks become easier when the data can be transformed into meaningful symbols. Most recent works on time series only address how to identify a given pattern from a time series and do not consider the problem of identifying a suitable set of time points for segmenting the time series in accordance with a given set of pattern templates (e.g., a set of technical patterns for stock analysis). However, the use of fixed-length segmentation is an oversimplified approach to this problem; hence, a dynamic approach (with high controllability) is preferable so that the time series can be segmented flexibly and effectively according to the needs of the users and the applications. In view of the fact that this segmentation problem is an optimization problem and evolutionary computation is an appropriate tool to solve it, we propose an evolutionary time series segmentation algorithm. This approach allows a sizeable set of pattern templates to be generated for mining or query. In addition, defining similarity between time series (or time series segments) is of fundamental importance in fitness computation. By identifying the perceptually important points directly from the time domain, time series segments and templates of different lengths can be compared and intuitive pattern matching can be carried out in an effective and efficient manner. Encouraging experimental results are reported from tests that segment both artificial time series generated from the combinations of pattern templates and the time series of selected Hong Kong stocks.

Abstract In certain bilingual and multi‐lingual societies, translated legal documents are as important as the original legal documents because they have the same legal status as the originals. However, there is little reported work on the retrieval and management of bilingual legal documents. We describe the design and development of a bilingual document retrieval and management prototype, called ELDoS, which is used by court interpreters and judges from the Hong Kong Judiciary. Since the speed of retrieval is a major concern for user acceptance, and therefore for widespread deployment of the system, the architecture of the prototype is designed to balance the workload of the client and server. Extensible Markup Language (XML) is used to mark up the bilingual legal documents for a variety of document retrieval and management tasks. XML enables the use of XML Stylesheet Language Transformation (XSLT) to align bilingual data in the client, instead of the server, and improve alignment speed linearly with respect to the size of the document, using a high‐end PC, when the server has no concurrent access. The design of the interface was continually improved after extensive consultation with court interpreters and after the user acceptance tests. In our evaluation, the facilities for highlighting translated terms have a macro‐averaged precision of 90+% and a macro‐average recall of 80+%, which were considered acceptable by our users. We believe that the experience in the design and development of this prototype is applicable to other language pairs as well as to other domains. Copyright © 2002 John Wiley & Sons, Ltd.

Abstract This paper describes the design and development of a computer interface for blind and visually‐impaired users, who are native speakers of Cantonese (i.e. a Chinese dialect). Apart from enabling the interface to (1) produce Chinese voice output, (2) convert Chinese characters to Braille codes, (3) facilitate Chinese Braille input, and (4) operate in a Microsoft Chinese Windows environment, the significant aspects of this paper include the following: (1) the description of an integrated architecture, which can be used for other languages; (2) a general bilingual Braille input mechanism; (3) a sentence‐based input method that can be used for contracted‐Braille‐to‐text conversion with an error rate of about 6%, operating at about 700 characters/second using a Pentium II 300 MHz PC; (4) a code‐mixed synthesis module for general bilingual and multilingual applications; (5) the potential to directly adopt the system for use with other ideographic languages (like Japanese and Korean), as well as agglutinating languages like Finnish and Turkish, which have no space between words. Copyright © 2003 John Wiley & Sons, Ltd.

Stock data in the form of multiple time series are difficult to process, analyze and mine. However, when they can be transformed into meaningful symbols like technical patterns, it becomes easier. Most recent work on time series queries concentrates only on how to identify a given pattern from a time series. Researchers do not consider the problem of identifying a suitable set of time points for segmenting the time series in accordance with a given set of pattern templates (e.g., a set of technical patterns for stock analysis). On the other hand, using fixed length segmentation is a primitive approach to this problem; hence, a dynamic approach (with high controllability) is preferred so that the time series can be segmented flexibly and effectively according to the needs of users and applications. In view of the fact that such a segmentation problem is an optimization problem and evolutionary computation is an appropriate tool to solve it, we propose an evolutionary time series segmentation algorithm. This approach allows a sizeable set of stock patterns to be generated for mining or query. In addition, defining the similarity between time series (or time series segments) is of fundamental importance in fitness computation. By identifying perceptually important points directly from the time domain, time series segments and templates of different lengths can be compared and intuitive pattern matching can be carried out in an effective and efficient manner. Encouraging experimental results are reported from tests that segment the time series of selected Hong Kong stocks.

Abstract XML holds the promise to yield (1) a more precise search by providing additional information in the elements, (2) a better integrated search of documents from heterogeneous sources, (3) a powerful search paradigm using structural as well as content specifications, and (4) data and information exchange to share resources and to support cooperative search. We survey several indexing techniques for XML documents, grouping them into flat‐file, semistructured, and structured indexing paradigms. Searching techniques and supporting techniques for searching are reviewed, including full text search and multistage search. Because searching XML documents can be very flexible, various search result presentations are discussed, as well as database and information retrieval system integration and XML query languages. We also survey various retrieval models, examining how they would be used or extended for retrieving XML documents. To conclude the article, we discuss various open issues that XML poses with respect to information retrieval and database research.

With the advent of the Internet and intranets, substantial interest is being shown in Asian language information retrieval; especially in Chinese, which is a good example of an Asian ideographic language (other examples include Japanese and Korean). Since, in this type of language, spaces do not delimit words, an important issue is which index terms should be extracted from documents. This issue also has wider implications for indexing other languages such as agglutinating languages (e.g., Finnish and Turkish), archaic ideographic languages like Egyptian hieroglyphs, and other types of information such as data stored in genomic databases. Although comparisons of indexing strategies for Chinese documents have been made, almost all of them are based on a single retrieval model. This article compares the performance of various combinations of indexing strategies (i.e., character, word, short-word, bigram, and Pircs indexing) and retrieval models (i.e., vector space, 2-Poisson, logistic regression, and Pircs models). We determine which model (and its parameters) achieves the (near) best retrieval effectiveness without relevance feedback, and compare it with the open evaluations (i.e., TREC and NTCIR) for both long and title queries. In addition, we describe a more extensive investigation of retrieval efficiency. In particular, the storage cost of word indexing is only slightly more than character indexing, and bigram indexing is about double the storage cost of other indexing strategies. The retrieval time typically varies linearly with the number of unique terms in the query, which is supported by correlation values above 90%. The Pircs retrieval system achieves robust and good retrieval performance, but it appears to be the slowest method, whereas vector space models were not very effective in retrieval, but were able to respond quickly. For robust, near-best retrieval effectiveness, without considering storage overhead, the 2-Poisson model using bigram indexing appears to be a good compromise between retrieval effectiveness and efficiency for both long and title queries.

Time series data are difficult to manipulate. When they can be transformed into meaningful symbols, it becomes an easy task to query and understand them. While most recent works in time series query only concentrate on how to identify a given pattern from a time series, they do not consider the problem of identifying a suitable set of time points based upon which the time series can be segmented in accordance with a given set of pattern templates, e.g., a set of technical analysis patterns for stock analysis. On the other hand, using fixed length segmentation is only a primitive approach to such kind of problem and hence a dynamic approach is preferred so that the time series can be segmented flexibly and effectively. In view of the fact that such a segmentation problem is actually an optimization problem and evolutionary computation is an appropriate tool to solve it, we propose an evolutionary segmentation algorithm in this paper. Encouraging experimental results in segmenting the Hong Kong Hang Seng Index using 22 technical analysis patterns are reported.

A directed acyclic word graph (DAWG) represents all factors of a string t over σ. By some isomorphism h : Σ* → (σq)*, the string t can be transformed into h(t), the factors of which are represented by another DAWG, called the morphic DAWG, over a different alphabet σ. Depending on h, t has many morphic DAWGs, which exhibit time-space trade-off compared with the original DAWG. The bounds for storage reduction and time-space efficiency between DAWG and its morphic DAWGs implemented as tables are derived, as well as for their optimal points. Likewise, the storage increases, comparing the morphic DAWG implemented as tables and DAWGs implemented using bucket arrays, are also derived. The bounds of storage increase have global minimum when |σ| = 3. Experiments show that round-off errors degrade storage reduction and time-space efficiency, so that q should be well chosen (i.e.|σ| q = |Σ|). The compact morphic DAWG was found to be more space efficient than both the corresponding morphic DAWG and the compact DAWG. The compact morphic DAWGs over the binary alphabet require the least storage but the access speed is slower than those over the ternary alphabet. The space demand of compact morphic DAWGs is of similar order (within a factor of 3.3) of the bucket-array implementation of DAWGs.

The author explores the use of tries to represent tries. A morphic trie image is a trie that represents a set of transformed keywords using an isomorphism h:/spl Sigma/*/spl rarr/(/spl sigma//sup q/)*. Morphic trie images using tenary alphabets achieve near optimal performances but approximation errors degrade their performances. A condition which determines whether tenary or bit tries should be used is found. Even though bit tries have better storage reduction in some cases, tenary tries access faster than bit tries. We show that the morphic trie images use less space than minimal prefix tries. If morphic trie images were compressed to form minimal prefix tries, then the total storage reduction is the product of the two. Approximation errors have no effect on minimal prefix tries.

The bigram language models are popular, in much language processing applications, in both Indo-European and Asian languages. However, when the language model for Chinese is applied in a novel domain, the accuracy is reduced significantly, from 96% to 78% in our evaluation. We apply pattern recognition techniques (i.e. Bayesian, decision tree and neural network classifiers) to discover language model errors. We have examined 2 general types of features: model-based and language-specific features. In our evaluation, Bayesian classifiers produce the best recall performance of 80% but the precision is low (60%). Neural network produced good recall (75%) and precision (80%) but both Bayesian and Neural network have low skip ratio (65%). The decision tree classifier produced the best precision (81%) and skip ratio (76%) but its recall is the lowest (73%).

This paper investigates (1) the robustness of epoch detection (i.e. identification of glottal closure) by the wavelet transform and (2) the methods to improve its robustness. We achieved a similar identification performance (2% error rate) to earlier investigation using the spline wavelet transform, under Gaussian noise degradation. However, the performance under other types of noise degradation, such as periodic noise (e.g. traffic lights) and short noise (e.g. keyboard noise), is not as robust as before. The scale matching technique could not secure good performance because the spline wavelet has poor recall performance. We explored the use of the Gaussian wavelet transform. Instead of scale matching, a single level is used and the recall of epochs associated with the nearest laryngograph differences by the Gaussian wavelet is about 30% more than by the spline wavelet, across different types of noise degradation. However, the spline wavelet has less false alarm (29% on average) in identification and the peaks correspond well to epoch positions (with less [standard] deviation). We evaluated detection schemes using both scalograms of Gaussian and spline wavelets and achieved improvement of recall (26%), with a relative position consistency of 1.4 ms.

A β heap, after D. B. Johnson, corresponds to an M-ary tree with a branch factor β where every vertex of the tree satisfies the heap property. The β heap was also known as the generalized heap and R-ary heap. In this paper, we prove that the address scheme in previous work is compact and correct. We investigated the global optimal values of β for sift-up, insert, delete-min, make heap and heapsort operations. Although closed form solutions for the global optimal values of β cannot be found, we prove that a (unique) global optimum solution exists for most cases and the equality conditions for optimal values of β are determined. Experiments show that the global optimal value of β for heapsort is approximately 4, which is theoretically a (near) optimal solution for all practical purposes. We show that the β heapsort performance is sensitive to the implementation of heap maintenance and we demonstrate that the speed-up of heap maintenance by microcodes can be achieved using high-level constructs. The speed-up in heapsort between β = 4 and 2 (i.e. binary) is between 10% and 30% where quicksort remains the fastest. If the main concern is the worst-case time complexity and exchange operations are taken into account, a β (=4) heapsort would be a suitable choice for all practical purposes.

This paper describes a modification to, and a fast implementation of the Viterbi algorithm for use in stochastic letter-to-phoneme conversion. A straightforward (but unrealistic) implementation of the Viterbi (1967) algorithm has a linear time complexity with respect to the length of the letter string, but quadratic complexity if we additionally consider the number of letter-to-phoneme correspondences to be a variable determining the problem size. Since the number of correspondences can be large, processing time is long. If the correspondences are precompiled to a deterministic finite-state automaton to simplify the process of matching to determine state survivors, execution time is reduced by a large multiplicative factor. Speed-up is inferred indirectly since the straightforward implementation of Viterbi decoding is too slow for practical comparison, and ranges between about 200 and 4000 depending upon the number of letters processed and the particular correspondences employed in the transduction. Space complexity is increased linearly with respect to the number of states of the automaton. This work has implications for fast, efficient implementation of a variety of speech and language engineering systems.

An algorithm for inferring correspondences between letters and phonemes from a large set of word spellings and their associated phonemic forms is described. The algorithm uses two techniques to infer correspondences: delimiting and dynamic time warping (DTW). The first technique delimits the part of the word spelling and pronunciation that cannot be aligned with the existing set of correspondences. The second technique derives correspondences from the delimited part of that word. The inferred correspondences are evaluated in terms of translation performance tested with unseen words, proper names and novel words. The translation performance is compared with those obtained using the manually driven correspondences as the benchmark. Nonparametric statistical tests are used to establish whether the performances of inferred correspondences are significantly different from the manually derived correspondences.>

An inference algorithm to obtain letter-phoneme correspondences for English using image-processing techniques is described. The main idea of the inference algorithm is to construct a table of association indices. The table is regarded as an image and image-processing algorithms are use to derive letter-phoneme correspondences. The advantages of the technique are that the association index has a theoretical basis in terms of modeling spelling and pronunciation as a homogeneous Markov chain, computational demand is low, and the inference process is not dependent on the ordering of the sample. The authors have implemented both a thresholding and a minimum spanning tree technique to derive correspondences. Illustrative examples are given for each technique.>