Diverse types of edge data, such as 2D geo-locations and 3D point clouds, are collected by sensors like lidar and GPS receivers on edge devices. On-device searches, such as k-nearest neighbor (kNN) search and radius search, are commonly used to enable fast analytics and learning technologies, such as k-means dataset simplification using kNN. To maintain high search efficiency, a representative approach is to utilize a balanced multi-way KD-tree (BMKD-tree). However, the index has shown limited gains, mainly due to substantial construction overhead, inflexibility to real-time insertion, and inconsistent query performance. In this paper, we propose UnIS to address the above limitations. We first accelerate the construction process of the BMKD-tree by utilizing the dataset distribution to predict the splitting hyperplanes. To make the continuously generated data searchable, we propose a selective sub-tree rebuilding scheme to accelerate rebalancing during insertion by reducing the number of data points involved. We then propose an auto-selection model to improve query performance by automatically selecting the optimal search strategy among multiple strategies for an arbitrary query task. Experimental results show that UnIS achieves average speedups of 17.96x in index construction, 1.60x in insertion, 7.15x in kNN search, and 1.09x in radius search compared to the BMKD-tree. We further verify its effectiveness in accelerating dataset simplification on edge devices, achieving a speedup of 217x over Lloyd's algorithm.

The$k$-means algorithm can simplify large-scale spatial vectors, such as 2D geo-Locations and 3D point clouds, to support fast analytics and learning. However, when processing large-scale datasets, existing$k$-means algorithms have been developed to achieve high performance with significant compu-tational resources, such as memory and CPU usage time. These algorithms, though effective, are not well-suited for resource-constrained devices. In this paper, we propose a fast, memory-efficient, and cost-predictable$k$-means called Dask-means. We first accelerate$k$-means by designing a memory-efficient accelerator, which utilizes an optimized nearest neighbor search over a memory-tunable index to assign spatial vectors to clusters in batches. We then design a lightweight cost estimator to predict the memory cost and runtime of the k-means task, allowing it to request appropriate memory from devices or adjust the accelerator's required space to meet memory constraints, and ensure sufficient CPU time for running k-means. Experiments show that when simplifying datasets with scale such as$10^{6}$, Dask-means uses less than 30MB of memory, and achieves over 168 times speedup compared to the widely-used Lloyd's algorithm. We also validate Dask-means on mobile devices, where it demonstrates significant speedup and low memory cost compared to other state-of-the-art (SOTA)$k$-means algorithms. Our cost estimator achieves a memory cost estimation error with a difference of less than 3% from the actual ones and an MSE for predicted runtime at least 52.1 % lower than SOTA methods.

Vector set search, an underexplored similarity search paradigm, aims to find vector sets similar to a query set. This search paradigm leverages the inherent structural alignment between sets and real-world entities to model more fine-grained and consistent relationships for diverse applications. This task, however, faces more severe efficiency challenges than traditional single-vector search due to the combinatorial explosion of pairings in set-to-set comparisons. In this work, we aim to address the efficiency challenges posed by the combinatorial explosion in vector set search, as well as the curse of dimensionality inherited from single-vector search. To tackle these challenges, we present an efficient algorithm for vector set search, BioVSS (Bio-inspired Vector Set Search). BioVSS simulates the fly olfactory circuit to quantize vectors into sparse binary codes and then designs an index based on the set membership property of the Bloom filter. The quantization and indexing strategy enables BioVSS to efficiently perform vector set search by pruning the search space. Experimental results demonstrate over 50 times speedup compared to linear scanning on million-scale datasets while maintaining a high recall rate of up to 98.9%, making it an efficient solution for vector set search.

With the development of modern cloud platforms, an increasing number of users are migrating their data analysis tasks to the cloud. Cloud platforms offer a “pay-as-you-go” model, prompting users to focus on both performance and resource costs. Existing query optimization methods primarily address query performance while neglecting resource costs. Mapping queries to their resource consumption is a complex task. To tackle this challenge, we propose a novel learning-based query resource recommendation method called LORE. LORE efficiently and accurately estimates the optimal resources for queries by leveraging dual information from SQL query statements and query execution plans. We model SQL queries and execution plans as directed acyclic graphs and utilize graph neural networks to derive comprehensive representations. To capture the dependencies among all nodes involved in data transmission within an execution plan, we assign path weights to the dependency edges of each node. Our approach integrates data distribution information and captures both direct and indirect dependencies among plan nodes while avoiding unnecessary redundant computations. Experimental results demonstrate that, compared to traditional and other learning-based methods, the LORE model achieves higher accuracy in predicting the optimal resources for queries.

The search for joinable data is pivotal for numerous applications, such as data integration, data augmentation, and data analysis. Although there have been many successful joinable search studies for table discovery, the study of finding joinable spatial datasets for a given query from multiple spatial data sources has not been well considered. This paper studies two cases of joinable search problems from multiple spatial data sources. In addition to the overlap joinable search problem (OJSP), we also propose a novel coverage joinable search problem (CJSP) that has not been considered before, motivated by many real-world applications in the field of spatial search. To support two cases of joinable search over multiple spatial data sources seamlessly, we propose a multi-source spatial dataset search framework. Firstly, we design a DIstributed Tree-based Spatial index structure called DITS, which is used not only to design acceleration strategies to speed up joinable searches, but also to support efficient communication between multiple data sources. Additionally, we prove that the CJSP is NP-hard and design a greedy approximate algorithm to solve the problem. We evaluate the efficiency of our search framework on five real-world data sources, and the experimental results show that our framework can significantly reduce running time and communication costs compared with baselines.

Abstract In the digital age, social networks have become critical platforms for information dissemination, but they also pose significant risks due to the rapid spread of rumors and misinformation. Existing approaches to rumor control often rely on models that assume a single exposure to anti-rumor information is sufficient to mitigate its impact, overlooking the necessity of multiple impressions for effective behavior change. In this work, we address the Rumor Control with Impression Counts problem by proposing the first-ever Machine Learning (ML)-based solution. Our approach leverages Graph Neural Networks combined with a greedy algorithm to efficiently manage large-scale social networks. To further enhance computational efficiency, we incorporate Evolutionary Optimization, resulting in a method that not only addresses the effectiveness challenges but also scales efficiently with network size. Extensive experiments on real-world datasets demonstrate that our approach outperforms existing methods in both effectiveness and scalability, improving computational efficiency by 1 to 2 orders of magnitude.

Balanced k -means ensures representative centroids by forming equal-sized clusters, but struggles with slow clustering of massive distributed attributes and data-sharing restrictions. A common approach is adapting it to a vertical federated learning (VFL) framework, preventing raw data exposure by only intermediate result exchange and accelerating clustering via parallelism, yet it remains unexplored. In this paper, we propose a time-efficient, federated, and balanced k -means algorithm, called Teb-means, to bridge the gap. We first formulate the balanced k -means problem as a trace maximization problem (TMP) and propose an efficient coordinate-wise optimization (CO) scheme to solve it. We then integrate TMP and CO into the VFL framework by demonstrating that TMP can be decomposed into multiple subproblems based on each party's data, which can be solved using CO while exchanging only intermediate results. Notably, we build a trade-off between utility and communication efficiency by designing a greedy block-based strategy for CO (GBCO). Our theoretical analysis shows that Teb-means achieves linear time complexity on each client, and our communication round is constant in the mild condition. Experiments show that Teb-means is on average 12.18× faster than other balanced clustering algorithms that can be federated, while achieving better balance without disrupting the cluster structure.

This paper studies the problem of fair clustering on heterogeneous information networks (HINs) by considering constraints on structural and sensitive attributes. We propose a Prerequisite-driven Fair Clustering (PDFC ) algorithm to solve this problem. Specifically, we define the structural constraint on the connection among nodes in HINs by combining meta-paths and prerequisite meta-paths and introduce Fairlets as the balance constraint. Under two constraints, we learn node embeddings based on graph models and perform theCholesky decomposition to obtain their orthogonal embeddings. We fuse node embeddings under constraints, define the loss function of PDFC, and perform k-means to achieve clustering. In addition, we design an update strategy of the adjacency matrix to achieve dynamic PDFC over time. Compared with several fair clustering algorithms on three real-world datasets, our experimental results verify the effectiveness and efficiency of PDFC.

This paper proposes a federated, fair, and fast k-means algorithm (F3KM) to solve the fair clustering problem efficiently in scenarios where data cannot be shared among different parties. The proposed algorithm decomposes the fair k-means problem into multiple subproblems and assigns each subproblem to a client for local computation. Our algorithm allows each client to possess multiple sensitive attributes (or have no sensitive attributes). We propose an in-processing method that employs the alternating direction method of multipliers (ADMM) to solve each subproblem. During the procedure of solving subproblems, only the computation results are exchanged between the server and the clients, without exchanging the raw data. Our theoretical analysis shows that F3KM is efficient in terms of both communication and computation complexities. Specifically, it achieves a better trade-off between utility and communication complexity, and reduces the computation complexity to linear with respect to the dataset size. Our experiments show that F3KM achieves a better trade-off between utility and fairness than other methods. Moreover, F3KM is able to cluster five million points in one hour, highlighting its impressive efficiency.

One key property in recommender systems is the long-tail distribution in user-item interactions where most items only have few user feedback. Improving the recommendation of tail items can promote novelty and bring positive effects to both users and providers, and thus is a desirable property of recommender systems. Current novel recommendation methods over-emphasize the importance of tail items without differentiating the degree of users’ intent on popularity and often incur a sharp decline of accuracy. Moreover, none of existing studies has ever taken the extreme case of tail items, i.e., cold-start items without any interaction, into consideration. In this work, we first disclose the mechanism that drives a user's interaction towards popular or niche items by disentangling her intent into conformity influence (popularity) and personal interests (preference). We then present a unified end-to-end framework to simultaneously optimize accuracy and novelty targets based on the disentangled intent of popularity and that of preference. We further develop a new paradigm for novel recommendation of cold-start items which exploits the self-supervised learning technique to model the correlation between collaborative features and content features. We conduct extensive experiments on three real-world datasets. The results demonstrate that our proposed model yields significant improvements over the state-of-the-art baselines in terms of the trade-off between accuracy and novelty.

In this paper, we would like to demonstrate a personal trajectory management system called Motorch, which allows users to manage their trajectories and enables risk analytics based on a lightweight similarity measure called LCTS. At the back end, a web crawler collects the desensitized COVID-19 cases information from data sources (news, social media, etc.) and pushes them to Elasticsearch for storage after data cleaning. At the front end, Motorch implements a set of operations including data collection, data preprocessing, indexing, storage, and visualization in a mobile application. Motorch aims to help individuals manipulate their data and evaluate personal risk without uploading data to a server.

The efficiency of query processing is highly affected by execution plans and allocated resources in the Spark SQL big data processing engine. However, the cost models for Spark SQL are still based on hand-crafted rules. The learning-based cost models have been proposed for relational databases, but it does not consider the effect of the available resources. To address this, we propose a resource-aware deep learning model that can automatically predict the execution time of query plans based on historical data. To train our model, we embed the query execution plans based on the query plan tree and extract features from the allocated resources. A deep learning model with adaptive attention mechanisms is then trained to predict the execution time of query plans. The experiments show that our deep cost model can achieve higher accuracy in predicting the execution time of query plans compared to traditional rule-based methods and relational database learning-based optimizers.

Recently, the topic of learning concept prerequisite relations has gained the attention of many researchers, which is crucial in the learning process for a learner to decide an optimal study order. However, the existing work still ignores three key factors. (1) People's cognitive differences could make a difference for annotating the prerequisite relation between resources (e.g., courses, textbooks) or concepts (e.g., binary tree). (2) The current vertex (resources or concepts) can be affected by the feature of the neighbor vertex in the resource or concept graph. (3) The feature information of the resource graph may affect the concept graph. To integrate the above factors, we propose an end-to-end graph network-based model called Multi-Head Attention Variational Graph Auto-Encoders (MHAVGAE ) to learn the prerequisite relation between concepts via a resource-concept graph. To address the first two problems, we introduce the multi-head attention mechanism to operate and compute the hidden representations of each vertex over the resource-concept graph. Then, we design a gated fusion mechanism to integrate the feature information of the resource and concept graphs to enrich concept content features. Finally, we conduct numerous experiments to demonstrate the effectiveness of the MHAVGAE across multiple widely used metrics compared with the state-of-the-art methods. The experimental results show that the performance of the MHAVGAE almost outperforms all the baseline methods.

The amount of spatial data in open data portals has increased rapidly, raising the demand for spatial dataset search in large data repositories. In this paper, we tackle spatial dataset search by using the Earth Mover's Distance (EMD) to measure the similarity between datasets. EMD is a robust similarity measure between two distributions and has been successfully applied to multiple domains such as image retrieval, document retrieval, multimedia, etc. However, the existing EMD-based studies typically depend on a common filtering framework with a single pruning strategy, which still has a high search cost. To address this issue, we propose a Dual-Bound Filtering (DBF) framework to accelerate the EMD-based spatial dataset search. Specifically, we represent datasets by Z-order histograms and organize them as nodes in a tree structure. During a query, two levels of filtering are conducted based on pooling-based bounds and a TICT bound on EMD to prune dissimilar datasets efficiently. We conduct experiments on four real-world spatial data repositories and the experimental results demonstrate the efficiency and effectiveness of our DBF framework.

Reorganizing bus frequencies to cater for the actual travel demands can significantly save the cost of the public transport system. Many, if not all, previous studies formulate this as a bus frequency optimization problem that tries to minimize passengers’ average waiting time. On the other hand, many investigations have confirmed that the user satisfaction drops faster as the waiting time increases. Consequently, this paper studies the bus frequency optimization problem considering the user satisfaction. Specifically, for the first time to our best knowledge, we study how to schedule the buses such that the total number of passengers who could receive their bus services within the waiting time threshold can be maximized. We propose two variants of the problem, FAST and FASTCO, to cater for different application needs and prove that both are NP-hard. To solve FAST effectively and efficiently, we first present an index-based$(1-1/e)$-approximation algorithm. By exploiting the locality property of routes in a bus network, we further propose a partition-based greedy method that achieves a$(1-\rho)(1-1/e)$approximation ratio. Then we propose a progressive partition-based greedy method to further boost the efficiency while achieving a$(1-\rho)(1-1/e-\varepsilon)$approximation ratio. For the FASTCO problem, two greedy-based heuristic methods are proposed. Experiments on a real city-wide bus dataset in Singapore have been conducted to verify the efficiency, effectiveness, and scalability of our methods in addressing FAST and FASTCO respectively.

Abstract Motivated by the application of viral marketing , the topic-aware influence maximization (TIM) problem has been proposed to identify the most influential users under given topics. In particular, it aims to find k seeds (users) in social network G , such that the seeds can maximize the influence on users under the specific query topics and diffusion model such as independent cascade (IC) or linear threshold (LT). This problem has been proved to be NP-hard, and most of the proposed techniques suffer from the efficiency issue due to the lack of generalization. Even worse, the design of these algorithms requires significant specialized knowledge which is hard to be understood and implemented. To overcome these issues, this paper aims to learn a generalized heuristic framework to solve TIM problems by meta-learning. To this end, we first propose two topic-aware social influence propagation models based on IC and LT model, respectively, which is conducive to better advertising injections. We then encode the feature of each node by a vector and introduce a model, called deep influence evaluation model , to evaluate the user influence under different circumstances. Based on this model, we can construct the solution according to the influence evaluations efficiently, rather than spending a high cost to compute the exact influence by considering the complex graph structure. We conducted experiments on generated graph instances and real-world social networks. The results show the superiority in performance and comparable quality of our framework.

In this paper, we demonstrate a satisfaction-boosting bus scheduling assistant called FASTS, which assists users to find an optimal bus schedule. FASTS performs bus scheduling based on the constraints specified by the user in either a coarse-grained or a fine-grained manner, supports different explorations with a varying number of constraints, and provides analysis to quantify the performance of bus schedules and presents the results in a visually pleasing way. We demonstrate FASTS using real-world bus routes (396 routes) and one-week bus touch-on/touch-off records (28 million trip records) in Singapore.

In this paper, we propose and study a new problem called the weighted random walk domination. Given a weighted graph G ( V, E ) and a budget B of the weighted random walk, it aims to find a k -size set S , which can minimize the total costs of the remaining nodes to access S through the weighted random walk, which is bounded by B. This problem is critical to a range of real-world applications, such as advertising in social networks and telecommunication base station selection in wireless sensor networks. We first present a dynamic programming based greedy method (DpSel) as a baseline. DpSel is time-consuming when | V | is huge. Thus, to overcome this drawback, we propose a matrix-based greedy method (MatrixSel), which can reduce the computation cost greatly. To further accelerate MatrixSel, we propose a BoundSel approach to reduce the number of the gain computations in each candidate selection by proactively estimating the upper bound of the marginal gain of the candidate node. Notably, all methods can achieve an approximation ratio of (1 - 1/ e ). Experiments on real datasets have been conducted to verify the efficiency, effectiveness, memory consumption and scalability of our methods.

In this article, we propose and study the problem of trajectory-driven influential billboard placement: given a set of billboards U (each with a location and a cost), a database of trajectories T , and a budget L , we find a set of billboards within the budget to influence the largest number of trajectories. One core challenge is to identify and reduce the overlap of the influence from different billboards to the same trajectories, while keeping the budget constraint into consideration. We show that this problem is NP-hard and present an enumeration based algorithm with (1-1/e) approximation ratio. However, the enumeration would be very costly when | U | is large. By exploiting the locality property of billboards’ influence, we propose a partition-based framework PartSel. PartSel partitions U into a set of small clusters, computes the locally influential billboards for each cluster, and merges them to generate the global solution. Since the local solutions can be obtained much more efficiently than the global one, PartSel would reduce the computation cost greatly; meanwhile it achieves a non-trivial approximation ratio guarantee. Then we propose a LazyProbe method to further prune billboards with low marginal influence, while achieving the same approximation ratio as PartSel. Next, we propose a branch-and-bound method to eliminate unnecessary enumerations in both PartSel and LazyProbe, as well as an aggregated index to speed up the computation of marginal influence. Experiments on real datasets verify the efficiency and effectiveness of our methods.

In this paper we propose and study the problem of trajectory-driven influential billboard placement: given a set of billboards $\ur$ (each with a location and a cost), a database of trajectories $\td$ and a budget $\budget$, find a set of billboards within the budget to influence the largest number of trajectories. One core challenge is to identify and reduce the overlap of the influence from different billboards to the same trajectories, while keeping the budget constraint into consideration. We show that this problem is NP-hard and present an enumeration based algorithm with $(1-1/e)$ approximation ratio. However, the enumeration should be very costly when $|\ur|$ is large. By exploiting the locality property of billboards' influence, we propose a partition-based framework \psel. \psel partitions $\ur$ into a set of small clusters, computes the locally influential billboards for each cluster, and merges them to generate the global solution. Since the local solutions can be obtained much more efficient than the global one, \psel should reduce the computation cost greatly; meanwhile it achieves a non-trivial approximation ratio guarantee. Then we propose a \bbsel method to further prune billboards with low marginal influence, while achieving the same approximation ratio as \psel. Experiments on real datasets verify the efficiency and effectiveness of our methods.

The recorded student activities in Massive Open Online Course (MOOC) provide us a unique opportunity to model their learning behaviors, identify their particular learning intents, and enable personalized assistance and guidance in online education. In this work, based on a thorough qualitative study of students' behaviors recorded in two MOOC courses with large student enrollments, we develop a non-parametric Bayesian model to capture students' sequential learning activities in a generative manner. Homogeneity of students' learning behaviors is captured by clustering them into latent student groups, where shared model structure characterizes the transitional patterns, intensity and temporal distribution of their learning activities. In the meanwhile, heterogeneity is captured by clustering students into different groups. Both qualitative and quantitative studies on those two MOOC courses confirmed the effectiveness of the proposed model in identifying students' learning behavior patterns and clustering them into related groups for predictive analysis. The identified student groups accurately predict student retention, course satisfaction and demographics.

Providing personalized high quality community recommendation for Web community members has become increasingly important. Traditional collaborative filtering methods based on explicit topic associations cannot solve the information sparsity problem. The recommendation methods based on latent topic association results in inaccurate results. To solve the above problems, we propose a collaborative Web community recommendation algorithm based on latent topic. Our algorithm generates the latent link between communities and members using latent topic associations to overcome the sparsity problem. Our algorithm also reduces inaccurate results by combining similar members' behaviors and interests. The experiment indicates that our recommendation algorithm has higher recommendation accuracy than traditional methods.

Patents are public and scientific literatures protected by the law, and their abstracts highly contained valuable information. Patent's semantic annotation can effectively protect intellectual property rights and promote corporations' scientific research innovation. Currently, automatic patent annotation mainly used supervised machine learning algorithms, which required abundant expensive labeled patent data. Due to lack of enough labeled Chinese patent data, this paper adopted a semi-supervised machine learning method named co-training, which started from a little labeled data. This method combined keyword extraction with list extraction, and incrementally annotated functional clauses in patent abstract. Experiment results indicated this method can gradually improve the recall without sacrificing the precision.

With the rapid development of Web technology, more and more data on the web are considered as the source of information in current society. However, as the qualities of data fetched from different sources are different, it takes a lot of time to search the valuable data from tremendous web information. This paper proposed an approach to evaluate the data quality through integrating all dimensions of data representations. The evaluation of weight is estimated by the scores for data quality provided by users, which results in that the search results sorted by data quality can achieve the requirements of users. This method has been applied in a microbe system.

With the rapid growing of data on Web, we are facing three serious problems. Firstly, there are a huge number of data resources which are heterogeneous and dynamic.Secondly, most of data on Web are unstructured. Thirdly, there are various kinds of Web users who have different interests and requirements. In this paper, we proposed a new system architecture for unstructured data management on Web to solve these problems by integrating data spaces, database and meta search engine. The system architecture consists of three layers for data gathering on demand, dynamic management and personalized service, respectively. Data servicing layer allows Web users to create data spaces with advanced functions to manipulate and access Web data, eg, cross media query and automatic recommendation. Data managing layer models both Web data and their semantic relationships using our object deputy database named as TOTEM; it also supports schema evolution and dynamic classification. Data gathering layer extracts user's interest from his or her data space; gathers the related data on Web and further analyzes their semantic relationships. Finally, we implemented a prototype system Tmusic based on this new system architecture to show its availability.

To improve query performance and space efficiency, an efficient random access blocked inverted index (RABI) is proposed. RABI divides an inverted list into blocks and compresses different part of each block with the corresponding encoding method to decrease space consumption. RABI can provide fast addressing and random access functions on the compressed blocked inverted index with the novel hybrid compression method, which can provide both block level and inner block level skipping function and further enhance both space and time efficiencies without inserting any additional auxiliary information. Experimental results show that RABI achieves both high space efficiency and search efficiency, and outperforms the existing approach significantly.

Multi-representation geographic information system (GIS) is used to store and manage geographic objects with different scales and semantics. It is difficult for relational and object-oriented databases to support multi-representation GIS. This paper proposed a new approach to realize multi-representation GIS using our object deputy database, where an object can have multiple deputy objects which inherit attributes and methods of the source object and can have their own attributes and methods. Multi-representations of a geographic object are defined by its deputy objects. So deputy objects can be used to represent viewpoint-multiplicity and role-multiplicity of geographic objects. Dynamic classification and automatic consistency maintenance of geographic objects can be supported through the update propagation mechanism of our object deputy database. In addition, the bilateral links between a geographic object and its deputy objects make cross-representation query easier. We have implemented a multi-representation GIS based on our object deputy database. Experiments show our method is more efficient than the traditional ones.

Providing integrated access to multiple, distributed, heterogeneous databases and other information sources has become one of the leading issues in database research and the industry. One of the most effective approaches is to extract and integrate information of interest from each source in advance and store them in a centralized repository (known as a data warehouse). When a query is posed, it is evaluated directly at the warehouse without accessing the original information sources. One of the techniques that this approach uses to improve the efficiency of query processing is materialized view(s). Essentially, materialized views are used for data warehouses, and various methods for relational databases have been developed. In this paper, we first discuss an object deputy approach to realize materialized object views for data warehouses which can also incorporate object-oriented databases. A framework has been developed using Smalltalk to prepare data for data warehousing, in which an object deputy model and database connecting tools have been implemented. The object deputy model can provide an easy-to-use way to resolve inconsistency and conflicts while preparing data for data warehousing, as evidenced by our empirical study.

In conventional computer supported cooperative work (CSCW) systems, usually only one video-based environment is shared by all the users. In this paper, we show that multiple environments are required and they can be realized by utilizing object-oriented database technology. A cooperative work environment can be regarded as a room where users work together by sharing documents and equipment through available communication facilities. In one environment, users, documents and equipment are handled as objects, and these different types of objects have some attributes and methods in common, such as location attributes and layout methods. However, using the existing concepts of the conventional object-oriented model, such as classes, complex objects and collection objects, it is difficult to define one environment: namely, a set with different types of elements but having some attributes and methods in common. The object deputy model, introduced by the authors, can be extended to formulate such environments. Since the object deputy model can uniformly handle object views, roles, migration and multiple inheritance, we can realize flexible, dynamic and powerful environments based on object-oriented databases.

Concepts of deputy objects and deputy classes for object-oriented databases (OODBs) are introduced. They can be used for unified realization of object views, roles and migration. The previous researches on these concepts were carried out separately, although they are very closely related. Objects appearing in a view can be regarded as playing roles in that view. Object migration is caused by change of roles of an object. Deputy objects can be used for unified treatment of them and generalization of these concepts. The schemata of deputy objects are defined by deputy classes. A set of algebraic operations are developed for deputy class derivation. In addition, three procedures for update propagation between deputy objects and source objects have been designed, which can support dynamic classification. The unified realization of object views, roles and migration by deputy mechanisms can achieve the following advantages. (1) Treating view objects as roles of an object allows them to have additional attributes and methods so that the autonomous views suitable for OODBs can be realized. (2) Handling object roles in the same way as object views enables object migration to be easily realized by dynamic classification functions of object views. (3) Generalization of object views, roles and migration makes it possible that various semantic constraints on them can, be defined and enforced uniformly.>