Authenticating q -Gram-Based Similarity Search Results for Outsourced String Databases

Liangyong Yang, Haizhou Ye, Xuyang Liu, Yijun Mao and Jilian Zhang ()
Additional contact information
Liangyong Yang: College of Cyber Security, Jinan University, Guangzhou 510632, China
Haizhou Ye: College of Cyber Security, Jinan University, Guangzhou 510632, China
Xuyang Liu: College of Cyber Security, Jinan University, Guangzhou 510632, China
Yijun Mao: College of Mathematics and Informatics, South China Agricultural University, Guangzhou 510642, China
Jilian Zhang: College of Cyber Security, Jinan University, Guangzhou 510632, China

Mathematics, 2023, vol. 11, issue 9, 1-25

Abstract: Approximate string searches have been widely applied in many fields, such as bioinformatics, text retrieval, search engines, and location-based services (LBS). However, the approximate string search results from third-party servers may be incorrect due to the possibility of malicious third parties or compromised servers. In this paper, we design an authenticated index structure (AIS) for string databases, which is based on the Merkle hash tree (MHT) method and the q -gram inverted index. Our AIS can facilitate verification object ( VO ) construction for approximate string searches with edit distance thresholds. We design an efficient algorithm named GS 2 for VO construction at the server side and search result verification at the user side. We also introduce an optimization method called GS 2 - opt that can reduce VO size dramatically. Finally, we conduct extensive experiments on real datasets to show that our proposed methods are efficient and promising.

Keywords: approximate string search; edit distance; query result authentication; database outsourcing; inverted index (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/9/2128/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/9/2128/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:9:p:2128-:d:1137862

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().