Authenticated join processing in outsourced databases

Authenticated join processing in outsourced databases,10.1145/1559845.1559849,Yin Yang,Dimitris Papadias,Stavros Papadopoulos,Panos Kalnis

Authenticated join processing in outsourced databases   (Citations: 6)
BibTex | RIS | RefWorks Download
Database outsourcing requires that a query server constructs a proof of result correctness, which can be verified by the client using the data owner's signature. Previous authentication techniques deal with range queries on a single relation using an authenticated data structure (ADS). On the other hand, authenticated join processing is inherently more complex than ranges since only the base relations (but not their combination) are signed by the owner. In this paper, we present three novel join algorithms depending on the ADS availability: (i) Authenticated Indexed Sort Merge Join (AISM), which utilizes a single ADS on the join attribute, (ii) Authenticated Index Merge Join (AIM) that requires an ADS (on the join attribute) for both relations, and (iii) Authenticated Sort Merge Join (ASM), which does not rely on any ADS. We experimentally demonstrate that the proposed methods outperform two benchmark algorithms, often by several orders of magnitude, on all performance metrics, and effectively shift the workload to the outsourcing service. Finally, we extend our techniques to complex queries that combine multi-way joins with selections and projections.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...For example, [6, 11, 21] study the authentication of relational queries; [7, 15] study the authentication of sliding window (data stream) queries; [12] addresses this issue on text similarity queries; [14, 22] study the authentication of static spatial queries; and [24] addresses the authentication of shortest path queries...
    • ...Query authentication In the literature, most authentication techniques [6, 7, 12, 14, 15, 21, 22, 24] are based on Merkle tree [8], which is an authenticated data structure (ADS) that is built on the dataset...

    Man Lung Yiuet al. Authentication of moving kNN queries

    • ...Yang et al. [16] provide techniques for authenticated join operation...
    • ...This result is also achieved in other papers [14,20,4,6,16,17] but with different trade offs...
    • ...The technique described by Yang et al. [16] provide verification objects of unpractical size and uses many query-rounds...

    Bernardo Palazziet al. Query Racing: Fast Completeness Certification of Query Results

    • ...In [26], possibly the closest in context work to ours, set intersection, union and difference are authenticated with linear costs. Similar bounds appear in [38]...

    Charalampos Papamanthouet al. Optimal Verification of Operations on Dynamic Sets

Sort by: