ERA Banner
Download Add to Cart Share
More Like This
  • http://hdl.handle.net/10402/era.25328
  • Indexing and Querying Natural Language Text
  • Chubak, Pirooz
  • English
  • Indexing
    Querying
    Natural Language Text
    Index Structures
    Tree Pattern Matching
    Subtree Index
  • Jan 30, 2012 3:21 PM
  • Thesis
  • English
  • Adobe PDF
  • 840212 bytes
  • Natural language text is a prominent source of representing and communicating information and knowledge. It is often desirable to search in granularities of text that are smaller than a document or to query the syntactic roles and relationships within syntactically annotated text sentences, often represented by parse trees. In this thesis, we study the problems of efficiently indexing and querying natural language text in the scenarios where (1) text is modelled as flat sequences of words and (2) text is modelled as collections of syntactically annotated trees. In the first scenario, we study some of the index structures that are capable of answering the class of queries referred to here as wild card queries and perform an analysis of their performance. Our experimental results on a large class of queries from different sources (including query logs and parse trees) and with various datasets reveal some of the performance barriers of these indexes. We present Word Permuterm Index (WPI) and show that it supports a wide range of wild card queries, is quick to construct and is highly scalable. Our experimental results comparing WPI to alternative methods on a wide range of wild card queries show a few orders of magnitude performance improvement for WPI while the memory usage is kept the same for all compared systems. In the second scenario, we study index structures and access methods that improve the performance of querying over syntactically parsed sentences. We propose a novel indexing scheme over unique subtrees as index keys. We also introduce the root-split coding scheme that concisely stores structural subtree information, making it possible to perform exact axes matching over subtrees. We theoretically study the properties of our coding and the limitations it imposes over query processing. Our extensive set of experiments show that root-split coding reduces the index size of a baseline index which stores the interval codes of all nodes by a factor of up to 5 (i.e. 80% reduction) and speeds up querying runtime by more than 6 times on average, when subtrees of sizes 1, . . . , 5 are indexed.
  • Pirooz Chubak and Davood Rafiei, "Index Structures for Efficiently Searching Natural Language Text", Proceedings of the 19th ACM international conference on Information and knowledge management, 2010
  • Doctoral
  • Doctor of Philosophy
  • Department of Computing Science
  • Spring 2012
  • Rafiei, Davood (Computing Science)
  • Barbosa, Denilson (Computing Science)
    Kondrak, Grzegorz (Computing Science)
    Newman, John (Linguistics)
    Ng, Raymond T. (Computer Science, UBC)