Optimal multiway search trees for variable size keys

Summary This paper considers the construction of optimal search trees for a sequence of n keys of varying sizes, under various cost measures. Constructing optimal search cost multiway trees is NP-hard, although it can be done in pseudo-polynomial time O ³ and space O ², where L is the page size limit. An optimal space multiway search tree is obtained in O ³ time and O ² space, while an optimal height tree in O(n ² log² n) time and O(n) space both having additionally minimal root sizes. The monotonicity principle does not hold for the above cases. Finding optimal search cost weak B-trees is NP-hard, but a weak B-tree of height 2 and minimal root size can be constructed in O(n log n) time. In addition, if its root is restricted to contain M keys then a different algorithm is applied, having time complexity O(nM log n). The latter solves a problem posed by McCreight.     

Covering sharing trees: a compact data structure for parameterized verification

The control state reachability problem is decidable for well-structured infinite-state systems like (Lossy) Petri Nets, Vector Addition Systems, and broadcast protocols. An abstract algorithm that solves the problem is the backward reachability algorithm of [1, 21 ]. The algorithm computes the closure of the predecessor operator with respect to a given upward-closed set of target states. When applied to this class of verification problems, symbolic model checkers based on constraints like [7, 26 ] suffer from the state explosion problem.In order to tackle this problem, in [13] we introduced a new data structure, called covering sharing trees, to represent in a compact way collections of infinite sets of system configurations. In this paper, we will study the theoretical complexity of the operations over covering sharing trees needed in symbolic model checking. We will also discuss several optimizations that can be used when dealing with Petri Nets. Among them, in [14] we introduced a new heuristic rule based on structural properties of Petri Nets that can be used to efficiently prune the search during symbolic backward exploration. The combination of these techniques allowed us to turn the abstract algorithm of [1, 21 ] into a practical method. We have evaluated the method on several finite-state and infinite-state examples taken from the literature [2, 18 , 20 , 30 ]. In this paper, we will compare the results we obtained in our experiments with those obtained using other finite and infinite-state verification tools.     

Optimal trees for a class of information retrieval problems

A review is given of the use of doubly-chained trees for information retrieval. It is shown that for several reasons related to the actual implementation of such a scheme and to properties of functions related to the retrieval process, the chaining steps, by which expected search time is measured, may be of different cost depending upon whether the step is vertical (equal compare result) or horizontal (unequal compare result). Since previous results are for equal cost steps, the problem of constructing an optimal retrieval tree under the new circumstances is formulated mathematically and a very rapid solution procedure is given.     

Transforming Unbalanced Multiway trees into a practical external data structure

Summary Unbalanced Multiway Trees (UM-trees) of degree m are external data structures wherein each node may be linked to at most m subtrees. Although they allow fast searches and updates UM-trees show poor space efficiency. In order to improve their time and space performance an overflow technique similar to that used previously for B ^*-trees is adapted to UM-trees. Analytical results show that when compared with UM-trees the new data structure improves average searching time and substantially increases space efficiency. Asymptotic space efficiency, measured as the ratio of space used to space generated, is 50% in the worst case and in the average case it is upper bounded by at least 85.7% for any m. Simulations suggest that this upper bound is tight. Compared with a homologous variant of B ^*-trees, simulation results indicate that the data structure proposed is highly balanced with comparable average space efficiency and lower average searching time. We conclude that overflow techniques can be applied not only to bottom-up type trees (e.g., B-trees) but also to top-down type trees such as UM-trees, in cases when the performance of an external data structure needs to be improved with little overhead.     

Enhanced layered segment trees: a pragmatic data structure for real-time processing of geometric objects

The data structure that is probably most used in the pattern recognition and image processing of geometric objects is the segment tree and its optimized variant, the “layered segment tree”. In all the versions currently known, except the work of Vaishnavi and Wood described later, these data structures do not operate in real time. Even in the latter scheme, although the structure can be implemented in real time and in an on-line fashion, the operation of insertion involves the sorting of the representations of the line segments in the tree. In essence, for all the reported algorithms, there is no known strategy to insert the segments one by one, other than the trivial strategy of processing them all together as in a batched-mode. In this paper, we present a strategy in which all the operations done on the tree can be done efficiently. Indeed, by improving the bottleneck, we prove that an arbitrary horizontal segment can be inserted into this data structure without invoking an expensive sorting process. We show that while this is accomplished by maintaining the same space and query complexity of the best-known algorithm, the version presented here is applicable to on-line real-time processing of line segments. The paper thus has applications in all areas of pattern recognition and image processing involving geometric objects.     

基于甲骨文数据库管理系统的化学结构检索数据库的设计与实现

设计了一种基于大型数据库管理系统Oracle的化学结构数据存储模式,并实现了相应于此模式的高效化学结构检索方法。结构检索方法建立在图子图匹配算法VF2的基础上,对其进行了必要的改造和扩展,使之适合于化学结构检索。在此基础上,针对美国NCl(National Cancer Institute)25万个化合物的2D结构建立了数据库,成功进行了结构检索试验。结果表明,这种实现方法不仅能高效存储并准确检索化合物的结构信息,而且也容易实现与药物研发过程中所产生的大量其它数据(如生物筛选数据和DNA芯片基因表达数据等)进行高效整合。这个设计的改进版已经集成于微芯公司的药物研发生化信息学软件系统——TASS(Target Activity Structure System)中。     

Binary trees for dissimilarity data

Binary segmentation procedures (in particular, classification and regression trees) are extended to study the relation between dissimilarity data and a set of explanatory variables. The proposed split criterion is very flexible, and can be applied to a wide range of data (e.g., mixed types of multiple responses, longitudinal data, sequence data). Also, it can be shown to be an extension of well-established criteria introduced in the literature on binary trees.     

RE-EM trees: a data mining approach for longitudinal and clustered data

Longitudinal data refer to the situation where repeated observations are available for each sampled object. Clustered data, where observations are nested in a hierarchical structure within objects (without time necessarily being involved) represent a similar type of situation. Methodologies that take this structure into account allow for the possibilities of systematic differences between objects that are not related to attributes and autocorrelation within objects across time periods. A standard methodology in the statistics literature for this type of data is the mixed effects model, where these differences between objects are represented by so-called “random effects” that are estimated from the data (population-level relationships are termed “fixed effects,” together resulting in a mixed effects model). This paper presents a methodology that combines the structure of mixed effects models for longitudinal and clustered data with the flexibility of tree-based estimation methods. We apply the resulting estimation method, called the RE-EM tree, to pricing in online transactions, showing that the RE-EM tree is less sensitive to parametric assumptions and provides improved predictive power compared to linear models with random effects and regression trees without random effects. We also apply it to a smaller data set examining accident fatalities, and show that the RE-EM tree strongly outperforms a tree without random effects while performing comparably to a linear model with random effects. We also perform extensive simulation experiments to show that the estimator improves predictive performance relative to regression trees without random effects and is comparable or superior to using linear models with random effects in more general situations.