Efficient Inverted List Search Technique using Bitmap Filters


The KIPS Transactions:PartD, Vol. 18, No. 6, pp. 415-422, Dec. 2011
10.3745/KIPSTD.2011.18.6.415,   PDF Download:

Abstract

Finding similar strings is an important operation because textual data can have errors, duplications, and inconsistencies by nature. Many algorithms have been developed for string approximate searches and most of them make use of inverted lists to find similar strings. These algorithms basically perform merge operations on inverted lists. In this paper, we develop a bitmap representation of an inverted list and propose an efficient search algorithm that can skip unnecessary inverted lists without searching using bitmap filters. Experimental results show that the proposed technique consistently improve the performance of the search.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
I. T. Kwon and J. I. Kim, "Efficient Inverted List Search Technique using Bitmap Filters," The KIPS Transactions:PartD, vol. 18, no. 6, pp. 415-422, 2011. DOI: 10.3745/KIPSTD.2011.18.6.415.

[ACM Style]
In Teak Kwon and Jong Ik Kim. 2011. Efficient Inverted List Search Technique using Bitmap Filters. The KIPS Transactions:PartD, 18, 6, (2011), 415-422. DOI: 10.3745/KIPSTD.2011.18.6.415.