Show simple item record

dc.contributor.authorCulpepper, JS
dc.contributor.authorMoffat, A
dc.date.available2014-05-22T00:10:46Z
dc.date.issued2010-12-01
dc.identifierhttp://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000285501000001&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=d4d813f4571fa7d6246bdc0dfeca3a1c
dc.identifierARTN 1
dc.identifier.citationCulpepper, J. S. & Moffat, A. (2010). Efficient Set Intersection for Inverted Indexing. ACM TRANSACTIONS ON INFORMATION SYSTEMS, 29 (1), https://doi.org/10.1145/1877766.1877767.
dc.identifier.issn1046-8188
dc.identifier.urihttp://hdl.handle.net/11343/30026
dc.description.abstractConjunctive Boolean queries are a key component of modern information retrieval systems, especially when Web-scale repositories are being searched. A conjunctive query q is equivalent to a | q |-way intersection over ordered sets of integers, where each set represents the documents containing one of the terms, and each integer in each set is an ordinal document identifier. As is the case with many computing applications, there is tension between the way in which the data is represented, and the ways in which it is to be manipulated. In particular, the sets representing index data for typical document collections are highly compressible, but are processed using random access techniques, meaning that methods for carrying out set intersections must be alert to issues to do with access patterns and data representation. Our purpose in this article is to explore these trade-offs, by investigating intersection techniques that make use of both uncompressed “integer” representations, as well as compressed arrangements. We also propose a simple hybrid method that provides both compact storage, and also faster intersection computations for conjunctive querying than is possible even with uncompressed representations.
dc.languageEnglish
dc.publisherASSOC COMPUTING MACHINERY
dc.subjectInformation Systems
dc.titleEfficient Set Intersection for Inverted Indexing
dc.typeJournal Article
dc.identifier.doi10.1145/1877766.1877767
melbourne.peerreviewPeer Reviewed
melbourne.affiliationThe University of Melbourne
melbourne.affiliation.departmentComputer Science and Software Engineering
melbourne.source.titleACM Transactions on Information Systems
melbourne.source.volume29
melbourne.source.issue1
dc.description.pagestart1
melbourne.publicationid157469
melbourne.elementsid330976
melbourne.contributor.authorMoffat, Alistair
melbourne.internal.ingestnoteAbstract bulk upload (2017-07-24)
dc.identifier.eissn1558-2868
melbourne.accessrightsThis item is currently not available from this repository


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record