File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Efficient answering of set containment queries for skewed item distributions

TitleEfficient answering of set containment queries for skewed item distributions
Authors
KeywordsContainment queries
Inverted files
Ordered inverted files
Set-values
Issue Date2011
PublisherAssociation for Computing Machinery.
Citation
The 14th International Conference on Extending Database Technology (EDBT 2011), Uppsala, Sweden, 21-24 March 2011. In Proceedings of the 14th EDBT, 2011, p. 225-236 How to Cite?
AbstractIn this paper we address the problem of efficiently evaluating containment (i.e., subset, equality, and superset) queries over set-valued data. We propose a novel indexing scheme, the Ordered Inverted File (OIF) which, differently from the state-of-the-art, indexes set-valued attributes in an ordered fashion. We introduce query processing algorithms that practically treat containment queries as range queries over the ordered postings lists of OIF and exploit this ordering to quickly prune unnecessary page accesses. OIF is simple to implement and our experiments on both real and synthetic data show that it greatly outperforms the current state-of-the-art methods for all three classes of containment queries.
Persistent Identifierhttp://hdl.handle.net/10722/137647
ISBN
References

 

DC FieldValueLanguage
dc.contributor.authorTerrovitis, Men_HK
dc.contributor.authorBouros, Pen_HK
dc.contributor.authorVassiliadis, Pen_HK
dc.contributor.authorSellis, Ten_HK
dc.contributor.authorMamoulis, Nen_HK
dc.date.accessioned2011-08-26T14:30:31Z-
dc.date.available2011-08-26T14:30:31Z-
dc.date.issued2011en_HK
dc.identifier.citationThe 14th International Conference on Extending Database Technology (EDBT 2011), Uppsala, Sweden, 21-24 March 2011. In Proceedings of the 14th EDBT, 2011, p. 225-236en_HK
dc.identifier.isbn978-1-4503-0528-0-
dc.identifier.urihttp://hdl.handle.net/10722/137647-
dc.description.abstractIn this paper we address the problem of efficiently evaluating containment (i.e., subset, equality, and superset) queries over set-valued data. We propose a novel indexing scheme, the Ordered Inverted File (OIF) which, differently from the state-of-the-art, indexes set-valued attributes in an ordered fashion. We introduce query processing algorithms that practically treat containment queries as range queries over the ordered postings lists of OIF and exploit this ordering to quickly prune unnecessary page accesses. OIF is simple to implement and our experiments on both real and synthetic data show that it greatly outperforms the current state-of-the-art methods for all three classes of containment queries.en_HK
dc.languageengen_US
dc.publisherAssociation for Computing Machinery.-
dc.relation.ispartofACM International Conference Proceeding Seriesen_HK
dc.rightsProceedings of the 14th International Conference on Extending Database Technology. Copyright © Association for Computing Machinery.-
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subjectContainment queriesen_HK
dc.subjectInverted filesen_HK
dc.subjectOrdered inverted filesen_HK
dc.subjectSet-valuesen_HK
dc.titleEfficient answering of set containment queries for skewed item distributionsen_HK
dc.typeConference_Paperen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=978-1-4503-0528-0&volume=&spage=225&epage=236&date=2011&atitle=Efficient+answering+of+set+containment+queries+for+skewed+item+distributions-
dc.identifier.emailMamoulis, N:nikos@cs.hku.hken_HK
dc.identifier.authorityMamoulis, N=rp00155en_HK
dc.description.naturepostprint-
dc.identifier.doi10.1145/1951365.1951394en_HK
dc.identifier.scopuseid_2-s2.0-79953849738en_HK
dc.identifier.hkuros190935en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-79953849738&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.spage225en_HK
dc.identifier.epage236en_HK
dc.publisher.placeUnited States-
dc.description.otherThe 14th International Conference on Extending Database Technology (EDBT 2011), Uppsala, Sweden, 21-24 March 2011. In Proceedings of the 14th EDBT, 2011, p. 225-236-
dc.identifier.scopusauthoridTerrovitis, M=6603383959en_HK
dc.identifier.scopusauthoridBouros, P=24512354200en_HK
dc.identifier.scopusauthoridVassiliadis, P=8892805000en_HK
dc.identifier.scopusauthoridSellis, T=35276183400en_HK
dc.identifier.scopusauthoridMamoulis, N=6701782749en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats