The main goal of this thesis is to investigate the complexity of a variety of problems related to text indexing and text searching. We present new data structures that can be used as building blocks for full-text indices which occupies minute space (FM-indexes) and wavelet trees. These data structures also can be used to represent labeled trees and posting lists. Labeled trees are applied in XML documents, and posting lists in search engines. The main emphasis of this thesis is on lower bounds for time-space tradeoffs for the following problems: the rank/select problem, the problem of representing a string of balanced parentheses, the text retrieval problem, the problem of computing a permutation and its inverse, and the problem of representing a binary relation. These results are divided in two groups: lower bounds in the cell probe model and lower bounds in the indexing model. The cell probe model is the most natural and widely accepted framework for studying data structures. In this model, we are concerned with the total space used by a data structure and the total number of accesses (probes) it performs to memory, while computation is free of charge. The indexing model imposes an additional restriction on the storage: the object in question must be stored in its raw form together with a small index that facilitates an efficient implementation of a given set of queries, e.g. finding rank, select, matching parenthesis, or an occurrence of a given pattern in a given text (for the text retrieval problem). We propose a new technique for proving lower bounds in the indexing model and use it to obtain lower bounds for the rank/select problem and the balanced parentheses problem. We also improve the existing techniques of Demaine and Lopez-Ortiz using compression and present stronger lower bounds for the text retrieval problem in the indexing model. The most important result of this thesis is a new technique for cell probe lower bounds. We demonstrate its strength by proving new lower bounds for the problem of representing permutations, the text retrieval problem, and the problem of representing binary relations. (Previously, there were no non-trivial results known for these problems.) In addition, we note that the lower bounds for the permutations problem and the binary relations problem are tight for a wide range of parameters, e.g. the running time of queries, the size and density of the relation.

Fire plays an important role in forest ecosystem management depending on the dual character of it. It should be managed and supervised effectively. In this particular study, the study area was located in the north part of Gävleborg County in Sweden, which is in a high- latitude region. Seven factors, divided into natural factors and human caused factors, were extracted from digital elevation model (DEM), classified land use map and feature shape files provided by National Land Survey of Sweden (Lantmäteriet). Two different weighting schemes for the factors were determined by the Analytic Hierarchy Process (AHP) method. With the help of ArcGIS 9.3 and Erdas 9.3, two classified result maps were obtained, where forest fire risk ranks were shown as five classes, very low, low, moderate, high and very high. The 43 fire incidents in the year 2007 and 2008 recorded by Global Fire Management System were used to evaluate the results. The results show that the higher rank the region is, the larger is the probability for forest fire risk and higher the risk to spread the fire. Furthermore, according to the occurrence time of the fire incidents, the period of time from end of May to beginning of June was generalized as a dangerous period for forest fire risk in this study area. After analyzing and discussing, even if there might be some uncertainties caused by variable selection, resolution problem and weighting schemes, the results were generally reliable.

We obtain a tight upper bound for the genus of a partition, and calculate the number of partitions of maximal genus. The generating series for genus zero and genus one rooted hypermonopoles is obtained in closed form by specializing the genus series for hypermaps. We discuss the connection between partitions and rooted hypermonopoles, and suggest how a generating series for genus one partitions may be obtained via the generating series for genus one rooted hypermonopoles. An involution on the poset of genus one partitions is constructed from the associated hypermonopole diagrams, showing that the poset is rank-symmetric. Also, a symmetric chain decomposition is constructed for the poset of genus one partitions, which consequently shows that it is strongly Sperner.

This thesis develops a semiunification-based type inference procedure for the rank 2 fragment of System F, with an emphasis on practical considerations for the adoption of such a procedure into existing programming languages. Current semiunification-based rank 2 inference procedures (notably that of Kfoury and Wells) are limited in several ways, which hinder their use in real-world settings. First of all, the translation from an instance of the type inference problem to an instance of the semiunification problem (SUP) is indirect; in particular, because of a series of source-level transformations that take place before translation, the translation is not syntax-directed. As a result, type errors discovered during the semiunification process cannot be cleanly translated back to specific subexpressions of the source program that caused the error. Also, because the rank 2 fragment of System F lacks a principal types property, an inference procedure cannot output a single type that encompasses all of a given term's derivable types. The procedure must therefore either rely on user assistance to produce the right type, or simply choose arbitrarily one of the given term's possible types. The algorithm of Kfoury and Wells in particular makes degenerate type assumptions in the absence of user assistance, and consequently produces types that are of no practical use. We build up our system in stages; we begin by improving the SUP translation. Whereas termination for the Kfoury-Wells rank 2 inference procedure is assured by translating terms into instances of the acyclic semiunification problem (a decidable subset of SUP, which is undecidable in general), we formulate and target the R-acyclic semiunification problem---a larger decidable subset of SUP that facilitates a more concise translation from source terms. We next eliminate the source-level transformation of terms, in order to formulate a truly syntax-directed translation from a source term to a set of SUP-like constraints. In doing so, we find that even the full SUP itself is not sufficiently equipped to support such a translation. We formulate USUP, a superset of SUP that incorporates a new class of identifier we call an unknown. We formulate decidable subsets of USUP, and then formulate a truly syntax-directed translation from source terms into USUP, with guaranteed termination. Finally, to address the principal types problem, we introduce a notation for types in which we allow a particular class of variable to stand for type constructors, rather than ordinary types (an idea based on the so-called third-order lambda-calculus). We show that, with third-order types we can not only output large sets of useful types for a given term, without programmer assistance, but the types we output also generalize over more System F types than any type within System F itself can do, and still be a valid type for the source term. Thus, our system increases opportunities for separate compilation and code reuse beyond any existing system of which we are aware. Our system is sound, though incomplete in certain well-characterized ways, despite which our system performs exactly as one would hope on a variety of examples, which we illustrate in this thesis.

The main goal of this thesis is to investigate the complexity of a variety of problems related to text indexing and text searching. We present new data structures that can be used as building blocks for full-text indices which occupies minute space (FM-indexes) and wavelet trees. These data structures also can be used to represent labeled trees and posting lists. Labeled trees are applied in XML documents, and posting lists in search engines. The main emphasis of this thesis is on lower bounds for time-space tradeoffs for the following problems: the rank/select problem, the problem of representing a string of balanced parentheses, the text retrieval problem, the problem of computing a permutation and its inverse, and the problem of representing a binary relation. These results are divided in two groups: lower bounds in the cell probe model and lower bounds in the indexing model. The cell probe model is the most natural and widely accepted framework for studying data structures. In this model, we are concerned with the total space used by a data structure and the total number of accesses (probes) it performs to memory, while computation is free of charge. The indexing model imposes an additional restriction on the storage: the object in question must be stored in its raw form together with a small index that facilitates an efficient implementation of a given set of queries, e.g. finding rank, select, matching parenthesis, or an occurrence of a given pattern in a given text (for the text retrieval problem). We propose a new technique for proving lower bounds in the indexing model and use it to obtain lower bounds for the rank/select problem and the balanced parentheses problem. We also improve the existing techniques of Demaine and Lopez-Ortiz using compression and present stronger lower bounds for the text retrieval problem in the indexing model. The most important result of this thesis is a new technique for cell probe lower bounds. We demonstrate its strength by proving new lower bounds for the problem of representing permutations, the text retrieval problem, and the problem of representing binary relations. (Previously, there were no non-trivial results known for these problems.) In addition, we note that the lower bounds for the permutations problem and the binary relations problem are tight for a wide range of parameters, e.g. the running time of queries, the size and density of the relation.

The structural development of Paiwan tribe traditional social ranks Abstract The Paiwan tribe, a native people in Taiwan, has a perfect traditional social rank. They have maintained their primitive, original tribal ranks in every tribe in Ping-tung county since the Japanese era till now in Taiwan. Before the primitive tribes were forced to move into level ground¡Xnew villages arranged by government, they lived a self-contained and self-sufficient lifestyle, poor and in lack of sources. However, their self-confidence, force of condense in their tribes are very steadily. Under being kept sight of their tribal tendency by Japanese, the common people in tribes always obey and respect their chief¡Xtribal leader, without being affected by the governors. The Japanese government had to face the big secret worries about how to control the conditions, than tried to persuade them to work as an attendant to manage their people. In 1945, the Chinese government ruled the Taiwan islands after World War II. Since the new ruler came from mainland China didn¡¦t have any awareness about the tribal culture in Paiwan primitive society, they regarded them as one kind of barbarian tribe came from China in ancient time. In order to control the conditions in a muddle within three months, they forced the native people in every tribal to accept the Chinese surname given by governor. Due to such kind of discriminative attitude against the tribal dignity, the native people were led to lose their traditional class consciousness and native identification to their original society until the declaration martial law ended in 1987. From 1987 to 1996, the new movement of asking human rights ¡V democracy and freedom like a rising wind and scudding clouds in whole islands. Consequently, the Paiwan tribe was also getting awareness to rebuild their primitive culture, Paiwan tribe consciousness, which had lost for forty-two years. The process of searching movement seems like looking for their relatives who had parted for more than forty years. Though they had their same blood relationship, they had lost the same life experiences for such a long time. Therefore, they could only make up for a few part even they tried to do their best effort. Thus, I¡¦ll try to analysis the phases of structural movement of Paiwan tribe traditional social ranks and the affections under the national policy, social background during these years. Chapter one includes the preface for introduction, the purposes of research, the study of bibliography, the ranges of the research, the methods and structures of the research to present the aspects of this paper. Chapter two discusses the original class forms, system of work, processes of the structural development of Paiwan tribe traditional social ranks to explain how the tribal chiefs manage their people, rule their tribal affairs in their territory before the external governor interrupted their principles of primitive society. Chapter three describes how the Taiwan external government new movement ¡§the policy of national assimilation¡¨ affected the tribal chiefs to control or manage their social orders and how the immigrants new idea ¡§communalism¡¨ works and what the government policy about managing the preservative land for tribal people is. Chapter four states what is the negative results of the traditional tribal ranks and ancestor sacrificial rites under the governor¡¦s plan control of their tribal resident movement and the external religions during the all-rounded communications between the tribal society and current society from 1950 to 1987¡Xthe phases of developing entire economics in Taiwan. Chapter five emphasizes on how the tribal people examined their own feelings and motives, thought deeply themselves critically from 1987 to 2005. Because of accepting the frame of democracy and being conscious of accumulation wealth help them to promote their cultural revives. Then every tribe and village founds one after another its relative groups, community culture associations, and shows their trials of class strength while holding their traditional wedding ceremony to strengthen their traditional awareness of class nature. Above all, we found that Taiwan tribes still maintained their essence of culture without being stoke down by the attack of the current social concepts and polices of government in every stage. That is, the system of firstborn inheritor is the basis of the ranks structure in Paiwan tribes till now. The firstborn inheritor influence the development of all relatives, certainly the other younger brothers and sisters not only give their respect to the original family but also offer all necessary helps to honor their original family. The firstborn inheritor also has the duty to hold the life rite for the relatives and give them supports in any emergency situations. Now, the real leading role and the ownership in traditional Paiwan tribe ranks society has changed into the leadership in spirit. Key words: Paiwan tribe, native people , tribal rank structure, cultural development , Tribal chief, common people.

Using page rank and semantic information are frequently used techniques in next page prediction systems. In our work, we extend the use of Page Rank algorithm for next page prediction with several navigational attributes, which are size of the page, duration of the page visit and duration of transition (two page visits sequentially), frequency of page and transition. In our model, we define popularity of transitions and pages by using duration information, use it in a relation with page size, and visit frequency factors. By using the popularity value of pages, we bias conventional Page Rank algorithm and model a next page prediction system that produces page recommendations under given top-n value. Moreover, we extract semantic terms from web URLs in order to tag pages semantically. The extracted terms are mapped into web URLs with different level of details in order to find semantically similar pages for next page recommendations. With this tagging, we model another next page prediction method, which uses Semantic Tagging (ST) similarity and exploits PPR values as a supportive method. Moreover, we model a Hybrid Page Rank (HPR) algorithm that uses both Semantic Tagging based approach and Popularity Based Page Rank values of pages together in order to investigate the effect of PPR and ST with equal weights. In addition, we investigate the effect of local (a synopsis of directed web graph) and global (whole directed web graph) modeling on next page prediction accuracy.

In this paper we propose a generalized rank test based on discrete interval-censored failure time data to determine whether two lifetime populations come from the same distribution. It reduces to the Logrank test or Wilcoxon test when one has exact or right-censored data. Simulation shows that the proposed test performs pretty satisfactory. An example is presented to demonstrate how the proposed test can be applied in AIDS study.

Interval-censored failure time data often occur in follow-up studies where subjects can only be followed periodically and the failure time can only be known to lie in an interval. In this paper we consider the problem of comparing two or more interval-censored samples. We propose a multiple imputation method for discrete interval-censored data to impute exact failure times from interval-censored observations and then apply existing test for exact data, such as the log-rank test, to imputed exact data. The test statistic and covariance matrix are calculated by our proposed multiple imputation technique. The formula of covariance matrix estimator is similar to the estimator used by Follmann, Proschan and Leifer (2003) for clustered data. Through simulation studies we find that the performance of the proposed log-rank type test is comparable to that of the test proposed by Finkelstein (1986), and is better than that of the two existing log-rank type tests proposed by Sun (2001) and Zhao and Sun (2004) due to the differences in the method of multiple imputation and the covariance matrix estimation. The proposed method is illustrated by means of an example involving patients with breast cancer. We also investigate applying our method to the other two-sample comparison tests for exact data, such as Mantel's test (1967) and the integrated weighted difference test.

Ranking model construction is an important topic in information retrieval. Recently, many approaches based on the idea of ¡§learning to rank¡¨ have been proposed for this task and most of them attempt to score all documents of different queries by resorting to a single function. In this thesis, we propose a novel framework of query-dependent ranking. A simple similarity measure is used to calculate similarities between queries. An individual ranking model is constructed for each training query with corresponding documents. When a new query is asked, documents retrieved for the new query are ranked according to the scores determined by a ranking model which is combined from the models of similar training queries. A mechanism for determining combining weights is also provided. Experimental results show that this query dependent ranking approach is more effective than other approaches.