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

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

来源：评论

学校读者我要写书评

暂无评论

Maintaining the classes of 4-edge-connectivity in a graph on-line

引用

ALGORITHMICA 1998年第3期20卷 242-276页

作者： Dinitz, Y Westbrook, J Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel AT&T Bell Labs Res Florham Pk NJ 07932 USA Yale Univ Dept Comp Sci New Haven CT 06520 USA

Two vertices of an undirected graph are called k-edge-connected if there exist k edge-disjoint paths between them (equivalently, they cannot be disconnected by the removal of less than k edges from the graph). Equivalence classes of this relation are called classes of k-edge-connectivity or k-edge-connected components. This paper describes graph structures relevant to classes of 4-edge-connectivity and traces their transformations as new edges are inserted into the graph. data structures and an algorithm to maintain these classes incrementally are given. Starting with the empty graph, any sequence of q Same-4-Class? queries and it Insert-Vertex and lit Insert-Edge updates can be performed in O(q + m + ii log n total time. Each individual query requires O(1) time in the worst-case. In addition, an algorithm for maintaining the classes of k-edge-connectivity (k arbitrary) in a (k-1)-edge-connected graph is presented. Its complexity is O(q + m + n). with O(M + k(2)n log(n/k)) preprocessing, where M is the number of edges initially in the graph and n is the number of its vertices.

关键词： dynamic algorithm dynamic data structure graph algorithm edge-connectivity connectivity class component analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

A PRACTICAL METHOD FOR COMPRESSING SPARSE MATRICES WITH VARIANT ENTRIES

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 1990年第3-4期36卷 163-173页

作者： AOE, J Department of Information Science and Intelligent Systems The University of Tokushima Minami-Josanjima-Cho Tokushima-Shi 770 Japan

A row displacement method compresses efficiently a sparse matrix into a one-dimensional array. The access time with this method isO(l), but the application was restricted to the static matrices. In order to extend the use of the row displacement method to the dynamic matrices, the algorithms for insertion and deletion are proposed and the effectivity is confirmed by theoretical and empirical observations.

关键词： A large sparse matrix dynamic data structure fast access storing and searching table compression table look up E.1 F.2.2 H.3.3

来源：评论

学校读者我要写书评

暂无评论

DYNAMIZATION OF THE TRAPEZOID METHOD FOR PLANAR POINT LOCATION IN MONOTONE SUBDIVISIONS

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 1992年第3期2卷 311-333页

作者： Chiang, Yi-Jen Tamassia, Roberto Brown Univ Dept Comp Sci Providence RI 02912 USA

We present a fully dynamic data structure for point location in a monotone subdivision, based on the trapezoid method. The operations supported are insertion and deletion of vertices and edges, and horizontal translation of vertices. Let n be the current number of vertices of the subdivision. Point location queries take O (log n) time, while updates take O (log(2) n) time (amortized for vertex insertion/deletion and worst-case for the other updates). The space requirement is O(n log n). This is the first fully dynamic point location data structure for monotone subdivisions that achieves optimal query time.

关键词： Computational geometry planar point location dynamic data structure monotone subdivision analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

TIMING ANALYSIS OF THE MONOTONIC LOGICAL GRID FOR MANY-BODY dynamicS

引用

SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING 1990年第2期11卷 368-388页

作者： PICONE, JM LAMBRAKOS, SG BORIS, JP

The Monotonic Logical Grid (MLG) data structure is compared to alternative data structures for tasks relevant to computing the dynamics of N moving objects. The tasks include identifying near neighbors of designated nodes, retrieving information on the near neighbors, and ordering this information according to distances of the associated near neighbors from the designated nodes. The test model consists of a collection of $N = 64{\text{K}}$ (65,536) noninteracting objects with randomly initialized velocities. The calculations took place on the Naval Research Laboratory (NRL) Cray X-MP computer, which has a hardware gather-scatter capability. The comparisons include two types of alternative data structures for which the indexing is static (the data corresponding to each node always have the same index and memory locations). data structure “Type 1” carries no additional information or “pointers” that could identify the near neighbors of each node. data structure “Type 2” does carry coarse information on near neighbors by maintaining linked lists or a related system of “pointers” that change with the motion of nodes in time. The numerical tests presented show that the MLG data structure is vastly superior to the Type 1 data structure when near-neighbor information is needed for a large number $N_f $ of designated or “focal” nodes. This occurs because the process of identifying near neighbors requires $N_f $ identical sorting or partitioning processes per frame (or timestep) in the case of Type 1 data structures while only one sort per frame is necessary to maintain the ordering of data in the MLG data structure. In addition, the MLG is superior for the task of finding some number $M_{nn} $ of the nearest neighbors for each of $N_f $ focal nodes, where $M_{nn} \ll N$ and $N_f \sim N$. The MLG provides several advantages over Type 2 data structures, even though the respective operation counts are quite similar. The advantages include efficiency of memory allocation and

关键词： 65K05 68A10 68A20 monotonic logical grid dynamic data structure near-neighbors problem

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Longest Common Factor After One Edit Operation 1

引用

24th International Symposium on String Processing and Information Retrieval (SPIRE)

作者： Amir, Amihood Charalampopoulos, Panagiotis Iliopoulos, Costas S. Pissis, Solon P. Radoszewski, Jakub Bar Ilan Univ Dept Comp Sci Ramat Gan Israel Kings Coll London Dept Informat London England Univ Warsaw Inst Informat Warsaw Poland

ISBN: (数字)9783319674285

ISBN: (纸本)9783319674285;9783319674278

It is well known that the longest common factor (LCF) of two strings over an integer alphabet can be computed in time linear in the total length of the two strings. Our aim here is to present an algorithm that preprocesses two strings S and T in order to answer the following type of queries: Given a position i on S and a letter alpha, return an LCF of T and S', where S' is the string resulting from S after substituting S[i] with alpha. In what follows, we present an algorithm that, given two strings of length at most n, constructs in O(n log(4) n) expected time a data structure of O(n log(3) n) space that answers such queries in O(log(3) n) time per query. After some trivial modifications, our approach can also support the case of single letter insertions or deletions in S.

关键词： Longest common factor dynamic data structure Suffix tree Heavy-path decomposition Orthogonal range searching

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

dynamically Exchanging Nodes of the Critical Node Problem 5

Dynamically Exchanging Nodes of the Critical Node Problem

引用

5th IEEE International Conference on Cloud Computing and Intelligence Systems (CCIS)

作者： Zeng, XiangRong Liu, SiYang Shen, Lifan Chen, YongQuan Fu, ZhangHua Chinese Univ Hong Kong Inst Robot & Intelligent Mfg Robot Lab Logist Serv Shenzhen 518172 Peoples R China Xi An Jiao Tong Univ Sch Software Engn Xian Shaanxi Peoples R China

ISBN: (纸本)9781538660058

The Critical Node Problem (CNP) aims to identify k nodes from an undirected graph G=(V,E), in order to minimize the number of pairwise connected nodes in the residual graph after deleting these k nodes. This problem has a wide range of applications in the fields of cyber security, disease control, biological analysis, social network, etc. The CNP is known to be NP-hard, and heuristics are commonly used to solve large-scale CNP instances, among which the node-exchange operation is a basic move operator widely adopted by local-search based heuristics. Given an initial CNP solution consisting of k nodes, there are totally kx (vertical bar V vertical bar-k) possible node-exchange operations. The current best algorithm requires a complexity of O((vertical bar V vertical bar-k)x(vertical bar V vertical bar+vertical bar E vertical bar+kxD(G))) to evaluate all these operations (vertical bar V vertical bar denotes the number of nodes, vertical bar E vertical bar denotes the number of edges, D(G) denotes the maximum degree of the node in graph G),In this paper, a series of dynamic data structures are implemented to reduce the above complexity to O((vertical bar V vertical bar-k)x(vertical bar V vertical bar+vertical bar E vertical bar)), so as to improve the efficiency of local search.

关键词： Critical Node Problem Node-Exchange Operator dynamic data structure

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：