EARS-DM: Efficient Auto Correction Retrieval Scheme for Data Management in Edge Computing

Kai Fan, Jie Yin, Kuan Zhang, Hui Li, Yintang Yang

TL;DR

This paper introduces EARS-DM, a novel retrieval scheme for edge computing that enhances data management by incorporating automatic spelling correction for search queries and a sophisticated R-tree index structure. This approach aims to improve search accuracy and efficiency in edge environments while maintaining data privacy and reducing computational overhead.

What Problem Does This Paper Address?

Edge computing, while offering benefits like reduced latency and bandwidth consumption by processing data closer to the source, introduces significant challenges in data management, particularly concerning security and privacy. Traditional cloud computing relies on centralized servers, but edge environments involve numerous distributed devices, making data management more complex. A key issue is enabling efficient and accurate data retrieval from these edge devices, especially when users might make spelling errors in their search queries. Existing solutions often struggle with handling these errors gracefully, can be computationally expensive, or compromise privacy. This paper tackles the problem of enabling secure, efficient, and error-tolerant multi-keyword search within edge computing environments.

Methods

The EARS-DM scheme introduces several key innovations:

  • Automatic Error Correction: Instead of relying on simple similar word expansion, EARS-DM employs an automatic error correction mechanism for query keywords. This allows the system to tolerate spelling mistakes, improving the user search experience and reducing the need for users to be perfectly accurate.
  • Syntactic Keyword Weighting: The scheme incorporates the syntactic significance of query keywords by calculating a "keyword weight" (KW). This weight, combined with the TF-IDF (Term Frequency-Inverse Document Frequency) value of keywords, helps to prioritize more important terms in the search, leading to more relevant results.
  • R-tree Index with Bloom Filters: A novel R-tree index structure is proposed. The R-tree nodes store encrypted keywords, and their children nodes contain encrypted file identifiers (FID) and Bloom filters (BF). The Bloom filters store TF values for keywords within files, while the trapdoor (generated by the user) stores KW * IDF values. This structure allows for efficient searching and filtering of relevant files.
  • Two-Step Matching: The search process involves a two-step matching method. First, encrypted keywords are matched against the R-tree. If a match is found, the Bloom filter of the corresponding file is then checked. This layered approach helps to quickly narrow down potential results.
  • Edge-Centric Search: The secure index is uploaded to edge devices (EDs), which are closer to the data source. Search queries are processed by these EDs, reducing the burden on the central cloud server and further improving response times. EDs then sort the matching encrypted file identifiers by relevance scores and send them to the cloud server.

Datasets

Not discussed in the paper. The paper mentions using "actual data" for performance analysis but does not specify the dataset.

Key Insights and Ideas

  • Bridging the Gap between Edge and Cloud: EARS-DM effectively leverages edge devices for localized, efficient, and privacy-preserving search, addressing the limitations of purely cloud-based solutions in edge environments.
  • Intelligent Query Handling: The combination of automatic error correction and syntactic keyword weighting is a significant step towards making search more user-friendly and accurate, especially in scenarios where data is vast and queries might be imperfect.
  • Optimized Indexing for Privacy and Efficiency: The R-tree structure, augmented with Bloom filters and encryption, provides a robust mechanism for balancing search performance, storage efficiency, and data confidentiality.
  • Decentralized Processing for Speed: Shifting the primary search processing to edge devices, rather than relying solely on the cloud, is crucial for achieving low latency and high throughput in edge computing scenarios.

Key Results

The paper presents performance analysis with actual data, indicating that the EARS-DM scheme is both efficient and accurate. While specific quantitative results are presented in figures, the text highlights:

  • Efficient Index Creation: The time consumption for index creation grows linearly with the number of keywords and files, suggesting scalability.
  • Fast Trapdoor Generation: Trapdoor generation time increases slowly with the number of query keywords.
  • Efficient Search: The search time complexity is noted as O(log n), which is efficient compared to other schemes like EliMFS. The search time grows slowly with the file set size, outperforming CKSER.
  • High Precision: The auto-correction system demonstrates good precision, with points evenly distributed around the average expected value, indicating its effectiveness in handling misspelled queries.

Limitations and Future Work

  • Semi-Trusted Entities: The scheme assumes that edge devices (EDs) and the cloud server (CS) are semi-trusted ("honest but curious"). While they follow protocols, they might infer information. The paper doesn't delve into advanced cryptographic techniques to mitigate such inferences beyond basic encryption.
  • Further Security Enhancements: The authors suggest that in future work, they will "further discuss the possibility of enhancing the security in the energy internet system based on ensuring efficiency." This implies a potential for more advanced security measures.
  • Dataset Specificity: The lack of detailed information about the "actual data" used for performance analysis makes it difficult to fully assess the generalizability of the results.

Summary updated

Abstract

Edge computing is an extension of cloud computing that enables messages to be acquired and processed at low cost. Many terminal devices are being deployed in the edge network to sense and deal with the massive data. By migrating part of the computing tasks from the original cloud computing model to the edge device, the message is running on computing resources close to the data source. The edge computing model can effectively reduce the pressure on the cloud computing center and lower the network bandwidth consumption. However, the security and privacy issues in edge computing are worth noting. In this paper, we propose an efficient auto-correction retrieval scheme for data management in edge computing, named EARS-DM. With automatic error correction for the query keywords instead of similar words extension, EARS-DM can tolerate spelling mistakes and reduce the complexity of index storage space. By the combination of TF-IDF value of keywords and the syntactic weight of query keywords, keywords who are more important will obtain higher relevance scores. We construct an R-tree index building with the encrypted keywords and the children nodes of which are the encrypted identifier FID and Bloom filter BF of files who contain this keyword. The secure index will be uploaded to the edge computing and the search phrase will be performed by the edge computing which is close to the data source. Then EDs sort the matching encrypted file identifier FID by relevance scores and upload them to the cloud server (CS). Performance analysis with actual data indicated that our scheme is efficient and accurate.
BibTeX
@inproceedings{fan2018ears,
  author = {Kai Fan and Jie Yin and Kuan Zhang and Hui Li and Yintang Yang},
  title = {{EARS-DM: Efficient Auto Correction Retrieval Scheme for Data Management in Edge Computing}},
  booktitle = {Sensors},
  year = {2018},
  url = {https://openreview.net/forum?id=OQeffO2KKs},
}
Figure