112,147 research outputs found
In-Place Suffix Sorting
No full textGiven string T = T[1,... ,n], the suffix sorting problem is to lexicographically sort the suffixes T[i,... ,n] for all i. This problem is central to the construction of suffix arrays and trees with many applications in string processing, computational biology and compression. A bottleneck in these applications is the amount of workspace needed to perform suffix sorting beyond the space needed to store the input as well as the output. In particular, emphasis is even on the constant c in the O(n) = cn space algorithms known for this problem, Currently the best previous result [5] takes O (nv + n log n) time and O (n/ √v) extra space, for any v ∈6 [1, √n] for strings from a general alphabet. We improve this and present the first known in-place suffix sorting algorithm. Our algorithm takes O (n log n) time using O(1) workspace and is optimal in the worst case for the general alphabet. © Springer-Verlag Berlin Heidelberg 2007
Static optimality theorem for external memory string access
No full textData warehouses are increasingly storing and managing large scale string data, and dealing with large volume of transactions that update and search string data. Motivated by this context, we initiate the study of self-adjusting data structures for string dictionary operations, that is, data structures that are designed to be efficient on an entire sequence rather than individual string operations. Furthermore, we study this problem in the external memory model where string data is too massive to be stored in internal memory and has to reside in disks; each access to a disk page fetches B items, and the cost of the operations is the number of pages accessed (I/Os). We show that given a dictionary of n strings S-1,...,S-n of total length N, a sequence of m string searches S-i1,Si-2,...,S-im takes
O(Sigma(j=1)(m)((B)/(\Sij\)) + Sigma(i=1)(n)(n(i)log(Bni)/(m))) expected I/Os, where n(i) is the number of times S-i is queried. Inserting or deleting a string S takes O((\S\)(B) + log(B) n) expected amortized I/Os. The Sigma(j=1)(m) (\Sij\)(B) term is a lower bound for reading the input; the Sigma(i=1)(n) n(i) log(B) (ni)/(m) term is the entropy of the query sequence and is a standard information-theoretic lower bound. This is the Static Optimality Theorem for external-memory string access. The static optimality theorem was first formalized and proved by Tarjan and Sleator for numerical dictionary in their classic splay trees paper in 1985 [16]; they left open the B-tree case for numerical values (page 684), and a fortiori, the case of string data in an external-memory setting, that we settle here. We obtain our result not by using traditional "splay" operations on search trees as in [16], but by designing a novel and conceptually simple self-adjusting data structure based on the well-known skip lists
A data structure for a sequence of string accesses in external memory
No full textWe introduce a new paradigm for querying strings in external memory, suited to the execution of sequences of operations. Formally, given a dictionary of n strings S1, . . . , Sn, we aim at supporting a search sequence for m not necessarily distinct strings T1, T2, . . . , Tm, as well as inserting and deleting individual strings. The dictionary is stored on disk, where each access to a disk page fetches B items, the cost of an operation is the number of pages accessed (I/Os), and efficiency must be attained on entire sequences of string operations rather than on individual ones.
Our approach relies on a novel and conceptually simple self-adjusting data structure (SASL) based on skip lists, that is also interesting per se
author-bios-SRD-19-0063.R1 – Supplemental material for The Network Structure of Police Misconduct
No full textSupplemental material, author-bios-SRD-19-0063.R1 for The Network Structure of Police Misconduct by George Wood, Daria Roithmayr and Andrew V. Papachristos in Socius</p
Symposium on utilisation of metallurgical wastes-A review
No full textThe control of industrial wastes is a problem of great significance, a proper solution of which involves economic, technical and legal factors. The rate at which the world's natural resources are being exhausted can be visualised from the fact that consumption of minerals and metals in the last half a century has exceeded what has been consumed in the previous 200 years. The rapid depletion of essential raw materials affects the industrialised countries much more than the relatively under-developed countries. From the standpoint of farsighted national economy, it is essential to conserve and efficiently utilise the raw materials and manufactured products including by-products. Large-scale expansion of industrial and mobilisation programmes continues to create critical shortages of various raw materials and brings into play the crucial role of the so-called waste material. The strategic importance of the use of waste products is forcibly brought up during times of war when the drive for self-sufficiency is of paramount importance. (Mr. J.E. Mannar, Senior Scientific Officer and Mr. V. Muthukrishnan, Senior Scientific Assistant, National Metallurgical Laboratory, Jamshedpur
Going Beyond Counting First Authors in Author Co-citation Analysis
No full textThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
No full text“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Phytochemical analysis, antioxidant and antimicrobial activity of wildand in vitro derived plants of Ceropegia thwaitesii Hook – An endemicspecies from Western Ghats, India
No full textCeropegia thwaitesii Hook (Asclepiadaceae), an endemic plant species, due to habitat destruction and overexploitation has a very restricted distribution in the Western Ghats of Tamil Nadu, India. The presentwrok aimed to determine the chemical composition, the total phenolic (TPC), flavonoid (TFC) and tannincontent (TEC), and to assess the antioxidant properties of various extracts of in vivo plants (IVP) andin vitro regenerated plants (IRP) of C. thwaitesii. Some phenolic compounds like gallic acid, cathechol,vanillin and salicylic acid were identified and quantified by HPLC. All the extracts possessed relevant rad-ical scavenging activity on DPPH, Superoxide radical scavenging activity, and Nitric oxide radicals as wellas total antioxidant ability. DPPH assay of in vitro methanol stems extracts and ethanol leaves extractsrevealed the best antioxidant properties with important IC50values of 0.248 ± 0.45 mg/mL and 0.397 ±0.67 mg/mL, respectively, whereas in vivo chloroform stems extracts showed a lower antioxidant activity(IC50of 10.99 ± 0.24 mg/mL). The IRP methanol extracts of stem and leaves had good inhibitory activityagainst all tested microorganisms in a dose-dependent manner. These results suggested that in vitroraised plants of C. thwaitesii are an excellent source of antioxidant compounds to be exploited on anindustrial level as food additive
- …
