document: Using d-gap patterns for index compression Sequential patterns of d-gaps exist pervasively in inverted lists of Web document collection indices due to the cluster property . In this paper the information of d-gap sequential patterns is used as a new dimension for improving inverted index compression . We first detect d-gap sequential patterns using a novel data structure , UpDown Tree . Based on the detected patterns , we further substitute each pattern with its pattern Id in the inverted lists that contain it . The resulted inverted lists are then coded with an existing coding scheme . Experiments show that this approach can effectively improve the compression ratio of existing codes .
doc_bio_tags: O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O