waashk/acm huggingface dataset:
three-layer bubble-sorting-based nonmanhattan channel routing  it is well known that a nonmanhattan channel router can use fewer routing tracks, and is never worse than a manhattan router in a channel. to my knowledge, a three-layer bubble-sorting-based nonmanhattan channel routing problem is always solved by the solution in a two-layer bubble-sorintg-based nonmanhattan channel routing problem. recently, an o(kn2) heuristic algorithm [chaudhary et al. 1991] and an o(kn2) optimal algorithm [chen et al. 1994] have been proposed, where k is the number of two-layer routing tracks and n is the number of terminals in a bubble-sorintg-based nonmanhattan channel. in this paper we propose an optimal three-layer bubble-sorintg-based nonmanhattan routing algorithm to minimize the number of three-layer routing tracks. furthermore, the time complexity of theis optimal algorithm is proven to be in o(hn) time, where h is the number of three-layer routing tracks and n is the number of terminals in a bubble-sorting- based nonmanhattan channel.  jin-tai yan
the correctness of concurrency control mechanisms in a system for distributed databases (sdd-1)  this paper presents a formal analysis of the concurrency control strategy of sdd-1. sdd-1, a system for distributed databases, is a prototype distributed database system being developed by computer corporation of america. in sdd-1, portions of data distributed throughout a network may be replicated at multiple sites. the sdd-1 concurrency control guarantees database consistency in the face of such distribution and replication.  this paper is one of a series of companion papers on sdd-1 [2, 8].  philip a. bernstein david w. shipman
construction of relations in relational databases  using a nonprocedural language for query formulation requires certain automatization of a query answering process. given a query for creation of a new relation, the problem is to find an efficient procedure which produces this relation from a given relational database. we concentrate upon sequences of join operations which losslessly produce a relation required by a query. a new property of such sequences is analyzed which provides a basis for the presented algorithms that construct an efficient join procedure. the algorithms have polynomial complexity. a modified and/or graph is used for the display of a given set of dependencies and a collection of relations representing a database.  eliezer l. lozinskii
incomplete information costs and database design  this paper presents a methodology for trading-off the cost of incomplete information against the data-related costs in the design of database systems. it investigates how the usage patterns of the database, defined by the characteristics of information requests presented to it, affect its conceptual design. the construction of minimum-cost answers to information requests for a variety of query types and cost structures is also studied. the resulting costs of incomplete database information are balanced against the data-related costs in the derivation of the optimal design.  haim mendelson aditya n. saharia
strudel - an extensible electronic conversation toolkit  this paper describes the conceptual model of strudel, a toolkit of generic components for conversation and action management. to empower work groups to more effectively conduct their computer-based communication, coordination, and information sharing activities, strudel packages within a simple model of task and action the semi-structured message, active message and conversation management paradigms. to facilitate acceptance and use within varying work cultures, we define this model in terms of a set of extensible components, which are implemented as a prototype software toolkit that is efficient, portable, customizable, and extensible. issues considered briefly in this paper include threading in conversations that are converging or multi-party, and interoperability between active message systems.  allan shepherd niels mayer allan kuchinsky
heuristic approach for generic audio data segmentation and annotation  a real-time audio segmentation and indexing scheme is presented in this paper. audio recordings are segmented and classified into basic audio types such as silence, speech, music, song, environmental sound, speech with the music background, environmental sound with the music background, etc. simple audio features such as the energy function, the average zero-crossing rate, the fundamental frequency, and the spectral peak track are adopted in this system to ensure on-line processing. morphological and statistical analysis for temporal curves of these features are performed to show differences among different types of audio. a heuristic rule-based procedure is then developed to segment and classify audio signals by using these features. the proposed approach is generic and model free. it can be applied to almost any content- based audio management system. it is shown that the proposed scheme achieves an accuracy rate of more than 90% for audio classification. examples for segmentation and indexing of accompanying audio signals in movies and video programs are also provided.  tong zhang c.-c. jay kuo
teambox: an exploration of collaborative interoperability  given that teams will tend to use a combination of generic groupware and individual applications, there is a need to address issues of interoperability. however, traditional system interoperability that focuses on making data and applications more accessible may not suffice. in collaborative work, the creating and acting on knowledge is inter-related. collaborative interoperability should support the sharing and coordination of the knowledge represented by the relationships and context of the data. the requirements and dimensions of collaborative interoperability are outlined. the concept of a "collaborative transaction" is proposed as a knowledge representation and coordination scheme. the teambox design architecture is introduced. the feasibility of the architecture is illustrated by the description of a working prototype.  munir mandviwalla peter grillo
experience in implementing a document delivery service  in this paper we propose an integration between electronic mail and web services for people such as library operators who need to send large files to internet users. the proposed solution permits libraries to continue using the e-mail service to send large documents, but at the same time overcomes problems that users can encounter downloading large size files with e-mail agents. the library operator sends the document as an attachment to the destination address, on fly the e-mail server extracts and saves the attachments in a web-server disk file and substitutes them with a new messsage part that includes the url pointing to the saved document. the reciever can download these large objects using a user-friendly browser.  francesco gennai laura abba marina buzzi maria g. balestri silvana mangiaracina
on-line information retrieval  the methods of information retrieval in general use today are straightforward and easy to understand. they include batch and interactive, either of which can utilize a sequential search or inverted index file structure - with peculiar advantages and disadvantages to each.  most important recorded literature from 1970 is represented in the form of bibliographic citations and abstracts; the purpose of the system is to identify citations which are relevant to a given interest. queries are most often formulated as boolean combinations of keywords and phrases.  many specialized service bureaus exist to provide information retrieval services. for the most part such services are located within the commercial sector of the economy, but more and more government services are tending to encroach upon the commercial market place.  vast networks of users are served via packet-switched, value-added telecommunications service networks. as the industry grows, various conflicts arise which are considered in some detail, as is the outlook and challenges faced by the industry.  roger k. summit
experience with the virtual notebook system: abstraction in hypertext  the virtual notebook system (vns) is a distributed collaborative hypertext system that has made a successful transition from research prototype to commercial product. experience in developing and deploying the vns in diverse settings including biomedical research, undergraduate education, and collaborative system prototyping has developed insight into the use of systems for computer-supported cooperative work (cscw). this paper provides a brief overview of the vns, discusses some of its strengths and weaknesses with respect to collaboration, and draws some conclusions about the impact of metaphor and extensibility on the collaborative process.  jerry fowler donald g. baker ross dargahi vram kouramajian hillary gilson kevin brook long cynthia petermann g. anthony gorry
self-tuning histograms: building histograms without looking at data  in this paper, we introduce self-tuning histograms. although similar in structure to traditional histograms, these histograms infer data distributions not by examining the data or a sample thereof, but by using feedback from the query execution engine about the actual selectivity of range selection operators to progressively refine the histogram. since the cost of building and maintaining self-tuning histograms is independent of the data size, self- tuning histograms provide a remarkably inexpensive way to construct histograms for large data sets with little up-front costs. self-tuning histograms are particularly attractive as an alternative to multi-dimensional traditional histograms that capture dependencies between attributes but are prohibitively expensive to build and maintain. in this paper, we describe the techniques for initializing and refining self-tuning histograms. our experimental results show that self-tuning histograms provide a low-cost alternative to traditional multi-dimensional histograms with little loss of accuracy for data distributions with low to moderate skew.  ashraf aboulnaga surajit chaudhuri
decision situations, decision processes, and decision functions: towards a theory-based framework for decision-aid design  decision augmentation systems differ qualitatively from current man-computer interactive systems because they involve intelligent, complex, and largely symbiotic man-machine relationships. they thus provide the stimulus for the development of a new branch of human factors, one concerned with the human engineering of relationships between humans and intelligent, quasi-autonomous, computer-based systems. the threefold objective of the research described in this paper has therefore been to identify the human factors problems which such a framework should address, to generate the basic information around which it should be built, and to determine the general structure which it should take.  w. zachary r. wherry f. glenn j. hopson
using statistical sampling for query optimization in heterogeneous library information systems  query optimization in heterogeneous database systems is not always possible since the component dbms may not have the ability to transmit necessary information. however, these systems need query optimization because the cost of transmitting large quantities of data across diverse databases is very high. we propose a query strategy which uses hypothesis testing to determine which of two sets of data are larger. our experiments show that this strategy is very likely to select the smaller set when the sampling results fall outside a region of uncertainty we call the "grey zone." this provides query optimization without transmission of database statistics.  gregory d. speegle michael j. donahoo
an approach to search for the digital library  the chief form of accessing the content of a digital library (dl) is i ts search interface. while a dl needs an interface that integrates a range of options from search to browse to serendipity, in this work we focus on analytical search. we propose using bates' search tactics as a basis for the re-design of search interfaces. we believe this approach will help to identify the types of tools that need to be supported by a dl interface.  elaine g. toms joan c. bartlett
parallel handling of integrity constraints on fragmented relations  integrity constraint handling is considered an important issue in relational database management systems. many studies were already conducted in this area. little attention has been paid however to the influence of relation fragmentation and parallelism on constraint handling. this paper shows how relation fragmentation complicates matters on the one hand, but how parallelism can help to get better efficiency in enforcing constraints on the other hand. the ideas as presented in this paper are used in the context of the prisma database machine; they have a more general applicability though.  paul w. p. j. grefen peter m. g. apers
integrating a dynamic lexicon with a dynamic full-text retrieval system  there has been a great deal of interest within the information retrieval community in evaluating the use of linguistic knowledge to improve the indexing and searching of textual databases. such systems must often employ a lexicon to store information about the words and phrases comprising the application's domain. unlike a static lexicon, a dynamic lexicon raises practical concerns about the coordination between the state of the lexicon and ir indexing schemes based on lexical knowledge. additionally, it introduces a host of database management issues, many of which are similar to those found in the text databases as well. in this paper, we explore a range of system design and performance issues that arise when integrating a dynamic lexicon with a dynamic full-text information retrieval system. we observe that the principle of functional isolation argues against the use of language-dependent information in article indexes and favors the use of query-time strategies for applying lexical knowledge. we propose and evaluate a system architecture which embodies this principle. we also show how a storage and retrieval infrastructure based on burkowski's [burkowski92] "containment model" abstraction can be employed to implement both the text retrieval and lexicon facilities required in an integrated system.  peter g. anick rex a. flynn
one dimensional motion tailoring for the disabled: a user study  the tailor project allows physically disabled users to provide real-time analog input to computer applications. we use a polhemus tracking device and create a custom tailored mapping from each user's best range and type of motion into the analog control signal. the application is a simple video game based on pong, where the analog input controls the position of the player's paddle. a group of able-bodied subjects was able to correctly hit the ball with the paddle 77% of the time, and a comparison group of children with cerebral palsy performed at the 50% level. more than half the disabled users were able to perform at a higher level than the worst able- bodied user.  randy pausch laura vogtle matthew conway
support for repetitive transactions and ad hoc queries in system r  system r supports a high-level relational user language called sql which may be used by ad hoc users at terminals or as an embedded data sublanguage in pl/i or cobol. host-language programs with embedded sql statements are processed by the system r precompiler which replaces the sql statements by calls to a machine-language access module. the precompilation approach removes much of the work of parsing, name binding, and access path selection from the path of a running program, enabling highly efficient support for repetitive transactions. ad hoc queries are processed by a similar approach of name binding and access path selection which takes place on-line when the query is specified. by providing a flexible spectrum of binding times, system r permits transaction-oriented programs and ad hoc query users to share a database without loss of efficiency.  system r is an experimental database management system designed and built by members of the ibm san jose research laboratory as part of a research program on the relational model of data. this paper describes the architecture of system r, and gives some preliminary measurements of system performance in both the ad hoc query and the "canned program" environments.  d. d. chamberlin m. m. astrahan w. f. king r. a. lorie j. w. mehl t. g. price m. schkolnick p. griffiths selinger d. r. slutz b. w. wade r. a. yost
on computing correlated aggregates over continual data streams  in many applications from telephone fraud detection to network management, data arrives in a stream, and there is a need to maintain a variety of statistical summary information about a large number of customers in an online fashion. at present, such applications maintain basic aggregates such as running extrema values (min, max), averages, standard deviations, etc., that can be computed over data streams with limited space in a straightforward way. however, many applications require knowledge of more complex aggregates relating different attributes, so-called _correlated aggregates_. as an example, one might be interested in computing the percentage of international phone calls that are longer than the average duration of a domestic phone call. exact computation of this aggregate requires multiple passes over the data stream, which is infeasible.  we propose single-pass techniques for approximate computation of correlated aggregates over both landmark and sliding window views of a data stream of tuples, using a very limited amount of space. we consider both the case where the independent aggregate (average duration in the example above) is an extrema value and the case where it is an average value, with any standard aggregate as the dependent aggregate; these can be used as building blocks for more sophisticated aggregates. we present an extensive experimental study based on some real and a wide variety of synthetic data sets to demonstrate the accuracy of our techniques. we show that this effectiveness is explained by the fact that our techniques exploit monotonicity and convergence properties of aggregates over data streams.  johannes gehrke flip korn divesh srivastava
efficient and cost-effective techniques for browsing and indexing large video databases  we present in this paper a fully automatic content-based approach to organizing and indexing video data. our methodology involves three steps:    * step 1: we segment each video into shots using a camera-tracking technique. this process also extracts the feature vector for each shot, which consists of two statistical variances _varba_ and _varoa_. these values capture how much things are changing in the background and foreground areas of the video shot.    * step 2: for each video, we apply a fully automatic method to build a browsing hierarchy using the shots identified in step 1.    * step 3: using the _varba_ and _varoa_ values obtained in step 1, we build an index table to support a variance-based video similarity model. that is, video scenes/shots are retrieved based on given values of _varba_ and _varoa& lt;/sup>_.  the above three inter-related techniques offer an integrated framework for modeling, browsing, and searching large video databases. our experimental results indicate that they have many advantages over existing methods.  junghwan oh kien a. hua
on designing database schemes bounded or constant-time maintainable with respect to functional dependencies  under the weak instance model, to determine if a class of database schemes is bounded with respect to dependencies is fundamental for the analysis of the behavior of the class of database schemes with respect to query processing and updates. however, proving that a class of database schemes is bounded with respect to dependencies seems to be very difficult even for restricted cases. to resolve this problem, we need to develop techniques for characterizing bounded database schemes  in this paper, we give a formal methodology for designing database schemes bounded with respect to functional dependencies using a new technique called extensibility. this methodology can also be used to design constant-time- maintainable database schemes  e. p. f. chan h. j. hernandez
database design for incomplete relations  although there has been a vast amount of research in the area ofrelational database design, to our knowledge, there has been very little work that considers whether this theory is still valid when relations in the database may be incomplete. when relations are incomplete and thus contain null values the problem of whether satisfaction is additive arises. additivity is the property of the equivalence of the satisfaction of a set of functional dependencies (fds) f with the individual satisfaction of each member of f in an incomplete relation. it is well known that in general, satisfaction of fds is not additive. previously we have shown that satisfaction is additive if and only if the set of fds is monodependent. we conclude that monodependence is a fundamental desirable property of a set of fds when considering incomplete information in relational database design. we show that, when the set of fds f either satifies the intersection property or the split-freeness property, then the problem of finding an optimum cover of f can be solved in polynomial time in the size of f; in general, this problem is known to be np-complete. we also show that when f satisfies the split-freeness property then deciding whether there is a superkey of cardinality k or less can be solved in polynomial time in the size of f, since all the keys have the same cardinality. if f only satisfies the intersection property then this problem is np-complete, as in the general case. moreover, we show that when f either satisfies the intersection property or the split-freeness property then deciding whether an attribute is prime can be solved in polynomial time in the size of f; in general, this problem is known to be np-complete. assume that a relation schema r is an appropriate normal form with respect to a set of fds f. we show that when f satisfies the intersection property then the notions of second normal form and third normal form are equivalent. we also show that when r is in boyce-codd normal form (bcnf), then f is monodependent if and only if either there is a unique key for r, or for all keys x for r, the cardinality of x is one less than the number of attributes associated with r. finally, we tackle a long-standing problem in relational database theory by showing that when a set of fds f over r satisfies the intersection property, it also satisfies the split-freeness property (i.e., is monodependent), if and only if every lossless join decomposition of r with respect to f is also dependecy preserving. as a corollary of this result we are able to show that when f satisfies the intersection property, it also satisfies the intersection property, it also satisfies the split-freeness property(i.e., is monodependent), if and only if every lossless join decomposition of r, which is in bcnf, is also dependency preserving. our final result is that when f is monodependent, then there exists a unique optimum lossless join decomposition of r, which is in bcnf, and is also dependency preserving. furthermore, this ultimate decomposition can be attained in polynomial time in the size of f.  mark levene george loizou
the state of the art in automating usability evaluation of user interfaces usability evaluation is an increasingly important part of the user interface design process. however, usability evaluation can be expensive in terms of time and human resources, and automation is therefore a promising way to augment existing approaches. this article presents an extensive survey of usability evaluation methods, organized according to a new taxonomy that emphasizes the role of automation. the survey analyzes existing techniques, identifies which aspects of usability evaluation automation are likely to be of use in future research, and suggests new ways to expand existing approaches to better support usability evaluation. melody y. ivory marti a. hearst