OpenRaiser/Intern-Atlas huggingface dataset:
Dynamic Ordered Sets with Exponential Search Trees
Venue: arXiv cs.DS 2003
Year: 2003

We introduce exponential search trees as a novel technique for converting static polynomial space search structures for ordered sets into fully-dynamic linear space data structures. This leads to an optimal bound of O(sqrt(log n/loglog n)) for searching and updating a dynamic set of n integer keys in linear space. Here searching an integer y means finding the maximum key in the set which is smaller than or equal to y. This problem is equivalent to the standard text book problem of maintaining an ordered set (see, e.g., Cormen, Leiserson, Rivest, and Stein: Introduction to Algorithms, 2nd ed., MIT Press, 2001). The best previous deterministic linear space bound was O(log n/loglog n) due Fredman and Willard from STOC 1990. No better deterministic search bound was known using polynomial space. We also get the following worst-case linear space trade-offs between the number n, the word length w, and the maximal key U < 2^w: O(min{loglog n+log n/log w, (loglog n)(loglog U)/(logloglog U)}). These trade-offs are, however, not likely to be optimal. Our results are generalized to finger searching and string searching, providing optimal results for both in terms of n.
Compact Floor-Planning via Orderly Spanning Trees
Venue: arXiv cs.DS 2003
Year: 2003

Floor-planning is a fundamental step in VLSI chip design. Based upon the concept of orderly spanning trees, we present a simple O(n)-time algorithm to construct a floor-plan for any n-node plane triangulation. In comparison with previous floor-planning algorithms in the literature, our solution is not only simpler in the algorithm itself, but also produces floor-plans which require fewer module types. An equally important aspect of our new algorithm lies in its ability to fit the floor-plan area in a rectangle of size (n-1)x(2n+1)/3. Lower bounds on the worst-case area for floor-planning any plane triangulation are also provided in the paper.
Lower Bounds on the Bounded Coefficient Complexity of Bilinear Maps
Venue: arXiv cs.CC 2003
Year: 2003

We prove lower bounds of order $n\log n$ for both the problem to multiply polynomials of degree $n$, and to divide polynomials with remainder, in the model of bounded coefficient arithmetic circuits over the complex numbers. These lower bounds are optimal up to order of magnitude. The proof uses a recent idea of R. Raz [Proc. 34th STOC 2002] proposed for matrix multiplication. It reduces the linear problem to multiply a random circulant matrix with a vector to the bilinear problem of cyclic convolution. We treat the arising linear problem by extending J. Morgenstern's bound [J. ACM 20, pp. 305-306, 1973] in a unitarily invariant way. This establishes a new lower bound on the bounded coefficient complexity of linear forms in terms of the singular values of the corresponding matrix. In addition, we extend these lower bounds for linear and bilinear maps to a model of circuits that allows a restricted number of unbounded scalar multiplications.
Completeness and Decidability Properties for Functional Dependencies in XML
Venue: arXiv cs.DB 2003
Year: 2003

XML is of great importance in information storage and retrieval because of its recent emergence as a standard for data representation and interchange on the Internet. However XML provides little semantic content and as a result several papers have addressed the topic of how to improve the semantic expressiveness of XML. Among the most important of these approaches has been that of defining integrity constraints in XML. In a companion paper we defined strong functional dependencies in XML(XFDs). We also presented a set of axioms for reasoning about the implication of XFDs and showed that the axiom system is sound for arbitrary XFDs. In this paper we prove that the axioms are also complete for unary XFDs (XFDs with a single path on the l.h.s.). The second contribution of the paper is to prove that the implication problem for unary XFDs is decidable and to provide a linear time algorithm for it.
Complexity and Completeness of Immanants
Venue: arXiv cs.CC 2003
Year: 2003

Immanants are polynomial functions of n by n matrices attached to irreducible characters of the symmetric group S_n, or equivalently to Young diagrams of size n. Immanants include determinants and permanents as extreme cases. Valiant proved that computation of permanents is a complete problem in his algebraic model of NP theory, i.e., it is VNP-complete. We prove that computation of immanants is VNP-complete if the immanants are attached to a family of diagrams whose separation is $Ω(n^δ)$ for some $δ>0$. We define the separation of a diagram to be the largest number of overhanging boxes contained in a single row. Our theorem proves a conjecture of Buergisser for a large variety of families, and in particular we recover with new proofs his VNP-completeness results for hooks and rectangles.
The integration of systems of linear PDEs using conservation laws of syzygies
Venue: arXiv cs.SC 2003
Year: 2003

A new integration technique is presented for systems of linear partial differential equations (PDEs) for which syzygies can be formulated that obey conservation laws. These syzygies come for free as a by-product of the differential Groebner Basis computation. Compared with the more obvious way of integrating a single equation and substituting the result in other equations the new technique integrates more than one equation at once and therefore introduces temporarily fewer new functions of integration that in addition depend on fewer variables. Especially for high order PDE systems in many variables the conventional integration technique may lead to an explosion of the number of functions of integration which is avoided with the new method. A further benefit is that redundant free functions in the solution are either prevented or that their number is at least reduced.
Size reduction and partial decoupling of systems of equations
Venue: arXiv cs.SC 2003
Year: 2003

A method is presented that reduces the number of terms of systems of linear equations (algebraic, ordinary and partial differential equations). As a byproduct these systems have a tendency to become partially decoupled and are more likely to be factorizable or integrable. A variation of this method is applicable to non-linear systems. Modifications to improve efficiency are given and examples are shown. This procedure can be used in connection with the computation of the radical of a differential ideal (differential Groebner basis).
Unique Pattern Matching in Strings
Venue: arXiv cs.PL 2003
Year: 2003

Regular expression patterns are a key feature of document processing languages like Perl and XDuce. It is in this context that the first and longest match policies have been proposed to disambiguate the pattern matching process. We formally define a matching semantics with these policies and show that the generally accepted method of simulating longest match by first match and recursion is incorrect. We continue by solving the associated type inference problem, which consists in calculating for every subexpression the set of words the subexpression can still match when these policies are in effect, and show how this algorithm can be used to efficiently implement the matching process.
Segmentation, Indexing, and Visualization of Extended Instructional Videos
Venue: arXiv cs.IR 2003
Year: 2003

We present a new method for segmenting, and a new user interface for indexing and visualizing, the semantic content of extended instructional videos. Given a series of key frames from the video, we generate a condensed view of the data by clustering frames according to media type and visual similarities. Using various visual filters, key frames are first assigned a media type (board, class, computer, illustration, podium, and sheet). Key frames of media type board and sheet are then clustered based on contents via an algorithm with near-linear cost. A novel user interface, the result of two user studies, displays related topics using icons linked topologically, allowing users to quickly locate semantically related portions of the video. We analyze the accuracy of the segmentation tool on 17 instructional videos, each of which is from 75 to 150 minutes in duration (a total of 40 hours); the classification accuracy exceeds 96%.
Analysis and Interface for Instructional Video
Venue: arXiv cs.IR 2003
Year: 2003

We present a new method for segmenting, and a new user interface for indexing and visualizing, the semantic content of extended instructional videos. Using various visual filters, key frames are first assigned a media type (board, class, computer, illustration, podium, and sheet). Key frames of media type board and sheet are then clustered based on contents via an algorithm with near-linear cost. A novel user interface, the result of two user studies, displays related topics using icons linked topologically, allowing users to quickly locate semantically related portions of the video. We analyze the accuracy of the segmentation tool on 17 instructional videos, each of which is from 75 to 150 minutes in duration (a total of 40 hours); it exceeds 96%.
Cryptographic Randomized Response Techniques
Venue: arXiv cs.CC 2003
Year: 2003

We develop cryptographically secure techniques to guarantee unconditional privacy for respondents to polls. Our constructions are efficient and practical, and are shown not to allow cheating respondents to affect the ``tally'' by more than their own vote -- which will be given the exact same weight as that of other respondents. We demonstrate solutions to this problem based on both traditional cryptographic techniques and quantum cryptography.
Recursive function templates as a solution of linear algebra expressions in C++
Venue: arXiv cs.MS 2003
Year: 2003

The article deals with a kind of recursive function templates in C++, where the recursion is realized corresponding template parameters to achieve better computational performance. Some specialization of these template functions ends the recursion and can be implemented using optimized hardware dependent or independent routines. The method is applied in addition to the known expression templates technique to solve linear algebra expressions with the help of the BLAS library. The whole implementation produces a new library, which keeps object-oriented benefits and has a higher computational speed represented in the tests.
Tiling space and slabs with acute tetrahedra
Venue: arXiv cs.CG 2003
Year: 2003

We show it is possible to tile three-dimensional space using only tetrahedra with acute dihedral angles. We present several constructions to achieve this, including one in which all dihedral angles are less than $77.08^\circ$, and another which tiles a slab in space.
Empirical Methods for Compound Splitting
Venue: arXiv cs.CL 2003
Year: 2003

Compounded words are a challenge for NLP applications such as machine translation (MT). We introduce methods to learn splitting rules from monolingual and parallel corpora. We evaluate them against a gold standard and measure their impact on performance of statistical MT systems. Results show accuracy of 99.1% and performance gains for MT of 0.039 BLEU on a German-English noun phrase translation task.
Experimental Software Schedulability Estimation For Varied Processor Frequencies
Venue: arXiv cs.SE 2003
Year: 2003

This paper describes a new approach to experimentally estimate the application schedulability for various processor frequencies. We use additional workload generated by an artificial high priority routine to simulate the frequency decrease of a processor. Then we estimate the schedulability of applications at different frequencies. The results of such estimation can be used to determine the frequencies and control algorithms of dynamic voltage scaling/dynamic frequency scaling (DVS/DFS) implementations. The paper presents a general problem description, the proposed schedulability estimation method, its analysis and evaluation.
A first approach for a possible cellular automaton model of fluids dynamics
Venue: arXiv cs.CC 2003
Year: 2003

In this paper I present a first attempt for a possible description of fluids dynamics by mean of a cellular automata technique. With the use of simple and elementary rules, based on random behaviour either, the model permits to obtain the evolution in time for a two-dimensional grid, where one molecule of the material fluid can ideally place itself on a single geometric square. By mean of computational simulations, some realistic effects, here showed by use of digital pictures, have been obtained. In a subsequent step of this work I think to use a parallel program for a high performances computational simulation, for increasing the degree of realism of the digital rendering by mean of a three-dimensional grid too. For the execution of the simulations, numerical methods of resolution for differential equations have not been used.
Multi-target particle filtering for the probability hypothesis density
Venue: arXiv cs.AI 2003
Year: 2003

When tracking a large number of targets, it is often computationally expensive to represent the full joint distribution over target states. In cases where the targets move independently, each target can instead be tracked with a separate filter. However, this leads to a model-data association problem. Another approach to solve the problem with computational complexity is to track only the first moment of the joint distribution, the probability hypothesis density (PHD). The integral of this distribution over any area S is the expected number of targets within S. Since no record of object identity is kept, the model-data association problem is avoided. The contribution of this paper is a particle filter implementation of the PHD filter mentioned above. This PHD particle filter is applied to tracking of multiple vehicles in terrain, a non-linear tracking problem. Experiments show that the filter can track a changing number of vehicles robustly, achieving near-real-time performance.
Complex Systems
Venue: arXiv cs.NI 2003
Year: 2003

The study of Complex Systems is considered by many to be a new scientific field, and is distinguished by being a discipline that has applications within many separate areas of scientific study. The study of Neural Networks, Traffic Patterns, Artificial Intelligence, Social Systems, and many other scientific areas can all be considered to fall within the realm of Complex Systems, and can be studied from this new perspective. The advent of more capable computer systems has allowed these systems to be simulated and modeled with far greater ease, and new understanding of computer modeling approaches has allowed the fledgling science to be studied as never before. The preliminary focus of this paper will be to provide a general overview of the science of Complex Systems, including terminology, definitions, history, and examples. I will attempt to look at some of the most important trends in different areas of research, and give a general overview of research methods that have been used in parallel with computer modeling. Also, I will further define the areas of the science that concern themselves with computer modeling and simulation, and I will attempt to make it clear why the science only came into its own when the proper modeling and simulation tools were finally available. In addition, although there seems to be general agreement between different authors and institutes regarding the generalities of the study, there are some differences in terminology and methodology. I have attempted in this paper to bring as many elements together as possible, as far as the scope of the subject is concerned, without losing focus by studying Complex System techniques that are bound to one particular area of scientific study, unless that area is that of computer modeling.
Differential Methods in Catadioptric Sensor Design with Applications to Panoramic Imaging
Venue: arXiv cs.CV 2003
Year: 2003

We discuss design techniques for catadioptric sensors that realize given projections. In general, these problems do not have solutions, but approximate solutions may often be found that are visually acceptable. There are several methods to approach this problem, but here we focus on what we call the ``vector field approach''. An application is given where a true panoramic mirror is derived, i.e. a mirror that yields a cylindrical projection to the viewer without any digital unwarping.
Preserving Peer Replicas By Rate-Limited Sampled Voting in LOCKSS
Venue: arXiv cs.DC 2003
Year: 2003

The LOCKSS project has developed and deployed in a world-wide test a peer-to-peer system for preserving access to journals and other archival information published on the Web. It consists of a large number of independent, low-cost, persistent web caches that cooperate to detect and repair damage to their content by voting in "opinion polls." Based on this experience, we present a design for and simulations of a novel protocol for voting in systems of this kind. It incorporates rate limitation and intrusion detection to ensure that even some very powerful adversaries attacking over many years have only a small probability of causing irrecoverable damage before being detected.
Analyzing and modelling the AS-level Internet topology
Venue: arXiv cs.NI 2003
Year: 2003

Recently we introduced the rich-club phenomenon as a quantitative metric to characterize the tier structure of the Autonomous Systems level Internet topology (AS graph) and we proposed the Interactive Growth (IG) model, which closely matches the degree distribution and hierarchical structure of the AS graph and compares favourble with other available Internet power-law topology generators. Our research was based on the widely used BGP AS graph obtained from the Oregon BGP routing tables. Researchers argue that Traceroute AS graph, extracted from the traceroute data collected by the CAIDA's active probing tool, Skitter, is more complete and reliable. To be prudent, in this paper we analyze and compare topological structures of Traceroute AS graph and BGP AS graph. Also we compare with two synthetic Internet topologies generated by the IG model and the well-known Barabasi-Albert (BA) model. Result shows that both AS graphs show the rich-club phenomenon and have similar tier structures, which are closely matched by the IG model, however the BA model does not show the rich-club phenomenon at all.
A Bird's eye view of Matrix Distributed Processing
Venue: arXiv cs.DC 2003
Year: 2003

We present Matrix Distributed Processing, a C++ library for fast development of efficient parallel algorithms. MDP is based on MPI and consists of a collection of C++ classes and functions such as lattice, site and field. Once an algorithm is written using these components the algorithm is automatically parallel and no explicit call to communication functions is required. MDP is particularly suitable for implementing parallel solvers for multi-dimensional differential equations and mesh-like problems.
Embedded Reflection Mapping
Venue: arXiv cs.GR 2003
Year: 2003

Environment maps are used to simulate reflections off curved objects. We present a technique to reflect a user, or a group of users, in a real environment, onto a virtual object, in a virtual reality application, using the live video feeds from a set of cameras, in real-time. Our setup can be used in a variety of environments ranging from outdoor or indoor scenes.
Glottochronologic Retrognostic of Language System
Venue: arXiv cs.CL 2003
Year: 2003

A glottochronologic retrognostic of language system is proposed
Computing only minimal answers in disjunctive deductive databases
Venue: arXiv cs.LO 2003
Year: 2003

A method is presented for computing minimal answers in disjunctive deductive databases under the disjunctive stable model semantics. Such answers are constructed by repeatedly extending partial answers. Our method is complete (in that every minimal answer can be computed) and does not admit redundancy (in the sense that every partial answer generated can be extended to a minimal answer), whence no non-minimal answer is generated. For stratified databases, the method does not (necessarily) require the computation of models of the database in their entirety. Compilation is proposed as a tool by which problems relating to computational efficiency and the non-existence of disjunctive stable models can be overcome. The extension of our method to other semantics is also considered.
Time-scales, Meaning, and Availability of Information in a Global Brain
Venue: arXiv cs.AI 2003
Year: 2003

We note the importance of time-scales, meaning, and availability of information for the emergence of novel information meta-structures at a global scale. We discuss previous work in this area and develop future perspectives. We focus on the transmission of scientific articles and the integration of traditional conferences with their virtual extensions on the Internet, their time-scales, and availability. We mention the Semantic Web as an effort for integrating meaningful information.
Finding a Posterior Domain Probability Distribution by Specifying Nonspecific Evidence
Venue: arXiv cs.AI 2003
Year: 2003

This article is an extension of the results of two earlier articles. In [J. Schubert, On nonspecific evidence, Int. J. Intell. Syst. 8 (1993) 711-725] we established within Dempster-Shafer theory a criterion function called the metaconflict function. With this criterion we can partition into subsets a set of several pieces of evidence with propositions that are weakly specified in the sense that it may be uncertain to which event a proposition is referring. In a second article [J. Schubert, Specifying nonspecific evidence, in Cluster-based specification techniques in Dempster-Shafer theory for an evidential intelligence analysis of multiple target tracks, Ph.D. Thesis, TRITA-NA-9410, Royal Institute of Technology, Stockholm, 1994, ISBN 91-7170-801-4] we not only found the most plausible subset for each piece of evidence, we also found the plausibility for every subset that this piece of evidence belongs to the subset. In this article we aim to find a posterior probability distribution regarding the number of subsets. We use the idea that each piece of evidence in a subset supports the existence of that subset to the degree that this piece of evidence supports anything at all. From this we can derive a bpa that is concerned with the question of how many subsets we have. That bpa can then be combined with a given prior domain probability distribution in order to obtain the sought-after posterior domain distribution.