bluuebunny/crossref_metadata_2025 huggingface dataset:
A brief survey of web data extraction tools
Authors: Laender Alberto H. F. , Ribeiro-Neto Berthier A. , da Silva Altigran S. , Teixeira Juliana S.
Published: November 2005

In the last few years, several works in the literature have addressed the problem of data extraction from Web pages. The importance of this problem derives from the fact that, once extracted, the data can be handled in a way similar to instances of a traditional database. The approaches proposed in the literature to address the problem of Web data extraction use techniques borrowed from areas such as natural language processing, languages and grammars, machine learning, information retrieval, databases, and ontologies. As a consequence, they present very distinct features and capabilities which make a direct comparison difficult to be done. In this paper, we propose a taxonomy for characterizing Web data extraction fools, briefly survey major Web data extraction tools described in the literature, and provide a qualitative analysis of them. Hopefully, this work will stimulate other studies aimed at a more comprehensive analysis of data extraction approaches and tools for Web data.
Recovery protocols for shared memory database systems
Authors: Molesky Lory D. , Ramamritham Krithi
Published: November 2005

Significant performance advantages can be gained by implementing a database system on a cache-coherent shared memory multiprocessor. However, problems arise when failures occur. A single node (where a
node
refers to a processor/memory pair) crash may require a reboot of the entire shared memory system. Fortunately, shared memory multiprocessors that isolate individual node failures are currently being developed. Even with these, because of the side effects of the cache coherency protocol, a transaction executing strictly on a single node may become dependent on the validity of the memory of
many
nodes thereby inducing unnecessary transaction aborts. This happens when
database objects,
such as records, and
database support structures,
such as index structures and shared lock tables, are stored in shared memory.In this paper, we propose crash recovery protocols for shared memory database systems which avoid the unnecessary transaction aborts induced by the effects of using shared physical memory. Our recovery protocols guarantee that if one or more nodes crash, all the effects of active transactions running on the crashed nodes will be undone, and no effects of transactions running on nodes which did not crash will be undone. In order to show the practicality of our protocols, we discuss how existing features of cache-coherent multiprocessors can be utilized to implement these recovery protocols. Specifically, we demonstrate that (1) for many types of database objects and support structures, volatile (in-memory) logging is sufficient to avoid unnecessary transaction aborts, and (2) a very low overhead implementation of this strategy can be achieved with existing multiprocessor features.
Adaptive parallel aggregation algorithms
Authors: Shatdal Ambuj , Naughton Jeffrey F.
Published: November 2005

Aggregation and duplicate removal are common in SQL queries. However, in the parallel query processing literature, aggregate processing has received surprisingly little attention; furthermore, for each of the traditional parallel aggregation algorithms, there is a range of grouping selectivities where the algorithm performs poorly. In this work, we propose new algorithms that dynamically adapt, at query evaluation time, in response to observed grouping selectivities. Performance analysis via analytical modeling and an implementation on a workstation-cluster shows that the proposed algorithms are able to perform well for all grouping selectivities. Finally, we study the effect of data skew and show that for certain data sets the proposed algorithms can even outperform the best of traditional approaches.
The Lotus notes storage system
Authors: Moore Kenneth
Published: November 2005

Lotus Notes is a commercial product that empowers individuals and organizations to collaborate and share information [1].Notes enables the easy development of applications such as messaging, document management, workflow, and asynchronous conferencing. Notes applications can be deployed globally, across independent organizations, among a heterogeneous network of loosely coupled computers that range in size from small notebooks to large multi-processor systems.The third major release of Lotus Notes occurred in May 1993. Notes is a client-server product, with clients available on Windows, OS/2, Macintosh, SCO UNIX, HP-UX, AIX, and Solaris. The server is available on Windows, OS/2, Windows NT (for Intel processors), NetWare, SCO UNIX, HP-UX, AIX, and Solaris.
Why and how to benchmark XML databases
Authors: Schmidt Albrecht , Waas Florian , Kersten Martin , Florescu Daniela , Carey Michael J. , Manolescu Ioana , Busse Ralph
Published: November 2005

Benchmarks belong to the very standard repertory of tools deployed in database development. Assessing the capabilities of a system, analyzing actual and potential bottlenecks, and, naturally, comparing the pros and cons of different systems architectures have become indispensable tasks as databases management systems grow in complexity and capacity. In the course of the development of XML databases the need for a benchmark framework has become more and more evident: a great many different ways to store XML data have been suggested in the past, each with its genuine advantages, disadvantages and consequences that propagate through the layers of a complex database system and need to be carefully considered. The different storage schemes render the query characteristics of the data variably different. However, no conclusive methodology for assessing these differences is available to date.In this paper, we outline desiderata for a benchmark for XML databases drawing from our own experience of developing an XML repository, involvement in the definition of the standard query language, and experience with standard benchmarks for relational databases.
Detection and classification of intrusions and faults using sequences of system calls
Authors: Cabrera João B. D. , Lewis Lundy , Mehra Raman K.
Published: November 2005

This paper investigates the use of sequences of system calls for classifying intrusions and faults induced by privileged processes in Unix. Classification is an essential capability for responding to an anomaly (attack or fault), since it gives the ability to associate appropriate responses to each anomaly type. Previous work using the well known dataset from the University of New Mexico (UNM) has demonstrated the usefulness of monitoring sequences of system calls for detecting anomalies induced by processes corresponding to several Unix Programs, such as sendmail, lpr, ftp, etc. Specifically, previous work has shown that the Anomaly Count of a running process, i.e., the number of sequences spawned by the process which are not found in the corresponding dictionary of normal activity for the Program, is a valuable feature for anomaly detection. To achieve Classification, in this paper we introduce the concept of Anomaly Dictionaries, which are the sets of anomalous sequences for each type of anomaly. It is verified that Anomaly Dictionaries for the UNM's sendmail Program have very little overlap, and can be effectively used for Anomaly Classification. The sequences in the Anomalous Dictionary enable a description of Self for the Anomalies, analogous to the definition of Self for Privileged Programs given by the Normal Dictionaries. The dependence of Classification Accuracy with sequence length is also discussed. As a side result, it is also shown that a hybrid scheme, combining the proposed classification strategy with the original Anomaly Counts can lead to a substantial improvement in the overall detection rates for the sendmail dataset. The methodology proposed is rather general, and can be applied to any situation where sequences of symbols provide an effective characterization of a phenomenon.
On the academic interview circuit
Authors: Çetintemel Uğur
Published: November 2005

This article summarizes my recent job search that effectively began in the late fall of 2000 and ended in the early summer of 2001. The opinions I express here are largely based on what I experienced, heard and read from various sources, and should be taken as mere tips or suggestions for Ph.D. students who are soon to graduate and look for a position in a research-oriented academic institution.This is by no means a comprehensive guide to job searching: in limited space, I address only the issues that I deem more relevant or important, in an effort to provide information and insight that I believe is not readily available elsewhere. I do, however, try to provide pointers to (hopefully) complementary information throughout the text wherever appropriate and in Section 13.Figure 1 illustrates the typical timeline for the entire process, from pre-application to final decision, and the documents and activities required at each stage. The rest of the article briefly discusses each of these stages.
An extension of the database language SQL to capture more relational concepts
Authors: Vossen Gottfried , Yacabucci Jim
Published: November 2005

An extension of the database language SQL is described which introduces several new concepts into the language that are standard in the relational model, but surprisingly not present in available SQL-based systems such as SQL/DS and DB2.
Emergent semantics and the multimedia semantic web
Authors: Grosky W. I. , Sreenath D. V. , Fotouhi F.
Published: November 2005

It is well known that context plays an important role in the meaning of a work of art. This paper addresses the dynamic context of a collection of linked multimedia documents, of which the web is a perfect example. Contextual document semantics emerge through identification of various users' browsing paths though this multimedia collection. In this paper, we present techniques that use multimedia information as part of this determination. Some implications of our approach are that the author of a webpage cannot completely define that document's semantics and that semantics emerge through use.
ANSI SQL hierarchical processing can fully integrate native XML
Authors: David Michael M.
Published: November 2005

Most SQL-based XML vendor support is through interoperation and not integration. One reason for this is that XML is inherently hierarchical and SQL is supposedly not. This paper demonstrates how ANSI SQL along with its relational Cartesian product model can naturally perform complete and flexible hierarchical query processing. With this ANSI SQL inherent hierarchical processing capability, native XML data can be fully and seamlessly integrated into SQL processing and operated on at a full hierarchical level. This paper will describe the basic stages involved in this hierarchical SQL processing: hierarchical data modeling, hierarchical working set creation, and hierarchical Cartesian product processing. These processes enable a complete relational, XML, and legacy data integration which maintains ANSI SQL compatibility even while performing the most complex multi-leg hierarchical processing, and includes the dynamic, direct, and controlled hierarchical joining of hierarchical structures. Also covered are ANSI SQL hierarchical support features: hierarchical SQL views, hierarchical data filtering, and hierarchical optimization. These make standard SQL a well rounded and complete hierarchical processor. With this full hierarchical level of processing established, it will be shown how the relational Cartesian product engine can be seamlessly replaced with a hierarchical engine, greatly increasing processing and memory utilization, and enabling advanced XML hierarchical data capabilities.
Evaluating the size of queries on relational databases with non-uniform distribution and stochastic dependence
Authors: Salza Silvio , Terranova Mario
Published: November 2005

The paper deals with the problem of evaluating how the originality of the attributes of a relation, i.e. the number of distinct values in each attribute, is affected by relational operations that reduce the cardinality of the relation. This is indeed an interesting problem in research areas such as database design and query optimization. Some authors have shown that non uniform distributions and stochastic dependence significantly affect the originality of the attributes. Therefore the models that have been proposed in the literature, based on uniformity and independence assumptions, in several situation can not be conveniently utilized. In this paper we propose a probabilistic model that overcomes the need of the uniformity and independence assumptions. The model is exact for non uniform distributions when the attributes are independent, and gives approximate results when stochastic dependence is considered. In the latter case the analytical results have been compared with a simulation, and proved to be quite accurate.
Incorporating hierarchy in a relational model of data
Authors: Jagadish H. V.
Published: November 2005

We extend the relational model of data to allow classes as attribute values, thereby permitting the representation of hierarchies of objects. Inheritance, including multiple inheritance with exceptions, is clearly supported. Facts regarding classes of objects can be stored and manipulated in the same way as facts regarding object instances. Our model is upwards compatible with the standard relational model.
Efficient evaluation of right-, left-, and multi-linear rules
Authors: Naughton J. F. , Ramakrishnan R. , Sagiv Y. , Ullman J. D.
Published: November 2005

We present an algorithm for the efficient evaluation of a useful subset of recursive queries. Like the magic sets transformation, the algorithm consists of a rewriting phase followed by semi-naive bottom-up evaluation of the resulting rules. We prove that on a wide range of recursions, this algorithm achieves a factor of
Ο
(
n
) speedup over magic sets. Intuitively, the transformations in this algorithm achieve their performance by reducing the arity of the recursive predicates in the transformed rules.
Efficient management of transitive relationships in large data and knowledge bases
Authors: Agrawal R. , Borgida A. , Jagadish H. V.
Published: November 2005

We argue that accessing the transitive closure of relationships is an important component of both databases and knowledge representation systems in Artificial Intelligence. The demands for efficient access and management of large relationships motivate the need for explicitly storing the transitive closure in a compressed and local way, while allowing updates to the base relation to be propagated incrementally. We present a transitive closure compression technique, based on labeling spanning trees with numeric intervals, and provide both analytical and empirical evidence of its efficacy, including a proof of optimality.
Nested historical relations
Authors: Tansel A. U. , Garnett L.
Published: November 2005

The paper extends nested relations for managing temporal variation of complex objects. It combines the research in temporal databases and nested relations for nontraditional database applications. The basic modelling construct is a temporal atom as an attribute value. A temporal atom consists of two components, a value and temporal set which is a set of times denoting the validity period of the value. We define algebra operations for nested historical relations. Data redundancy in nested historical relations is also discussed and criteria for well-structured nested relations are established.
Optimization of large join queries: combining heuristics and combinatorial techniques
Authors: Swami A.
Published: November 2005

We investigate the use of heuristics in optimizing queries with a large number of joins. Examples of such heuristics are the augmentation and local improvement heuristics described in this paper and a heuristic proposed by Krishnamurthy et al. We also study the combination of these heuristics with two general combinatorial optimization techniques, iterative improvement and simulated annealing, that were studied in a previous paper. Several interesting combinations are experimentally compared. For completeness, we also include simple iterative improvement and simulated annealing in our experimental comparisons. We find that two combinations of the augmentation heuristic and iterative improvement perform the best under most conditions. The results are validated using two different cost models and several different synthetic benchmarks.
Extensible query processing in starburst
Authors: Haas L. M. , Freytag J. C. , Lohman G. M. , Pirahesh H.
Published: November 2005

Today's DBMSs are unable to support the increasing demands of the various applications that would like to use a DBMS. Each kind of application poses new requirements for the DBMS. The Starburst project at IBM's Almaden Research Center aims to extend relational DBMS technology to bridge this gap between applications and the DBMS. While providing a full function relational system to enable sharing across applications, Starburst will also allow (sophisticated) programmers to add many kinds of extensions to the base system's capabilities, including language extensions (e.g., new datatypes and operations), data management extensions (e.g., new access and storage methods) and internal processing extensions (e.g., new join methods and new query transformations). To support these features, the database query language processor must be very powerful and highly extensible. Starburst's language processor features a powerful query language, rule-based optimization and query rewrite, and an execution system based on an extended relational algebra. In this paper, we describe the design of Starburst's query language processor and discuss the ways in which the language processor can be extended to achieve Starburst's goals.
A static pessimistic scheme for handling replicated databases
Authors: Tang T. , Natarajan N.
Published: November 2005

A replicated database system may partition into isolated groups in the presence of node and link failures. When the system has partitioned, a
pessimistic scheme
maintains availability and consistency of replicated data by ensuring that updates occur in at most one group. A pessimistic scheme is called a
static scheme
if these
distinguished
groups are determined only by the membership of different groups in the partitioned system. In this paper, we present a new static scheme that is more powerful than voting. In this scheme, the set of distinguished groups, called an
acceptance set
, is chosen at design time. To commit an update, a node checks if its enclosing group is a member of this acceptance set. Using an encoding scheme for groups, this check is implemented very efficiently. Another merit of the proposed scheme is that the problem of determining an
optimal
acceptance set is formulated as a
sparse 0-1 linear programming problem
. Hence, the optimization problem can be handled using the very rich class of existing techniques for solving such problems. Based on our experiments, we feel that this optimization approach is feasible for systems containing up to 10 nodes (copies).
A syntax and semantics for set-oriented production rules in relational database systems
Authors: Widom J. , Finkelstein S. J.
Published: November 2005

We propose incorporating a production rules facility into a relational database system. Such a facility allows definition of database operations that are automatically executed whenever certain conditions are met. In keeping with the set-oriented approach of relational data manipulation languages, our production rules are also set-oriented—they are triggered by sets of changes to the database and may consequently perform sets of changes. The condition and action parts of our production rules may refer to the current state of the database as well as to the sets of changes triggering the rules. We define a syntax for production rule definition as an extension to SQL. A model of system behavior is used to give an exact semantics for production rule execution, taking into account externally-generated operations, self-triggering rules, and simultaneous triggering of multiple rules.

Due to space constraints, some details and discussion are omitted, and only a few examples are included. See [19] for a more extensive description.
Optimizing SQL queries for parallel execution
Authors: von Bultzingsloewen G.
Published: November 2005

The optimization problem discussed in this paper is the translation of an SQL query into an efficient parallel execution plan for a multiprocessor database machine under the performance goal of reduced response times as well as increased throughput in a multiuser environment. We describe and justify the most important research problems which have to be solved to achieve this task, and we explain our approach to solve these problems.
XPath processing in a nutshell
Authors: Gottlob Georg , Koch Christoph , Pichler Reinhard
Published: November 2005

We provide a concise yet complete formal definition of the semantics of XPath 1 and summarize efficient algorithms for processing queries in this language. Our presentation is intended both for the reader who is looking for a short but comprehensive formal account of XPath as well as the software developer in need of material that facilitates the rapid implementation of XPath engines.
Research issues for data communication in mobile ad-hoc network database systems
Authors: Fife Leslie D. , Gruenwald Le
Published: November 2005

Mobile Ad-hoc Networks (MANET) is an emerging area of research. Most current work is centered on routing issues. This paper discusses the issues associated with data communication with MANET database systems. While data push and data pull methods have been previously addressed in mobile networks, the proposed methods do not handle the unique requirements associated with MANET. Unlike traditional mobile networks,
all
nodes within the MANET are mobile and battery powered. Existing wireless algorithms and protocols are insufficient primarily because they do not consider the mobility and power requirements of both clients and servers. This paper will present some of the critical tasks facing this research.
A mapping mechanism to support bitmap index and other auxiliary structures on tables stored as primary B
+
-trees
Authors: Chong Eugene Inseok , Srinivasan Jagannathan , Das Souripriya , Freiwald Chuck , Yalamanchi Aravind , Jagannath Mahesh , Tran Anh-Tuan , Krishnan Ramkumar , Jiang Richard
Published: November 2005

Any auxiliary structure, such as a bitmap or a B
+
-tree index, that refers to rows of a table stored as a primary B
+
-tree (e.g.,
tables with clustered index
in Microsoft SQL Server, or
index-organized tables
in Oracle) by their physical addresses would require updates due to inherent volatility of those addresses. To address this problem, we propose a mapping mechanism that 1) introduces a single mapping table, with each row holding one key value from the primary B
+
-tree, as an intermediate structure between the primary B
+
-tree and the associated auxiliary structures, and 2) augments the primary B
+
-tree structure to include in each row the physical address of the corresponding mapping table row. The mapping table row addresses can then be used in the auxiliary structures to indirectly refer to the primary B
+
-tree rows. The two key benefits are: 1) the mapping table shields the auxiliary structures from the volatility of the primary B
+
-tree row addresses, and 2) the method allows reuse of existing conventional table mechanisms for supporting auxiliary structures on primary B
+
- trees.This paper presents the mapping mechanism, its possible application in supporting various auxiliary structures on primary B
+
-trees, and a case study describing its use for supporting bitmap indexes on index-organized tables in Oracle9
i
. The case study demonstrates that the proposed mapping mechanism allows us to reuse existing bitmap index technologies with minimal changes. It also includes a comparison between bitmap and non-bitmap (B
+
- tree) index performance on index-organized tables for both single-table queries and star queries. The analytical and experimental studies show that the method is storage efficient, and (despite the mapping table overhead) provides performance benefits that are similar to those provided by bitmap indexes implemented on conventional tables.
Encapsulation of parallelism in the Volcano query processing system
Authors: Graefe Goetz
Published: November 2005

Volcano is a new dataflow query processing system we have developed for database systems research and education. The uniform interface between operators makes Volcano extensible by new operators. All operators are designed and coded as if they were meant for a single-process system only. When attempting to parallelize Volcano, we had to choose between two models of parallelization, called here the
bracket
and
operator
models. We describe the reasons for not choosing the bracket model, introduce the novel operator model, and provide details of Volcano's
exchange
operator that parallelizes all other operators. It allows intra-operator parallelism on partitioned datasets and both vertical and horizontal inter-operator parallelism. The exchange operator encapsulates all parallelism issues and therefore makes implementation of parallel database algorithms significantly easier and more robust. Included in this encapsulation is the translation between demand-driven dataflow within processes and data-driven dataflow between processes. Since the interface between Volcano operators is similar to the one used in “real,” commercial systems, the techniques described here can be used to parallelize other query processing engines.
Organizing long-running activities with triggers and transactions
Authors: Dayal Umeshwar , Hsu Meichun , Ladin Rivka
Published: November 2005

This paper addresses the problem of organising and controlling activities that involve multiple steps of processing and that typically are of long duration. We explore the use of triggers and transactions to specify and organize such long-running activities. Triggers offer data- or event-driven specification of control flow, and thus provide a flexible and modular framework with which the control structures of the activities can be extended or modified. We describe a model based on event-condition-action rules and coupling modes. The execution of these rules is governed by an extended nested transaction model. Through a detailed example, we illustrate the utility of the various features of the model for chaining related steps without sacrificing concurrency, for enforcing integrity constraints, and for providing flexible failure and exception handling.
Magic is relevant
Authors: Mumick I. S. , Finkelstein S. J. , Pirahesh Hamid , Ramakrishnan Raghu
Published: November 2005

We define the magic-sets transformation for traditional relational systems (with duplicates, aggregation and grouping), as well as for relational systems extended with recursion. We compare the magic-sets rewriting to traditional optimization techniques for nonrecursive queries, and use performance experiments to argue that the magic-sets transformation is often a better optimization technique.
Toward network data independence
Authors: Hellerstein Joseph M.
Published: November 2005

A number of researchers have become interested in the design of global-scale networked systems and applications. Our thesis here is that the database community's principles and technologies have an important role to play in the design of these systems. The point of departure is at the roots of database research: we generalize Codd's notion of data independence to physical environments beyond storage systems. We note analogies between the development of database indexes and the new generation of structured peer-to-peer networks. We illustrate the emergence of data independence in networks by surveying a number of recent network facilities and applications, seen through a database lens. We present a sampling of database query processing techniques that can contribute in this arena, and discuss methods for adoption of these technologies.
The hyperion project
Authors: Arenas Marcelo , Kantere Vasiliki , Kementsietsidis Anastasios , Kiringa Iluju , Miller Renée J. , Mylopoulos John
Published: November 2005

We present an architecture and a set of challenges for peer database management systems. These systems team up to build a network of nodes (peers) that coordinate at run time most of the typical DBMS tasks such as the querying, updating, and sharing of data. Such a network works in a way similar to conventional multidatabases. Conventional multidatabase systems are founded on key concepts such as those of a global schema, central administrative authority, data integration, global access to multiple databases, permanent participation of databases, etc. Instead, our proposal assumes total absence of any central authority or control, no global schema, transient participation of peer databases, and constantly evolving coordination rules among databases. In this work, we describe the status of the Hyperion project, present our current solutions, and outline remaining research issues.
Relational data sharing in peer-based data management systems
Authors: Ooi Beng Chin , Shu Yanfeng , Tan Kian-Lee
Published: November 2005

Data sharing in current P2P systems is very much restricted to file-system-like capabilities. In this paper, we present the strategies that we have adopted in our BestPeer project to support more fine-grained data sharing, especially, relational data sharing, in a P2P context. First, we look at some of the issues in designing a peer-based data management system, and discuss some possible solutions to address these issues. Second, we present the design of our first prototype system, PeerDB, and report our experience with it. Finally, we discuss our current extensions to PeerDB to support keyword-based queries.
Understanding the semantics of sensor data
Authors: Mani Murali
Published: November 2005

Our system architecture to manage sensor data is described. Our data mining applications require past history of the sensor data. Therefore, unlike most present systems that focus on streaming data, and cache a small window of historic data, we store the entire historic data. Several interesting problems arise in these scenarios. We study two of them: (a) Given that a sensor can send data corresponding to its current configuration at any particular instant, how do we define the data that should be stored in the database? (b) Sensors try to minimize the amount of data transmitted. Also there could be data loss in the network. So the data stored will have lots of "holes". In this case, how can an application make sense of the stored data? In this paper, we describe our approach to solve these problems that enables an application to recreate the environment that generated the data as precisely as possible.
Bluetooth-based sensor networks
Authors: Bonnet Philippe , Beaufour Allan , Dydensborg Mads Bondo , Leopold Martin
Published: November 2005

It is neither desirable nor possible to abstract sensor network software from the characteristics of the underlying hardware components. In particular the radio has a major impact on higher level software. In this paper, we review the lessons we learnt using Bluetooth radios in the context of sensor networks. These lessons are relevant for (a) application designers choosing the best radio given a set of requirements and for (b) researchers in the data management community who need to formulate assumptions about underlying sensor networks.
An environmental sensor network to determine drinking water quality and security
Authors: Ailamaki Anastassia , Faloutos Christos , Fischbeck Paul S. , Small Mitchell J. , VanBriesen Jeanne
Published: November 2005

Finding patterns in large, real, spatio/temporal data continues to attract high interest (e.g., sales of products over space and time, patterns in mobile phone users; sensor networks collecting operational data from automobiles, or even from humans with wearable computers). In this paper, we describe an interdisciplinary research effort to couple knowledge discovery in large environmental databases with biological and chemical sensor networks, in order to revolutionize drinking water quality and security decision making. We describe a distribution and operation protocol for the placement and utilization of in situ environmental sensors by combining (1) new algorithms for spatialtemporal data mining, (2) new methods to model water quality and security dynamics, and (3) a sophisticated decision-analysis framework. The project was recently funded by NSF and represents application of these research areas to the critical current issue of ensuring safe and secure drinking water to the population of the United States.
Distributed deviation detection in sensor networks
Authors: Palpanas Themistoklis , Papadopoulos Dimitris , Kalogeraki Vana , Gunopulos Dimitrios
Published: November 2005

Sensor networks have recently attracted much attention, because of their potential applications in a number of different settings. The sensors can be deployed in large numbers in wide geographical areas, and can be used to monitor physical phenomena, or to detect certain events.An interesting problem which has not been adequately addressed so far is that of distributed online deviation detection in streaming data. The identification of deviating values provides an efficient way to focus on the interesting events in the sensor network.In this work, we propose a technique for online deviation detection in streaming data. We discuss how these techniques can operate efficiently in the distributed environment of a sensor network, and discuss the tradeoffs that arise in this setting. Our techniques process as much of the data as possible in a decentralized fashion, so as to avoid unnecessary communication and computational effort.
Performance evaluation of the statistical aggregation by categorization in the SM3 system
Authors: Baru C. K , Su S. Y. W.
Published: November 2005

To perform a statistical aggregation operation over a large file often requires that the records of the file be divided into categories based on the values of the attribute(s) over which some statistical computation is to be performed. It is rather inefficient to perform the necessary data transfer, categorization and statistical computation using a single processor Parallel algorithms designed for multiprocessor systems have been proposed and their performance improvement over the conventional systems has been demonstrated. It is shown in this paper that three to four times performance improvement can be further gained by using a dynamically partitionable multicomputer system with switchable main memory modules (SM3).
Making smalltalk a database system
Authors: Copeland George , Maier David
Published: November 2005

To overcome limitations in the modeling power of existing database systems and provide a better tool for database application programming, Servio Logic Corporation is developing a computer system to support a set-theoretic data model in an object-oriented programming environment We recount the problems with existing models and database systems We then show how features of Smalltalk, such such as operational semantics, its type hierarchy, entity identity and the merging of programming and data language, solve many of those problems Nest we consider what Smalltalk lacks as a database system secondary storage management, a declarative semantics, concurrency, past states To address these shortcomings, we needed a formal data model We introduce the GemStone data model, and show how it helps to define path expressions, a declarative semantics and object history in the OPAL language We summarize similar approaches, and give a brief overview of the GemStone system implementation
Optimization of large join queries
Authors: Swami Arun , Gupta Anoop
Published: November 2005

We investigate the problem of optimizing Select—Project—Join queries with large numbers of joins. Taking advantage of commonly used heuristics, the problem is reduced to that of determining the optimal join order. This is a hard combinatorial optimization problem. Some general techniques, such as iterative improvement and simulated annealing, have often proved effective in attacking a wide variety of combinatorial optimization problems. In this paper, we apply these general algorithms to the large join query optimization problem. We use the statistical techniques of factorial experiments and analysis of variance (ANOVA) to obtain reliable values for the parameters of these algorithms and to compare these algorithms. One interesting result of our experiments is that the relatively simple iterative improvement proves to be better than all the other algorithms (included the more complex simulated annealing). We also find that the general algorithms do quite well at the maximum time limit.
Grammar-like functional rules for representing query optimization alternatives
Authors: Lohman Guy M.
Published: November 2005

Extensible query optimization requires that the “repertoire” of alternative strategies for executing queries be represented as data, not embedded in the optimizer code. Recognizing that query optimizers are essentially expert systems, several researchers have suggested using strategy rules to transform query execution plans into alternative or better plans. Though extremely flexible, these systems can be very inefficient at any step in the processing, many rules may be eligible for application and complicated conditions must be tested to determine that eligibility during unification. We present a constructive, “building blocks” approach to defining alternative plans, in which the rules defining alternatives are an extension of the productions of a grammar to resemble the definition of a function in mathematics. The extensions permit each token of the grammar to be parametrized and each of its alternative definitions to have a complex condition. The terminals of the grammar are base-level database operations on tables that are interpreted at run-time. The non-terminals are defined declaratively by production rules that combine those operations into meaningful plans for execution. Each production produces a set of alternative plans, each having a vector of properties, including the estimated cost of producing that plan. Productions can require certain properties of their inputs, such as tuple order and location, and we describe a “glue” mechanism for augmenting plans to achieve the required properties. We give detailed examples to illustrate the power and robustness of our rules and to contrast them with related ideas.
QUASAR
Authors: Lazaridis Iosif , Han Qi , Yu Xingbo , Mehrotra Sharad , Venkatasubramanian Nalini , Kalashnikov Dmitri V. , Yang Weiwen
Published: November 2005

Sensor devices are promising to revolutionize our interaction with the physical world by allowing continuous monitoring and reaction to natural and artificial processes at an unprecedented level of spatial and temporal resolution. As sensors become smaller, cheaper and more configurable, systems incorporating large numbers of them become feasible. Besides the technological aspects of sensor design, a critical factor enabling future sensor-driven applications will be the availability of an integrated infrastructure taking care of the onus of data management. Ideally, accessing sensor data should be no difficult or inconvenient than using simple SQL.In this paper we investigate some of the issues that such an infrastructure must address. Unlike conventional distributed database systems, a sensor data architecture must handle extremely high data generation rates from a large number of small autonomous components. And, unlike the emerging paradigm of data streams, it is infeasible to think that all this data can be streamed into the query processing site, due to severe bandwidth and energy constraints of battery-operated wireless sensors. Thus, sensing data architectures must become
quality-aware
, regulating the quality of data at all levels of the distributed system, and supporting user applications' quality requirements in the most efficient manner possible.
State-of-the-art in privacy preserving data mining
Authors: Verykios Vassilios S. , Bertino Elisa , Fovino Igor Nai , Provenza Loredana Parasiliti , Saygin Yucel , Theodoridis Yannis
Published: November 2005

We provide here an overview of the new and rapidly emerging research area of privacy preserving data mining. We also propose a classification hierarchy that sets the basis for analyzing the work which has been performed in this context. A detailed review of the work accomplished in this area is also given, along with the coordinates of each work to the classification hierarchy. A brief evaluation is performed, and some initial conclusions are made.
Simulation data as data streams
Authors: Abdulla Ghaleb , Critchlow Terence , Arrighi William
Published: November 2005

Computational or scientific simulations are increasingly being applied to solve a variety of scientific problems. Domains such as astrophysics, engineering, chemistry, biology, and environmental studies are benefiting from this important capability. Simulations, however, produce enormous amounts of data that need to be analyzed and understood. In this overview paper, we describe scientific simulation data, its characteristics, and the way scientists generate and use the data. We then compare and contrast simulation data to data streams. Finally, we describe our approach to analyzing simulation data, present the AQSim (Ad-hoc Queries for Simulation data) system, and discuss some of the challenges that result from handling this kind of data.
A multiprocessing system for the direct execution of LISP
Authors: Williams Rhon
Published: November 2005

Current implementations were found to be impractical for airborne use due to LISP's incompatability with conventional computer architectures. Direct execution of LISP with tasks distributed between three processors, seemed to be a workable solution. The language was analyzed, and a special token was devised, using a descriptor with a single pointer. Through careful distribution of responsibilities, control and data flow between the processors was minimized. Significant memory savings resulted from ASCII storage and real time garbage collection. A simulation was used to help estimate execution times and showed a factor of 50 to 100 increase in speed. Thus, through the direct execution of LISP by a multiprocessing system, Computer-Aided Decision-Making could be implimented to enhance the safety of flight operations.
An extensible architecture for data flow processing
Authors: Gavish Bezalel , Koch Harvey
Published: November 2005

In this research, we propose a general model for computer architectures. This model allows us to integrate some of the existing system architecture approaches for increasing computer capacity and indicates new possibilites for improving the cost/performance ratio of future computer systems. The model leads to the development of general purpose data flow machines and to different degrees of sophistication within these machines. Our fundamental approach is to separate the CPU into elementary components. This allows us to make a distinction between components for control and components for performing various processing functions, thus yielding a high degree of resource sharing.
Exploiting parallelism in a Relational Associative Processor
Authors: Sadowski Paul J. , Schuster S. A.
Published: November 2005

The Relational Associative Processor (RAP) is a special purpose non-numeric back-end processor used in supporting general Data Base Management Systems. In particular, it is ideally suited for supporting a relational data base. The architecture and instruction set of RAP are discussed in this context. It is the purpose of this paper to show that RAP performance can be enhanced considerably by more fully exploiting its parallel nature. It is shown that a greater degree of concurrent activity will result in better overall performance. An operating system executive to support this high level of concurrency is proposed and modelled using simulation techniques. Both the analytic and simulation results support the value of the proposals.
A distributed structure for the automization of the catalog of the national cultural heritage
Authors: Matteucci Dante R.
Published: November 2005

Efforts to automate the handling of information concerning the Catalog of the Italian cultural and artistic heritage have been made in the past by the Institute for the Catalog and Documentation (ICCD) of the Ministry of Cultural and Environmental Heritage.A feasibility study for the realization of a data base of the national cultural heritage has been conducted by CNUCE, the scientific computing center of the Italian National Research Council and ICCD. This study led to the determination of the caracteristics of data contained on the record cards, to the location of some samples areas, sufficiently representative of the Italian situation, for the setting up of a model of information system and to the implementation of a data bank on CNUCE computers using the IBM STAIRS information retrieval system.Following this study, a project is presently conducted by the two institutions, with the aim of setting up a distributed structure for the preparation, acquisition, access to and dissemination of the information concerning the Italian cultural and artistic heritage.This paper describes the functions of this proposed structure, with reference to the results of the first experiences and implementations.
Use of an inverted file structure for interactive retrieval of computer program abstracts
Authors: Buschman A. Camille
Published: November 2005

Standard Oil Company of California's Program Abstracts System will interactively search for, and list by title and mnemonic, all Company computer programs belonging to a particular category or technical application area in the filed of petroleum exploration and production. If one or more titles are of interest, the user can request a display of those abstracts. Retrieval is by search of an inverted index made up of a fixed set of terms covering application areas, programming languages, processing mode, and machine designations.
Errors in 'process synchronization in database systems'
Authors: Bernstein Philip A. , Casanova Marco A. , Goodman Nathan
Published: November 2005

This paper disproves several results pertaining to database concurrency control that are claimed in [8]. The results we disprove are•theorems 3.1, 3.2, 3.6 -- which claim a polynomial time algorithm for testing whether transaction schedules are serializable, and•theorems 4.2 and 4.7 -- which claim a necessary and sufficient mechanism for preserving the "weak consistency" of databases.In addition, we demonstrate that the notion of "weak consistency" introduced in [8] admits database states that are strictly inconsistent.
New proposal for a common command language in information systems
Authors: Auwera Yves Vander , Bernard Luc
Published: November 2005

A new command language based on the proposal by A. E. Negus is introduced for bibliographic data base searches. It is adapted to any bibliograpic database (universality), provides large and powerfull facilities. Finally it is simple to use and to analyse.
The optimal selection of secondary indices is NP-complete
Authors: Piatetsky-Shapiro Gregory
Published: November 2005

The problem of selecting secondary indices for a file so as to minimize the expected transaction cost was frequently analyzed before. We prove that it is NP-complete by reducing the MINIMUM SET COVER problem to it.