waashk/acm huggingface dataset:
towards constructive axiomatic specifications  the main goal of our efforts is the specification of data bases whose structure and behaviour are restricted by semantic integrity constraints. research proceeds along the following stages:  1\\. choose a data model;  2\\. establish a taxonomy of integrity constraints;  3\\. specify the data model formally;  4\\. develop a methodology for specifying conceptual schemas for different applications, based on the data model;  5\\. provide a conceptual characterization of query and update operations.  c. s. dos santos a. l. furtado j. m.v. de castilho s. e.r. de carvalho
optimizing search by showing results in context  we developed and evaluated seven interfaces for integrating semantic category information with web search results. list interfaces were based on the familiar ranked-listing of search results, sometimes augmented with a category name for each result. category interfaces also showed page titles and/or category names, but re- organized the search results so that items in the same category were grouped together visually. our user studies show that all category interfaces were more effective than list interfaces even when lists were augmented with category names for each result. the best category performance was obtained when both category names and individual page titles were presented. either alone is better than a list presentation, but both together provide the most effective means for allowing users to quickly examining search results. these results provide a better understanding of the perceptual and cognitive factors underlying the advantage of category groupings and provide some practical guidance to web search interface designers.  susan dumais edward cutrell hao chen
secure statistical databases with random sample queries  a new inference control, called random sample queries, is proposed for safeguarding confidential data in on-line statistical databases. the random sample queries control deals directly with the basic principle of compromise by making it impossible for a questioner to control precisely the formation of query sets. queries for relative frequencies and averages are computed using random samples drawn from the query sets. the sampling strategy permits the release of accurate and timely statistics and can be implemented at very low cost. analysis shows the relative error in the statistics decreases as the query set size increases; in contrast, the effort required to compromise increases with the query set size due to large absolute errors. experiments performed on a simulated database support the analysis.  dorothy e. denning
selectively estimation for boolean queries  in a variety of applications ranging from optimizing queries on alphanumeric attributes to providing approximate counts of documents containing several query terms, there is an increasing need to quickly and reliably estimate the number of strings (tuples, documents, etc.) matching a boolean query. boolean queries in this context consist of substring predicates composed using boolean operators. while there has been some work in estimating the selectivity of substring queries, the more general problem of estimating the selectivity of boolean queries over substring predicates has not been studied.  our approach is to extract selectivity estimates from relationships between the substring predicates of the boolean query. however, storing the correlation between all possible predicates in order to provide an exact answer to such predicates is clearly infeasible, as there is a super- exponential number of possible combinations of these predicates. instead, our novel idea is to capture correlations in a space-efficient but approximate manner. we employ a monte carlo technique called set hashing to succinctly represent the set of strings containing a given substring as a signature vector of hash values. correlations among substring predicates can then be generated on-the-fly by operating on these signatures.  we formalize our approach and propose an algorithm for estimating the selectivity of any boolean query using the signatures of its substring predicates. we then experimentally demonstrate the superiority of our approach over a straight-forward approach based on the independence assumption wherein correlations are not explicitly captured.  zhiyuan chen nick koudas flip korn s. muthukrishnan
disk allocation for cartesian product files on multiple-disk systems  cartesian product files have recently been shown to exhibit attractive properties for partial match queries. this paper considers the file allocation problem for cartesian product files, which can be stated as follows: given a k-attribute cartesian product file and an m-disk system, allocate buckets among the m disks in such a way that, for all possible partial match queries, the concurrency of disk accesses is maximized. the disk modulo (dm) allocation method is described first, and it is shown to be strict optimal under many conditions commonly occurring in practice, including all possible partial match queries when the number of disks is 2 or 3. it is also shown that although it has good performance, the dm allocation method is not strict optimal for all possible partial match queries when the number of disks is greater than 3. the general disk modulo (gdm) allocation method is then described, and a sufficient but not necessary condition for strict optimality of the gdm method for all partial match queries and any number of disks is then derived. simulation studies comparing the dm and random allocation methods in terms of the average number of disk accesses, in response to various classes of partial match queries, show the former to be significantly more effective even when the number of disks is greater than 3, that is, even in cases where the dm method is not strict optimal. the results that have been derived formally and shown by simulation can be used for more effective design of optimal file systems for partial match queries. when considering multiple- disk systems with independent access paths, it is important to ensure that similar records are clustered into the same or similar buckets, while similar buckets should be dispersed uniformly among the disks.  h. c. du j. s. sobolewski
concepts for transaction recovery in nested transactions  the concept of nested transactions offers more decomposable execution units and finer grained control over recovery and concurrency as compared to 'flat' transactions. to exploit these advantages, especially transaction recovery has to be refined and adjusted to the requirements of the control structure.  in this paper, we investigate transaction recovery for nested transactions. therefore, a model for nested transaction is introduced allowing for synchronous and asynchronous transaction invocation as well as single call and conversational interfaces. for the resulting four parameter combinations, the properties and dependencies of transaction recovery are explored if a transaction is 'unit of recovery' and if savepoints within transactions are used to gain finer recovery units.  theo haerder kurt rothermel
cq: a personalized update monitoring toolkit  the cq project at ogi, funded by darpa, aims at developing a scalable toolkit and techniques for update monitoring and event-driven information delivery on the net. the main feature of the cq project is a "personalized update monitoring" toolkit based on continual queries [3]. comparing with the pure pull (such as dbmss, various web search engines) and pure push (such as pointcast, marimba, broadcast disks) technology, the cq project can be seen as a hybrid approach that combines the pull and push technology by supporting personalized update monitoring through a combined client-pull and server-push paradigm.  ling liu calton pu wei tang david buttler john biggs tong zhou paul benninghoff wei han fenghua yu
hill climbing algorithms for content-based retrieval of similar configurations  the retrieval of stored images matching an input configuration is an important form of content-based retrieval. exhaustive processing (i.e., retrieval of the best solutions) of configuration similarity queries is, in general, exponential and fast search for sub-optimal solutions is the only way to deal with the vast (and ever increasing) amounts of multimedia information in several real-time applications. in this paper we discuss the utilization of hill climbing heuristics that can provide very good results within limited processing time. we propose several heuristics, which differ on the way that they search through the solution space, and identify the best ones depending on the query and image characteristics. finally we develop new algorithms that take advantage of the specific structure of the problem to improve performance.  dimitris papadias
correcting execution of distributed queries  algorithms for processing distributed queries require a priori estimates of the size of intermediate relations. most such algorithms take a "static" approach in which the algorithm is completely determined before processing begins. if size estimates are found to be inaccurate at some intermediate stage, there is no opportunity to re-schedule, and the result may be far from optimal. adaptive query execution may be used to alleviate the problem. care is necessary, though, to ensure that the delay associated with re-scheduling does not exceed the time saved through the use of a more efficient strategy. this paper presents a low overhead delay method to decide when to correct a strategy. sampling is used to estimate the size of relations, and alternative heuristic strategies prepared in a background mode are used to decide when to correct. correction is made only if lower overall delay is achieved, including correction time. evaluation using a model of a distributed data base indicates that the heuristic strategies are near optimal. moreover, it also suggests that it is usually correct to abort creation of an intermediate relation which is much larger than predicted.  p. bodorik j. pyra j. s. riordon
overview of the first trec conference  the first text retrieval conference (trec-1) was held in early november 1992 and was attended by about 100 people working in the 25 participating groups. the goal of the conference was to bring research groups together to discuss their work on a new large test collection. there was a large variety of retrieval techniques reported on, including methods using automatic thesaurii, sophisticated term weighting, natural language techniques, relevance feedback, and advanced pattern matching. as results had been run through a common evaluation package, groups were able to compare the effectiveness of different techniques, and discuss how differences among the sytems affected performance.  donna harman
rabbit: an interface for database access  a new kind of user interface for information retrieval has been designed and implemented to aid users in formulating a query. the system, called rabbit, relies upon a new paradigm for retrieval by reformulation, based on a psychological theory of human remembering. the paradigm actually evolved from an explicit attempt to design a 'natural' interface which imitated human retrieval processes.  to make a query in rabbit, the user interactively refines partial descriptions of his target item(s) by criticizing successive example (and counterexample) instances that satisfy the current partial description. instances from the database are presented to the user from a perspective inferred from the user's query description and the structure of the knowledge base. among other things, this constructed perspective reminds users of likely terms to use in their descriptions, enhances their understanding of the meaning of given terms, and prevents them from creating certain classes of semantically improper query descriptions. rabbit particularily facilitates users who approach a database with only a vague idea of what it is that they want and who thus, need to be guided in the (re)formulation of their queries. rabbit is also of substantial value to casual users who have limited knowledge of a given database or who must deal with a multitude of databases.  michael d. williams frederich n. tou
portholes: supporting awareness in a distributed work group  we are investigating ways in which media space technologies can support distributed work groups through access to information that supports general awareness. awareness involves knowing who is "around", what activities are occurring, who is talking with whom; it provides a view of one another in the daily work environments. awareness may lead to informal interactions, spontaneous connections, and the development of shared cultures \---all important aspects of maintaining working relationships which are denied to groups distributed across multiple sites.  the portholes project, at rank xerox europarc in cambridge, england, and xerox parc in palo alto, california, demonstrates that awareness can be supported across distance. a data network provides a shared database of image information that is regularly updated and available at all sites. initial experiences of the system in use at europarc and parc suggest that portholes both supports shared awareness and helps to build a "sense of community".  paul dourish sara bly
meaning-making in the creation of useful summary reports  summary reports are the periodic assemblings of text, numbers, and other data, drawn from diverse sources to present a picture of some aspect of an organization's state. they have become ubiquitous in organizations with the advent of computers, but are not always as useful as their readers would like them to be. this paper focuses on the meaning-making work that report contributors and readers must do in order for reports to be useful and presents some examples drawn from everyday interactions in a business unit of a large corporation. the paper uses these examples as a foundation for asking what it might mean to purposefully support meaning-making in organizational reporting.  barbara katzenberg john mcdermott
an information structure dealing with term dependance and polysemy  an information structure (is) that is regarded as a formal description of a domain of discourse is proposed. this is is aimed at increasing the effectiveness of an information retrieval system. it is shown how the retrieval algorithm can take into account the term dependencies that are provided by the is. moreover, these term dependencies can be used by an automatic indexing procedure in order to interpret polysemic terms. the theoretical framework of our is has some favorable properties. as a consequence, the construction and maintenance of such an is is simpler than that of a thesaurus.  p. schauble
powers of ten thousand: navigating in large information spaces  how would you interactively browse a very large display space, for example, a street map of the entire united states? the traditional solution is zoom and pan. but each time a zoom-in operation takes place, the context from which it came is visually lost. sequential applications of the zoom-in and zoom-out operations may become tedious. this paper proposes an alternative technique, the macroscope, based on zooming and planning in multiple translucent layers. a macroscope display should comfortably permit browsing continuously on a single image, or set of images in multiple resolutions, on a scale of at least 1 to 10,000.  henry lieberman
optimization of the number of copies in a distribution data base  we consider the effect on system performance of the distribution of a data base in the form of multiple copies at distinct sites. the purpose of our analysis is to determine the gain in read throughput that can be obtained in the presence of consistency preserving algorithms that have to be implemented when update operations are carried out on each copy. we show that read throughput diminishes if the number of copies exceeds an optimal value. the theoretical model we develop is applied to a system in which consistency is preserved through the use of ellis's ring algorithm.  e. g. coffman e. gelenbe b. plateau
implementing digital libraries (panel session)  this panel will address some of the practical issues of implementing digital libraries. everyone seems to agree that digital libraries are in their infancy. many of us watch in amazement as new developments occur. in the year 2000 building a production digital library means analyzing tradeoffs between stability, innovation, and costs/benefits. in this panel we will address some of the more interesting issues of digital library implementation.  one of the critical challenges is the economics of digital libraries. institutions are forming consortia out of necessity and this raises issues of trust, cooperation and commitment.  in order for institutions to deliver web-based resources effectively sophisticated cross-organizational access management tools are needed to authenticate and authorize.  institutions are developing new tools and exporting them from research departments into libraries. how well does this collaboration work?  the above issues are only a sampling of the challenges this panel will explore.  rebecca wesley dan greenstein david millman margery tibbetts gregory zick
turbo-charging vertical mining of large databases  in a vertical representation of a market-basket database, each _item_ is associated with a column of values representing the transactions in which it is present. the association-rule mining algorithms that have been recently proposed for this representation show performance improvements over their classical horizontal counterparts, but are either efficient only for certain database sizes, or assume particular characteristics of the database contents, or are applicable only to specific kinds of database schemas. we present here a new vertical mining algorithm called viper, which is general-purpose, making no special requirements of the underlying database. viper stores data in compressed bit-vectors called "snakes" and integrates a number of novel optimizations for efficient snake generation, intersection, counting and storage. we analyze the performance of viper for a range of synthetic database workloads. our experimental results indicate significant performance gains, especially for large databases, over previously proposed vertical and horizontal mining algorithms. in fact, there are even workload regions where viper outperforms an optimal, but practically infeasible, horizontal mining algorithm.  pradeep shenoy jayant r. haritsa s. sundarshan gaurav bhalotia mayank bawa devavrat shah
preserving update semantics in schema integration  in this paper, we propose a methodology for schema integration where the semantics of updates is preserved during the view integration process. we propose to divide view integration into three steps: combination, restructuring, and optimization. in the view combination step, we define the combined schema that contains all original views, plus a new set of constraints that express how data in distinct views are interrelated. the restructuring step is devoted to normalizing the views so that merging becomes possible. the optimization step tries to reduce redundancy and the size of the schema. our methodology defines a set of transformation primitives that allows schema integration to be realized in a safe (information preserving) and algorithmic way. in the proposed transformation primitives, the relationship between the original and transformed schema is formally specified by the instance and update mappings. we introduce the notion of an update semantics preserving transformation, which guarantees that the relationships between each view and the global schema, originated during the view integration process, reflect exactly the relationships between the views as defined by the combined schema. in our approach, the view definition mappings and the view update translator can be directly defined from the instance and update mappings between the different intermediate schemas generated during the view integration process.  vânia m. p. vidal marianne winslett
automatic discovery of language models for text databases  the proliferation of text databases within large organizations and on the internet makes it difficult for a person to know which databases to search. given language models that describe the contents of each database, a database selection algorithm such as gioss can provide assistance by automatically selecting appropriate databases for an information need. current practice is that each database provides its language model upon request, but this cooperative approach has important limitations.  this paper demonstrates that cooperation is not required. instead, the database selection service can construct its own language models by sampling database contents via the normal process of running queries and retrieving documents. although random sampling is not possible, it can be approximated with carefully selected queries. this sampling approach avoids the limitations that characterize the cooperative approach, and also enables additional capabilities. experimental results demonstrate that accurate language models can be learned from a relatively small number of queries and documents.  jamie callan margaret connell aiqun du
using icons to find documents: simplicity is critical  a common task at almost any computer interface is that of searching for documents, which guis typically represent with icons. oddly, little research has been done on the processes underlying icon search. this paper outlines the factors involved in icon search and proposes a model of the process. an experiment was conducted which suggests that the proposed model is sound, and that the most important factor in searching for files is the type of icons used. in general, simple icons (those discriminable based on a few features) seem to help users, while complex icons are no better than simple rectangles.  michael d. byrne
counting, enumerating, and sampling of execution plans in a cost-based query optimizer  testing an sql database system by running large sets of deterministic or stochastic sql statements is common practice in commercial database development. however, code defects often remain undetected as the query optimizer's choice of an execution plan is not only depending on the query but strongly influenced by a large number of parameters describing the database and the hardware environment. modifying these parameters in order to steer the optimizer to select other plans is difficult since this means anticipating often complex search strategies implemented in the optimizer.  in this paper we devise algorithms for counting, exhaustive generation, and uniform sampling of plans from the complete search space. our techniques allow extensive validation of both generation of alternatives, and execution algorithms with plans other than the optimized one \---if two candidate plans fail to produce the same results, then either the optimizer considered an invalid plan, or the execution code is faulty. when the space of alternatives becomes too large for exhaustive testing, which can occur even with a handful of joins, uniform random sampling provides a mechanism for unbiased testing.  the technique is implemented in microsoft's sql server, where it is an integral part of the validation and testing process.  florian waas cesar galindo-legaria
duplicate record elimination in large data files  the issue of duplicate elimination for large data files in which many occurrences of the same record may appear is addressed. a comprehensive cost analysis of the duplicate elimination operation is presented. this analysis is based on a combinatorial model developed for estimating the size of intermediate runs produced by a modified merge-sort procedure. the performance of this modified merge-sort procedure is demonstrated to be significantly superior to the standard duplicate elimination technique of sorting followed by a sequential pass to locate duplicate records. the results can also be used to provide critical input to a query optimizer in a relational database system.  dina bitton david j. dewitt