基于Divide-and-Conquer的搜索引擎数据库设计思想

目的提出一种基于Divide and Conquer的搜索引擎数据库设计思想 (Divide and ConquerDesign ,DCD)。方法通过将搜索引擎索引数据库中的庞大数据表分解为数据量较少的表 ,以降低系统的复杂性。结果模拟实验表明基于DCD的数据库设计大大提高了数据库的性能。

A Divide-and-Conquer Strategy for Embedding a Distance-Net Point Set Into E^n and Its Application

A divide-and-conquer strategy is given for embedding a distance-net point set into Euclidean space En, and the problem of embedding a bounded distance-net point set into E3 and its application to the macromolecular conformation with Nuclear Magnetic Resonance data are discussed.

Coalition-based downlink resource allocation for LTE system with divide-and-conquer approach

To take advantage of the multiuser diversity resulted from the variation in channel conditions among the users, it has become an interesting and challenging problem to efficiently allocate the resources such as subcarriers, bits, and power. Most of current research concentrates on solving the resource-allocation problem for all users together in a centralized way, which brings about high computational complexity and makes it impractical for real system. Therefore, a coalitional game framework for downlink multi-user resource allocation in long term evolution （LTE） system is proposed, based on the divide-and-conquer idea. The goal is to maximize the overall system data rate under the constraints of each user＇s minimal rate requirement and maximal transmit power of base station while considering the fairness among users. In this framework, a coalitional formation algorithm is proposed to achieve optimal coalition formation and a two-user bargaining algorithm is designed to bargain channel assignment between two users. The total computational complexity is greatly reduced in comparison with conventional methods. The simulation results show that the proposed algorithms acquire a good tradeoff between the overall system throughout and fairness, compared to maximal rate and max-min schemes.

一类图的彩虹连通数紧的上界的FPT算法

基于divide-and-conquer模式,针对有界树宽度的图设计了一个FPT算法,计算其彩虹连通数紧的上界,该算法是多项式时间可解的.

AUTOMATED EXTRACTION OF THE INNER CONTOUR OF THE ANTERIOR CHAMBER USING OPTICAL COHERENCE TOMOGRAPHY IMAGES

Manual analysis of anterior segment optical coherence tomography(AS-OCT)images is fairly time consuming,and inter-observer reproducibility cannot be guaranteed.Therefore,automated analysis methods of AS-OCT images are necessary in clinical applications.This paper presents a novel approach to extract the inner contour of the anterior chamber automatically from AS-OCT images using a"divide-and-conquer"strategy.Werstnd the anchor points in an image and these points are used to divide the image into subimages where the iris,lens and cornea are located.Then the endothelial surface of the cornea,lens surface and iris surface are obtained from these subimages with dierent schemes,and they are merged together to obtain the complete inner contour.In our method,the endothelial surface of the cornea istted by using three circular arcs under continuity constraints.Experiments show that the proposed algorithm can extract the inner contour of the anterior chamber from AS-OCT images accurately in real time.

23-Gauge Pars Plana Vitrectomy Alone by a Bimanual Technique for the Removal of Dense Posteriorly Dislocated Crystalline Lens

Background: We sought to verify the efficacy and safety of transconjunctival 23-gauge pars plana vitrectomy (PPV) alone by our bimanual technique for the removal of dense posteriorly dislocated crystalline lens. Methods: A retrospective, noncomparative, interventional study of 31 consecutive cases of patients who underwent 23-gauge PPV alone for the removal of dense posteriorly dislocated crystalline lens following complicated cataract surgeries using our bimanual technique was conducted. The main outcomes measured included best-corrected visual acuity (BCVA), preoperative intraocular pressure (IOP), postoperative IOP and postoperative complications. Results: In all 31 cases included in this study, those dense posteriorly dislocated crystalline lenses were successfully removed. The enrolled patients consisted of 17 males and 14 females with a mean age of (75.84 ± 6.17) years (range 59 - 90). The mean follow-up length was (7.61 ± 1.87) months with a range of 6 months to 1 year. The mean preoperative BCVA was 0.22 ± 0.11 logMAR system, and the postoperative BCVA was 0.33 ± 0.07 logMAR system after 6 months of follow-up. The mean operative time was 46.32 ± 4.80 minutes with a range of 38.00 to 57.00 minutes. All of the conjunctival incisions self-closed within the first week with no wound leakage or hemorrhage. The postoperative complications were relatively rare. Conclusions: The removal of dense posteriorly dislocated crystalline lens might be a challenge for micro-incision vitrectomy. Our bimanual technique was proved to be an effective and safe method for those particular dense lenses using 23-gauge alone.

A short note on fitting a single-index model with massive data

This paper studies the inference problem of index coefficient in single-index models under massive dataset.Analysis of massive dataset is challenging owing to formidable computational costs or memory requirements.A natural method is the averaging divide-and-conquer approach,which splits data into several blocks,obtains the estimators for each block and then aggregates the estimators via averaging.However,there is a restriction on the number of blocks.To overcome this limitation,this paper proposed a computationally efficient method,which only requires an initial estimator and then successively refines the estimator via multiple rounds of aggregations.The proposed estimator achieves the optimal convergence rate without any restriction on the number of blocks.We present both theoretical analysis and experiments to explore the property of the proposed method.

Application of Improved PSO-LSSVM on Network Threat Detection

To solve the problem of the design of classifier in network threat detection, we conduct a simulation experiment for the parameters’ optimal on least squares support vector machine （LSSVM） using the classic PSO algorithm, and the experiment shows that uneven distribution of the initial particle swarm exerts a great impact on the results of LSSVM algorithm’s classification. This article proposes an improved PSO-LSSVM algorithm based on Divide-and-Conquer （DCPSO- LSSVM） to split the optimal domain where the parameters of LSSVM are in. It can achieve the purpose of distributing the initial particles uniformly. And using the idea of Divide-and-Conquer, it can split a big problem into multiple sub-problems, thus, completing problems’ modularization Meanwhile, this paper introduces variation factors to make the particles escape from the local optimum. The results of experiment prove that DCPSO-LSSVM has better effect on classification of network threat detection compared with SVM and classic PSOLSSVM.

Security analysis of a new stream cipher

In this paper, we analyze the security of a new stream cipher-COSvd（2,128）. This cipher was proposed by E. Filiol et al. at the ECRYPT SASC＇2004 （The State of the Art of Stream Ciphers）. It uses clock-controlled non-linear feedback registers together with an S-box controlled by a chaotic sequence and was claimed to prevent any existing attacks. However, our analysis shows that there are some serious security flaws in the design of the S-box, resulting in heavy biased byte distribution in the keystream. In some broadcast applications, this flaw will cause a ciphertext-only attack with high success rate. Besides, there are also many security flaws in other parts of the cipher. We point out these flaws one by one and develop a divide-and-conquer attack to recover the secret keys from O（2^26）-byte known plaintext with success rate 93.4597% and complexity O（2^113）, which is much lower than 2^512, the complexity of exhaustive search.

A review of distributed statistical inference

The rapid emergence of massive datasets in various fields poses a serious challenge to tra-ditional statistical methods.Meanwhile,it provides opportunities for researchers to develop novel algorithms.Inspired by the idea of divide-and-conquer,various distributed frameworks for statistical estimation and inference have been proposed.They were developed to deal with large-scale statistical optimization problems.This paper aims to provide a comprehensive review for related literature.It includes parametric models,nonparametric models,and other frequently used models.Their key ideas and theoretical properties are summarized.The trade-off between communication cost and estimate precision together with other concerns is discussed.

A parallel scheduling algorithm for reinforcement learning in large state space

The main challenge in the area of reinforcement learning is scaling up to larger and more complex problems. Aiming at the scaling problem of reinforcement learning, a scalable reinforcement learning method, DCS-SRL, is proposed on the basis of divide-and-conquer strategy, and its convergence is proved. In this method, the learning problem in large state space or continuous state space is decomposed into multiple smaller subproblems. Given a specific learning algorithm, each subproblem can be solved independently with limited available resources. In the end, component solutions can be recombined to obtain the desired result. To ad- dress the question of prioritizing subproblems in the scheduler, a weighted priority scheduling algorithm is proposed. This scheduling algorithm ensures that computation is focused on regions of the problem space which are expected to be maximally productive. To expedite the learning process, a new parallel method, called DCS-SPRL, is derived from combining DCS-SRL with a parallel scheduling architecture. In the DCS-SPRL method, the subproblems will be distributed among processors that have the capacity to work in parallel. The experimental results show that learning based on DCS-SPRL has fast convergence speed and good scalability.

An adaptive lack of fit test for big data

New technological advancements combined with powerful computer hardware and high-speed network make big data available.The massive sample size of big data introduces unique computational challenges on scalability and storage of statistical methods.In this paper,we focus on the lack of fit test of parametric regression models under the framework of big data.We develop a computationally feasible testing approach via integrating the divide-and-conquer algorithm into a powerful nonparametric test statistic.Our theory results show that under mild conditions,the asymptotic null distribution of the proposed test is standard normal.Furthermore,the proposed test benefits fromthe use of data-driven bandwidth procedure and thus possesses certain adaptive property.Simulation studies show that the proposed method has satisfactory performances,and it is illustrated with an analysis of an airline data.

On the Arc Consistency Problem

In this paper, we propose a new arc consistency algorithm, AC-8,which requires less computation time and space than AC-6 and AC-7. The main ideaof the optimization is the divide-and-conquer strategy, thereby decomposing an arcconsistency problem into a series of smaller ones and trying to solve them in sequence.In this way, not only the space complexity but also the time complexity can be reduced. The reason for this is that due to the ahead of time performed inconsistencypropagation (in the sense that some of them are executed before the entire inconsis-tency checking has been finished), each constraint subnetwork will be searched with agradually shrunk domain. In addition, the technique of AC-6 can be integrated intoour algorithm, leading to a further decrease in computational complexity.

Big data analytics: six techniques

Big data have 4V characteristics of volume, variety, velocity, and veracity, which authentically calls for big data analytics. However, what are the dominant characteristics of big data analysis? Here, the analytics is related to the entire methodology rather than the individual specific analysis. In this paper, six techniques concerning big data analytics are proposed, which include: (1) Ensemble analysis related to a large volume of data, (2) Association analysis related to unknown data sampling, (3) High-dimensional analysis related to a variety of data, (4) Deep analysis related to the veracity of data, (5) Precision analysis related to the veracity of data, and (6) Divide-and-conquer analysis related to the velocity of data.The essential of big data analytics is the structural analysis of big data in an optimal criterion of physics, computation, and human cognition. fundamentally, two theoretical challenges, ie the violation of independent and identical distribution, and the extension of general set-theory, are posed. In particular, we have illustrated three kinds of association in geographical big data, ie geometrical associations in space and time, spatiotemporal correlations in statistics, and space-time relations in semantics. furthermore, we have illustrated three kinds of spatiotemporal data analysis, ie measurement (observation) adjustment of geometrical quantities, human spatial behavior analysis with trajectories, data assimilation of physical models and various observations, from which spatiotemporal big data analysis may be largely derived.