Many location-based applications are enabled by handling numerous moving queries over mobile objects. Efficient processing of such queries mainly relies on effective probing, i.e., polling the objects to obtain their current locations (required for processing the queries). With effective probing, one can monitor the current location of the objects with sufficient accuracy for the existing queries, by striking a balance between communication cost of probing and accuracy of the knowledge about current location of the objects. In this paper, we focus on location-based applications that reduce to processing a large set of proximity monitoring queries simultaneously, where each query continuously monitors if a pair of objects are within a certain predefined distance. Accordingly, we propose an effective object probing solution for efficient processing of proximity monitoring queries. In particular, with our proposed solution for the first time we formulate optimal probing as a batch processing problem and propose a method to prioritize probing the objects such that the total number of probes required to answer all queries is minimized. Our extensive experiments demonstrate the efficiency of our proposed solution for a wide range of applications involving up to hundreds of millions of queries.

The 13 papers in this special issue focus on knowledge and data engineering for e-learning. Some of these papers were recommended submissions from the best ranked papers presented at the Sixth International Conference on Web-Based Learning (ICWL '07), held in August 2007 in Edinburgh, United Kingdom.

Searching data streams has been traditionally very limited, either in the complexity of the search or in the size of the searched dataset. In this paper, we investigate the design and optimization of constructs that enable SQL to express complex patterns. In particular we propose the RSPS (recursive sequential pattern search) algorithm that inspired by the KMP (Knuth-Morris-Pratt) string matching algorithm and exploits the inter-dependencies between the elements of a sequential pattern to minimize repeated passes over the same data. Performance gains derived from a set of experiments and a sensitivity analysis for the RSPS are also discussed. Our experimental results demonstrate impressive speedup. 1.

No abstract available.

Given the recent advancement of microarray technologies, we present a density-based clustering approach for the purpose of co-expressed gene clusters identi cation. Underlying hypothesis is that a set of co-expressed gene clusters can be used to unreveal a common biological function. By addressing the strengths and limitations of previous densitybased clustering approaches, we present anovel clustering algorithm that utilizes a neighborhood de ned by k-nearest neighbors. Experimental results indicate that the proposed method identi es biologically meaningful and co-expressed gene clusters.

An adaptive probe-based optimization technique is developed and demonstrated in the context of an Internet-based distributed database environment. More and more common are database systems, which are distributed across servers communicating via the Internet where a query at a given site might require data from remote sites. Optimizing the response time of such queries is a challenging task due to the unpredictability of server performance and network traffic at the time of data shipment; this may result in the selection of an expensive query plan using a static query optimizer. We constructed an experimental setup consisting of two servers running the same DBMS connected via the Internet. Concentrating on join queries, we demonstrate how a static query optimizer might choose an expensive plan by mistake. This is due to the lack of a priori knowledge of the run-time environment, inaccurate statistical assumptions in size estimation, and neglecting the cost of remote method invocation. These shortcomings are addressed collectively by proposing a probing mechanism. Furthermore, we extend our mechanism with an adaptive technique that detects sub-optimality of a plan during query execution and attempts to switch to the cheapest plan while avoiding redundant work and imposing little overhead. An implementation of our run-time optimization technique for join queries was constructed in the Java language and incorporated into an experimental setup. The results demonstrate the superiority of our probe-based optimization over a static optimization.

A mobile environment is weakly-connected, characterized by low communication bandwidth and poor connectivity. The conventional paradigm for surfing mobile Web documents is ineffective since portions of a document could be corrupted during transmission and it is expensive to re-transmit the whole document. It is important that the high content-bearing portions should be transmitted successfully so that a mobile client could at least obtain a high level content and determine if the corrupted portions need to be retransmitted. We have proposed a multi-resolution transmission paradigm which allows higher content-bearing portions of a Web document to be transmitted, by partitioning it into multiple organizational units and associating an information content with each unit. The client can explore the higher content-bearing portion earlier and terminate browsing an irrelevant document sooner. We extend our previous work and propose a fault-tolerant multi-resolution transmission scheme which allows units of higher information content to be recovered from transmission error. The client can obtain an overall content of a Web document and either terminate the transmission of the remaining portions or decide if the corrupted portions need to be retransmitted. We demonstrate its feasibility with a prototype and with simulation results.

A Cooperative Federated Database System (CFDBS) is an information sharing environment in which units of information to be shared may be substantially structured, and participants are actively involved in sharing activities. We focus on the problem of shared ontology for the purpose of discovery in the CFDBS context. We introduce the concept and mechanism of the Dynamic Classificational Ontology (DCO), which is a mediator to help participants identify and resolve ontological similarities and differences. A DCO contains top level knowledge about information units exported by information providers, along with classificational knowledge. By contrast with fixed hierarchical classifications, the DCO builds domain specific, dynamically changing classification schemes; it specifically contains knowledge about overlap among information units. Information providers contribute to the DCO when information units are exported, and the current knowledge in the DCO is in turn utilized to guide export and discovery of information. At the cost of information providers' cooperative efforts, this approach supports much more systematic discovery than that provided by keyword based search, with substantially greater precision and recall. An experimental prototype of the DCO has been developed, and applied and tested to improve the precision and recall of Medline document searches for biomedical information sharing.

To support database interoperability in federated databases systems, it is critical to be able to identify (potentially) equivalent data instances from individual autonomous database components. Since the components in a federation are autonomous, their data may be updated asynchronously, viz., modifications to a real world entity may be captured in different databases at different times; the authors term this effect update heterogeneity. Existing approaches largely base data instance similarity identification only on current attribute/property values; in the face of update heterogeneity, this is inadequate. They present an approach to address the problem of update heterogeneity in the federated databases context. They employ a probabilistic model, which utilizes historical database update information to estimate the degree of similarity between candidate data instances from different database components. They employ transaction history (log) information to this end, which is typically already available in the component database systems. They have experimentally implemented and tested this approach within the context of a prototype experimental federated databases system, FeXpress.

An approach and mechanism to support the dynamic discovery of information units within a collection of autonomous and heterogeneous database systems is described. The mechanism is based upon a core set of database constructs that characterizes object database systems, along with a set of self-adaptive heuristics employing techniques from machine learning. The approach provides an uniform framework for organizing, indexing, searching, and browsing database information units within an environment of multiple, autonomous, interconnected databases. The feasibility of the approach and mechanism is illustrated using a protein/genetics application environment. Metrics for measuring the performance of the discovery system are presented and the effectiveness of the system is thereby evaluated. Performance tradeoffs are examined and analyzed by experiments performed, employing a simulation model.>

A novel execution model for rule application in active databases is developed and applied to the problem of updating derived data in a database represented using a semantic, object-based database model. The execution model is based on the use of “limited ambiguity rules” (LARs), which permit disjunction in rule actions. The execution model essentially performs a breadth-first exploration of alternative extensions of a user-requested update. Given an object-based database schema, both integrity constraints and specifications of derived classes and attributes are compiled into a family of limited ambiguity rules. A theoretical analysis shows that the approach is sound: the execution model returns all valid “completions” of a user-requested update, or terminates with an appropriate error notification. The complexity of the approach in connection with derived data update is considered.

Changes to the conceptual structure (meta-data) of a database are common in many application environments and are in general inadequately supported by existing database systems. An approach to supporting such meta-data evolution in a simple, extensible, object database environment is presented. Machine learning techniques are the basis for a cooperative user/system database design and evolution methodology. An experimental end-user database evolution tool based on this approach has been designed and implemented.>

An approach and mechanism to support the sharing of objects are described, an experimental implementation is presented, and the performance of the system is analyzed and evaluated. The mechanism is based on a core set of constructs that characterize object-based database systems. The approach provides a basis for controlled sharing in a heterogeneous database environment, using a kernel object-base model as an intercomponent exchange forum. A major goal is to make the importation of nonlocal information as transparent to a component as possible.>

An approach to accommodating semantic heterogeneity in a federation of interoperable, autonomous, heterogeneous databases is presented. A mechanism is described for identifying and resolving semantic heterogeneity while at the same time honoring the autonomy of the database components that participate in the federation. A minimal, common data model is introduced as the basis for describing sharable information, and a three-pronged facility for determining the relationships between information units (objects) is developed. Our approach serves as a basis for the sharing of related concepts through (partial) schema unification without the need for a global view of the data that is stored in the different components. The mechanism presented here can be seen in contrast with more traditional approaches such as “integrated databases” or “distributed databases”. An experimental prototype implementation has been constructed within the framework of the Remote-Exchange experimental system.

We present an analytical formula for estimating the cardinality of the projection on certain attributes of a subset of a relation in a relational database. This formula takes into account a priori knowledge of the semantics of the real-world objects and relationships that the database is intended to represent. Experimental testing of the formula shows that it has an acceptably low percentage error, and that its worst-case error is smaller than the best-known formula. Furthermore, the formula presented here has the advantage that it does not require a scan of the relation.

The 3-Dimensional Information Space (3DIS) is an extensible object-oriented framework for information management. It is specifically oriented toward supporting the database requirements for data-intensive information system applications in which (1) information objects of various levels of abstraction and modalities must be accommodated, (2) descriptive and structural information (metadata) is rich and dynamic, and (3) users who are not database experts must be able to design, manipulate, and evolve databases. In response to these needs, the 3DIS provides an approach in which data and the descriptive information about data are handled uniformly in an extensible framework. The 3DIS provides a simple, geometric, and formal representation of data which forms a basis for understanding, defining, and manipulating databases. Several prototype implementations based upon the 3DIS have been designed and implemented and are in experimental use.

An approach to the coordinated sharing and interchange of computerized information is described emphasizing partial, controlled sharing among autonomous databases. Office information systems provide a particularly appropriate context for this type of information sharing and exchange. A federated database architecture is described in which a collection of independent database systems are united into a loosely coupled federation in order to share and exchange information. A federation consists of components (of which there may be any number) and a single federal dictionary. The components represent individual users, applications, workstations, or other components in an office information system. The federal dictionary is a specialized component that maintains the topology of the federation and oversees the entry of new components. Each component in the federation controls its interactions with other components by means of an export schema and an import schema. The export schema specifies the information that a component will share with other components, while the import schema specifies the nonlocal information that a component wishes to manipulate. The federated architecture provides mechanisms for sharing data, for sharing transactions (via message types) for combining information from several components, and for coordinating activities among autonomous components (via negotiation). A prototype implementation of the federated database mechanism is currently operational on an experimental basis.

A model and methodology for describing the information objects in an office information system and how such objects flow among the components of such a system are presented. The model and methodology support the specification of information objects at multiple levels of abstraction. An interactive prototype design tool based on the methodology and model has been designed and experimentally implemented.

A simple model for object sharing in distributed office information systems is described.The model provides a small set of operators for object definition, manipulation, and retrieval in a distributed environment, modeled as a logical network of workstations.Relationships among objects can be established across work station boundaries, objects are relocatable within the distributed environment, and mechanisms are provided for access control and the dynamic sharing of objects among individual work stations.An object naming convention supports location-transparent object references; that is, objects can be referenced by user-defined names rather than by addresses.The primitive operations introduced can be used as the basis for the specification and stepwise development of office information models and systems of increasing complexity.An experimental prototype implementation of the distributed object sharing model is described.

No abstract available.

SDM is a high-level semantics-based database description and structuring formalism (database model) for databases. This database model is designed to capture more of the meaning of an application environment than is possible with contemporary database models. An SDM specification describes a database in terms of the kinds of entities that exist in the application environment, the classifications and groupings of those entities, and the structural interconnections among them. SDM provides a collection of high-level modeling primitives to capture the semantics of an application environment. By accommodating derived information in a database structural specification, SDM allows the same information to be viewed in several ways; this makes it possible to directly accommodate the variety of needs and processing requirements typically present in database applications. The design of the present SDM is based on our experience in using a preliminary version of it. SDM is designed to enhance the effectiveness and usability of database systems. An SDM database description can serve as a formal specification and documentation tool for a database; it can provide a basis for supporting a variety of powerful user interface facilities, it can serve as a conceptual database model in the database design process; and, it can be used as the database model for a new kind of database management system.

Conventional data models are not satisfactory for modelling data base application systems. The features that they provide are too low level and representational to allow the semantics of a data base to be directly expressed in the schema. The semantic data model (SDM) has been designed as a natural application modelling mechanism that can capture and express the structure of an application environment. The features of the SDM correspond to the principal intensional structures naturally occurring in contemporary data base applications. Furthermore, facilities for expressing derived (redundant) information are an essential part of the SDM; derived information is as prominent in an SDM schema as is primitive data. The SDM is designed to enhance the effectiveness and usability of computerized data bases. It can serve as a formal specification and documentation mechanism for a data base, can support a variety of powerful user interface facilities, and can be used as a tool in the data base design process.

As a model of some aspect(s) of the real world, the data in a data base must be accurate. In the context of a relational data base system, a facility to allow the expression and enforcement of a set of semantic integrity constraints is discussed. Semantic integrity constraints may describe properties of and relationships between data objects (in a relational data base) that are to hold (state snapshot constraints). Constraints may also place limitations on permissible data base operations (state transition constraints).