目的提出一种基于Divide and Conquer的搜索引擎数据库设计思想 (Divide and ConquerDesign ,DCD)。方法通过将搜索引擎索引数据库中的庞大数据表分解为数据量较少的表 ,以降低系统的复杂性。结果模拟实验表明基于DCD的数据库设计大大...目的提出一种基于Divide and Conquer的搜索引擎数据库设计思想 (Divide and ConquerDesign ,DCD)。方法通过将搜索引擎索引数据库中的庞大数据表分解为数据量较少的表 ,以降低系统的复杂性。结果模拟实验表明基于DCD的数据库设计大大提高了数据库的性能。展开更多
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 co...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.展开更多
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 subcar...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.展开更多
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...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.展开更多
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. Metho...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.展开更多
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 na...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.展开更多
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 alg...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.展开更多
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 ...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.展开更多
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 i...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.展开更多
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, i...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.展开更多
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 ...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.展开更多
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 decomposi...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 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 i...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.展开更多
基金Project supported by the National Natural Science Foundation of China.
文摘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.
基金supported by the National Science and Technology Major Project(2011ZX03001-007-03)the National Natural Science Foundation of China(61271182)
文摘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.
基金supported by the National Natural Science Foundation of China under Grant No.60971006The AS-OCT images were provided by Shenzhen Moptim Imaging Technique Co.,Ltd.,China.
文摘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.
文摘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.
基金the Fundamental Research Funds for the Central Universities of China(No.2232020D-43).
文摘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.
基金Supported by the Special Fund of Financial Support for Development of Local Universities in China(2012-140 &2012-118)The Science and Technology Foundation of Guizhou Provincial([2011] 2213)Natural Sciences Research Foundation of Guizhou Normal University for Student(201219)
文摘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.
基金supported by the National Natural Science Foundation of China(Grant Nos.60273027,60373047)the National Grand Fundamental Research 973 Program of China(Grant No.2004CB318004).
文摘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.
基金This work is supported by National Natural Science Foun-dation of China(No.11971171)the 111 Project(B14019)and Project of National Social Science Fund of China(15BTJ027)+3 种基金Weidong Liu’s research is supported by National Program on Key Basic Research Project(973 Program,2018AAA0100704)National Natural Science Foundation of China(No.11825104,11690013)Youth Talent Sup-port Program,and a grant from Australian Research Council.Hansheng Wang’s research is partially supported by National Natural Science Foundation of China(No.11831008,11525101,71532001)It is also supported in part by China’s National Key Research Special Program(No.2016YFC0207704).
文摘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.
基金Acknowledgements This paper was supported by the National Natural Science Foundation of China (Grant Nos. 61272005, 61070223, 61103045, 60970015, and 61170020), Natural Science Foundation of Jiangsu (BK2012616, BK2009116), High School Natural Foundation of Jiangsu (09KJA520002), and Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University (93K172012K04).
文摘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.
基金This paper was supported by the National Natural Science Foundation of China[grant number 11431006][grant num-ber 11690015]+1 种基金[grant number 11371202][grant number 11622104].
文摘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.
文摘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.
基金This study is supported jointly by the Fundamental Research Funds for the Central Universities, the Key Project of National Natural Science Foundation of China [grant number 41331175, and the LIESMARS Special Research Funding
文摘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.