A shortest path algorithm for moving objects in spatial network databases

One of the most important kinds of queries in Spatial Network Databases (SNDB) to support location-based services (LBS) is the shortest path query. Given an object in a network, e.g. a location of a car on a road network, and a set of objects of interests, e.g. hotels,gas station, and car, the shortest path query returns the shortest path from the query object to interested objects. The studies of shortest path query have two kinds of ways, online processing and preprocessing. The studies of preprocessing suppose that the interest objects are static. This paper proposes a shortest path algorithm with a set of index structures to support the situation of moving objects. This algorithm can transform a dynamic problem to a static problem. In this paper we focus on road networks. However, our algorithms do not use any domain specific information, and therefore can be applied to any network. This algorithm’s complexity is O(klog2 i), and traditional Dijkstra’s complexity is O((i + k)2).

a shortest path algorithm for moving objects in spatial network databases

中国计算机学会

并行最优路径算法及K优路径算法研究

最优路径问题是计算机科学、运筹学、工程设计等领域很多问题的基础。它的应用包括网络路由、电路设计、交通运输、机器人运动规划、事务调度中关键路径的计算以及VLSI设计等。同时，它也为很多最优化问题提供了解决框架，如背包问题、分子生物学中的序列比对、内接多边形的构造和长度受限的霍夫曼编码等都可以转化成最优路径问题进行求解。 求解网络中最优路径的方法可以分为两大类。一种是标号设定算法（label setting ,LS）,另一种是标号改变算法（label correcting ,LC）。由于网络路径算法的应用越来越强调动态性和及时性，使得高效求解最优路径问题变得越来越重要。在这里，我们利用一种高效的网络划分方法，实现了基于网络划分的LS/LC并行算法。实验结果表明，基于这种网络划分的并行算法对于求解最优路径有很好的加速比和扩展比。 在许多更加复杂的应用中，不仅要求计算出最优路径，而且要求给出前K优路径。K优路径是长期研究的泛化最优路径问题，即不但要求得到最优路径，还要得到次短、再次短等路径。 节点s到节点t的K优路径问题可以分为两大类：一类是求解K优非简单路径，即得到的路径可以包含环路；另一类是求解K优简单路径，即路径是简单通路，不包含环路。经过大量学者的研究，求解K优非简单路径相对容易。Fox 于1975年提出了复杂度为O(m+nlogn) 的求解K优非简单路径的算法，最近， Eppstein于1998年给出了一种优化的求解K优非简单路径的算法，时间复杂度达到了O(m+nlogn+k) ，基本上达到了理论下限。 在2000年对E 的算法进行并行化，时间复杂度为 。求解K优简单路径已被证明是更为具有挑战性，这个问题最先由Hofman和Pavley 在1957年进行开始研究，但几乎所有试图解决该问题的算法时间复杂度都达到指数时间。众所周知，Yen提出了一结果比较好的算法，利用现代的数据结构达到O(kn(n+nlogn)) 时间复杂度。John Hershberger于2007年给出了一个新的求K优路径的算法，该算法基于有效率的替代路径算法,相对于以前的替代路径算法，其加速比可达到O(n) 。在本文中，我们基于John Hershberger给出的K优路径算法，尝试给出其并行的方法，并在SMP的高性能计算机上进行了测试。 关键词 并行算法、最优路径、K优路径、网络划分

工艺计划选择的图论方法

Kusiak和Finke讨论了工艺计划选择问题,并对此建立了图论和整数规划模型。本文给出一个修改的模型,模型求解归结为求非循环有向图的最短路径,使问题求解大为简化。

井间地震速度层析成像方法与软件系统

Crosshole Seismic tomography has been broadly studied and applied in the fields of resource exploration and engineering exploration because of its special observing manner and better resolution than normal seismic exploration. This thesis will state the theory and method of Crosshole Seismic tomography. Basing on the previous studies，the thesis studied the initial velocity model，ray-tracing method, and developed the three-dimension tomography software. All the cells that a ray passes through are of the same velocities if the paths from transmitters to receivers are straight. The cells that the each ray passes through are recorded, and rays that pass through each cell are calculated. The ray average velocity which passes through a cell is set as the cell velocity. Analogously we can make a initial node velocity model because the velocity sum is calculated on the all cells which own to a certain node, and the cell number is summed about each nodes，the ratio of the velocity sum to the all cells number is set as the node velocity. The inversion result from the initial node velocity model is better than that of the average velocity model. Ray-bending and Shortest Path for Rays (SPR) have shortcomings and limitations respectively. Using crooked rays obtained from SPR rather than straight lines as the starting point can not only avoid ray bending converging to the local minimum travel time path, but also settle the no smooth ray problem obtained by SPR. The hybrid method costs much computation time, which is roughly equal to the time that SPR expends. The Delphi development tool based on the Object Pascal language standard has an advantage of object-oriented. TDTOM (Three Dimensions Tomography) was developed by using Delphi from the DOS version. Improvement on the part of inversion was made, which bring faster convergence velocity. TDTOM can be used to do velocity tomography from the first arrival travel time of the seismic wave, and it has the good qualities of friendly user interface and convenient operation. TDTOM is used to reconstruct the velocity image for a set of crosshole data from Karamay Oil Field. The geological explanation is then given by comparing the inversion effects of different ray-tracing methods. High velocity zones mean the cover of oil reservoir, and low velocity zones correspond to the reservoir or the steam flooding layer.

改善三维波动方程叠前深度偏移处理效果的方法研究

3D wave equation prestack depth migration is the effective tool for obtaining the exact imaging result of complex geology structures. It's a part of the 3D seismic data processing. 3D seismic data processing belongs to high dimension signal processing, and there are some difficult problems to do with. They are: How to process high dimension operators? How to improve the focusing? and how to construct the deconvolution operator? The realization of 3D wave equation prestack depth migration, not only realized the leap from poststack to prestack, but also provided the important means to solve the difficult problems in high dimension signal processing. In this thesis, I do a series research especially for the solve of the difficult problems around the 3D wave equation prestack depth migration and using it as a mean. So this thesis service for the realization of 3D wave equation prestack depth migration for one side and improve the migration effect for another side. This thesis expatiates in five departs. Summarizes the main contents as the follows: In the first part, I have completed the projection from 3D data point area to low dimension are using de big matrix transfer and trace rearrangement, and realized the liner processing of high dimension signal. Firstly, I present the mathematics expression of 3D seismic data and the mean according to physics, present the basic ideal of big matrix transfer and describe the realization of five transfer models for example. Secondly, I present the basic ideal and rules for the rearrange and parallel calculate of 3D traces, and give a example. In the conventional DMO focusing method, I recall the history of DM0 process firstly, give the fundamental of DMO process and derive the equation of DMO process and it's impulse response. I also prove the equivalence between DMO and prestack time migration, from the kinematic character of DMO. And derive the relationship between DMO base on wave equation and prestack time migration. Finally, I give the example of DMO process flow and synthetic data of theoretical models. In the wave equation prestak depth migration, I firstly recall the history of migration from time to depth, from poststack to prestack and from 2D to 3D. And conclude the main migration methods, point out their merit and shortcoming. Finally, I obtain the common image point sets using the decomposed migration program code.In the residual moveout, I firstly describe the Viterbi algorithm based on Markov process and compound decision theory and how to solve the shortest path problem using Viterbi algorithm. And based on this ideal, I realized the residual moveout of post 3D wave equation prestack depth migration. Finally, I give the example of residual moveout of real 3D seismic data. In the migration Green function, I firstly give the concept of migration Green function and the 2D Green function migration equation for the approximate of far field. Secondly, I prove the equivalence of wave equation depth extrapolation algorithms. And then I derive the equation of Green function migration. Finally, I present the response and migration result of Green function for point resource, analyze the effect of migration aperture to prestack migration result. This research is benefit for people to realize clearly the effect of migration aperture to migration result, and study on the Green function deconvolution to improve the focusing effect of migration.

油气流线模拟方法研究与系统研制

The modeling of petroleum flow path (petroleum charging) and the detail of corresponding software development are presented in this paper, containing principle of petroleum charging, quantitative method, and practical modeling in two oil fields. The Modeling of Petroleum Flow Path is based on the result of basin modeling, according to the principle of petroleum migrating along the shortest path from the source to trap, Petroleum System Dynamics (Prof. Wu Chonglong, 1998), the concept of Petroleum Migration and Dynamic Accumulation (Zhou Donyan, Li Honhui, 2002), etc. The simulation is done combing with all parameters of basin, and considering the flow potential, non-uniformity of source and porous layer. It's the extending of basin modeling, but not belong to it. It is a powerful simulating tool of petroleum system, and can express quantitatively every kind of geology elements of a petroleum basin, and can recuperate dynamically the geology processes with 3D graphics. At result, we can give a result that the petroleum flow shows itself the phenomena of main path, and without using the special theory such as deflection flow in fractures(Tian Kaiming, 1989, 1994, Zhang Fawang, Hou Xingwei, 1998), and flow potential(England, 1987). The contour map of petroleum flow quantitative show clearly where the coteau - dividing slot is, and which convergence region are the main flow path of petroleum, and where is the favorable play of petroleum. The farsighted trap can be determined if there are enough information about structural diagram and can be evaluated, such as the entrapment extent, spill point, area, oil column thickness, etc. Making full use of the result of basin modeling with this new tool, the critical moment and scheme of the petroleum generation and expulsion can be showed clearly. It's powerful analysis tool for geologist.

海洛因成瘾脑灰质密度和结构网络研究

Behavioral and functional imaging studies consistently show that heroin abuse leads to various cognitive impairments, while brain structural changes associated with heroin use remain poorly understood. In the current study, we used voxel-based morphology (VBM), a method sensitive to structural changes of the brain, to investigate the gray concentration in MRI structure images of heroin addicts. Results show that the concentration of the temporal cortex and frontal cortex of heroin users significantly decreased as compared to age/education matched normal controls. Further analysis revealed that this brain structure change was detectable only in the users who had used heroin more than 5 year, but not in the remaining users. These results converge to the abnormality of the brain structure in heroin users and this abnormality is clearly associated with duration of drug use. We then analyzed the large-scale brain structure network in the heroin addicts. As compared to the normal controls, there was significant difference in interregional correlation between the temporal cortex, hippocampus, thalamus, and frontal cortex. Importantly, two major indices of the small-world properties, Clustering coefficient(Cp) and shortest path length (Lp), which are thought to reflect the local specialty and global integrity, were marginal-significantly larger than the normal controls, especially for Lp. These results suggest that chronic use of heroin results in the reorganization of the brain system. Taken together, this thesis has provided compelling evidence for brain structure impairments in chronic heroin users and further characterized the large-scale brain structure network in the same population.

Structural electrochemical study of hemoglobin by in situ circular dichroism thin layer spectroelectrochemistry

Secondary and tertiary or quaternary structural changes in hemoglobin (HB) during an electroreduction process were studied by in situ circular dichroism (CD) spectroelectrochemistry with a long optical path thin-layer cell. By means of singular value decomposition least-squares analysis, CD spectra in the far-UV region give two similar a components with different CD intensity, indicating slight denaturation in the secondary structures due to the electric field effect. CD spectra in the Soret band show a R --> T transition of two quaternary structural components induced by electroreduction of the heme, which changes the redox states of the center ion from Fe3+ to Fe2+ and the coordination number from 6 to 5. The double logarithmic analysis shows that electroreduction of hemoglobin follows a chemical reaction with R --> T transition. Some parameters in the electrochemical process were obtained: formal potential, E-0t = -0.167 V; electrochemical kinetic overpotential, DeltaE(0) = -0.32 V; standard electrochemical reaction rate constant, k(0) = 1.79 x 10(-5) cm s(-1); product of electron transfer coefficient and electron number, alphan=0.14; and the equilibrium constant of R --> T transition, K-c = 9.0.

Circular dichroism spectro electrochemical and voltammetric studies of vitamin B-2

Electroreduction of vitamin B-2 (VB2) was studied by in situ circular dichroism (CD) spectroelectrochemistry (SEC) with a long optical path length thin layer cell (LOPLTLC). The results showed that the electroreduction of VB2 in phosphate buffer solution (PBS) (PH 6.8) was a two-electron electrochemical process with weak adsorption of the reactant at the glassy carbon (GC) electrode surface. The CD spectra change of VB2 in the reduction process was explained with the theory of electronic states. We also treated the CD spectra with a singular value decomposition least square (SVDLS) method, and have found not only the number of components and their spectra, but also the fraction distribution of each component in the electroreduction process of VB2.

The electrochemically induced conformational transition of disulfides in bovine serum albumin studied by thin layer circular dichroism spectroelectrochemistry

The conformational transition of disulfides in bovine serum albumin (BSA) induced by electrochemical redox reaction of disulfides were monitored by in-situ circular dichroism (CD) spectroelectrochemistry, with a long optical path thin layer cell and analyzed by a singular value decomposition least square (SVDLS) method. Electrochemical reduction of disulfides drives the left-handed conformation of disulfides changed into the right-handed. At open circuit, eight of the 17 disulfides were of left-handed conformation. Four of the 17 disulfides took part in the electrochemical reduction with an EC mechanism. Only one-fourth of the reduced disulfides returned to left-handed conformation in the re-oxidation process. Some parameters of the electrochemical reduction process, i.e. the number of electrons transferred and electron transfer coefficient, n=8, alphan=0.15, apparent formal potential, E-1(0') = -0.65(+/-0.01) V, standard heterogeneous electron transfer rate constant, k(1)(0) = (2.84 +/- 0.14)x 10(-5) cm s(-1) and chemical reaction equilibrium constant, K-c=(5.13 +/- 0.12) x 10(-2), were also obtained by double logarithmic analysis based on the near-UV absorption spectra with applied potentials. (C) 2001 Elsevier Science B.V. All rights reserved.

In-situ circular dichroism spectroelectrochemical study on the redox process of norepinephrine

The redox process of norepinephrine in pH = 7.0 phosphate buffer solution at glassy carbon electrode was studied by circular dichroism spectroelectrochemistry with a long optical path thin layer cell. The spectroelectrochemical data were analyzed with the double logarithm method. According to the double logarithsmic plot results, the mechanism of electrochemical oxidation of norepinephrine is an irreversible process with a subsequent chemical reaction (EC) to form a norepinephrinechrome. Both of norepinephrinequinone and norepinephrinechrome are followed E mechanisms. Some kinetic parameters about the electrochemical process, i.e. the electron transfer coefficient and number of electron transfered, alpha n = 0.38, the formal potential, E-1(0)' = 0.20 V, the standard heterogenous electron transfer rate constant, k(1)(0) = 1.2 x 10(-4) cm s(-1) for the oxidation of norepinephrine, alpha n = 0.37, E-2(0)' = 0.25 V and k(2)(0) = 4.4 x 10(-5) cm . s(-1) for the reduction of norepinephrinequnone and alpha n = 0.33, E-3(0)' = -0.25V and k(3)(0) = 1.1 x 10(-4) cm . s(-1) for the reduction of norpinephrinechrome, were also estimated.

Study of electrochemical behavior of ergosterol by in situ thin layer circular dichroic spectroelectrochemistry

The electroxidation of ergosterol was studied by in situ circular dichroic (CD) spectroelectrochemistry with a long optical path length thin layer cell. It was confirmed that the oxidation of ergosterol in ethanol solution is a two-electron irreversible electrochemical process with strong adsorption of an electroinactive product at the glassy carbon electrode, which blocks the electrochemical reaction. The CD spectroelectrochemical data were treated by the double logarithm method together with nonlinear regression, from which the formal potential, E-0 = 1.00 V, alpha n(alpha) = 0.302, the standard electrochemical rate constant, k(0) = 6.1(+/-0.4) x 10(-4) cm s(-1) and the adsorption constant, beta = 19 +/- 1, were obtained. The number of electrons transferred (n = 1.86) was estimated by cyclic voltammetry.

Investigation of the self-accelerating process of ascorbic acid by in-situ circular dichroism spectroelectrochemistry

The electrode reaction process of ascorbic (Vc) was studied by in-situ circular dichroic(CD) spectroelectrochemistry with a long optical path thin layer cell on glassy carbon(GC) electrode. The spectroelectrochemical data were analyzed by the double logarithmic method together with nonlinear regression. The results suggested that the mechanism of Ve in pH 7.0 phosphate buffer solution at GC electrode was a two-electron irreversible electrooxidation followed by adsorption of the oxidation product. That is a self-accelerated process. Some kinetic parameters at free and at adsorbed electrode surface, i.e, the formal potentials, E-0' = 0.09 V, E-a(0') = 0.26 +/- 0.02 V; the electron transfer coefficient and number of transfered electron, alpha n = 0.41, alpha(a)n = 0.07;the standard heterogeneous electron transfer rate constant, k(0) = 8.0 x 10(-5) cm.s(-1), k(a)(0) = 1.9 x 10(-4) cm.s(-1) and adsorption constant, beta = 102.6 were also estimated.

Investigation of ergosterol in situ circular dichroic spectroelectrochemistry

In the present paper, the electrochemical behavior of ergosterol has been investigated by in situ circular dichroism (CD) spectroelectrochemistry with long path-length thin layer cell. E-0 (1.02V), alpha n(alpha) (0.302) of the electroxidation process of ergosterol were obtained from the CD spectroelectrochemical data. The mechanism of the electroxidation process of ergosterol is suggested.