LOB: Bucket Based Index for Range Queries

摘要：

Database-as-a-Service is a promising data management paradigm in which data is encrypted before being sent to the untrusted server. Efficient querying on encrypted data is a performance critical problem which has various solutions, among which bucket based index is an effective and flexible one. In previous research some metrics are proposed to measure security and efficiency. In this paper, we illustrate by example the limitations of these metrics and introduce a new security metric based on probability distribution variance and efficiency metric based on overlapping ratio. Based on these metrics we propose a local overlapping bucket algorithm (LOB) with time complexity of O(nlogn), where n represents the cardinality of the table. Experiments on synthetic and real dataset show that our algorithm can achieve higher security by trading off efficiency.

作者: Jieping Wang Xiaoyong Du

作者单位: Key Laboratory of Data Engineering and Knowledge Engineering,MOE;School of Information,Renmin University of China Beijing 100872,China

会议类型: 国际会议

会议名称: The Ninth International Conference on Web-Age Information Management(第九届web时代信息管理国际会议)(WAIM 2008)

会议地点: 张家界

会议语种:英文

在线出版日期: 2008-07-20（万方平台首次上网日期，不代表论文的发表时间）