| COMPUTER SCIENCE AND TECHNOLOGY |
|
|
|
|
|
Query authentications based on a fixed grid partitioning quad-tree index in LBS big data |
| NING Bo, PEI Xiaoxia, LI Yuju, PEI Xinyu |
| School of Information Science and Technology, Dalian Maritime University, Dalian 116026, China |
|
|
|
|
Abstract When publishing data from location-based services (LBS), the data owner authorizes a third party publisher to be responsible for forwarding the appropriate result to the mobile clients. However, the service provider in the LBS big data may be susceptible to attacks which may lead to garbled or incorrect query results that can have commercial interest. This paper describes a quad-tree indexing structure based on a fixed grid partitioning mechanism for spatial range query authentication that partitions and indexes the spatial data. The position of an object in the LBS big data changes with time, so the data requires a dynamic index structure that can deal with many update operations. The spatial index structure presented here to update the price has low overhead, is convenient for data management systems, shortens the retrieval time for range queries, and uses a quad-tree index for high query efficiencies. The system ensures the authenticity, completeness and correctness of the query results. Tests show that this method is effective.
|
| Keywords
location-based service
query authentication
quad-tree
privacy preservation
big data
|
|
|
|
Issue Date: 15 July 2016
|
|
|
[1] Li F, Hadjieleftheriou M, Kollios G, et al. Dynamic authenticated index structures for outsourced databases[C]//Proceedings of the 2006 ACM SIGMOD international conference of data. Chicago, IL, USA:ACM, 2006:121-132.
[2] Hu H, Xu J, Chen Q, et al. Authenticating location-based services without compromising location privacy[C]//Proceedings of the 2012 ACM SIGMOD International Conference of Data. New York, NY, USA:ACM, 2012:301-312.
[3] Guttman A. R-trees:A Dynamic Index Structure for Spatial Searching[M]. ACM, 1984.
[4] Finkel R A, Bentley J L. Quad trees a data structure for retrieval on composite keys[J]. Acta informatica, 1974, 4(1):1-9.
[5] Xie M, Wang H, Yin J, et al. Integrity auditing of outsourced data[C]//Proceedings of the 33rd international conference on Very large data bases. Vienna, Austria:VLDB Endowment, 2007:782-793.
[6] 范红, 冯登国, 邹良惠. 数字签名技术及其在网络通信安全中的应用[J]. 中国科学院研究生院学报, 2001, 18(2):101-104. FAN Hong, FENG Dengguo, ZOU Lianghui. The digital signature technology and its application in the network communication security[J]. Graduate school of Chinese academy of sciences journal, 2001, 18(2):101-104.
[7] 卓先德, 赵菲, 曾德明. 非对称加密技术研究[J]. 四川理工学院学报:自然科学版, 2010, 23(5):562-564.ZHUO Xiande, ZHAO Fei, ZENG Deming. Authentication encryption technology research[J]. Journal of Sichuan University of Science and Engineering, 2010, 23(5):562-564.
[8] Narasimha M, Tsudik G. Authentication of outsourced databases using signature aggregation and chaining[C]//Database Systems for Advanced Applications. Jeju Island, Korea:Springer Berlin Heidelberg, 2006:420-436.
[9] Pang H H, Tan K L. Authenticating query results in edge computing[C]//Data Engineering, 2004. Proceedings of the 20th International Conference on. Chicago, IL, USA:IEEE, 2004:560-571.
[10] Merkle R C. A certified digital signature[C]//Advances in Cryptology-CRYPTO'89 Proceedings. New York, NY, USA:Springer, 1990:218-238.
[11] Yuan D, Wang X. Query authentication method based on merkle hash tree in outsourced database[J]. Computer Engineering, 2010, 36(4):115-117.
[12] Sion R. Query execution assurance for outsourced databases[C]//Proceedings of the 31st international conference on Very large data bases. Trondheim, Norway:VLDB Endowment, 2005:601-612.
[13] Mykletune, Naras Imuha M, Tsudik G. Authentication and integrity in outsourced databases[J]. ACM Transactions on Storage, 2006, 2(2):107-138.
[14] Lin X, Xu J, Hu H. Authentication of location-based skyline queries[C]//Proceedings of the 20th ACM international conference on Information and knowledge management. Glasgow, UK:ACM, 2011:1583-1588.
[15] Yiu M L, Lo E, Yung D. Authentication of moving kNN queries[C]//Data Engineering (ICDE), 2011 IEEE 27th International Conference on. IEEE, 2011:565-576.
[16] Hu H, Chen Q, Xu J. VERDICT:Privacy-preserving authentication of range queries in location-based services[C]//Data Engineering (ICDE), 2013 IEEE 29th International Conference on. IEEE, 2013:1312-1315.
[17] Jing Y, Hu L, Ku W S, et al. Authentication of k nearest neighbor query on road networks[J]. Knowledge and Data Engineering, IEEE Transactions on, 2014, 26(6):1494-1506.
[18] Wang J, Du X, Lu J, et al. Bucket-based authentication for outsourced databases[J]. Concurrency and Computation:Practice and Experience, 2010, 22(9):1160-1180.
[19] Samet H. The quadtree and related hierarchical data structures[J]. ACM Computing Surveys (CSUR), 1984, 16(2):187-260.
[20] Nievergelt J, Hinterberger H, Sevcik K C. The grid file:An adaptable, symmetric multikey file structures[J]. ACM Transactions on Database Systems (TODS), 1984, 9(1):38-71. |
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
2016,
Vol. 56
