Multi-pattern matching with wildcards is a problem of finding the occurrence of all patterns in a pattern set {p^1,… ,p^k} in a given text t. If the percentage of wildcards in pattern set is not high, this problem ca...Multi-pattern matching with wildcards is a problem of finding the occurrence of all patterns in a pattern set {p^1,… ,p^k} in a given text t. If the percentage of wildcards in pattern set is not high, this problem can be solved using finite automata. We introduce a multi-pattern matching algorithm with a fixed number of wildcards to overcome the high percentage of the occurrence of wildcards in patterns. In our proposed method, patterns are matched as bit patterns using a sliding window approach. The window is a bit window that slides along the given text, matching against stored bit patterns. Matching process is executed using bit wise operations. The experimental results demonstrate that the percentage of wildcard occurrence does not affect the proposed algorithm＇s performance and the proposed algorithm is more efficient than the algorithms based on the fast Fourier transform. The proposed algorithm is simple to implement and runs efficiently in O（n ＋ d（n/σ ）（m/w）） time, where n is text length, d is symbol distribution over k patterns, m is pattern length, and σ is alphabet size.展开更多
In this article, based on Chatterjee-Sarkar＇ hierarchical identity-based encryption （HIBE）, a novel identity-based encryption with wildcards （WIBE） scheme is proposed and is proven secure in the standard model （...In this article, based on Chatterjee-Sarkar＇ hierarchical identity-based encryption （HIBE）, a novel identity-based encryption with wildcards （WIBE） scheme is proposed and is proven secure in the standard model （without random oracle）. The proposed scheme is proven to be secure assuming that the decisional Bilinear Diffie-Hellman （DBDH） problem is hard. Compared with the Wa-WIBE scheme that is secure in the standard model, our scheme has shorter common parameters and ciphertext length.展开更多
Pattern matching with wildcards（PMW） has great theoretical and practical significance in bioinformatics,information retrieval, and pattern mining. Due to the uncertainty of wildcards, not only is the number of all m...Pattern matching with wildcards（PMW） has great theoretical and practical significance in bioinformatics,information retrieval, and pattern mining. Due to the uncertainty of wildcards, not only is the number of all matches exponential with respect to the maximal gap flexibility and the pattern length, but the matching positions in PMW are also hard to choose. The objective to count the maximal number of matches one by one is computationally infeasible. Therefore,rather than solving the generic PMW problem, many research efforts have further defined new problems within PMW according to different application backgrounds. To break through the limitations of either fixing the number or allowing an unbounded number of wildcards, pattern matching with flexible wildcards（PMFW） allows the users to control the ranges of wildcards. In this paper, we provide a survey on the state-of-the-art algorithms for PMFW, with detailed analyses and comparisons, and discuss challenges and opportunities in PMFW research and applications.展开更多
We propose a simple statistical approach for using Dispersal-Vicariance Analysis （DIVA） software to infer biogeographic histories without fully bifurcating trees. In this approach, ancestral ranges are first optimiz...We propose a simple statistical approach for using Dispersal-Vicariance Analysis （DIVA） software to infer biogeographic histories without fully bifurcating trees. In this approach, ancestral ranges are first optimized for a sample of Bayesian trees. The probability P of an ancestral range r at a node is then calculated as P（rY） = ∑t^n=1 F（rY）t Pt where Y is a node, and F（rY） is the frequency of range r among all the optimal solutions resulting from DIVA optimization at node Y, t is one of n topologies optimized, and Pt is the probability of topology t. Node Y is a hypothesized ancestor shared by a specific crown lineage and the sister of that lineage ＂x＂, where x may vary due to phylogenetic uncertainty （polytomies and nodes with posterior probability 〈 100%）. Using this method, the ancestral distribution at Y can be estimated to provide inference of the geographic origins of the specific crown group of interest. This approach takes into account phylogenetic uncertainty as well as uncertainty from DIVA optimization. It is an extension of the previously described method called Bayes-DIVA, which pairs Bayesian phylogenetic analysis with biogeographic analysis using DIVA. Further, we show that the probability P of an ancestral range at Y calculated using this method does not equate to pp＊F（rY） on the Bayesian consensus tree when both variables are 〈 100%, where pp is the posterior probability and F（rY） is the frequency of range r for the node containing the specific crown group. We tested our DIVA-Bayes approach using Aesculus L., which has major lineages unresolved as a polytomy. We inferred the most probable geographic origins of the five traditional sections of Aesculus and ofAesculus californica Nutt. and examined range subdivisions at parental nodes of these lineages. Additionally, we used the DIVA-Bayes data from Aesculus to quantify the effects on biogeographic inference of including two wildcard fossil taxa in phylogenetic analysis. Our analysis resolved the geographic ranges of the parental nodes of the lineages of Aesculus with moderate to high probabilities. The probabilities were greater than those estimated using the simple calculation ofpp＊F（rY） at a statistically significant level for two of the six lineages. We also found that adding fossil wildcard taxa in phylogenetic analysis generally increased P for ancestral ranges including the fossil＇s distribution area. The AP was more dramatic for ranges that include the area of a wildcard fossil with a distribution area underrepresented among extant taxa. This indicates the importance of including fossils in biogeographic analysis. Exmination of range subdivision at the parental nodes revealed potential range evolution （extinction and dispersal events） along the stems ofA. californica and sect. Parryana.展开更多
Wildcard searchable encryption allows the server to efficiently perform wildcard-based keyword searches over encrypted data while maintaining data privacy.A promising solution to achieve wildcard SSE is to extract the...Wildcard searchable encryption allows the server to efficiently perform wildcard-based keyword searches over encrypted data while maintaining data privacy.A promising solution to achieve wildcard SSE is to extract the characteristics of the queried keyword and check the existence based on a membership test structure.However,existing schemes have false positives of character order,that is,the server cannot identify the order between the first and the last wildcard character.Besides,the schemes also suffer from characteristic matching pattern leakage due to the one-by-one membership testing.In this paper,we present the first efficient wildcard SSE scheme to eliminate the false positives of character order and characteristic matching pattern leakage.To this end,we design a novel characteristic extraction technique that enables the client to exact the characteristics of the queried keyword maintaining the order between the first and the last wildcard character.Then,we utilize the primitive of Symmetric Subset Predicate Encryption,which supports checking if one set is a subset of another in one shot to reduce the characteristic matching pattern leakage.Finally,by performing a formal security analysis and implementing the scheme on a real-world database,we demonstrate that the desired security properties are achieved with high performance.展开更多
基金Supported by the European Framework Program(FP7)(FP7-PEOPLE-2011-IRSES)the National Sci-Tech Support Plan of China(2014BAH02F03)
文摘Multi-pattern matching with wildcards is a problem of finding the occurrence of all patterns in a pattern set {p^1,… ,p^k} in a given text t. If the percentage of wildcards in pattern set is not high, this problem can be solved using finite automata. We introduce a multi-pattern matching algorithm with a fixed number of wildcards to overcome the high percentage of the occurrence of wildcards in patterns. In our proposed method, patterns are matched as bit patterns using a sliding window approach. The window is a bit window that slides along the given text, matching against stored bit patterns. Matching process is executed using bit wise operations. The experimental results demonstrate that the percentage of wildcard occurrence does not affect the proposed algorithm＇s performance and the proposed algorithm is more efficient than the algorithms based on the fast Fourier transform. The proposed algorithm is simple to implement and runs efficiently in O（n ＋ d（n/σ ）（m/w）） time, where n is text length, d is symbol distribution over k patterns, m is pattern length, and σ is alphabet size.
基金supported by the National Natural Science Foundation of China (60473027).
文摘In this article, based on Chatterjee-Sarkar＇ hierarchical identity-based encryption （HIBE）, a novel identity-based encryption with wildcards （WIBE） scheme is proposed and is proven secure in the standard model （without random oracle）. The proposed scheme is proven to be secure assuming that the decisional Bilinear Diffie-Hellman （DBDH） problem is hard. Compared with the Wa-WIBE scheme that is secure in the standard model, our scheme has shorter common parameters and ciphertext length.
基金supported in part by the National Natural Science Foundation of China under Grant Nos.61229301 and 60828005the Program for Changjiang Scholars and Innovative Research Team in University(PCSIRT)of the Ministry of Education,China,under Grant No.IRT13059the National Science Foundation(NSF)of USA under Grant No.0514819
文摘Pattern matching with wildcards（PMW） has great theoretical and practical significance in bioinformatics,information retrieval, and pattern mining. Due to the uncertainty of wildcards, not only is the number of all matches exponential with respect to the maximal gap flexibility and the pattern length, but the matching positions in PMW are also hard to choose. The objective to count the maximal number of matches one by one is computationally infeasible. Therefore,rather than solving the generic PMW problem, many research efforts have further defined new problems within PMW according to different application backgrounds. To break through the limitations of either fixing the number or allowing an unbounded number of wildcards, pattern matching with flexible wildcards（PMFW） allows the users to control the ranges of wildcards. In this paper, we provide a survey on the state-of-the-art algorithms for PMFW, with detailed analyses and comparisons, and discuss challenges and opportunities in PMFW research and applications.
基金a National Science Foundation (USA) grant made to Xiang(DEB-0444125)supported by a NSF grant funded to D.E.Soltis (DEB-0090283)
文摘We propose a simple statistical approach for using Dispersal-Vicariance Analysis （DIVA） software to infer biogeographic histories without fully bifurcating trees. In this approach, ancestral ranges are first optimized for a sample of Bayesian trees. The probability P of an ancestral range r at a node is then calculated as P（rY） = ∑t^n=1 F（rY）t Pt where Y is a node, and F（rY） is the frequency of range r among all the optimal solutions resulting from DIVA optimization at node Y, t is one of n topologies optimized, and Pt is the probability of topology t. Node Y is a hypothesized ancestor shared by a specific crown lineage and the sister of that lineage ＂x＂, where x may vary due to phylogenetic uncertainty （polytomies and nodes with posterior probability 〈 100%）. Using this method, the ancestral distribution at Y can be estimated to provide inference of the geographic origins of the specific crown group of interest. This approach takes into account phylogenetic uncertainty as well as uncertainty from DIVA optimization. It is an extension of the previously described method called Bayes-DIVA, which pairs Bayesian phylogenetic analysis with biogeographic analysis using DIVA. Further, we show that the probability P of an ancestral range at Y calculated using this method does not equate to pp＊F（rY） on the Bayesian consensus tree when both variables are 〈 100%, where pp is the posterior probability and F（rY） is the frequency of range r for the node containing the specific crown group. We tested our DIVA-Bayes approach using Aesculus L., which has major lineages unresolved as a polytomy. We inferred the most probable geographic origins of the five traditional sections of Aesculus and ofAesculus californica Nutt. and examined range subdivisions at parental nodes of these lineages. Additionally, we used the DIVA-Bayes data from Aesculus to quantify the effects on biogeographic inference of including two wildcard fossil taxa in phylogenetic analysis. Our analysis resolved the geographic ranges of the parental nodes of the lineages of Aesculus with moderate to high probabilities. The probabilities were greater than those estimated using the simple calculation ofpp＊F（rY） at a statistically significant level for two of the six lineages. We also found that adding fossil wildcard taxa in phylogenetic analysis generally increased P for ancestral ranges including the fossil＇s distribution area. The AP was more dramatic for ranges that include the area of a wildcard fossil with a distribution area underrepresented among extant taxa. This indicates the importance of including fossils in biogeographic analysis. Exmination of range subdivision at the parental nodes revealed potential range evolution （extinction and dispersal events） along the stems ofA. californica and sect. Parryana.
基金supported by the National Cryptologic Science Fund of China(2025NCSF02025)National Natural Science Foundation of China(U24B20149,62272385,U23A20302,62311540156 and 62102313)+1 种基金the Key Research and Development Program of Shaanxi(2024GX-ZDCYL-01-09,2022KWZ-01)Major Program of Shandong Provincial Natural Science Foundation for the Fundamental Research(ZR2022ZD03).
文摘Wildcard searchable encryption allows the server to efficiently perform wildcard-based keyword searches over encrypted data while maintaining data privacy.A promising solution to achieve wildcard SSE is to extract the characteristics of the queried keyword and check the existence based on a membership test structure.However,existing schemes have false positives of character order,that is,the server cannot identify the order between the first and the last wildcard character.Besides,the schemes also suffer from characteristic matching pattern leakage due to the one-by-one membership testing.In this paper,we present the first efficient wildcard SSE scheme to eliminate the false positives of character order and characteristic matching pattern leakage.To this end,we design a novel characteristic extraction technique that enables the client to exact the characteristics of the queried keyword maintaining the order between the first and the last wildcard character.Then,we utilize the primitive of Symmetric Subset Predicate Encryption,which supports checking if one set is a subset of another in one shot to reduce the characteristic matching pattern leakage.Finally,by performing a formal security analysis and implementing the scheme on a real-world database,we demonstrate that the desired security properties are achieved with high performance.
