Title page for ETD etd-07082010-190449

Type of Document Master's Thesis
Author Chandrasekaran, Sabrina
Author's Email Address sabrina.chandrasekaran@gmail.com
URN etd-07082010-190449
Title Implementation and Analysis of a Top-K Retrieval System for Strings
Degree Master of Science in Systems Science (M.S.S.S.)
Department Computer Science
Advisory Committee
Advisor Name Title
Shah, Rahul Committee Chair
Busch, Konstantin Committee Member
Kannan, Rajgopal Committee Member
  • suffix trees
  • Top-K retrieval system
Date of Defense 2010-06-30
Availability unrestricted
Given text which is a union of d documents of strings, D = d1, d2,...., dd, the emphasis

of this thesis is to provide a practical framework to retrieve the K most relevant documents

for a given pattern P, which comes as a query. This cannot be done directly, as going

through every occurrence of the query pattern may prove to be expensive if the number of

documents that the pattern occurs in is much more than the number of documents (K) that

we require. Some advanced query functionality will be required, as compared to listing the

documents that the pattern occurs in, because a de ned notion of "most relevant" must be

provided. Therefore, an index needs to be built before hand on T so that the documents

can be retrieved very quickly. Traditionally, inverted indexes have proven to be effective

in retrieving the Top-K documents. However, inverted indexes have certain disadvantages,

which can be overcome by using other data structures like suffix trees and suffix arrays.

A framework was originally provided by Muthukrishnan [29] that takes advantage of

the number of relevant documents being less than the occurence of the query pattern. He

considered two metrics for relevance:frequency and proximity and provided a framework

that took O(n log n) space. Recently, Hon et al [14] provided a framework that takes O(n)

space to retrieve the Top-K documents with more optimal query times, O(P + K logK)

for arbitrary score functions. In this thesis we study the practicality of this index and

provide added functionalities, based on the index, to retrieve Top-K documents for specific

cases like phrase searching. We also provide functionality to output the K most relevant

documents(according to page rank) when two patterns are given as queries.

  Filename       Size       Approximate Download Time (Hours:Minutes:Seconds) 
 28.8 Modem   56K Modem   ISDN (64 Kb)   ISDN (128 Kb)   Higher-speed Access 
  ChandrasekaranThesis.pdf 2.34 Mb 00:10:50 00:05:34 00:04:52 00:02:26 00:00:12

Browse All Available ETDs by ( Author | Department )

If you have questions or technical problems, please Contact LSU-ETD Support.