TY - JOUR
T1 - Authenticating location-based skyline queries in arbitrary subspaces
AU - Lin, Xin
AU - Xu, Jianliang
AU - Hu, Haibo
AU - Lee, Wang Chien
N1 - This work was supported in part by the HK RGC Grants 210811 and 210612, NSFC Grant 60903169, and in part by the Hong Kong Scholar Program (Grant XJ2011008).
PY - 2014/6
Y1 - 2014/6
N2 - With the ever-increasing use of smartphones and tablet devices, location-based services (LBSs) have experienced explosive growth in the past few years. To scale up services, there has been a rising trend of outsourcing data management to Cloud service providers, which provide query services to clients on behalf of data owners. However, in this data-outsourcing model, the service provider can be untrustworthy or compromised, thereby returning incorrect or incomplete query results to clients, intentionally or not. Therefore, empowering clients to authenticate query results is imperative for outsourced databases. In this paper, we study the authentication problem for location-based arbitrary-subspace skyline queries (LASQs), which represent an important class of LBS applications. We propose a basic Merkle Skyline R-tree method and a novel Partial S4-tree method to authenticate one-shot LASQs. For the authentication of continuous LASQs, we develop a prefetching-based approach that enables clients to compute new LASQ results locally during movement, without frequently contacting the server for query re-evaluation. Experimental results demonstrate the efficiency of our proposed methods and algorithms under various system settings.
AB - With the ever-increasing use of smartphones and tablet devices, location-based services (LBSs) have experienced explosive growth in the past few years. To scale up services, there has been a rising trend of outsourcing data management to Cloud service providers, which provide query services to clients on behalf of data owners. However, in this data-outsourcing model, the service provider can be untrustworthy or compromised, thereby returning incorrect or incomplete query results to clients, intentionally or not. Therefore, empowering clients to authenticate query results is imperative for outsourced databases. In this paper, we study the authentication problem for location-based arbitrary-subspace skyline queries (LASQs), which represent an important class of LBS applications. We propose a basic Merkle Skyline R-tree method and a novel Partial S4-tree method to authenticate one-shot LASQs. For the authentication of continuous LASQs, we develop a prefetching-based approach that enables clients to compute new LASQ results locally during movement, without frequently contacting the server for query re-evaluation. Experimental results demonstrate the efficiency of our proposed methods and algorithms under various system settings.
KW - Query processing
KW - Spatial databases and GIS
UR - http://www.scopus.com/inward/record.url?scp=84902175354&partnerID=8YFLogxK
U2 - 10.1109/TKDE.2013.137
DO - 10.1109/TKDE.2013.137
M3 - Journal article
AN - SCOPUS:84902175354
SN - 1041-4347
VL - 26
SP - 1479
EP - 1493
JO - IEEE Transactions on Knowledge and Data Engineering
JF - IEEE Transactions on Knowledge and Data Engineering
IS - 6
M1 - 6574865
ER -