waashk/acm huggingface dataset:
the dedale system for complex spatial queries  this paper presents dedale, a spatial database system intended to overcome some limitations of current systems by providing an abstract and non- specialized data model and query language for the representation and manipulation of spatial objects. dedale relies on a logical model based on linear constraints, which generalizes the constraint database model of [kkr90]. while in the classical constraint model, spatial data is always decomposed into its convex components, in dedale holes are allowed to fit the need of practical applications. the logical representation of spatial data although slightly more costly in memory, has the advantage of simplifying the algorithms. dedale relies on nested relations, in which all sorts of data (thematic, spatial, etc.) are stored in a uniform fashion. this new data model supports declarative query languages, which allow an intuitive and efficient manipulation of spatial objects. their formal foundation constitutes a basis for practical query optimization. we describe several evaluation rules tailored for geometric data and give the specification of an optimizer module for spatial queries. except for the latter module, the system has been fully implemented upon the o2 dbms, thus proving the effectiveness of a constraint- based approach for the design of spatial database systems.  stephane grumbach philippe rigaux luc segoufin
automatic generation of overview timelines  we present a statistical model of feature occurrence over time, and develop tests based on classical hypothesis testing for significance of term appearance on a given date. using additional classical hypothesis testing we are able to combine these terms to generate "topics" as defined by the topic detection and tracking study. the groupings of terms obtained can be used to automatically generate an interactive timeline displaying the major events and topics covered by the corpus. to test the validity of our technique we extracted a large number of these topics from a test corpus and had human evaluators judge how well the selected features captured the gist of the topics, and how they overlapped with a set of known topics from the corpus. the resulting topics were highly rated by evaluators who compared them to known topics.  russell swan james allan
using information scent to model user information needs and actions and the web  on the web, users typically forage for information by navigating from page to page along web links. their surfing patterns or actions are guided by their information needs. researchers need tools to explore the complex interactions between user needs, user actions, and the structures and contents of the web. in this paper, we describe two computational methods for understanding the relationship between user needs and user actions. first, for a particular pattern of surfing, we seek to infer the associated information need. second, given an information need, and some pages as starting pints, we attempt to predict the expected surfing patterns. the algorithms use a concept called "information scent", which is the subjective sense of value and cost of accessing a page based on perceptual cues. we present an empirical evaluation of these two algorithms, and show their effectiveness.  ed h. chi peter pirolli kim chen james pitkow
realizing a video environment: europarc's rave system  at europarc, we have been exploring ways to allow physically separated colleagues to work together effectively and naturally. in this paper, we briefly discuss several examples of our work in the context of three themes that have emerged: the need to support the full range of shared work; the desire to ensure privacy without giving up unobtrusive awareness; and the possibility of creating systems which blur the boundaries between people, technologies and the everyday world.  william gaver thomas moran allan maclean lennart lövstrand paul dourish kathleen carter william buxton
transactions and consistency in distributed database systems  the concepts of transaction and of data consistency are defined for a distributed system. the cases of partitioned data, where fragments of a file are stored at multiple nodes, and replicated data, where a file is replicated at several nodes, are discussed. it is argued that the distribution and replication of data should be transparent to the programs which use the data. that is, the programming interface should provide location transparency, replica transparency, concurrency transparency, and failure transparency. techniques for providing such transparencies are abstracted and discussed.  by extending the notions of system schedule and system clock to handle multiple nodes, it is shown that a distributed system can be modeled as a single sequential execution sequence. this model is then used to discuss simple techniques for implementing the various forms of transparency.  irving l. traiger jim gray cesare a. galtieri bruce g. lindsay
dolphin: integrated meeting support across local and remote desktop environments and liveboards  this paper describes dolphin, a fully group aware application designed to provide computer support for different types of meetings: face-to-face meetings with a large interactive electronic whiteboard with or without networked computers provided for the participants, extensions of these meetings with remote participants at their desktop computers connected via computer and audio/video networks, and/or participants in a second meeting room also provided with an electronic whiteboard as well as networked computers. dolphin supports the creation and manipulation of informal structures (e.g., freehand drawings, handwritten scribbles), formal structures (e.g., hypermedia documents with typed nodes and links), their coexistence, and their transformation.  norbert a. streitz jorg geibler jorg m. haake jeroen hol
the statistical security of a statistical database  this note proposes a statistical perturbation scheme to protect a statistical database against compromise. the proposed scheme can handle the security of numerical as well as nonnumerical sensitive fields. furthermore, knowledge of some records in a database does not help to compromise unknown records. we use chebyshev's inequality to analyze the trade-offs among the magnitude of the perturbations, the error incurred by statistical queries, and the size of the query set to which they apply. we show that if the statistician is given absolute error guarantees, then a compromise is possible, but the cost is made exponential in the size of the database.  j. f. traub y. yemini h. wozniakowski
management of information technology innovation: a heuristic contingency paradigm research perspective  this paper presents a contingency model which causally relates information technology acquisition and diffusion (it/ad) to organization culture (heterogeneous versus homogeneous), organization learning (innovative versus adaptive), and knowledge sharing (networked versus hierarchical). the model integrates multiple and well- grounded theoretical streams of research.  these three primary driving forces interact in a recursive dynamic, expressed in both rational driving forces and political driving forces. this paper focuses on the political driving forces, operationalizing them with five categories of measurement variables.  a preliminary set of research propositions associated with the five categories of political driving forces are presented. future research is suggested, addressing moderating variables, and information technology acquisition and diffusion patterns of s-curves.  mathew j. klempa
characterization of hierarchies and some operators in olap environment  recently numerous proposals for modelling and querying multidimensional databases (mddb) are proposed. among the still open problems there is a rigorous classification of the different types of hierarchies. in this paper we propose and discuss some different types of hierarchies within a single dimension of a cube. these hierarchies divide in different levels of aggregation a single dimension. depending on them, we discuss the characterization of some olap operators which refer to hierarchies in order to maintain the data cube consistency. moreover, we propose a set of operators for changing the hierarchy structure. the issues discussed provides modelling flexibility during the scheme design phase and correct data analysis.  elaheh pourabbas maurizio rafanelli
caching and database scaling in distributed shared-nothing information retrieval systems  a common class of existing information retrieval system provides access to abstracts. for example stanford university, through its folio system, provides access to the inspect database of abstracts of the literature on physics, computer science, electrical engineering, etc. in this paper this database is studied by using a trace-driven simulation. we focus on physical index design, inverted index caching, and database scaling in a distributed shared-nothing system. all three issues are shown to have a strong effect on response time and throughput. database scaling is explored in two ways. one way assumes an "optimal" configuration for a single host and then linearly scales the database by duplicating the host architecture as needed. the second way determines the optimal number of hosts given a fixed database size.  anthony tomasic hector garcia-molina
improving the effectiveness of information retrieval with local context analysis  techniques for automatic query expansion have been extensively studied in information research as a means of addressing the word mismatch between queries and documents. these techniques can be categorized as either global or local. while global techniques rely on analysis of a whole collection to discover word relationships, local techniques emphasize analysis of the top- ranked documents retrieved for a query. while local techniques have shown to be more effective that global techniques in general, existing local techniques are not robust and can seriously hurt retrieved when few of the retrieval documents are relevant. we propose a new technique, called local context analysis, which selects expansion terms based on cooccurrence with the query terms within the top-ranked documents. experiments on a number of collections, both english and non- english, show that local context analysis offers more effective and consistent retrieval results.  jinxi xu w. bruce croft
magic conditions  much recent work has focused on the bottom-up evaluation of datalog programs [bancilhon and ramakrishnan 1988]. one approach, called magic-sets, is based on rewriting a logic program so that bottom-up fixpoint evaluation of the program avoids generation of irrelevant facts [bancilhon et al. 1986; beeri and ramakrishnan 1987; ramakrishnan 1991]. it was widely believed for some time that the principal application of the magic-sets technique is to restrict computation in recursive queries using equijoin predicates. we extend the magic-sets transformation to use predicates other than equality (x>10, for example) in restricting computation. the resulting ground magic-sets transformation is an important step in developing an extended magic-sets transformation that has practical utility in "real" relational databases, not only for recursive queries, but for nonrecursive queries as well [mumick et al. 1990b; mumick 1991].  inderpal singh mumick sheldon j. finkelstein hamid pirahesh raghu ramakrishnan
the rhetoric of an online document retrieval system  the purpose of this paper is to establish a working definition of the term rhetoric, and to explore four tools that can be used to understand and analyze the rhetoric of online sytems. it is meant to persuade designers and writers of online systems that all information presented online is rhetorical, and as such its impact is better managed than ignored.  working definition: rhetoric means creating or using an "orientation to action" to persuade someone to act in a certain way.  tools: the rhetoric of the following are addressed: graphics, discourse communities, readership, and story emplotment.  carol m. l. lee
sql open heterogeneous data access  we describe the open, extensible architecture of sql for accessing data stored in external data sources not managed by the sql engine. in this scenario, sql engines act as middleware servers providing access to external data using sql dml statements and joining external data with sql tables in heterogeneous queries. we describe the state- of-the art in object-relational systems and their companion products, and provide an outlook on future directions.  berthold reinwald hamid pirahesh
structured answers for a large structured document collection  there is a simple method for integrating information retrieval and hypertext. this consists of treating nodes as isolated documents and retrieving them in order of similarity. if the nodes are structured, in particular, if sets of nodes collectively constitute documents, we can do better. this paper shows how the formation of the hypertext, the retrieval of nodes in response to content based queries, and the presentation of the nodes can be achieved in a way that exploits the knowledge encoded as the structure of the documents. the ideas are then exemplified in an sgml based hypertext information retrieval system.  michael fuller eric mackie ron sacks-davis ross wilkinson
object normal forms and dependency constraints for object-oriented schemata  we address the development of a normalization theory for object- oriented data models that have common features to support objects. we first provide an extension of functional dependencies to cope with the richer semantics of relationships between objects, called path dependency, local dependency, and global dependency constraints. using these dependency constraints, we provide normal forms for object-oriented data models based on the notions of user interpretation (user-specified dependency constraints) and object model. in constrast to conventional data models in which a normalized object has a unique interpretation, in object-oriented data models, an object may have many multiple interpretations that form the model for that object. an object will then be in a normal form if and only if the user's interpretation is derivable from the model of the object. our normalization process is by nature iiterative, in which objects are restructured until their models reflect the user's interpretation.  zahir tari john stokes stefano spaccapietra
2001 (invited talk. abstract only): a statistical odyssey  this talk is an interim report on the 5 year plan launched in 1996 to provide a theoretical and computational foundation of statistics for massive data sets. the plan coincided with the formation of at&amp;t; labs and the proposed research agenda of the infolab, which is both a physical laboratory and an interdisciplinary collection of information researchers in cs, mathematics, and statistics. at the halfway point of this odyssey we can identify some success stories but more importantly it is an opportune time to re-calibrate the challenges and the milestones.  daryl pregibon
an efficient multiversion algorithm for secure servicing of transaction reads  we propose an efficient multiversion algorithm for servicing read requests in secure multilevel databases. rather than keep an arbitrary number of versions of a datum, as standard multiversion algorithms do, the algorithm presented here maintains only a small fixed number of versions---up to three \---for a modified datum. each version corresponds to the state of the datum at the end of an externally defined version period. the algorithm avoids both covert channels and starvation of high transactions, and applies to security structures that are arbitrary partial orders. the algorithm also offers long- read transactions at any security level conflict-free access to a consistent, though slightly dated, view of any authorized portion of the database. we derive constraints sufficient to guarantee one-copy serializability of executions histories, and then exhibit an algorithm that satisfies these constraints.  paul ammann sushil jajodia
xmill: an efficient compressor for xml data  we describe a tool for compressing xml data, with applications in data exchange and archiving, which usually achieves about twice the compression ratio of gzip at roughly the same speed. the compressor, called xmill, incorporates and combines existing compressors in order to apply them to heterogeneous xml data: it uses zlib, the library function for gzip, a collection of datatype specific compressors for simple data types, and, possibly, user defined compressors for application specific data types.  hartmut liefke dan suciu
altruistic locking  long-lived transactions (llts) hold on to database resources for relatively long periods of time, significantly delaying the completion of shorter and more common transactions. to alleviate this problem we propose an extension to two-phase locking, called altruistic locking, whereby llts can release their locks early. transactions that access this released data are said to run in the wake of the llt and must follow special locking rules. like two-phase locking, altruistic locking is easy to implement and guarantees serializability.  kenneth salem hector garcia-molina jeannie shands
object identity as a query language primitive  we demonstrate the power of object identities (oids) as a database query language primitive. we develop an object-based data model, whose structural part generalizes most of the known complex-object data models: cyclicity is allowed in both its schemas and instances. our main contribution is the operational part of the data model, the query language iql, which uses oids for three critical purposes: (1) to represent data-structures with sharing and cycles, (2) to manipulate sets, and (3) to express any computable database query. iql can be type checked, can be evaluated bottom-up, and naturally generalizes most popular rule-based languages. the model can also be extended to incorporate type inheritance, without changes to iql. finally, we investigate an analogous value-based data model, whose structural part is founded on regular infinte trees and whose operational part is iql.  serge abiteboul paris c. kanellakis
distributed logging for transaction processing  increased interest in using workstations and small processors for distributed transaction processing raises the question of how to implement the logs needed for transaction recovery. although logs can be implemented with data written to duplexed disks on each processing node, this paper argues there are advantages if log data is written to multiple log server nodes. a simple analysis of expected logging loads leads to the conclusion that a high performance, microprocessor based processing node can support a log server if it uses efficient communication protocols and low latency, non volatile storage to buffer log data. the buffer is needed to reduce the processing time per log record and to increase throughput to the logging disk. an interface to the log servers using simple, robust, and efficient protocols is presented. also described are the disk data structures that the log servers use. this paper concludes with a brief discussion of remaining design issues, the status of a prototype implementation, and plans for its completion.  dean s. daniels alfred z. spector dean s. thompson
integrating theoreticians' and practitioners' perspectives with design rationale  qoc design rationale represents argumentation about design alternatives and assessments. it can be used to generate design spaces which capture and integrate information from design discussions and diverse kinds of theoretical analyses. such design spaces highlight how different theoretical approaches can work together to help solve design problems. this paper describes an example of the generation of a multi-disciplinary qoc design space which shows how designers' deliberations can be augmented with design contributions from a combination of different theoretical hci approaches.  victoria bellotti
on the equivalence of an egd to a set of fd's  the question "is a given join dependency equivalent to some set of multivalued dependencies?" led to the development of acyclicity theory [1]. the central question of this paper is: "is a given equality-generating dependency equivalent to a set of functional dependencies?" an algorithm is presented that answers that question in polynomial time without using the chase process and, in the case of a "yes" answer, can be used to find (a cover of) the set of functional dependencies involved. this question is also related to the similar question about join dependencies and multivalued dependencies by proving a result about the hypergraph representation of an egd. it is interesting to note that a minimal representation of an egd must be β-acyclic for the egd to be equivalent to a set of fd's, in contrast to the jd/mvd case, in which only α-acyclicity is needed. the β-acyclicity of an egd not necessarily minimal is always sufficient for the egd to be equivalent to a set of fd's as shown. finally, the algorithm is extended for a single egd to answer the question whether a set of egd's with the same right-hand-side column is equivalent to a set of fd's.  marc h. graham ke wang
objects with roles  the use of object-oriented conceptual models for modeling office applications and information systems is discussed. a model for describing object behavior based on the concept of role is presented. roles allow one to describe different perspectives for object evolution. for each role, relevant characteristics such as role properties, role states, messages, and role-state transition rules and constraints are defined. the implications of considering several roles in parallel for an object are discussed, and a classification of possible role interactions is given.  b. pernici