SWMQ: Secure wildcard pattern matching with query Xu, Lin; Wei, Xiaochao; Cai, Guopeng ...
International journal of intelligent systems,
September 2022, 2022-09-00, 20220901, Volume:
37, Issue:
9
Journal Article
Peer reviewed
Open access
Secure wildcard pattern matching (WPM) allows the pattern holder to obtain the matched positions without revealing pattern and text information about both parties. However, standard secure WPM may ...have limitations in practical applications, as users may prefer to have access to the actual data of the match in many scenarios. Fortunately, secure wildcard pattern matching with query (SWMQ) extends standard secure WPM by allowing the pattern holder to obtain the matched positions and the actual data, which has important applications in many scenarios, such as electronic healthcare and gene matching. This also motivates the research of SWMQ in this paper. In this study, we focus on the efficient construction of SWMQ in the semihonest adversary setting. First, we propose two new primitives, hereafter referred to as shared wildcard pattern matching (Sh‐WPM) and choice‐sharing oblivious transfer (CSOT). Furthermore, we propose an SWMQ protocol via Shared WPM and CSOT. In addition, we evaluate the performance of SWMQ. More specifically, the running time in local area network and wide area network settings is less than 0.4 and 2 s, respectively, when the text length is
2
16 ${2}^{16}$ and the pattern length is
2
12 ${2}^{12}$. In fact, our evaluation results suggest that SWMQ is not only more broadly functional, but also comparable in efficiency to state‐of‐the‐art approaches.
Full text
Available for:
FZAB, GIS, IJS, KILJ, NLZOH, NUK, OILJ, SBCE, SBMB, UL, UM, UPUK
Pattern matching with wildcards is a string matching problem with the goal of finding all factors of a text t of length n that match a pattern x of length m, where wildcards (characters that match ...everything) may be present. In this paper we present a number of complexity results and fast average-case algorithms for pattern matching where wildcards are allowed in the pattern, however, the results are easily adapted to the case where wildcards are allowed in the text as well. We analyse the average-case complexity of these algorithms and derive non-trivial time bounds. These are the first results on the average-case complexity of pattern matching with wildcards which provide a provable separation in time complexity between exact pattern matching and pattern matching with wildcards. We introduce the wc-period of a string which is the period of the binary mask xb where xbi=aiffxi≠ϕ and b otherwise. We denote the length of the wc-period of a string x by ▪. We show the following results for constant 0<ϵ<1 and a pattern x of length m and g wildcards with ▪ the prefix of length p contains gp wildcards:•If limm→∞gpp=0 there is an optimal algorithm running in O(nlogσmm)-time on average.•If limm→∞gpp=1−ϵ there is an algorithm running in O(nlogσmlog2pm)-time on average.•If limm→∞gm=limm→∞1−f(m)=1 any algorithm takes at least Ω(nlogσmf(m))-time on average.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Most current customer baseline load (CBL) estimation methods for incentive-based demand response (DR) rely heavily on historical data and are unable to adapt to the cases when the load patterns (LPs) ...in the DR event day are not similar enough to those in non-DR days. After the error generation mechanism of current methods is revealed, a synchronous pattern matching principle-based residential CBL estimation approach without historical data requirement is proposed. All customers are split into DR and CONTROL group, including DR participants and non-DR customers, respectively. First, all CONTROL group customers are clustered into several non-overlapping clusters according to LPs similarity in the DR event day. Second, each DR participant is matched to the most similar cluster in the CONTROL group according to the similarity between its load curve segments in DR event day, excluding DR part and cluster centroids. Third, the CBL of each DR participant is estimated with an optimized weight combination method using the load data within the DR event period of all the customers in the very matching cluster in the CONTROL group. A comparison with five well-known CBL estimation methods using a dataset of 736 residential customers indicates that the proposed approach has better overall performance than other current CBL estimation methods.
Research Summary
We apply pattern‐matching techniques to contrast qualitative case study data with perspectives from strategic management and institutional economics about how a firm can address ...voids in market‐based institutions. We identify a novel approach whereby the firm builds an open institutional infrastructure (OII) by investing in a pool of resources widely accessible beyond its exchange partners. To collectively govern OII, the firm must empower other actors within multilateral cross‐sector partnerships, and it must enforce the resulting rules through relational norms based on alignment between public and private value creation. These findings, achieved by adapting Elinor Ostrom's principles of polycentric governance to corporate actors who take the lead in building OII, advance our understanding of new organizational forms that transcend the traditional boundaries of firms and markets.
Managerial Summary
Emerging markets typically present additional obstacles for business operations because they lack the necessary underlying institutional infrastructure such as access to capital and labor markets. We introduce a new way for firms to overcome these obstacles—which we call building an OII—by investing in such infrastructure themselves and making it available to their commercial partners, local communities, and even to competitors. Firms must empower those actors to take the lead in collectively defining the rules for accessing this infrastructure, by orchestrating cross‐sector partnerships. This process creates relational norms around the alignment of public and private interests, which ultimately can promote firms' competitive advantage.
Full text
Available for:
BFBNIB, FZAB, GIS, IJS, KILJ, NLZOH, NUK, OILJ, SBCE, SBMB, UL, UM, UPUK
Goal: Traditional visual brain-computer interfaces (BCIs) preferred to use large-size stimuli to attract the user's attention and elicit distinct electroencephalography (EEG) features. However, the ...visual stimuli are of no interest to the users as they just serve as the hidden codes behind the characters. Furthermore, using stronger visual stimuli could cause visual fatigue and other adverse symptoms to users. Therefore, it's imperative for visual BCIs to use small and inconspicuous visual stimuli to code characters. Methods: This study developed a new BCI speller based on miniature asymmetric visual evoked potentials (aVEPs), which encodes 32 characters with a space-code division multiple access scheme and decodes EEG features with a discriminative canonical pattern matching algorithm. Notably, the visual stimulus used in this study only subtended 0.5° of visual angle and was placed outside the fovea vision on the lateral side, which could only induce a miniature potential about 0.5 μ V in amplitude and about 16.5 dB in signal-to-noise rate. A total of 12 subjects were recruited to use the miniature aVEP speller in both offline and online tests. Results: Information transfer rates up to 63.33 b/min could be achieved from online tests (online demo URL: https://www.youtube.com/edit?o=U&video_id=kC7btB3mvGY ). Conclusion: Experimental results demonstrate the feasibility of using very small and inconspicuous visual stimuli to implement an efficient BCI system, even though the elicited EEG features are very weak. Significance: The proposed innovative technique can broaden the category of BCIs and strengthen the brain-computer communication.
Event-related potentials (ERPs) are one of the most popular control signals for brain-computer interfaces (BCIs). However, they are very weak and sensitive to the experimental settings including ...paradigms, stimulation parameters and even surrounding environments, resulting in a diversity of ERP patterns across different BCI experiments. It's still a challenge to develop a general decoding algorithm that can adapt to the ERP diversities of different BCI datasets with small training sets. This study compared a recently developed algorithm, i.e., discriminative canonical pattern matching (DCPM), with seven ERP-BCI classification methods, i.e., linear discriminant analysis (LDA), stepwise LDA, bayesian LDA, shrinkage LDA, spatial-temporal discriminant analysis (STDA), xDAWN and EEGNet for the single-trial classification of two private EEG datasets and three public EEG datasets with small training sets. The feature ERPs of the five datasets included P300, motion visual evoked potential (mVEP), and miniature asymmetric visual evoked potential (aVEP). Study results showed that the DCPM outperformed other classifiers for all of the tested datasets, suggesting the DCPM is a robust classification algorithm for assessing a wide range of ERP components.
Besides its NP-completeness, the strict constraints of subgraph isomorphism are making it impractical for graph pattern matching (GPM) in the context of big data. As a result, relaxed GPM models have ...emerged as they yield interesting results in a polynomial time. However, massive graphs generated by mostly social networks require a distributed storing and processing of the data over multiple machines, thus, requiring GPM to be revised by adopting new paradigms of big graphs processing, e.g., Think-Like-A-Vertex and its derivatives. This article discusses and proposes a classification of distributed GPM approaches with a narrow focus on the relaxed models.
Full text
Available for:
IZUM, KILJ, NUK, PILJ, SAZU, UL, UM, UPUK
The key of image and sentence matching is to accurately measure the visual-semantic similarity between an image and a sentence. However, most existing methods make use of only the intra-modality ...relationship within each modality or the inter-modality relationship between image regions and sentence words for the cross-modal matching task. Different from them, in this work, we propose a novel MultiModality Cross Attention (MMCA) Network for image and sentence matching by jointly modeling the intra-modality and inter-modality relationships of image regions and sentence words in a unified deep model. In the proposed MMCA, we design a novel cross-attention mechanism, which is able to exploit not only the intra-modality relationship within each modality, but also the inter-modality relationship between image regions and sentence words to complement and enhance each other for image and sentence matching. Extensive experimental results on two standard benchmarks including Flickr30K and MS-COCO demonstrate that the proposed model performs favorably against state-of-the-art image and sentence matching methods.
•In this paper, four new online portfolio selection algorithms have been proposed.•In these algorithms, clustering techniques are used in pattern matching approaches.•Transaction costs have been ...considered in the proposed algorithms.•Based on the results, the proposed algorithms outperform the competing algorithms.
This paper presents an online portfolio selection algorithm based on pattern matching principle where it makes a decision on the optimal portfolio in each period and updates the optimal portfolio at the beginning of each period. The proposed method consists of two steps: i) sample selection, ii) portfolio optimization. First, in the sample selection, clustering algorithms including k-means, k-medoids, spectral and hierarchical clustering are applied to discover time windows (TW) similar to the recent time window. Then, after finding the similar time windows and predicting the market behavior of the next day, the optimum function along with the transaction cost is used in the portfolio optimization step in which, four algorithms including KMNLOG, KMDLOG, SPCLOG and HRCLOG are proposed for this purpose. The presented algorithms are applied on 5 different datasets with different characteristics including different markets, stocks, and time periods, and their performance has been evaluated. The results show that the provided algorithms in this paper, have better performance in terms of efficiency compared to the algorithms provided in the literature.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Optical proximity correction (OPC) is a widely used technique to enhance the printability of designs in various foundaries. Recently, there has been a growing interest in using rigorous numerical ...optimization and machine learning to improve the robustness and efficiency of OPC. Our research focuses on developing a self-adaptive OPC framework that leverages the properties of pattern distribution and repetition in design layouts to optimize the correction process. We observe that different sub-regions in a design layer have varying pattern complexities, and many patterns repeat themselves throughout the layout. By exploiting these properties, we propose a framework that adaptively selects the most suitable OPC solvers from an extensible pool to optimize the correction process for each pattern based on its complexity. This approach allows for a co-optimization of speed and accuracy. Additionally, we introduce a graph-based dynamic pattern library that reuses optimized masks for repeated patterns, further accelerating the OPC flow. Our experimental results demonstrate a significant improvement in both performance and efficiency using our proposed framework.
PDF
