bluuebunny/crossref_metadata_2025 huggingface dataset:
Management guidelines for PC security
Authors: Anderson Troy E.
Published: November 2005

In the last several years, the number of personal computers (PCs) in offices worldwide has skyrocketed. In fact, some businesses now have PC bases in the thousands, a fact which makes company security officers' jobs a nightmare. Much of the existing literature addresses security in general, or security in large mainframe environments. The goal of this paper is to present potential security problems for stand-alone and networked PCs, and to offer guidelines to prevent or avoid these threats to PC security.
On seamless prototyping
Authors: Berghel Hal
Published: November 2005

With the advent of visual programming environments and visual programming languages, the face of software prototyping has changed forever. Modern software interfaces have a look-and-feel which was inconceivable to most practitioners just a decade ago, and this rapid advance has been fueled by imaginative research in human factors and computer graphics. However, we view this as a mixed blessing for (a) these advances have distracted researchers from more pressing, fundamental methodological concerns, and (b) the sophisticated interface technology encourages "facade" prototyping. Many modern prototypes are, s a result, shallow if not hollow and of little utility beyond what could be accomplished more easily and more inexpensively with presentation software.In this paper we encourage practitioners to consider more widespread use of a
seamless
prototyping strategy. Seamless prototyping is characterized by the closeness with which the prototype resembles the final product. We argue that this proximity may be achieved by extending the prototype development time and delaying its initiation and a continuous, gradual development process. While a seamless approach to prototyping will require more time and energy than less robust alternatives the reward follows from the fact that the prototype is faithful to the vision of the end result and that little development effort is wasted. We then illustrate seamless prototyping with examples from our own experience.
A foreign vocabulary learning aid for the networked world of tomorrow
Authors: Berleant Daniel , Lovelady Steven , Viswanathan Karthikeyan
Published: November 2005

Further increases in society's reliance on computing appear inevitable. An important role of computing will be in customizing textual information from the flood of available text to meet the unique needs of individuals. Information customization services will likely run on relatively powerful computers dedicated to individual users, as exemplified by work-stations.The LEARN project is a
C
omputer
A
ided
L
anguage
L
earning (CALL) system that serves (1) as a demonstration of an information customization service likely to run on the personal workstations of tomorrow's electronically networked world, and (2) as a pragmatically oriented foundation for research on semantically based word sense disambiguation.
How to modify SQL queries in order to guarantee sure answers
Authors: Klein H.-J.
Published: November 2005

Some problems connected with the handling of null values in SQL are discussed. A definition of sure answers to SQL queries is proposed which takes care of the “no information” meaning of null values in SQL. An algorithm is presented for modifying SQL queries such that answers are not changed for databases without null values but sure answers are obtained for arbitrary databases with standard SQL semantics.
A new join algorithm
Authors: Shin Dong Keun , Meltzer Arnold Charles
Published: November 2005

This paper introduces a new efficient join algorithm to increase the speed of the join relational operation. Using a divide and conquer strategy, stack oriented filter technique in the new join algorithm filters unwanted tuples as early as possible while none of the currently existing join algorithms takes advantage of any filtering concept. Other join algorithms may carry the unnecessary tuples up to the last moment of join attribute comparisons.Four join algorithms are described and discussed in this paper: the nested-loop join algorithm, the sort-merge join algorithm, the hash join algorithm, and the new join algorithm.
Metadata for mixed-media access
Authors: Chen Francine , Hearst Marti , Kupiec Julian , Pedersen Jan , Wilcox Lynn
Published: November 2005

In this paper, we discuss
mixed-media access
, an information access paradigm for multimedia data in which the media type of a query may differ from that of the data. The types of media considered in this paper are speech, images of text, and full-length text. Some examples of metadata for mixed-media access are locations of keywords in speech and images, identification of speakers, locations of emphasized regions in speech, and locations of topic boundaries in text. Algorithms for automatically generating this metadata are described, including word spotting, speaker segmentation, emphatic speech detection, and subtopic boundary location. We illustrate queries composed of diverse media types in an example of access to recorded meetings, via speaker and keyword location.
Grey system and grey relational model
Authors: Ng David K. W.
Published: November 2005

An introduction to grey system is presented. Modeling grey relation theory is also introduced. The nature of this article is expository and is intended for general readers.
A personal computer data flow research environment
Authors: Enright Aaron Garth , Wilkens Linda M.
Published: November 2005

Data flow computers have traditionally been limited to research centers with large budgets. In this article, we present the SAS (Simple Arithmetic SISAL) environment which provides a low cost data flow platform from which to teach and perform research. This environment simulates real hardware - the U. Lowell Data Flow Imaging Co-processor Board - which allows users to develop code for the simulator and then port it to an actual machine.
Two-level congestion control schemes for ATM networks
Authors: Wang Jin-Long , Lee Liang-Teh
Published: November 2005

In this paper, congestion control schemes are proposed to prevent the network from congestion for ATM (Asynchronous Transfer Mode) networks by controlling the congestion at VC (virtual circuit) and cell levels. At VC level, a bandwidth allocation scheme is performed during the call setup in the form of bandwidth reservation. Call acceptance is decided on the basis of on-line evaluation of traffic utilization. This scheme confines the bandwidth allocation according to the anticipated traffic characteristics and the quality requirements of connected calls. On the other hand, at cell level, an enforcement scheme is proposed to smooth the unexpected traffic from each source during the transmission period. This scheme only allows a cell to be dispatched at the begin of each slot time, thereby regulating cells entering the public network. In addition, several bandwidth enforcement mechanisms and bandwidth allocation methods are presented in order for comparison with the proposed schemes. It shows from the simulation that our schemes perform better than other methods.
Adaptive selectivity estimation using query feedback
Authors: Chen Chungmin Melvin , Roussopoulos Nick
Published: November 2005

In this paper, we propose a novel approach for estimating the record selectivities of database queries. The real attribute value distribution is adaptively approximated by a curve-fitting function using a query feedback mechanism. This approach has the advantage of requiring no extra database access overhead for gathering statistics and of being able to continuously adapt the value distribution through queries and updates. Experimental results show that the estimation accuracy of this approach is comparable to traditional methods based on statistics gathering.
Multi-step processing of spatial joins
Authors: Brinkhoff Thomas , Kriegel Hans-Peter , Schneider Ralf , Seeger Bernhard
Published: November 2005

Spatial joins are one of the most important operations for combining spatial objects of several relations. In this paper, spatial join processing is studied in detail for extended spatial objects in two-dimensional data space. We present an approach for spatial join processing that is based on three steps. First, a spatial join is performed on the minimum bounding rectangles of the objects returning a set of candidates. Various approaches for accelerating this step of join processing have been examined at the last year's conference [BKS 93a]. In this paper, we focus on the problem how to compute the answers from the set of candidate which is handled by the following two steps. First of all, sophisticated approximations are used to identify answers as well as to filter out false hits from the set of candidates. For this purpose, we investigate various types of conservative and progressive approximations. In the last step, the exact geometry of the remaining candidates has to be tested against the join predicate. The time required for computing spatial join predicates can essentially be reduced when objects are adequately organized in main memory. In our approach, objects are first decomposed into simple components which are exclusively organized by a main-memory resident spatial data structure. Overall, we present a complete approach of spatial join processing on complex spatial objects. The performance of the individual steps of our approach is evaluated with data sets from real cartographic applications. The results show that our approach reduces the total execution time of the spatial join by factors.
Predictive dynamic load balancing of parallel and distributed rule and query processing
Authors: Dewan Hasanat M. , Stolfo Salvatore J. , Hernández Mauricio , Hwang Jae-Jun
Published: November 2005

Expert Databases are environments that support the processing of rule programs against a disk resident database. They occupy a position intermediate between active and deductive databases, with respect to the level of abstraction of the underlying rule language. The operational semantics of the rule language influences the problem solving strategy, while the architecture of the processing environment determines efficiency and scalability.

In this paper, we present elements of the PARADISER architecture and its kernel rule language, PARULEL. The PARADISER environment provides support for parallel and distributed evaluation of rule programs, as well as static and dynamic load balancing protocols that predictively balance a computation at runtime. This combination of features results in a scalable database rule and complex query processing architecture. We validate our claims by analyzing the performance of the system for two realistic test cases. In particular, we show how the performance of a parallel implementation of transitive closure is significantly improved by predictive dynamic load balancing.
Outerjoins as disjunctions
Authors: Galindo-Legaria César A.
Published: November 2005

The outerjoin operator is currently available in the query language of several major DBMSs, and it is included in the proposed SQL2 standard draft. However, “associativity problems” of the operator have been pointed out since its introduction. In this paper we propose a shift in the intuition behind outerjoin: Instead of computing the join while also
preserving
its arguments, outerjoin delivers tuples that come
either
from the join
or
from the arguments. Queries with joins and outerjoins deliver tuples that come from one out of several joins, where a single relation is a trivial join. An advantage of this view is that, in contrast to preservation,
disjunction
is commutative and associative, which is a significant property for intuition, formalisms, and generation of execution plans.

Based on a disjunctive normal form, we show that some data merging queries cannot be evaluated by means of binary outerjoins, and give alternative procedures to evaluate those queries. We also explore several evaluation strategies for outerjoin queries, including the use of semijoin programs to reduce base relations.
Sequence query processing
Authors: Seshadri Praveen , Livny Miron , Ramakrishnan Raghu
Published: November 2005

Many applications require the ability to manipulate sequences of data. We motivate the importance of sequence query processing, and present a framework for the optimization of sequence queries based on several novel techniques. These include query transformations, optimizations that utilize meta-data, and caching of intermediate results. We present a bottom-up algorithm that generates an efficient query evaluation plan based on cost estimates. This work also identifies a number of directions in which future research can be directed.
A performance study of transitive closure algorithms
Authors: Dar Shaul , Ramakrishnan Raghu
Published: November 2005

We present a comprehensive performance evaluation of transitive closure (reachability) algorithms for databases. The study is based upon careful implementations of the algorithms, measures page I/O, and covers algorithms for full transitive closure as well as
partial
transitive closure (finding all successors of each node in a set of given source nodes). We examine a wide range of acyclic graphs with varying density and “locality” of arcs in the graph. We also consider query parameters such as the selectivity of the query, and system parameters such as the buffer size and the page and successor list replacement policies. We show that significant cost tradeoffs exist between the algorithms in this spectrum and identify the factors that influence the performance of the algorithms.

An important aspect of our work is that we measure a number of different cost metrics, giving us a good understanding of the predictive power of these metrics with respect to I/O cost. This is especially significant since metrics such as number of tuples generated or number of successor list operations have been widely used to compare transitive closure algorithms in the literature. Our results strongly suggest that these other metrics cannot be reliability used to predict I/O cost of transitive closure evaluation.
Contrasting grey system theory to probability and fuzzy
Authors: Ng David K. W. , Deng Julong
Published: November 2005

By contrasting grey system theory with probability theory, statistics, and fuzzy systems, we know the features that make the grey system different are:• reality law• grey hazy set (foundation)• small sample (data)• nonrequirement for distribution• Disregard of a priori-experience
Grey group relation and their general problems (I)
Authors: Li Xiaozhong , Shi Kaiquan
Published: November 2005

In this paper, we define grey set relation and grey group relation. Their general problems are studied. Some basic results are obtained.
The third manifesto
Authors: Darwen Hugh , Date C. J.
Published: November 2005

We present a manifesto for the future direction of data and database management systems. The manifesto consists of a series of prescriptions, proscriptions, and "very strong suggestions."
An aspect of query optimization in multidatabase systems
Authors: Lee Chiang , Chen Chia-Jung , Lu Hongjun
Published: November 2005

It is becoming increasingly important to manage databases as a repository resource and to allow application programs to access this resource in a heterogeneous distributed environment. Data requested by a query are sometimes available in multiple sites such that the query becomes executable in different ways. Under this circumstance, choosing the best execution plan becomes an important task for optimizing the query execution. Until today, however, query optimization in multidatabase systems has not been discussed much in the literature. In this work, we utilize the knowledge of
scope relationship
of relations in multidatabases to identify the sites that will return the same results. Then, we propose a novel way of optimizing queries which takes advantage of the conflicts of schemas in searching for the execution plan with the least execution cost. We achieve the goal by first classifying various schema conflicts into different types. The costs of executing the same relational operation on relations of conflicting schemas are evaluated and a weight is assigned to each of the cases to reflect the complexity of executing the operation. As this method only involves simple iterative computations of the weights and the saving of a query execution time can be dramatic, the method developed here can be regarded as an effective way of optimizing query processing in a multidatabase environment.
A framework for providing consistent and recoverable agent-based access to heterogeneous mobile databases
Authors: Pitoura Evaggelia , Bhargava Bharat
Published: November 2005

Information applications are increasingly required to be distributed among numerous remote sites through both wireless and wired links. Traditional models of distributed computing are inadequate to overcome the communication barrier this generates and to support the development of complex applications. In this paper, we advocate an approach based on agents. Agents are software modules that encapsulate data and code, cooperate to solve complicated tasks, and run at remote sites with minimum interaction with the user. We define an agent-based framework for accessing mobile heterogeneous databases. We then investigate concurrency control and recovery issues and outline possible solutions. Agent-based computing advances database transaction and control flow management concepts and remote programming techniques.
Turmoil at NASA, and numerous funding announcements
Authors: Qian Xiaolei
Published: November 2005

Since the last issue of this column six months ago, there have been many interesting program announcements, some of which have already passed deadline. We'll go over these announcements anyway, with the hope that they can get the readers better prepared for future funding opportunities. But first, we'll talk about the continuing budget battle at Congress, and the recent turmoil at NASA.
Report on the 1995 international workshop on temporal databases
Authors: Segev Arie , Jensen Christian S. , Snodgrass Richard Thomas
Published: November 2005

This paper provides an overview of the 1995 International Workshop on Temporal Databases. It summarizes the technical papers and related discussions, and three panels: “Wither TSQL3?”, “Temporal Data Management in Financial Applications,” and “Temporal Data Management Infrastructure & Beyond.”
Opportunities at ARPA, NSF, and elsewhere
Authors: Qian Xiaolei
Published: November 2005

We first report the relatively minor development on the federal budget. We then touch upon announcements from ARPA, NSF, Defense Nuclear Agency, Rome Laboratory, US Special Operations Command, and Office of National Drug Control Policy. We also report a recent ARPA reorganization.
The new middleware
Authors: Finkelstein Rich
Published: November 2005

USING MIDDLEWARE, CUSTOMERS CAN DEPLOY COST-EFFECTIVE AND HIGHLY FUNCTIONAL CLIENT/SERVER APPLICATIONS — ONCE THEY WORK OUT THE KINKS.
The inevitable demise of the Web
Authors: Berghel Hal
Published: November 2005

There is no doubt that the fastest growing part of the Internet is the World Wide Web. From its inception in 1990, the Web has established itself as the leading packet hauler on the Internet, passing beyond FTP, Telnet, WAIS Gopher and all of the other, more established Internet client protocols. The reason for this success is that the Web has established itself as the standard unifying environment for the Internet's digital riches.However, the days of the Web are numbered. The technology behind the Web is outdated already and may not survive the decade. The current growth rate, which some estimate at 15% per month, suggests that if the end of the Web is to come soon, it will likely be cataclysmal. If this seems unrealistic, consider that this fate befell Gopherspace. As Figure 1 shows, Gopher lead the Web in packet volume as late as March, 1994. In the following twelve months Gopher presence on the Internet all but disappeared. Life cycles are accelerated to frightening paces on the Internet.
Microsoft certification
Authors: Kwan Pak L.
Published: November 2005

The Microsoft Certified Professional program is the best way to prove your ability of mastering of current Microsoft products and technologies. Computer professionals who become Microsoft Certified are recognized as experts and are sought after industry.
The MS-DOS memory environment
Authors: Crow Jerry
Published: November 2005

When I first started experimenting with and using MS-DOS in 1986, I was confused by the various types of memory available with the then contemporary PCs: expanded, extended, enhanced expanded, etc. I found that I was frequently asked to explain the concepts associated with these terms and, frankly, could not do so. I decided to remedy that situation by researching the subject and acquiring sufficient knowledge to permit me to understand what was happening from a hardware and software standpoint vis a vis the MS-DOS memory environment. When I had accomplished that task, I wrote an article for the Phoenix PC Users Group Newsletter documenting my new found knowledge. The original article was published in 1989.
How source code can help you
Authors: Leisner Marty
Published: November 2005

The last twenty years in computers have seen enormous changes. The increases in processor speed and disk capacity, the advent of window systems, and the decrease of cost is often discussed. What is overlooked is the fact there is now quality freeware you can use on a daily basis to use computers in business. Most "free software" is often described as public domain, and dismissed as games. Or people who write free freeware are dismissed as amateurs, who can't find jobs as real programmers. This is less true than ever. The quality of freeware has grown tremendously over the last twenty years in quantity and quality. The following describes most of the common arrangement available:
PC note
Authors: Styer Eugene
Published: November 2005

In this fourth installment in the series, we will start looking at instructions that the 80x86 can execute. Each member of the 80x86 family had added new instructions, and sometimes changed the behaviour of current instructions. The 8086 will be discussed here. The additions and changes implemented in the 286, 386, 486, and Pentium will be discussed next time.
Guidelines for presentation and comparison of indexing techniques
Authors: Zobel Justin , Moffat Alistair , Ramamohanarao Kotagiri
Published: November 2005

Descriptions of new indexing techniques are a common outcome of database research, but these descriptions are sometimes marred by poor methodology and a lack of comparison to other schemes. In this paper we describe a framework for presentation and comparison of indexing schemes that we believe sets a minimum standard for development and dissemination of research results in this area.
Much ado about shared-nothing
Authors: Norman Michael G. , Zurek Thomas , Thanisch Peter
Published: November 2005

In a 'shared-nothing' parallel computer, each processor has its own memory and disks and processors communicate by passing messages through an interconnect. Many academic researchers, and some vendors, assert that shared-nothingness is the 'consensus' architecture for parallel DBMSs. This alleged consensus is used as a justification for simulation models, algorithms, research prototypes and even marketing campaigns.

We argue that shared-nothingness is no longer the consensus hardware architecture and that hardware resource sharing is a poor basis for categorising parallel DBMS software architectures if one wishes to compare the performance characteristics of parallel DBMS products.
Middle East Technical University Software Research and Development Center
Authors: Dogac Asuman
Published: November 2005

Middle East Technical University (METU) is the leading technical university in Turkey. The Software Research and Development Center was established by the Scientific and Technical Research Council of Turkey (TUBITAK) at the Department of Computer Engineering of METU in October 1991. The aim of this center is twofold: to lead large scale software research and development projects, and to foster international cooperation. SRDC is involved in a number of research and development projects supported by the government, industrial companies and international organizations. Although SRDC projects also cover other fields of computer science, the main emphasis is on database systems.

SRDC is organized around the ongoing projects and several engineers and graduate students work in these projects: M. Altinel, B. Arpinar, I. Cingil, Y. Ceken, C. Dengi, E. Gokkoca, C. Evrendilek, P. Karagoz, E. Kilic, P. Koksal, S. Mancuhan, S. Nural, F. Ozcan, G. Ozhan, V. Sadjadi, N. Tatbul. Its infrastructure includes a LAN with Sun Workstations and PCs and commercial software like Oracle7, Sybase, Informix, Adabas D, Ingres and DEC's ObjectBroker. SRDC is a beta test site for several products including SunSoft's Joe and Concerto and Orbix's Object Transaction Service. The remainder of this report describes the main projects.
UniSQL's next-generation object-relational database management system
Authors: D'Andrea Albert , Janus Phil
Published: November 2005

Object-Relational DBMSs have been receiving a great deal of attention from industry analysts and press as the
next generation
of database management systems. The motivation for a next generation DBMS is driven by the reality of shortened business cycles. This dynamic environment demands fast, cost-effective, time-to-market of new or modified business processes, services, and products. To support this important business need, the next generation DBMS must: 1. leverage the large investments made in existing relational technology, both in data and skill set; 2. Take advantage of the flexibility, productivity, and performance benefits of OO modeling; and 3. Integrate robust DBMS services for production quality systems. The objective of this article is to provide a brief overview of UniSQL's commercial object-relational database management system.
Optimizing queries over multimedia repositories
Authors: Chaudhuri Surajit , Gravano Luis
Published: November 2005

Repositories of multimedia objects having multiple types of attributes (e.g., image, text) are becoming increasingly common. A selection on these attributes will typically produce not just a set of objects, as in the traditional relational query model (
filtering
), but also a
grade of match
associated with each object, indicating how well the object matches the selection condition (
ranking
). Also, multimedia repositories may allow access to the attributes of each object only through indexes. We investigate how to optimize the processing of queries over multimedia repositories. A key issue is the choice of the indexes used to search the repository. We define an execution space that is
search-minimal,
i.e., the set of indexes searched is minimal. Although the general problem of picking an optimal plan in the search-minimal execution space is NP-hard, we solve the problem efficiently when the predicates in the query are independent. We also show that the problem of optimizing queries that ask for a few top-ranked objects can be viewed, in many cases, as that of evaluating selection conditions. Thus, both problems can be viewed together as an extended filtering problem.
BIRCH
Authors: Zhang Tian , Ramakrishnan Raghu , Livny Miron
Published: November 2005

Finding useful patterns in large datasets has attracted considerable interest recently, and one of the most widely studied problems in this area is the identification of
clusters,
or densely populated regions, in a multi-dimensional dataset. Prior work does not adequately address the problem of large datasets and minimization of I/O costs.This paper presents a data clustering method named
BIRCH
(Balanced Iterative Reducing and Clustering using Hierarchies), and demonstrates that it is especially suitable for very large databases.
BIRCH
incrementally and dynamically clusters incoming multi-dimensional metric data points to try to produce the best quality clustering with the available resources (i.e., available memory and time constraints).
BIRCH
can typically find a good clustering with a single scan of the data, and improve the quality further with a few additional scans.
BIRCH
is also the first clustering algorithm proposed in the database area to handle "noise" (data points that are not part of the underlying pattern) effectively.We evaluate
BIRCH
's time/space efficiency, data input order sensitivity, and clustering quality through several experiments. We also present a performance comparisons of
BIRCH
versus
CLARANS,
a clustering method proposed recently for large datasets, and show that
BIRCH
is consistently superior.
Random I/O scheduling in online tertiary storage systems
Authors: Hillyer Bruce K. , Silberschatz Avi
Published: November 2005

New database applications that require the storage and retrieval of many terabytes of data are reaching the limits for disk-based storage systems, in terms of both cost and scalability. These limits provide a strong incentive for the development of databases that augment disk storage with technologies better suited to large volumes of data. In particular, the seamless incorporation of tape storage into database systems would be of great value. Tape storage is two orders of magnitude more efficient than disk in terms of cost per terabyte and physical volume per terabyte; however, a key problem is that the random access latency of tape is three to four orders of magnitude slower than disk. Thus, to incorporate a tape bulk store in an online storage system, the problem of tape access latency must be solved. One approach to reducing the latency is careful I/O scheduling. The focus of this paper is on efficient random I/O scheduling for tape drives that use a serpentine track layout, such as the Quantum DLT and the IBM 3480 and 3590. For serpentine tape, I/O scheduling is problematic because of the complex relationships between logical block numbers, their physical positions on tape, and the time required for tape positioning between these physical positions. The results in this paper show that our scheduling schemes provide a significant improvement in the latency of random access to serpentine tape.
Implementing data cubes efficiently
Authors: Harinarayan Venky , Rajaraman Anand , Ullman Jeffrey D.
Published: November 2005

Decision support applications involve complex queries on very large databases. Since response times should be small, query optimization is critical. Users typically view the data as multidimensional data cubes. Each cell of the data cube is a view consisting of an aggregation of interest, like total sales. The values of many of these cells are dependent on the values of other cells in the data cube. A common and powerful query optimization technique is to materialize some or all of these cells rather than compute them from raw data each time. Commercial systems differ mainly in their approach to materializing the data cube. In this paper, we investigate the issue of which cells (views) to materialize when it is too expensive to materialize all views. A lattice framework is used to express dependencies among views. We present greedy algorithms that work off this lattice and determine a good set of views to materialize. The greedy algorithm performs within a small constant factor of optimal under a variety of models. We then consider the most common case of the hypercube lattice and examine the choice of materialized views for hypercubes in detail, giving some good tradeoffs between the space used and the average time to answer a query.
Partition based spatial-merge join
Authors: Patel Jignesh M. , DeWitt David J.
Published: November 2005

This paper describes PBSM (Partition Based Spatial-Merge), a new algorithm for performing spatial join operation. This algorithm is especially effective when neither of the inputs to the join have an index on the joining attribute. Such a situation could arise if both inputs to the join are intermediate results in a complex query, or in a parallel environment where the inputs must be dynamically redistributed. The PBSM algorithm partitions the inputs into manageable chunks, and joins them using a computational geometry based plane-sweeping technique. This paper also presents a performance study comparing the the traditional indexed nested loops join algorithm, a spatial join algorithm based on joining spatial indices, and the PBSM algorithm. These comparisons are based on complete implementations of these algorithms in Paradise, a database system for handling GIS applications. Using real data sets, the performance study examines the behavior of these spatial join algorithms in a variety of situations, including the cases when both, one, or none of the inputs to the join have an suitable index. The study also examines the effect of clustering the join inputs on the performance of these join algorithms. The performance comparisons demonstrates the feasibility, and applicability of the PBSM join algorithm.
Estimating alphanumeric selectivity in the presence of wildcards
Authors: Krishnan P. , Vitter Jeffrey Scott , Iyer Bala
Published: November 2005

Success of commercial query optimizers and database management systems (object-oriented or relational) depend on accurate cost estimation of various query reordering [BGI]. Estimating predicate selectivity, or the fraction of rows in a database that satisfy a selection predicate, is key to determining the optimal join order. Previous work has concentrated on estimating selectivity for numeric fields [ASW, HaSa, IoP, LNS, SAC, WVT]. With the popularity of textual data being stored in databases, it has become important to estimate selectivity accurately for alphanumeric fields. A particularly problematic predicate used against alphanumeric fields is the SQL
like
predicate [Dat]. Techniques used for estimating numeric selectivity are not suited for estimating alphanumeric selectivity.In this paper, we study for the first time the problem of estimating alphanumeric selectivity in the presence of wildcards. Based on the intuition that the model built by a data compressor on an input text encapsulates information about common substrings in the text, we develop a technique based on the suffix tree data structure to estimate alphanumeric selectivity. In a statistics generation pass over the database, we construct a compact suffix tree-based structure from the columns of the database. We then look at three families of methods that utilize this structure to estimate selectivity during query plan costing, when a query with predicates on alphanumeric attributes contains wildcards in the predicate.We evaluate our methods empirically in the context of the TPC-D benchmark. We study our methods experimentally against a variety of query patterns and identify five techniques that hold promise.
Change detection in hierarchically structured information
Authors: Chawathe Sudarshan S. , Rajaraman Anand , Garcia-Molina Hector , Widom Jennifer
Published: November 2005

Detecting and representing changes to data is important for active databases, data warehousing, view maintenance, and version and configuration management. Most previous work in change management has dealt with flat-file and relational data; we focus on hierarchically structured data. Since in many cases changes must be computed from old and new versions of the data, we define the hierarchical change detection problem as the problem of finding a "minimum-cost edit script" that transforms one data tree to another, and we present efficient algorithms for computing such an edit script. Our algorithms make use of some key domain characteristics to achieve substantially better performance than previous, general-purpose algorithms. We study the performance of our algorithms both analytically and empirically, and we describe the application of our techniques to hierarchically structured documents.
Comments on data analysis in software experiments
Authors: Chen Yeh-Ling , Stromberg Arnold J.
Published: November 2005

Software development, like other scientific developments, requires formal experiments with a great deal of plan and analysis if they are to provide meaningful results[11]. This paper uses examples to extend the discussion to a certain statistical analysis, the prediction confidence interval, which have been pointed out but never been fully discussed. The purpose of this paper is to provide a better understanding of a statistical analysis for software experimenters when the experimental data is not as nice as expected.
Security considerations for active messages
Authors: McBride R. A.
Published: November 2005

Messages are generally regarded as passive since they merely act as a conveyance for information. An active message triggers processing activities at each of its recipients. A discussion is provided on the different classes of processing activities that can occur for active messages. A mechanism for ensuring the security of an active message and its associated processing operations is also outlined.
PC note
Authors: Styer Eugene
Published: November 2005

In this seventh installment in the series we now look at the 8087 numeric coprocessor.
A response to R. Camps' article “Domains, relations and religious wars”
Authors: Date C. J.
Published: November 2005

Since it quotes extensively from writings of my own, I feel obliged to respond to the article “Domains, Relations and Religious Wars,” by R. Camps (
SIGMOD Record 25
, No. 3, September 1996). In that article, Camps is clearly suggesting (among other things) that my definition of the term “domain” has changed over the years. I agree, it has! But Camps goes on to say: “… considering that [Date's book
An Introduction to Database Systems
] was the
bible
[Camps' italics] where most university graduates all over the world learnt, I believe that Date can be held partly responsible for the lack of implementation of domains [in today's SQL DBMSs].”
The aggregate data problem
Authors: Rafanelli M. , Bezenchek A. , Tininini L.
Published: November 2005

In this paper we describe the fundamental components of a database management system for the definition, storage, manipulation and query of aggregate data, i.e. data which are obtained by applying statistical aggregations and statistical analysis functions over raw data. In particular, the attention has been focused on: (1) a data structure for the efficient storage and manipulation of aggregate data, called ADaS; (2) the graphical structures of the aggregate data model ADAMO for a more user-friendly definition and query of aggregate data; (3) a graphical user interface which enables a straightforward specification of the ADAMO structures; (4) a textual declarative query language to retrieve data from the aggregate database, called ADQUEL.
Spotfire
Authors: Ahlberg Christopher
Published: November 2005

In this paper we examine the issues involved in developing information visualisation systems and present a framework for their construction. The framework addresses the components which must be considered in providing effective visualisations. The framework is specified using a declarative object oriented language; the resulting object model may be mapped to a variety of graphical user interface development platforms. This provides general support to developers of visualisation systems. A prototype system exists which allows the investigation of alternative visualisations for a range of data sources.
To table or not to table
Authors: Santucci Giuseppe , Tarantino Laura
Published: November 2005

Suitable data set organizers are necessary to help users assimilating information retrieved from a database. In this paper we present (1) a general hypertextual framework for the interaction with tables, and (2) a specialization of the framework in order to present in hypertextual format the results of queries expressed in terms of a visual semantic query language.
Applying database visualization to the World Wide Web
Authors: Hasan Masum Z. , Mendelzon Alberto O. , Vista Dimitra
Published: November 2005

In this paper, we present visualizations of parts of the network of documents comprising the World Wide Web. We describe how we are using the Hy
+
visualization system to visualize the portion of the World Wide Web explored during a browsing session. As the user browses, the web browser communicates the URL and title of each document fetched as well as all the anchors contained in the document. Hy
+
displays graphically the history of the navigation and multiple views of the structure of that portion of the web.
3D geographic network displays
Authors: Cox Kenneth C. , Eick Stephen G. , He Taosong
Published: November 2005

Many types of information may be represented as graphs or networks with the nodes corresponding to entities and the links to relationships between entities. Often there is geographical information associated with the network. The traditional way to visualize geographical networks employs node and link displays on a two-dimensional map. These displays are easily overwhelmed, and for large networks become visually cluttered and confusing. To overcome these problems we have invented five novel network views that generalize the traditional displays. Two of the views show the complete network, while the other three concentrate on a portion of a larger network defined by connectivity to a given node. Our new visual metaphors retain many of the well-known advantages of the traditional network maps, while exploiting three-dimensional graphics to address some of the fundamental problems limiting the scalability of two-dimensional displays.
An orthogonally persistent Java
Authors: Atkinson M. P. , Daynès L. , Jordan M. J. , Printezis T. , Spence S.
Published: November 2005

The language Java is enjoying a rapid rise in popularity as an application programming language. For many applications an effective provision of database facilities is required. Here we report on a particular approach to providing such facilities, called “orthogonal persistence”. Persistence allows data to have lifetimes that vary from transient to (the best approximation we can achieve to) indefinite. It is orthogonal persistence if the available lifetimes are the same for all kinds of data. We aim to show that the programmer productivity gains and possible performance gains make orthogonal persistence a valuable augmentation of Java.
The effect of join selectives on optimal nesting order
Authors: Kumar Akhil , Stonebraker Michael
Published: November 2005

A heuristic query optimizer must choose the best way to process an incoming query. This choice is based on comparing the expected cost of many (or all) of the ways that a command might be processed. This expected cost calculation is determined by statistics on the sizes of the relations involved and the selectivities of the operations being performed. Of course, such estimates are subject to error, and in this paper we investigate the sensitivity of the best query plan to errors in the selectivity estimates. We treat the common case of join queries and show that the optimal plan for most queries is very insensitive to selectivity inaccuracies. Hence, there is little reason for a data manager to spend a lot of effort making accurate estimates of join selectivities.
Improving access to environmental data using context information
Authors: Tomasic Anthony , Simon Eric
Published: November 2005

A very large number of data sources on environment, energy, and natural resources are available worldwide. Unfortunately, users usually face several problems when they want to search and use environmental information. In this paper, we analyze these problems. We describe a conceptual analysis of the four major tasks in the production of environmental data, from the technology point of view, and describe the organization of the data that results from these tasks. We then discuss the notion of metainformation and outline an architecture for environmental data systems that formally models metadata and addresses some of the major problems faced by users.
Extraction of object-oriented structures from existing relational databases
Authors: Ramanathan Shekar , Hodges Julia
Published: November 2005

Due to the wide use of object-oriented technology in software development and the existence of many relational databases, reverse engineering of relational schemas to object-oriented schemas is gaining in interest. One of the major problems with existing approaches for this schema mapping is that they fail to take into consideration many modern relational database design alternatives (e.g., use of binary data to store multiple-valued attributes). This paper presents a schema mapping procedure that can be applied on existing relational databases without changing their schema. The procedure maps a relational schema that is at least in 2NF into an object-oriented schema by taking into consideration various types of relational database design optimizations.
An overview of data warehousing and OLAP technology
Authors: Chaudhuri Surajit , Dayal Umeshwar
Published: November 2005

Data warehousing and on-line analytical processing (OLAP) are essential elements of decision support, which has increasingly become a focus of the database industry. Many commercial products and services are now available, and all of the principal database management system vendors now have offerings in these areas. Decision support places some rather different requirements on database technology compared to traditional on-line transaction processing applications. This paper provides an overview of data warehousing and OLAP technologies, with an emphasis on their new requirements. We describe back end tools for extracting, cleaning and loading data into a data warehouse; multidimensional data models typical of OLAP; front end client tools for querying and data analysis; server extensions for efficient query processing; and tools for metadata management and for managing the warehouse. In addition to surveying the state of the art, this paper also identifies some promising research issues, some of which are related to problems that the database research community has worked on for years, but others are only just beginning to be addressed. This overview is based on a tutorial that the authors presented at the VLDB Conference, 1996.
Fast parallel similarity search in multimedia databases
Authors: Berchtold Stefan , Böhm Christian , Braunmüller Bernhard , Keim Daniel A. , Kriegel Hans-Peter
Published: November 2005

Most similarity search techniques map the data objects into some high-dimensional feature space. The similarity search then corresponds to a nearest-neighbor search in the feature space which is computationally very intensive. In this paper, we present a new parallel method for fast nearest-neighbor search in high-dimensional feature spaces. The core problem of designing a parallel nearest-neighbor algorithm is to find an adequate distribution of the data onto the disks. Unfortunately, the known declustering methods to not perform well for high-dimensional nearest-neighbor search. In contrast, our method has been optimized based on the special properties of high-dimensional spaces and therefore provides a near-optimal distribution of the data items among the disks. The basic idea of our data declustering technique is to assign the buckets corresponding to different quadrants of the data space to different disks. We show that our technique - in contrast to other declustering methods - guarantees that all buckets corresponding to neighboring quadrants are assigned to different disks. We evaluate our method using large amounts of real data (up to 40 MBytes) and compare it with the best known data declustering method, the Hilbert curve. Our experiments show that our method provides an almost linear speed-up and a constant scale-up. Additionally, it outperforms the Hilbert approach by a factor of up to 5.