Query Processing Issues in Region-Based Image Databases

Many modern image database systems adopt a region-based paradigm, in which images are segmented into homogeneous regions in order to improve the retrieval accuracy. With respect to the case where images are dealt with as a whole, this leads to some peculiar query processing issues that have not been investigated so far in an integrated way. Thus, it is currently hard to understand how the different alternatives for implementing the region-based image retrieval model might impact on performance. In this paper, we analyze in detail such issues, in particular the type of matching between regions (either one-to-one or many-to-many). Then, we propose a novel ranking model, based on the concept of Skyline, as an alternative to the usual one based on aggregation functions and k-Nearest Neighbors queries. We also discuss how different query types can be efficiently supported. For all the considered scenarios we detail efficient index-based algorithms that are provably correct. Extensive experimental analysis shows, among other things, that: (1) the 1–1 matching type has to be preferred to the N–M one in terms of efficiency, whereas the two have comparable effectiveness, (2) indexing regions rather than images performs much better, and (3) the novel Skyline ranking model is consistently the most efficient one, even if this sometimes comes at the price of a reduced effectiveness.