published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

No description available.

Report (M.S.)--Virginia Polytechnic Institute and State University. M.S. 1993. / Vita. Abstract. Includes bibliographical references (leaves 81-83). Also available via the Internet.

Thesis (PhD) -- AUT University, 2009. / Includes bibliographical references. Also held in print (xi, 190 leaves : ill. ; 30 cm.) in the Archive at the City Campus (T 005.73 HWA)

The amount of data that people and companies store has grown exponentially over the last few years. Storing this information alone is not enough, because in order to make it useful we need to be able to efficiently search inside it. Furthermore, it is highly valuable to keep the historic data of each document stored, allowing to not only access and search inside the newest version, but also over the whole history of the documents. Grammar-based compression has proven to be very effective for repetitive data, which is the case for versioned documents. In this thesis we present several results on representing textual information and searching in it. In particular, we present text indexes for grammar-based compressed text that support searching for a pattern and extracting substrings of the input text. These are the first general indexes for grammar-based compressed text that support searching in sublinear time. In order to build our indexes, we present new results on representing binary relations in a space-efficient manner, and construction algorithms that use little space to achieve their goal. These two results have a wide range of applications. In particular, the representations for binary relations can be used as a building block for several structures in computer science, such as graphs, inverted indexes, etc. Finally, we present a new index, that uses on grammar-based compression, to solve the document listing problem. This problem deals with representing a collection of texts and searching for the documents that contain a given pattern. In spite of being similar to the classical text indexing problem, this problem has proven to be a challenge when we do not want to pay time proportional to the number of occurrences, but time proportional to the size of the result. Our proposal is designed particularly for versioned text, allowing the storage of a collection of documents with all their historic versions in little space. This is currently the smallest structure for such a purpose in practice.

The amount of data that people and companies store has grown exponentially over the last few years. Storing this information alone is not enough, because in order to make it useful we need to be able to efficiently search inside it. Furthermore, it is highly valuable to keep the historic data of each document stored, allowing to not only access and search inside the newest version, but also over the whole history of the documents. Grammar-based compression has proven to be very effective for repetitive data, which is the case for versioned documents. In this thesis we present several results on representing textual information and searching in it. In particular, we present text indexes for grammar-based compressed text that support searching for a pattern and extracting substrings of the input text. These are the first general indexes for grammar-based compressed text that support searching in sublinear time. In order to build our indexes, we present new results on representing binary relations in a space-efficient manner, and construction algorithms that use little space to achieve their goal. These two results have a wide range of applications. In particular, the representations for binary relations can be used as a building block for several structures in computer science, such as graphs, inverted indexes, etc. Finally, we present a new index, that uses on grammar-based compression, to solve the document listing problem. This problem deals with representing a collection of texts and searching for the documents that contain a given pattern. In spite of being similar to the classical text indexing problem, this problem has proven to be a challenge when we do not want to pay time proportional to the number of occurrences, but time proportional to the size of the result. Our proposal is designed particularly for versioned text, allowing the storage of a collection of documents with all their historic versions in little space. This is currently the smallest structure for such a purpose in practice.

Thesis (Ph. D.)--University of Washington, 1990. / Vita. Includes bibliographical references (leaves [159]-165).

Thesis (M. Phil.)--University of Hong Kong, 2000. / Includes bibliographical references (leaves 101-103).

Thesis (Ph. D.)--University of Wisconsin--Madison, 1983. / Typescript. Vita. eContent provider-neutral record in process. Description based on print version record. Includes bibliographical references (leaves 94-95).

Over the years there have been many papers supporting the use of design patterns in a traditional data structures course. In support of this approach, we present an evolutionary sequence of five programming exercises, concentrating on problems that require the use of six different design patterns in the context of a data structures course. Included with these exercises are brief descriptions, code segments, and teaching tips to demonstrate the simplicity and power of design patterns to teach object-oriented design principles. UML class diagrams are used to visualize and supplement the discussions.