A combination of trie-trees and inverted files for the indexing of set-valued objects

Terrovitis, M, Passas, S, Vassiliadis, P and Sellis, T 2006, 'A combination of trie-trees and inverted files for the indexing of set-valued objects', in Proceedings of the ACM 15th International Conference on Information and Knowledge Management (CIKM 06), Arlington, VA, USA, 6-11 November 2006, pp. 728-737.


Document type: Conference Paper
Collection: Conference Papers

Title A combination of trie-trees and inverted files for the indexing of set-valued objects
Author(s) Terrovitis, M
Passas, S
Vassiliadis, P
Sellis, T
Year 2006
Conference name 15th International Conference on Information and Knowledge Management (CIKM 06)
Conference location Arlington, VA, USA
Conference dates 6-11 November 2006
Proceedings title Proceedings of the ACM 15th International Conference on Information and Knowledge Management (CIKM 06)
Publisher ACM
Place of publication New York, USA
Start page 728
End page 737
Total pages 10
Abstract Set-valued attributes frequently occur in contexts like marketbasked analysis and stock market trends. Late research literature has mainly focused on set containment joins and data mining without considering simple queries on set valued attributes. In this paper we address superset, subset and equality queries and we propose a novel indexing scheme for answering them on set-valued attributes. The proposed index superimposes a trie-tree on top of an inverted file that indexes a relation with set-valued data. We show that we can efficiently answer the aforementioned queries by indexing only a subset of the most frequent of the items that occur in the indexed relation. Finally, we show through extensive experiments that our approach outperforms the state of the art mechanisms and scales gracefully as database size grows.
Subjects Database Management
Keyword(s) HTI
inverted files
tries
containment queries
DOI - identifier 10.1145/1183614.1183718
Copyright notice © ACM
ISBN 1595934332
Versions
Version Filter Type
Altmetric details:
Access Statistics: 256 Abstract Views  -  Detailed Statistics
Created: Tue, 19 Feb 2013, 12:43:00 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us