Chris Pollett > Students >

    ( Print View )


    [Project Blog]

    [CS297 Proposal]

    [Deliverable 1]

    [Deliverable 2]

    [Deliverable 3]

    [Deliverable 4]

    [CS297 Project Report - PDF]

    [CS298 Proposal]

    [CS298 Spring 2011 - Progress Report]

    [CS298 Report]

    [CS298 Presentation]

    [CS298 Project Code]


Deliverable 4: Learn about Full-text indexing and inverted indexes

Description: Read chapters about inverted indexing from book titled "Information Retrieval"

Basic Techniques: The chapter includes topics regarding phrase search, inverted index, functions related to that. Implementation using Binary tree search, sequential search and galloping search is explained in the chapter.

Abstract Structure of Inverted Index: If the collection is static and small enough, it can be maintained within memory with simple data structure like Hash Table, and posting list for each term in a simple array Pt[]. first and last methods of inverted index can be implemented in constant time by returning 1st and last index content from collection. next and prev methods however needs be to implemented using binary search with time complexity O(log(lt)).