检索结果-内蒙古大学图书馆

On the number of elements to reorder when updating a suffix array

JOURNAL OF DISCRETE ALGORITHMS 2012年第1期11卷 87-99页

作者： Leonard, M. Mouchard, L. Salson, M. Univ Rouen Dept Comp Sci LITIS EA 4108 F-76821 Mont St Aignan France Kings Coll London Dept Informat Algorithm Design Grp London WC2R 2LS England Univ Lille 1 LIFL UMR CNRS 8022 INRIA Lille Nord Europe Villeneuve Dascq France

Recently new algorithms appeared for updating the Burrows-Wheeler Transform or the suffix array, when the text they index is modified. These algorithms proceed by reordering entries and the number of such reordered entries may be as high as the length of the text. However, in practice, these algorithms are faster for updating the Burrows-Wheeler Transform or the suffix array than the fastest reconstruction algorithms. In this article we focus on the number of elements to be reordered for real-life texts. We show that this number is related to LCP values and that, on average, Lave entries are reordered, where Lave denotes the average LCP value, defined as the average length of the longest common prefix between two consecutive sorted suffixes. Since we know little about the LCP distribution for real-life texts, we conduct experiments on a corpus that consists of DNA sequences and natural language texts. The results show that apart from texts containing large repetitions, the average LCP value is close to the one expected on a random text. (C) 2011 Elsevier B.V. All rights reserved.

关键词： FM-index Burrows-Wheeler Transform Suffix array Longest common prefix dynamic data structure Self-index Complexity

来源：评论

学校读者我要写书评

暂无评论

Optimizing to Memory Application in Embedded Multimedia Device

Optimizing to Memory Application in Embedded Multimedia Devi...

引用

International Conference on Advanced Design and Manufacturing Engineering (ADME 2011)

作者： Wang, Xiaosheng Yu, Qian Shandong Womens Univ Informat & Technol Sch Jinan Peoples R China

ISBN: (纸本)9783037852132

The modern embedded multimedia electronic devices rely on dynamically-allocated data structures to store and process their data, as a result, the demand of its memory capacity and dynamic are increasing unceasingly. In order to better solve the memory application optimization in embedded device, this paper represents multimedia application's dynamic data structures optimization flow and improved or modified NSGA-II multi-objective evolutionary algorithm (MNSGA-II), and uses three objective functions: embedded device's memory accesses, memory use and energy consumption. The MNSGA-II algorithm adopts repeat crowded distance sorting tactics to improve NSGA-II based on keeping the advantage of the original NSGA-II for multi-objective optimization problem. The experiment results show that MNSGA-II has better performance of the convergence and the diversity of solutions than original NSGA-II, and the optimal dynamic data structure implementation is successful by performing our method for one real embedded multimedia device's memory application.

关键词： Embedded multimedia device Memory Application dynamic data structure Multi-objective optimization improved NSGA-II algorithm

来源：评论

学校读者我要写书评

暂无评论

Skip quadtrees: dynamic data structures for multidimensional point sets

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 2008年第1-2期18卷 131-160页

作者： Eppstein, David Goodrich, Michael T. Sun, Jonathan Z. Univ Calif Irvine Donald Bren Sch Informat & Comp Sci Dept Comp Sci Irvine CA 92697 USA Univ So Mississippi Sch Comp Hattiesburg MS 39406 USA

We present a new multi-dimensional data structure, which we call the skip quadtree ( for point data in R-2) or the skip octree (for point data in R., with constant d > 2). Our data structure combines the best features of two well-known data structures, in that it has the well-defined "box"-shaped regions of region quadtrees and the logarithmicheight search and update hierarchical structure of skip lists. Indeed, the bottom level of our structure is exactly a region quadtree (or octree for higher dimensional data). We describe efficient algorithms for inserting and deleting points in a skip quadtree, as well as fast methods for performing point location, approximate range, and approximate nearest neighbor queries.

关键词： skip quadtree quadtree octree dynamic data structure point location range nearest neighbor approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Shooting Permanent Rays among Disjoint Polygons in the Plane

Shooting Permanent Rays among Disjoint Polygons in the Plane

引用

25th Annual Symposium on Computational Geometry

作者： Ishaque, Mashhood Speckmann, Bettina Toth, Csaba D. Tufts Univ Dept Comp Sci Medford MA 02155 USA

ISBN: (纸本)9781605585017

We present a data structure for ray shooting-and-insertion in the free space among disjoint polygonal obstacles with a total of n vertices in the plane, where each ray starts at the boundary of some obstacle. The portion of each query ray between the starting point and the first obstacle hit is inserted permanently as a new obstacle. Our data, structure uses O(n log n) space and preprocessing time, and it supports m successive ray shooting-and-insertion queries in O(n log(2) n + m log m) total time. We present two applications for our data structure: (1) Our data structure supports efficient implementation of auto-partitions in the plane i.e. binary space partitions where each partition is done along the supporting line of an input segment. If n input line segments are fragmented into m, pieces by an auto-partition, then it can now be implemented in O(n log(2) n + m log m) time. This improves the expected runtime of Patersen and Yao's classical randomized auto-partition algorithm for n disjoint line segments to O(n log(2) n). (2) If we are given disjoint polygonal obstacles with a total of n vertices in the plane, a permutation of the reflex vertices, and a half-line at each reflex vertex that partitions the reflex angle into two convex angles, then the folklore convex partitioning algorithm draws a ray emanating from each reflex vertex in the prescribed order in the given direction until it hits another obstacle, a previous ray, or infinity. The previously best implementation (with a semi-dynamic ay shooting data structure) requires O(n(3/2-epsilon/2)) time using O(n(1+epsilon)) space. Our data structure improves the runtime to O(n log(2) n).

关键词： Ray Shooting Segment Insertion dynamic data structure Convex Partition Binary Space Partition

来源：评论

学校读者我要写书评

暂无评论

External Memory Planar Point Location with Logarithmic Updates

External Memory Planar Point Location with Logarithmic Updat...

引用

24th Annual Symposium on Computational Geometry

作者： Arge, Lars Brodal, Gerth Stolting Rao, S. Srinivasa Univ Aarhus Dept Comp Sci MADALGO DK-8200 Aarhus N Denmark

ISBN: (纸本)9781605580715

Point location is art extremely well-studied problem both in internal memory models and recently also in the external memory model. In this paper, we present an I/O-efficient dynamic data structure for point location in general planar subdivisions. Our structure uses linear space to store a subdivision with N segments. Insertions and deletions of segments can be performed in amortized O(log(B) N) I/Os and queries can be answered in O(log(B)(2) N) I/Os in the worst-case. The previous best known linear space dynamic structure also answers queries in O(log(B)(2) N) I/Os, but only supports insertions in amortized O(log(B)(2) N) I/Os. Our structure is also considerably simpler than previous structures.

关键词： External memory planar subdivisions point location dynamic data structure

来源：评论

学校读者我要写书评

暂无评论

A dynamic clinical dental relational database

引用

IEEE TRANSACTIONS ON INFORMATION TECHNOLOGY IN BIOMEDICINE 2004年第3期8卷 298-305页

作者： Taylor, D Naguib, RNG Boulton, S Coventry Univ Sch Math & Informat Sci BIOCORE Coventry CV1 5FB W Midlands England Coventry Hlth Author Dent Publ Hlth Dept Coventry CV1 2GQ W Midlands England

The traditional approach to relational database design is based on the logical organization of data into a number of related normalized tables. One assumption is that the nature and structure of the data is known at the design stage. In the case of designing a relational database to store historical dental epidemiological data from individual clinical surveys, the structure of the data is not known until the data is presented for inclusion into the database. This paper addresses the issues concerned with the theoretical design of a clinical dynamic database capable of adapting the internal table structure to accommodate clinical survey data, and presents a prototype database application capable of processing, displaying, and querying the dental data.

关键词： dental epidemiology dynamic data structure relational database application

来源：评论

学校读者我要写书评

暂无评论

Translating a regular grid over a point set

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2003年第1-2期25卷 21-34页

作者： Bose, P van Kreveld, M Maheshwari, A Morin, P Morrison, J Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada Univ Utrecht Dept Comp Sci NL-3508 TB Utrecht Netherlands

We consider the problem of translating a (finite or infinite) square grid G over a set S of n points in the plane in order to maximize some objective function. We say that a grid cell is k-occupied if it contains k or more points of S. The main set of problems we study have to do with translating an infinite grid so that the number of k-occupied cells is maximized or minimized. For these problems we obtain running times of the form O(kn polylog (n)). We also consider the problem of translating a finite size grid, with m cells, in order to maximize the number of k-occupied cells. Here we obtain a running time of the form O(knm polylog (nm)). In solving these problems, we design a data structure T that maintains in O(log n) time per operation, a function f : R --> R under the following query and update operations where [a, b) is a continuous interval in R: 1. INSERT(T, a, b, delta): Increase the value of f (x) by delta for all x is an element of [a, b). 2. DELETE(T, a, b, delta): Decrease the value of f (x) by delta for all x is an element of [a, b). 3. MAX-COVER(): Return max{f (x): x is an element of R}. 4. MAX-COVER-WITNESS(): Return a value x* such that f (x*) = max{f (x): x is an element of R}. 5. MAX-IN(a, b): Returns max{f (x): x is an element of [a, b)}. 6. MAX-WITNESS-IN(a, b): Returns a value x* such that f (x*) = max{f (x): x is an element of [a, b)}. as well as the min counter-parts of these queries. (C) 2002 Published by Elsevier Science B.V.

关键词： dynamic data structure binary tree intervals lazy update facility location maintenance of functions

来源：评论

学校读者我要写书评

暂无评论

A strategy to implement a dynamic dental epidemiological relational database

A strategy to implement a dynamic dental epidemiological rel...

引用

23rd Annual International Conference of the IEEE-Engineering-in-Medicine-and-Biology-Society

作者： Taylor, D Naguib, RNG Amin, S James, A Boulton, S Coventry Univ Sch Math & Informat Sci BIOCORE Coventry W Midlands England

ISBN: (纸本)0780372115

Dental surveys to collect data on the developing dentition of school aged children are routinely performed by Health Authorities in the UK. The information collected varies greatly from survey to survey, so that each survey file has a unique structure and consists of unique data elements. The data itself is currently stored in such a way that analysis of data between different survey sets is not possible. This paper investigates a method of modelling a dynamic data store capable of accepting differing historical survey data sets, and studies the functionality required to support the dynamic data store design.

关键词： dynamic data structure dentistry

来源：评论

学校读者我要写书评

暂无评论

dynamic data structures for fat objects and their applications

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2000年第4期15卷 215-227页

作者： Efrat, A Katz, MJ Nielsen, F Sharir, M Ben Gurion Univ Negev Dept Math & Comp Sci IL-84105 Beer Sheva Israel Tel Aviv Univ Sch Math Sci IL-69978 Tel Aviv Israel SONY Comp Sci Labs Inc Tokyo Japan NYU Courant Inst Math Sci New York NY USA

We present several efficient dynamic data structures for point-enclosure queries, involving convex fat objects in R-2 or R-3. Our planar structures are actually fitted for a more general class of objects - (beta, delta)-covered objects which are not necessarily convex, see definition below. These structures are more efficient than alternative known structures, because they exploit the fatness of the objects. We then apply these structures to obtain efficient solutions to two problems: (i) finding a perfect containment matching between a set of points and a set of convex fat objects, and (ii) finding a piercing set for a collection of convex fat objects, whose size is optimal up to some constant factor. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： fat objects dynamic data structure point enclosure containment matching piercing set

来源：评论

学校读者我要写书评

暂无评论

Design considerations for a relational database schema to hold dental epidemiological data

Design considerations for a relational database schema to ho...

引用

Joint Meeting of the 3rd IEEE EMBS International Conference on Information Technology Applications in Biomedicine/3rd Workshop of the Int-Telemedical-Information-Society

作者： Taylor, D Naguib, RNG Amin, S James, A Boulton, S Coventry Univ Sch Math & Informat Sci Coventry CV1 5FB W Midlands England

ISBN: (纸本)078036449X

Dental surveys to collect data on the developing dentition of school children are routinely performed by many health authorities in the UK. A standard software package is used by Health Authorities to store the results of the surveys. At present only one data file can be loaded into the dental survey program for analysis at any given time. Analysis of more than one data set at a time is therefore not possible. The overall aims of the collection of vast amounts of clinical data are many. Analysis of data sets containing both clinical and socio-economical data elements are of great interest to senior management of Health Authorities. The results of data analysis can aid in the planning and provision of dental resources in areas of identified need. To date no evidence is available to suggest that previous efforts to amalgamate and analyse the available epidemiological data have been made. This paper looks at the problems and a possible solution of designing and populating a relational database with the collection of survey data sets.

关键词： dental survey epidemiology relational database dynamic data structure

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：