Options
Fraunhofer Institut für Integrierte Publikations-und Informationssysteme IPSI
Now showing
1 - 10 of 10
-
-
PublicationOn regular tree embeddings( 2000)
;Chen, W.Turau, V.Regular trees are a natural extension of finite trees, which have many applications. The path-embedding problem is to determine whether a regular tree S can be obtained from another regular tree T by deleting (probably infinitely many) subtrees of T. This paper explores efficient algorithms for the path-embedding problem in ordered and unordered trees. Given two regular trees S and T represented by rational graphs, our algorithms solve the ordered version of path-embedding problem in O(|ESET|) time and the unordered version in O(|ESET|DSDT) time. Here |ES| denotes the number of edges in the rational graph for S, and DS denotes the maximum outdegree of a vertex in S. We also demonstrate that our approach can be applied to pattern matching problems for regular trees recently studied by Fu. -
-
PublicationEfficient querying on genomic databases by using metric space indexing technology(GMD Forschungszentrum Informationstechnik, 1997)
;Chen, W.Aberer, K. -
PublicationEfficient querying on genomic databases by using metric space indexing technology( 1997)
;Chen, W.Aberer, K. -
PublicationEfficient algorithm for determining the optimal execution strategy for path queries in OODBS( 1996)
;Chen, W.Aberer, K.To select an optimal query evaluation strategy for a path query in an object-oriented database system one has to exploit the available index structures on the path. In a database with a large database schema many alternative strategies have to be considered for the evaluation of a path query by choosing from a large set of available indices, which can make the selection of the optimal strategy expensive. We give an algorithm that finds the optimal strategy for evaluating a path query with time complexity independent of the set of indices available in the database. The algorithm considers all possible forward and backward traversal strategies and has time complexity O(n2) in the path length n. Incorporating this algorithm into the query optimization for object-oriented database management systems can improve the response time of the system, by optimizing an equally important and frequent type of queries with high efficiency. -
-
PublicationEfficient algorithm for determining the optimal execution strategy for path queries in OODBS(GMD Forschungszentrum Informationstechnik, 1995)
;Chen, W. ;Aberer, K.Neuhold, E.J. -
PublicationEfficient multiple dispatching using nested transition-arrays(GMD Forschungszentrum Informationstechnik, 1995)
;Chen, W.Aberer, K. -
PublicationEfficient dynamic look-up strategy for multi-methods( 1994)
;Chen, W. ;Turau, V.Klas, W.