Article Preview
TopIntroduction
With the rapid growth of the volume and diversity of digital data produced by all kinds of commercial, scientific and leisure-time applications, the retrieval in large data sets became one of the key IT tasks nowadays. The complex data types, such as multimedia or various sensor data, introduce a natural requirement to be searched not only by their metadata but also by the content of the data itself. This is typically beyond the capabilities of classic exact match or keyword search techniques, which is one of the reasons why the importance of various similarity search technologies increases significantly in current applications. A considerable research effort has been invested in this topic resulting in both theoretical background (Zezula et al., 2006) and large-scale practical results, e.g. (Novak et al., 2009; Esuli, 2011; Batko et al., 2010).
However, the similarity search is a very resource demanding process and the underlying technologies are rather complex. Therefore, there is a strong motivation to develop a general method that would provide the similarity search as a service to make it easily available to the authorized users. With a growing popularity of cloud services, the natural approach is to outsource this task to the cloud environment in a Software as a Service (SaaS) manner. This approach provides many advantages for the owners of the data, such as low initial investments, low storage costs and very good scalability. Also, outsourcing should transfer the computational burden from the clients to the servers, which would enable the clients to be simpler devices (such as cell phones).
On the other hand, the principle of service outsourcing fundamentally assumes that the data is provided to third party repositories that are not fully controlled by the users authorized for the service. The outsourced data may be sensitive (e.g. medicine data), confidential, or otherwise valuable (e.g. collected from a scientific research) and thus the privacy of the data is of high importance. Hence, besides providing effective and efficient searching, outsourced similarity search solutions should also employ mechanisms to ensure privacy requirements not only by standard access permissions, but, more importantly, by securing the content of the indexed data in a potentially hostile third-party environment.
A typical application area for outsourced similarity search is healthcare. The healthcare data is often heterogeneous and complex (X-rays, MRT outputs, various electric signals) which calls for content-based retrieval using similarity search. At the same time, the data managed by healthcare institutions is often extremely voluminous and thus outsourcing the data management can be more convenient than maintaining own complex IT infrastructure. However, privacy of patients-related data is required by law and thus the whole process must be secure and privacy-preserving (Wei et al., 2013).
Ensuring privacy of outsourced search is a widely studied topic in the context of classic databases. There has been a lot of focus on so called symmetric searchable encryption schemes that can form building blocks of secure cloud storages. Such schemes allow encryption of the data in such a way that it is possible to perform selective data retrieval (search) over the encrypted collection while the data privacy is ensured. Recently, Kamara et al. (2010) described the requirements of a practical secure cloud storage considering the general case of relational databases and they proposed a symmetric searchable encryption for this scenario (Kamara et al., 2012). Also, a prototype system providing privacy-preserving outsourced SQL search has been implemented recently (Tu et al., 2013).
These general principles can also be applied in the context of similarity search, however, this area has several specifics that make the outsourcing more difficult. First of all, the similarity search often deals with more than “one level” of the data to be processed: The raw data (for example a set of images) is typically preprocessed to obtain descriptive features (descriptors) that are indexed and searched (for example SIFT features from images (Lowe, 1999)). From the privacy point of view, it is crucial to ensure privacy of both the raw data and the indexed data objects (descriptors), which can be highly correlated with the raw data objects.