Low complexity quantum private queries protocol

Private information retrieval(PIR) is an important privacy protection issue of secure multi-party computation, but the PIR protocols based on classical cryptography are vulnerable because of new technologies,such as quantum computing and cloud computing. The quantum private queries(QPQ) protocols available, however, has a high complexity and is inefficient in the face of large database. This paper, based on the QKD technology which is mature now, proposes a novel QPQ protocol utilizing the key dilution and auxiliary parameter. Only N quits are required to be sent in the quantum channel to generate the raw key, then the straight k bits in the raw key are added bitwise to dilute the raw key, and a final key is consequently obtained to encrypt the database. By flexible adjusting of auxiliary parameters θ and k, privacy is secured and the query success ratio is improved. Feasibility and performance analyses indicate that the protocol has a high success ratio in first-trial query and is easy to implement, and that the communication complexity of O(N) is achieved.     

On recommendation problems beyond points of interest

Recommendation systems aim to recommend items or packages of items that are likely to be of interest to users. Previous work on recommendation systems has mostly focused on recommending points of interest (POI), to identify and suggest top-k items or packages that meet selection criteria and satisfy compatibility constraints on items in a package, where the (packages of) items are ranked by their usefulness to the users. As opposed to prior work, this paper investigates two issues beyond POI recommendation that are also important to recommendation systems. When there exist no sufficiently many POI that can be recommended, we propose (1) query relaxation recommendation to help users revise their selection criteria, or (2) adjustment recommendation to guide recommendation systems to modify their item collections, such that the users׳ requirements can be satisfied.We study two related problems, to decide (1) whether the query expressing the selection criteria can be relaxed to a limited extent, and (2) whether we can update a bounded number of items, such that the users can get desired recommendations. We establish the upper and lower bounds of these problems, all matching, for both combined and data complexity, when selection criteria and compatibility constraints are expressed in a variety of query languages, for both item recommendation and package recommendation. To understand where the complexity comes from, we also study the impact of variable sizes of packages, compatibility constraints and selection criteria on the analyses of these problems. Our results indicate that in most cases the complexity bounds of query relaxation and adjustment recommendation are comparable to their counterparts of the basic recommendation problem for testing whether a given set of (resp. packages of) items makes top-k items (resp. packages). In other words, extending recommendation systems with the query relaxation and adjustment recommendation functionalities typically does not incur extra overhead.     

GOS+MU:一种查询对象选择新方法

在分析单一MU(Most Uncertainty)采样缺陷的基础上,提出一种"全局最优搜寻"方法 GOS(Global Optimal Search),并结合MU共同完成查询选择。GOS+MU方法中,GOS着眼全局寻找目标,在应用环境能提供的训练样本数量有限、分类器受训不充分时,该方法选择的对象学习价值高,能快速推进分类器学习进程;MU则能够在GOS采样失效情形下,利用分类器当前训练成果,选择查询不确定性最强的样本补充训练集。通过对网络商品的用户评论进行分类仿真,并比较其他采样学习方法的效果,证明了GOS+MU方法在压缩学习成本、提高训练效率方面的有效性。     

Optimal shift partitioning of pharmacies

The pharmacy service requires that some pharmacies are always available and shifts have to be organized: a shift corresponds to a subset of pharmacies that must be open 24 hours a day on a particular week. Under the requirement that each pharmacy belongs to exactly one shift and the assumption that users minimize the distance to the closest open pharmacy during each shift, we want to determine a partition of the pharmacies into a given number of shifts, such that the total distance covered by users is minimized. It may be also required that shift cardinalities are balanced. We discuss different versions and the related computational complexity, showing that the problem is NP-hard in general. A set packing formulation is presented and solved by branch-and-price, together with a fast solution technique based on a tabu search. They have been applied to real and random instances showing that (i) the set packing formulation is very tight and often exhibits no integrality gap; (ii) the branch-and-price solves problems of practical relevance to optimality in a reasonable amount of time (order of minutes); (iii) the tabu search finds optimal or near-optimal solutions in order of seconds.     

Learning keyword phrases from query logs of USPTO patent examiners for automatic query scope limitation in patent searching

Professional search in patent repositories poses several unique challenges. One key requirement is to search the entire affected space of concepts, following well-defined procedures to ensure traceability of results obtained. Several techniques have been introduced to enhance query generation, preferably via automated query term expansion, to improve retrieval effectiveness. Currently, these approaches are mostly limited to computing additional query terms from patent documents based on statistical measures. For conceptual search to solve the limitation of traditional keyword search standard dictionaries are used to provide synonyms and keyword phrases for query refinement. Studies show that these are insufficient in such highly specialized domains. In this paper, we present an approach to extract keyword phrases from query logs created during the validation procedure of the patent applications. This creates valuable domain-specific lexical databases for several specific patent classes that can be used to both expand as well as limit the scope of a patent search. This provides a more powerful means to guide a professional searcher through the search process. We evaluate the lexical databases based on real query sessions of patent examiners.     

一种实用的多数据库量子信息检索协议

针对目前量子私有信息检索不能适用与云存储的多数据库问题,基于现在成熟的量子密钥分发方法,提出了一种适合在多数据库环境下,实用的量子私有信息检索协议。对于不同大小的数据库,协议可通过调节参数θ和k,在保证数据库安全及用户隐私的情况下,完成信息的检索。性能分析结果表明,协议的通信复杂度低,检索成功率高、易于实施。     

On keys' meanings and modes: the impact of different key solutions on children's efficiency using a mobile phone

The present study investigates the impact of different key solutions of mobile phones on users' effectiveness and efficiency using the devices. In the first experiment, 36 children (9 - 14 years) and in the second experiment 45 young adults (19 - 33 years) completed four common phone tasks twice consecutively on three simulated phones that had identical menus, but different key solutions. An approach was undertaken to quantify the complexity of keys in three models, incorporating different factors contributing to the keys' complexity (number of key options, number of modes and number of modes with a semantically dissimilar meaning), in order to predict users' performance decrements. As a further main factor, the degree of the users' locus of control (LOC) was measured and interactions with performance outcomes were studied. As dependent measures, the number of inefficient keystrokes, the number of tasks solved and the processing time were determined. Results showed a significant effect of control key solutions on users' efficiency and effectiveness for both children and young adults. Moreover, children's LOC values significantly interacted with performance: children with low LOC values showed the lowest performance and no learnability, especially when using keys with a high complexity. From the three factors contributing to the complexity of keys, keys exerting different functions with semantically inconsistent meanings had the worst effect on performance. It is concluded that in mobile user interface design keys with semantically inconsistent meanings should be generally avoided.     

Study on the Complexity of the Bullwhip Effect

Recent years have witnessed a rapid growth of interest in the study of the dynamic behavior of replenishment rules of bullwhip effect. We prove that bullwhip effect and butterfly effect share a same the self-oscillation amplifying mechanism that is the ordering decisions the supplier self-oscillation amplify the perturbations brought by the errors in the processing of retailers' demand information. This results as an explicit self-similar structure of the sensitivity of the system to the initial values duty to the nonlinear mechanism. In this paper, the causes process of the bullwhip effect is described as the internal nonlinear mechanism and study on the complexity of bullwhip effect for order-up-to policy under demand signal processing. The methodology is based on fractal and chaotic theory and allows important insights to be gained about the complexity behavior of bullwhip effect.