Using Bitmap Indexing Technology for Combined Numerical and TextQueries

Stockinger, Kurt ; Cieslewicz, John ; Wu, Kesheng ; Rotem, Doron ; Shoshani, Arie

Lawrence Berkeley National Laboratory

关键词: Compression;    99;    Bitmap Index Full-Text Index Inverted File Performanceevaluation Database And Information Retrieval;    Algorithms;    Numerical Data;   

DOI  :  10.2172/918636
RP-ID  :  LBNL--61768
RP-ID  :  DE-AC02-05CH11231
RP-ID  :  918636

美国|英语

来源: UNT Digital Library

【 摘 要 】

In this paper, we describe a strategy of using compressedbitmap indices to speed up queries on both numerical data and textdocuments. By using an efficient compression algorithm, these compressedbitmap indices are compact even for indices with millions of distinctterms. Moreover, bitmap indices can be used very efficiently to answerBoolean queries over text documents involving multiple query terms.Existing inverted indices for text searches are usually inefficient forcorpora with a very large number of terms as well as for queriesinvolving a large number of hits. We demonstrate that our compressedbitmap index technology overcomes both of those short-comings. In aperformance comparison against a commonly used database system, ourindices answer queries 30 times faster on average. To provide full SQLsupport, we integrated our indexing software, called FastBit, withMonetDB. The integrated system MonetDB/FastBit provides not onlyefficient searches on a single table as FastBit does, but also answersjoin queries efficiently. Furthermore, MonetDB/FastBit also provides avery efficient retrieval mechanism of result records.