Regular path queries (RPQs) find pairs of vertices of paths satisfying given regular expressions on an edge-labeled, directed multigraph. When evaluating an RPQ, the evaluation of a Kleene closure is very expensive. Furthermore, when multiple RPQs include a Kleene closure as a common sub-query, repeated evaluations of the common sub-query cause serious performance degradation. In this paper, we present a novel concept of RPQ-based graph reduction, which significantly simplifies the original graph through edge-level and vertex-level reductions. Interestingly, RPQ-based graph reduction can replace the evaluation of the Kleene closure on the large original graph to that of the transitive closure to the small reduced graph. We then propose a reduced transitive closure (RTC) as a lightweight structure for efficiently sharing the result of a Kleene closure. We also present an RPQ evaluation algorithm, RTCSharing, which treats each clause in the disjunctive normal form of the given RPQ as a batch unit. If the batch units include a Kleene closure as a common sub-query, we share the lightweight RTC instead of the heavyweight result of the Kleene closure. RPQ-based graph reduction further enables us to formally represent the result of an RPQ including a Kleene closure as a relational algebra expression including the RTC. Through the formal expression, we optimize the evaluation of the batch unit by eliminating useless and redundant operations of the previous method. Experiments show that RTCSharing improves the performance significantly by up to 73.86 times compared with existing methods in terms of query response time.

Abstract This study proposes an efficient exact k-flexible aggregate nearest neighbor (k-FANN) search algorithm in road networks using the M-tree. The state-of-the-art IER-kNN algorithm used the R-tree and pruned off unnecessary nodes based on the Euclidean coordinates of objects in road networks. However, IER-kNN made many unnecessary accesses to index nodes since the Euclidean distances between objects are significantly different from the actual shortest-path distances between them. In contrast, our algorithm proposed in this study can greatly reduce unnecessary accesses to index nodes compared with IER-kNN since the M-tree is constructed based on the actual shortest-path distances between objects. To the best of our knowledge, our algorithm is the first exact FANN algorithm that uses the M-tree. We prove that our algorithm does not cause any false drop. In conducting a series of experiments using various real road network datasets, our algorithm consistently outperformed IER-kNN by up to 6.92 times.

Coverage maximization is an important issue of Mobile wireless sensor networks (M-WSN). Especially for visual sensors like video camera which have a specific sensing direction and range, obstacles and the position of the sensors should also be considered. In this paper, we propose an efficient coverage maximization method for mobile video camera networks by leveraging DQN, a deep reinforcement learning algorithm. Evaluation results show that the proposed method can cover up to 4.93% better than existing ones.

Unmanned Aerial Vehicles (UAVs) are gaining more popularity thanks to their versatility, miniaturization, and inexpensiveness. Beyond the limits of single UAV system, multi-UAV systems which can perform complex missionoriented tasks better have been recently introduced. However, previous systems are less automated in the way that human intervention is still required to execute missions, and they were implemented for the only purpose of carrying out specific scenarios. In this paper, in order to automate the required procedures in the system and increase system flexibility, we propose a control integrated query processing system for coordination of multiple UAVs. We devise a high level query language to express a user command for a variety of UAVs' tasks by integrating the ways of controlling movements and actions of multiple UAVs and collecting data from them. We present the overall architecture of the query processing system and experimental results on testbed using real UAVs.

The proliferation of the Internet into every household has provided more opportunities for residents to become closer to each other than before. However, solid structural barrier is raised and social relationships within such neighborhoods are weak compared to those in traditional towns. Accordingly, activating communities and ultimately enhancing a sense of community through constructive participation and communal sharing of labor among residents has currently emerged as a challenging issue in a contemporary housing complex. In an effort to activate those communities, a notion of smart community is presented in which multiple smart homes are equipped with Internet of Things and interconnected with each other. Beyond the unadorned smart community composed by physical proximity, it is essential to discover a human-centric community that achieves communal benefits and enables residents to maximize individual economic gain by leveraging collective intelligence. In this article, we present a multi-dimensional smart community discovery scheme that enables householders to find human-centric community considering multi-dimensional factors in terms of physical, social, and economical aspects. We conduct experiments with 30 real households by applying a community-based energy saving scenario. Experiment results show that the proposed scheme performs better when compared to the physical proximity-based one in energy consumption and user satisfaction.

We present a generic framework for group activity recognition using simple non-obtrusive sensors. The proposed scheme is based on that group activity patterns can be derived from mining interval-based relationships between users' temporally overlapped actions. We leverage a hybrid architecture of probabilistic and logic knowledge that can capture the essence of the temporal dependencies, represented as a set of weighed rules. It can also learn different weights for common rules between similar group activities, which share most of sensor events and events order. The evaluation results show that our scheme outperforms the sequential baseline model, a mixture of Gaussian Hidden Markov Models.

The combination of online social networking services (OSNSs) and the smartphones has changed the ways to acquire information and also influenced the ways people get to know and interact with each other. Despite with many advanced functions, online social interactions can hardly provide online social users with real-world (i.e., offline) social interactions. In this paper, we present an offline friend recommendation system for the OSNS users to have more serendipitous offline interactions. For that, we modeled both offline information (i.e., place visit history) and online social data (i.e., friend relationships) for recommending their offline interactions. Our system discovers those who seems most likely to have potential friend relationship so as to meet in the physical world. We present the design and implementation of our proposed system and conduct real-world experiment to show how the place visit information and online friend relationship together produce a new offline social networking service.

Since the Web of Things (WoT) term was first proposed, there has a big trend in IT vendors providing users with various services through their smart products. To enable users to discover and leverage these services, SDPs play an important role. However, so many variations of SDPs have been introduced it has caused a heterogeneity issue. Including standardization, many solutions have been proposed, but they require too much overhead or have practicality issues. In this paper, we propose a system composed of fundamental building blocks, including a knowledge base and probing packets to address this issue. We evaluate the performance of our system by conducting real world experiments using smart object services in a local network. The experiment results show that Sherlock-SD identifies up to 92% of target services correctly only with 3 probing packets out of 6 in the best case, without any of the overhead that existing solutions impose. In terms of resource consumption overhead, compared to 4 SDPs enumeration, Sherlock-SD requires 67.6% of the memory and consumes 30.7% of power.

This paper presents a distributed smart home middleware where each appliance is able to learn user behavior and customize their actions by themselves as well as cooperate with other appliances through a more light-weight smart home gateway. As the key components, we present a knowledge base which describes common- and appliance-specific concepts in a smart home domain, and design libraries for smart appliances and a smart home gateway. We implement the proposed middleware on our testbed and conduct evaluations. The result shows that our scheme reduces the interaction time and the runtime memory allocation.

In this paper, we present an opportunistic service recommendation scheme in a place with smart objects to provide users with appropriate composite services to accomplish their task goals. The proposed scheme infers possible tasks from interactions that people have experienced with smart objects including other places that are similar to a given place. The proposed scheme then evaluates the candidate tasks by measuring quality satisfaction of each task against given QoS constraints. We test the proposed scheme on our three smart testbeds where various smart objects equipped. Experiment results show that the proposed scheme finds potential tasks in the testbeds in a reasonable time.

Indoor positioning and tracking services are garnering more attention. Recently, several state-of-the-art localization techniques have been proposed that use radio maps or the sensors readily available on smartphones. This paper presents a localization system called Indoor Localization using Physical maps and smartphone Sensors (ILPS), which is based on a building blueprint database and smartphone sensors. The blueprint database and access points (APs) provide a number of reference points that can be used to acquire the initial position and adjust the user position each time a reference point is detected. The proposed method is implemented on a smartphone and tested in real indoor environments. The experiments with ILPS demonstrate that using a static blueprint will avoid the costly database updates that are usually required in other approaches due to signal attenuation. Furthermore, ILPS performs better than existing work in term of accuracy and effectiveness for indoor localization.

Although the latest video codecs such as H.264/AVC, H.264/SVC, and VP8 were developed with network-friendly features, provisioning the quality of video delivery over IEEE 802.11 wireless networks is still challenging because of error-prone medium and random access. This paper evaluates the quality of video delivery using those latest video codecs over IEEE 802.11. Our results show that reduction of coded video data, consideration of the queue size of each Access Category, and the mandatory implementation of error recovery features in H.264/SVC can help provide robust multimedia transmission over IEEE 802.11. In addition, the performance of the latest video codecs is compared via extensive simulation scenarios. Our comparison shows that VP8 achieves good video quality with the basic medium access control techniques of IEEE 802.11, whereas H.264/AVC and H.264/SVC benefit significantly from appropriate mapping schemes between encoded video fragments and IEEE 802.11e Access Categories.

Uncovering user interest plays an important role to develop personalized systems in various fields including the Web and pervasive computing. In particular, online social networks (OSNs) are being spotlighted as the means to understand users' social behavior out of abundant online social information. In this paper, we explore a computational method of inferring user interest in Facebook by combining the degree of familiarity and topic similarity with social neighbors based on social correlation phenomenon. By conducting a question-naire survey, we demonstrate that our proposed method increases the accuracy of inference by 12.4% compared to existing methods which do not consider the latent topic structure implied in social contents.

Map services help people find places they wish to visit. Users input the target address and the system returns that location on a map, with additional information such as nearby points of interest, directions to the location, etc. However, these applications mainly focus on general knowledge, failing to provide personalized information that may help users find/identify a place faster. In this paper, we present a map application based on previous user knowledge. We represent two types of knowledge - spatial and social - in the form of a social-location ontology. This ontology is then used to present a destination based on places familiar to the user. By showing an unknown location in terms of a familiar place, we allow the user to find the target location with much briefer instructions. This is especially useful on mobile devices, in which the limited screen size restricts the amount of information that can be displayed. In order to adapt to new knowledge, the ontology evolves as the user visits new places and meets new people. Our evaluation shows that users prefer to have concrete information related to a destination for easier understanding.

Context data are updated frequently due to the dynamic changes of the various sensor values and the situations of application entities. Without a proper management, the stored contexts will become different from those of the real-world. Those invalid contexts will cause context inconsistency problems and thus should be eliminated at the right time and in an appropriate manner. In this paper, we propose a context inconsistency management scheme based on context elimination rules that describe the semantics of context invalidity to solve context inconsistency problems. The proposed rule-based scheme will enable users to easily specify elimination conditions for inconsistent contexts. Our performance evaluation shows that the rule processing overhead is compensated for by virtue of the well-maintained repository of the stored contexts.

In this paper, we propose QoS-constrained peer selection and nondisruptive rate adaptation schemes with considering shared bottleneck problem to provide a stable peer-to-peer live video streaming service during vertical handoff. In the proposed scheme, a QoS-constrained peer is selected by estimating bandwidth with active probing, and a reception rate converges to a stable state without any QoS degradation with help of multi-path handoff. The shared bottleneck problem is addressed by adjusting the estimated bandwidth and yielding the redundant bandwidth usage.

Abstract With the expansion of the internet and its bandwidth, distributed virtual environment (DVE) applications have become more prevalent. In DVE applications, users frequently crowd in a specific place, and a key aspect to consider is how to provide interactive performance for users. However, existing approaches using multicast require users to receive uninteresting messages. Even though recent works have addressed fine‐grained filtering, they still incur other drawbacks in terms of assigning lots of multicast addresses or handling overhead of multicast groups. This makes the system less scalable as the number of users increases. In this paper, we propose a new scalable filtering scheme that reduces not only the number of messages during interaction in a region and among neighboring regions, but also the number of multicast addresses without significant computational overhead. Interest management in a region dynamically creates groups of users with the same interests. While members communicate with each other with high fidelity, a representative sends information to non‐members with low frequency. For interaction among neighboring regions, we propose a sub‐region concept to select only a subset of users from the neighboring regions based on proximity, the distribution of the users' locations, and the viewing direction of a user. Copyright © 2007 John Wiley & Sons, Ltd.

In this paper, we propose a context-conflict management scheme for group-aware ubiquitous computing environments that allows context-aware applications to serve multiple users without distracting and sacrificing each other. The proposed scheme can detect semantic conflicts without explicit descriptions of the conflicts between different applications. Conflicts are resolved by a dynamically generated adaptation policy based on the weight value of user preference on each service. Individual context-aware applications can be reused without modification since middleware components for the context-conflict management take charge of detecting and resolving conflicts. Thus, the complicated context-conflict situation becomes more transparent to application programmers.

Shared sense of a virtual world is often enhanced by replicating the information at each user's site since replication provides acceptable interactive performance, especially when users are geographically distributed over large networks like the Internet. However, multiple concurrent updates may lead to inconsistent views among replicas. Therefore concurrency control is a key factor to maintaining a consistent state among replicas. We proposed a scalable prediction-based scheme in which an ownership request is multicasted to only the users surrounding a target entity. In our previous work, we assumed that all the users navigate a virtual world with a single speed. It, however, is quite common in a networked virtual environment like a network game that users are allowed to change their navigation speed as they interact with a virtual world for adding more realism. This paper proposes an enhancement to support users with various speeds. The enhanced scheme allows as many Entity Radii as the number of different speed and allocates a separate queue for users of each speed. Each queue is examined in parallel to predict the next owner candidate and among the selected candidates is chosen the final candidate, which has a minimum predicted collision time. It contributes to the timely advanced transfer of ownership by using appropriate Entity Radius based on a user's speed, fair granting of ownership by reducing the interference between users with different speed and latency, and high prediction accuracy by reducing the redundant ownership transfer.

We propose an enhanced prediction-based concurrency control scheme that supports the scalability of concurrency control for large distributed virtual environments especially where entities are highly populated and tend to gather closely. The prediction scheme is based on an entity-centric multicast group. Only the users surrounding a target entity multicast the ownership requests via an entity multicast group and become owner candidates. The current owner predicts the next owner among the owner candidates and sends an ownership to the next owner in advance. However, if entities are assigned their own multicast address when they are close to each other, users have to continuously issue join messages as moving by the entities. To reduce the network and message exchange overhead, we use the location proximity of entities in virtual environments. By grouping closely gathered entities into one entity group and sharing a multicast address among group member entities, we reduce the number of frequent join and leave operations and join messages, therefore maintain enough interactive performance. The experiment results show that the proposed mechanism improves scalability especially when entities are closely gathered.

This paper describes an object-oriented temporal association algebra (called TA-algebra) which is intended to serve as a formal foundation for supporting a pattern-based query specification and processing paradigm. Different from the traditional table-and-attribute-based paradigm, the pattern-based paradigm views the intension of an object-oriented temporal database as a network of object classes interconnected by different association types and its extension as a network of associated temporal object instances. Consistent with this view, queries can be specified in terms of patterns of temporal object associations or nonassociations (i.e., linear, tree and network structures of object classes/objects with logical AND and OR branches). TA-algebra provides a set of algebraic operators for processing these patterns and allows the direct and/or indirect associations and/or nonassociations among temporal object instances to be more explicitly represented and maintained during processing than the traditional tabular representation of temporary or final query results. TA-algebra operators are based on time-interval and valid-time semantics and they preserve the closure property. The algebra is capable of operating on heterogeneous as well as homogeneous patterns of object associations. Both homogeneous and heterogeneous patterns are decomposed into a set of primitive temporal pattern instances for uniform treatment. This paper formally defines the TA-algebra operators and their mathematical properties. The applications of these operators in query decomposition and processing are illustrated by examples.