waashk/acm huggingface dataset:
analysis of object oriented spatial access methods  this paper provides an analysis of r-trees and a variation (r+-trees) that avoids overlapping rectangles in intermediate nodes of the tree. the main contributions of the paper are the following. we provide the first known analysis of r-trees. although formulas are given for objects in one dimension (line segments), they can be generalized for objects in higher dimensions as well. we show how the transformation of objects to higher dimensions [hinr83] can be effectively used as a tool for the analysis of r- and r+\\- trees. finally, we derive formulas for r+-trees and compare the two methods analytically. the results we obtained show that r+-trees require less than half the disk accesses required by a corresponding r-tree when searching files of real life sizes r+-trees are clearly superior in cases where there are few long segments and a lot of small ones.  christos faloutsos timos sellis nick roussopoulos
asynchronous information space analysis architecture using content and structure-based service brokering  our project focuses on rapid formation and utilization of custom collections of information for groups focused on high-paced tasks. assembling such collections, as well as organizing and analyzing the documents within them, is a complex and sophisticated task. it requires understanding what information management services and tools are provided by the system, when they appropriate to use, and how those services can be composed together to perform more complex analyses. this paper describes the architecture of a prototype implementation of the information analysis management system that we have developed. the architecture uses metadata to describe collections of documents both in term of their content and structure. this metadata allows the system to dynamically and in a content-sensitive manner to determine the set of appropriate analysis services. to facilitate the invocation of those services, the architecture also provides an asynchronous and transparent service access mechanism.  ke-thia yao in-young ko ragy eleish robert neches
research issues in active database systems: report from the closing panel at ride-ads '94  the discussions during the panel stayed largely but not entirely focused on the question of active database research issues from the application perspective. there were nine panelists. each panelist was asked to prepare brief answers to a set of questions. the sets of answers were discussed by all participants, and finally a number of more general issues were discussed.  the questions asked of the panelists were:  name an application that will certainly be supported by active database systems in the not-too-distant future.  name an application that will certainly not be supported by active database systems in the near future.  name an area of active database systems in which you are not working but that is crucial to meet the needs of applications.  name an area of active database systems that is not on the critical path to supporting applications.  name an area of active database systems that should have been discussed in the course of the workshop but was not.  jennifer widom
hodfa: an architectural framework for homogenizing heterogeneous legacy databases  one of the main difficulties in supporting global applications over a number of localized databases and migrating legacy information systems to modern computing environment is to cope with the heterogeneities of these systems. in this paper, we present a novel flexible architecture (called hodfa) to dynamically connect such localized heterogeneous databases in forming a homogenized federated database system and to support the process of transforming a collection of heterogeneous information systems onto a homogeneous environment. we further develop an incremental methodology of homogenization in the context of our hodfa framework, which can facilitate different degrees of homogenization in a stepwise manner, so that existing applications will not be affected during the process of homogenization.  kamalakar karlapalem qing li chung-dak shum
a data model and data structures for moving objects databases  we consider spatio-temporal databases supporting spatial objects with continuously changing position and extent, termed _moving objects databases_. we formally define a data model for such databases that includes complex evolving spatial structures such as line networks or multi- component regions with holes. the data model is given as a collection of data types and operations which can be plugged as attribute types into any dbms data model (e.g. relational, or object-oriented) to obtain a complete model and query language. a particular novel concept is the _sliced representation_ which represents a temporal development as a set of _units_, where unit types for spatial and other data types represent certain "simple" functions of time. we also show how the model can be mapped into concrete physical data structures in a dbms environment.  luca forlizzi ralf hartmut guting enrico nardelli markus schneider
adaptive multi-stage distance join processing  a spatial distance join is a relatively new type of operation introduced for spatial and multimedia database applications. additional requirements for ranking and stopping cardinality are often combined with the spatial distance join in on-line query processing or internet search environments. these requirements pose new challenges as well as opportunities for more efficient processing of spatial distance join queries. in this paper, we first present an efficient _k_-distance join algorithm that uses spatial indexes such as r-trees. bi-directional node expansion and plane-sweeping techniques are used for fast pruning of distant pairs, and the plane-sweeping is further optimized by novel strategies for selecting a sweeping axis and direction. furthermore, we propose adaptive multi-stage algorithms for _k_-distance join and incremental distance join operations. our performance study shows that the proposed adaptive multi-stage algorithms outperform previous work by up to an order of magnitude for both _k_-distance join and incremental distance join queries, under various operational conditions.  hyoseop shin bongki moon sukho lee
freedom from deadlock of locked transactions in a distributed database  we examine the problem of determining whether a given set of locked transactions, accessing a distributed database, is free from deadlock. a deadlock graph is used to derive a new characterization for deadlock-free two- transaction systems in a distributed environment. the characterization provides a direct and efficient polynomial test for deadlock-freedom in two- transaction systems. the method is not dependent on the number of sites in a distributed database, and hence improves previously known results, which are exponential in the number of sites.  henry tirri
snowball: extracting relations from large plain- text collections  text documents often contain valuable structured data that is hidden yin regular english sentences. this data is best exploited infavailable as arelational table that we could use for answering precise queries or running data mining tasks.we explore a technique for extracting such tables from document collections that requires only a handful of training examples from users. these examples are used to generate extraction patterns, that in turn result in new tuples being extracted from the document collection.we build on this idea and present our snowball system. snowball introduces novel strategies for generating patterns and extracting tuples from plain-text documents.at each iteration of the extraction process, snowball evaluates the quality of these patterns and tuples without human intervention,and keeps only the most reliable ones for the next iteration. in this paper we also develop a scalable evaluation methodology and metrics for our task, and present a thorough experimental evaluation of snowball and comparable techniques over a collection of more than 300,000 newspaper documents.  eugene agichtein luis gravano
supporting valid-time indeterminacy  in valid-time indeterminacy it is known that an event stored in a database did in fact occur, but it is not known exactly when. in this paper we extend the sql data model and query language to support valid-time indeterminacy. we represent the occurrence time of an event with a set of possible instants, delimiting when the event might have occurred, and a probability distribution over that set. we also describe query language constructs to retrieve information in the presence of indeterminacy. these constructs enable users to specify their credibility in the underlying data and their plausibility in the relationships among that data. a denotational semantics for sql's select statement with optional credibility and plausibility constructs is given. we show that this semantics is reliable, in that it never produces incorrect information, is maximal, in that if it were extended to be more informative, the results may not be reliable, and reduces to the previous semantics when there is no indeterminacy. although the extended data model and query language provide needed modeling capabilities, these extensions appear initially to carry a significant execution cost. a contribution of this paper is to demonstrate that our approach is useful and practical. an efficient representation of valid-time indeterminacy and efficient query processing algorithms are provided. the cost of support for indeterminacy is empirically measured, and is shown to be modest. finally, we show that the approach is general, by applying it to the temporal query language constructs being proposed for sql3.  curtis e. dyreson richard t. snodgrass
office automation and the changing definition of the workplace  the introduction of telecommunications and computer technology into the workplace has profound implications for the nature of work itself. in particular, the implementation of "office automation" permits significant changes in the organization and execution of office work. it is possible that the term "office" may take on new meanings. office automation provides the potential to alter the locational and temporal definitions of large numbers of office jobs.  this discussion focuses on the phenomenon of "remote office work", which is facilitated by developments in telecommunications and computer technology. the general position is that technology can support either positive or negative implementations of remote office work; social and economic forces, as well as policy, provide the impetus for change in one direction or the other. this discussion emphasizes one particular form of remote work, that is, work at home. the reason for this emphasis is that work at home serves as an excellent example of the wide range of potential implications of remote work.  margrethe h. olson
tip: a temporal extension to informix  commercial relational database systems today provide only limited temporal support. to address the needs of applications requiring rich temporal data and queries, we have built tip (t_emporal_ i_nformation_ p_rocessor_), a temporal extension to the informix database system based on its datablade technology. our tip datablade extends informix with a rich set of datatypes and routines that facilitate temporal modeling and querying. tip provides both c and java libraries for client applications to access a tip-enabled database, and provides end-users with a gui interface for querying and browsing temporal data.  jun yang huacheng c. ying jennifer widom
on computing functions with uncertainty  we study the problem of computing a function _f_(_x_ 1,…, _xn_) given that the actual values of the variables _xi_'s are known only with some uncertainty. for each variable _xi_, an interval _ii_ is known such that the value of _xi_ is guaranteed to fall within this interval. any such interval can be probed to obtain the actual value of the underlying variable; however, there is a cost associated with each such probe. the goal is to adaptively identify a minimum cost sequence of probes such that regardless of the actual values taken by the unprobed _xi_'s, the value of the function _f_ can be computed to within a specified precision.  we design online algorithms for this problem when _f_ is either the selection function or an aggregation function such as sum or average. we consider three natural models of precision and give algorithms for each model. we analyze our algorithms in the framework of competitive analysis and show that our algorithms are asymptotically optimal. finally, we also study online algorithms for functions that are obtained by composing together selection and aggregation functions.  sanjeev khanna wang-chiew tan
facilitating the exploration of interface design alternatives: the humanoid model of interface design  humanoid is a user interface design tool that lets designers express abstract conceptualizations of an interface in an executable form, allowing designers to experiment with scenarios and dialogues even before the application model is completely worked out. three properties of the humanoid approach allow it to do so: a modularization of design issues into independent dimensions, support for multiple levels of specificity in mapping application models to user interface constructs, and mechanisms for constructing executable default user interface implementations from whatever level of specificity has been provided by the designer.  pedro szekely ping luo robert neches
constraint checking with partial information  constraints are a valuable tool for managing information across multiple databases, as well as for general purposes of assuring data integrity. however, efficient implementation of constraint checking is difficult. in this paper we explore techniques for assuring constraint satisfaction without performing a complete evaluation of the constraints. we consider methods that use only constraint definitions, methods that use constraints and updates, and methods that use constraints, updates, and "local" data.  ashish gupta yehoshua sagiv jeffrey d. ullman jennifer widom
tools for supporting cooperative work near and far: highlights from the cscw conference  the second conference on computer supported cooperative work has provided focus on use of computers for supporting workers that are at various levels of geographic dispersion. the participants in this panel reported case studies at that conference on group work (1) in face-to-face meetings, (2) in the same building, and (3) distributed across a number of sites. each panelist therefore brings insight about the communication needs of their research subjects and both the value and limitations of particular technologies for supporting the communication that ties the members of the groups together as geographic distance varies.  each of the panelists will address the following two questions:  what are the preferred types of communication (visual, written, spoken) for people working together at particular geographic distances?  what are the benefits and shortcomings of available technologies (video, electronic-mail, telephone/voice mail) for supporting these types of communication?  s. f. ehrlich t. bikson w. mackay j. c. tang
a formal view integration method  the design of an appropriate conceptual database scheme is one of the most difficult tasks in usual database applications. especially, the design of a common global database scheme for many different user groups requires a great amount of effort and skill, because the desired scheme should fit a great variety of requirements and expectations. here, view integration is a natural method that should help to manage the complexity of such a design problem. for each user group the requirements and expectations are separately collected and specified as views, that are subsequently integrated into a global scheme supporting all those different views.  in this paper, we carefully develop a formal model, clarifying many notions and concepts, related to the view integration method. this formal model serves as a theoretical basis of our integration approach that uses equivalence preserving, local scheme transformations as the main integration operations.  joachim biskup bernhard convent
global applications of collaborative technology: introduction collaborative technologies, sometimes referred to as "groupware applications" given their deployment to support groups of individuals engaging in collaborative tasks, have developed rapidly in the last few years. much of this expansion has been fueled by the dramatic increases in internet penetration in societies around the world, making it possible for globally distributed teams to work on projects. we see these technologies being applied in a variety of ways, ranging from organizational communication and decision making to distributed software inspections and development to virtual education initiatives. the systems themselves include an array of technologies that may include video- and audioconferencing, shared calendaring, (digital) document management systems, text-based group support systems, and many more. robert davison gert- jan de vreede
vodak open nested transactions - visualizing database internals  vodak is a prototype of an object-oriented, distributed database system developed during the past five years at the integrated publication and information systems institute (ipsi). the aim of demonstrating vodak open nested transactions is to provide insights into internals of database systems that are usually hidden from application programmers and users. by utilizing semantics of methods, vodak open nested transactions increase the degree of parallelism between concurrent transactions compared to conventional transaction management schemes. demonstrating the difference in parallelism provides users with a "feeling" for internal database mechanisms, application programmers with information about the impact of transaction management on performance, and system developers with ideas how to improve their systems with respect to transaction management.  peter muth thomas c. rakow
surrogate subsets: a free space management strategy for the index of a text retrieval system  this paper presents a new data structure and an associated strategy to be utilized by indexing facilities for text retrieval systems. the paper starts by reviewing some of the goals that may be considered when designing such an index and continues with a small survey of various current strategies. it then presents an indexing strategy referred to as surrogate subsets discussing its appropriateness in the light of the specified goals. various design issues and implementation details are discussed. our strategy requires that a surrogate file be divided into a large number of subsets separated by free space which will allow the index to expand when new material is appended to the database. experimental results report on the utilization of free space when the database is enlarged.  f. j. burkowski
interactive clustering for navigating in hypermedia systems  this paper talks about clustering related nodes of an overview diagram to reduce its complexity and size. this is because although overview diagrams are useful for helping the user to navigate in a hypermedia system, for any real- world system these become too complicated and large to be really useful. both structure-based and content-based clustering are used. since the nodes can be related to each other in different ways, depending on the situation different clustered views will be useful. hence, it should be possible to interactively specify the clustering conditions and examine the resulting views. we present efficient clustering algorithms which can cluster the information space in real-time. we talk about the navigational view builder, a tool that allows the interactive development of overview diagrams. finally, we propose a 3-dimensional approach for visualizing these abstracted views.  sougata mukherjea james d. foley scott e. hudson
making b+\\- trees cache conscious in main memory  previous research has shown that cache behavior is important for main memory index structures. cache conscious index structures such as cache sensitive search trees (css-trees) perform lookups much faster than binary search and t-trees. however, css-trees are designed for decision support workloads with relatively static data. although b+-trees are more cache conscious than binary search and t-trees, their utilization of a cache line is low since half of the space is used to store child pointers. nevertheless, for applications that require incremental updates, traditional b+-trees perform well.  our goal is to make b+-trees as cache conscious as css-trees without increasing their update cost too much. we propose a new indexing technique called "cache sensitive b+-trees" (csb+-trees). it is a variant of b+-trees that stores all the child nodes of any given node contiguously, and keeps only the address of the first child in each node. the rest of the children can be found by adding an offset to that address. since only one child pointer is stored explicitly, the utilization of a cache line is high. csb+-trees support incremental updates in a way similar to b+-trees.  we also introduce two variants of csb+-trees. segmented csb+-trees divide the child nodes into segments. nodes within the same segment are stored contiguously and only pointers to the beginning of each segment are stored explicitly in each node. segmented csb+-trees can reduce the copying cost when there is a split since only one segment needs to be moved. full csb+-trees preallocate space for the full node group and thus reduce the split cost. our performance studies show that csb+-trees are useful for a wide range of applications.  jun rao kenneth a. ross
reading patterns and formats of academic articles on the web various formats are being used for web-based academic articles such as conference papers and journal papers. we surveyed the formats being used and tried to identify reading activities and the proper formats by carrying out two online surveys: an email-based survey with an email-based questionnaire and a web-based survey with a web-based questionnaire.the survey results show that readers overview web-based academic articles from the screen, print them out and then read the printed articles. the results also show that the structural formats employed by most papers on the web are against readers' preferences. the simple two- frame format was most preferred by 47% of the respondents as readers, but the cascade format of page windows was regarded as the worst by 65%. an interesting result is that 26% of the respondents selected as the worst style the paper-like format that is currently widely used for web-based articles. brief data sets and results are shown in this article.in addition, the importance of examples embedded in the web-based questionnaire was shown by two consecutive surveys. y. rho t. d. gedeon
interaction and outeraction: instant messaging in action  we discuss findings from an ethnographic study of instant messaging (im) in the workplace and its implications for media theory. we describe how instant messaging supports a variety of informal communication tasks. we document the affordances of im that support flexible, expressive communication. we describe some unexpected uses of im that highlight aspects of communication which are not part of current media theorizing. they pertain to communicative processes people use to connect with each other and to manage communication, rather than to information exchange. we call these processes "outeraction". we discuss how outeractional aspects of communication affect media choice and patterns of media use.  bonnie a. nardi steve whittaker erin bradner