LBS大数据中基于固定网格划分四叉树索引的查询验证  

Query authentications based on a fixed grid partitioning quad-tree index in LBS big data

作　　者：宁博[1] 裴晓霞[1] 李玉居 裴新宇[1] 

机构地区：[1]大连海事大学信息科学技术学院,大连116026

出　　处：《清华大学学报（自然科学版）》2016年第7期785-792,共8页Journal of Tsinghua University(Science and Technology)

基　　金：国家自然科学基金青年基金项目(61202083);国家自然科学基金面上项目(61272369);辽宁省教育厅一般项目(L2014055);辽宁省电力有限公司科技项目(2015YF-67);中央高校基本科研业务费项目(3132016034)

摘　　要：基于位置的服务(LBS)进行数据发布时,数据拥有者委派第三方服务商来发布数据,服务提供商代表数据拥有者向用户提供服务。但是LBS中的服务提供商可能是不可信的,这样会在LBS大数据的查询中形成由于商业目的而篡改的不准确的结果。LBS大数据中移动对象的位置随时间而变化,因此数据的动态性导致了索引结构大量的更新操作。该文提出了一种基于固定网格划分四叉树索引机制的空间范围查询验证技术,该技术采用网格划分的方法对空间数据进行划分,并采用四叉树对划分后的网格进行索引。该空间索引结构更新代价低,方便了数据的管理,缩短了检索的时间,四叉树索引对于范围查询具有较高的查询验证效率。该方法确保了用户查询结果的真实性、完整性和正确性。通过实验验证了该方法是有效的。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.

关 键 词：基于位置的服务 查询验证 四叉树 隐私保护 大数据 

分 类 号：TP309.2[自动化与计算机技术—计算机系统结构]