The Optimization And Application Of The Maxima-finding Algorithm For Massive Information

In recent years, massive information has become ubiquitous. Facing the hugeamount of data, how to effectively process these data in time is an important challengecurrently, or else a lot of data will lose its value. Fortunately, the maxima-finding issuch an effective data processing tool, which can help people find interested contentsrapidly from massive information. The maxima-finding came from computationalgeometry, and have appeared a great deal of applications in many areas recentlyincluding multiobjective optimization, data base, etc., because of its good applicationprospects. These applications often require extensive computational resources, whichlead traditional maxima-finding algorithms are hard to use effectively. To solve suchproblem, this dissertation is focus on the research of the performance optimization ofmaxima-finding algorithms and its applications.First, a survey of research status of maxima-finding algorithms is presented in thisdissertation. The current existing maxima-finding algorithms are comprehensiveanalyzed from two aspects of internal memory and external memory algorithms. Onthis foundation, a new maxima-finding algorithm based on volume first heuristics, anda linear I/O maxima-finding external memory algorithm, are presented. Theapplication of the combination of the two algorithms, in the field of database skylinequery and financial asset allocation problems, gets good experimental results. Primaryresearches and creations in this dissertation include the following four aspects:(1) A new maxima-finding algorithm based on volume first heuristics isconstructed. The result of experiments indicates that the efficiency of the algorithm ishigher than the classic MTF algorithm proposed by Bently et al. The theoretic proofshows that the time complexity of the algorithm keeps linearity with extremely highprobability. The open problem of no linear time maxima-finding algorithm has solvedpartial. The theoretic proof in high dimension spaces provides the beneficial referenceto the complexity analysis of maxima-finding algorithms in high dimensional spaces.(2) Because classical algorithms often cannot handle data properly when dataexceed main memory limits, recent attention has focused on algorithms that processdata in external storage. In these cases, the efficiency of algorithms is usuallymeasured by the communication number between input and output data (I/O number). For the maxima-finding problem, there has no linear I/O external memory algorithmyet. So a linear I/O maxima-finding algorithm dealing with massive data has beenpresented in this dissertation, which is based on the probability nature of maximanumber, and in connection with the independent identically distributed data set. Thecorresponding reliability has been validated from experiments and theor y.(3) The database skyline query processing is a hot research point in the field ofdatabase query in recent years. The maxima-finding problem has a natural relationshipwith the skyline query. In this dissertation, the proposed algorithm is applied in thefield of skyline query in database, and gets a nice experimental performance. Theinternal memory time complexity and I/O complexity of the algorithm both havereached linear time.(4) The massive data information appears in financial areas frequently. H ow tofind the valuable information from these data guiding investment decisions is one ofthe most important problems in the modern investment theory. To investigate theapplication of the maxima-finding problem in the field of investment decisions, someinteresting phenomenon has been discovered during the study of the historyperformance of asset categories. A stock classification method, which is based on thecommunity structure in complex networks, and a new portfolio strategy usingmaxima-finding are systematic proposed for the first time.