In cognitive radio networks, rendezvous is a fundamental operation by which cognitive users establish communication links. Most of existing works were devoted to shortening the time-to-rendezvous (TTR) but paid little attention to qualities of the channels on which rendezvous is achieved. In fact, qualities of channels, such as resistance to primary users' activities, have a great effect on the rendezvous operation. If users achieve a rendezvous on a low-quality channel, the communication link is unstable and the communication performance is poor. In this case, re- rendezvous is required which results in considerable communication overhead and a large latency. In this paper, we first show that actual TTRs of existing rendezvous solutions increase by 65.40-104.38% if qualities of channels are not perfect. Then we propose a Quality-Aware Rendezvous Framework (QARF) that can be applied to any existing ren-dezvous algorithms to achieve rendezvous on high-quality channels. The basic idea of QARF is to expand the set of available channels by selectively duplicating high-quality channels. We prove that QARF can reduce the expected TTR of any rendezvous algorithm when the expanded ratio$\lambda$is smaller than the threshold$(-3+\sqrt{1+4(\frac{\sigma}{\mu})^{2}}) / 2$, where$\mu$and$\sigma$, respectively, are the mean and the standard deviation of qualities of channels. We further prove that QARF can always reduce the expected TTR of Random algorithm by a factor of$1+(\frac{\sigma}{\mu})^{2}$. Extensive experiments are conducted and the results show that QARF can significantly reduce the TTRs of the existing rendezvous algorithms by 10.50-51.05 % when qualities of channels are taken into account.

We have developed a method called skill2vec, which applies big data techniques to automatically analyze the learning data to discover skill relationship, leading to a more objective and data-informed decision making. Skill2vec is a neural network architecture which can transform a skill to a new vector space called embedding. The embedding can facilitate the comparison and visualization of different skills and their relationship. We conducted a pilot experiment using benchmark dataset to demonstrate the effectiveness of our method.

Automated analysis and assessment of students' programs, typically implemented in automated program assessment systems (APASs), are very helpful to both students and instructors in modern day computer programming classes. The mainstream of APASs employs a black-box testing approach which compares students' program outputs with instructor-prepared outputs. A common weakness of existing APASs is their inflexibility and limited capability to deal with admissible output variants, that is, outputs produced by acceptable correct programs that differ from the instructor's. This paper proposes a more robust framework for automatically modelling and analysing student program output variations based on a novel hierarchical program output structure called HiPOS. Our framework assesses student programs by means of a set of matching rules tagged to the HiPOS, which produces a better verdict of correctness. We also demonstrate the capability of our framework by means of a pilot case study using real student programs.

In this paper, we study the important performance issues in using the purging-range query to reclaim old data versions to be free blocks in a flash-based multi-version database. To reduce the overheads for using the purging-range query in garbage collection, the physical block labeling (PBL) scheme is proposed to provide a better estimation on the purging version number to be used for purging old data versions. With the use of the frequency-based placement (FBP) scheme to place data versions in a block, the efficiency in garbage collection can be further enhanced by increasing the deadspans of data versions and reducing reallocation cost especially when the spaces of the flash memory for the databases are limited.

We study the problem of distance queries on a road network under the wireless data broadcast environment. By exploiting special properties of road networks, we design an air-index (indexing scheme on the wireless broadcast model) called the CH Index. Experimental evaluation shows that our CH Index is more energy efficient than previous indices by an order of magnitude. We also extend the CH Index to the CHBN Index which provides a tradeoff between energy efficiency and response time via a user-tunable parameter. It has faster response time than CH while being more energy-efficient than previous methods.

A location-aware news feed system enables mobile users to share geo-tagged user-generated messages, e.g., a user can receive nearby messages that are the most relevant to her. In this paper, we present MobiFeed that is a framework designed for scheduling news feeds for mobile users. MobiFeed consists of three key functions, location prediction, relevance measure, and news feed scheduler. The location prediction function is designed to predict a mobile user's locations based on an existing path prediction algorithm. The relevance measure function is implemented by combining the vector space model with non-spatial and spatial factors to determine the relevance of a message to a user. The news feed scheduler works with the other two functions to generate news feeds for a mobile user at her current and predicted locations with the best overall quality. To ensure that MobiFeed can scale up to a larger number of messages, we design a heuristic news feed scheduler.

Graph reachability is a fundamental research problem that finds its use in many applications such as geographic navigation, bioinformatics, web ontologies and XML databases, etc. Given two vertices, u and v, in a directed graph, a reachability query asks if there is a directed path from u to v. Over the last two decades, many indexing schemes have been proposed to support reachability queries on large graphs. Typically, those schemes based on chain or tree covers work well when the graph is sparse. For dense graphs, they still have fast query time but require large storage for their indices. In contrast, the 2-Hop cover and its variations/extensions produce compact indices even for dense graphs but have slower query time than those chain/tree covers. In this paper, we propose a new indexing scheme, called Path-Hop, which is even more space-efficient than those schemes based on 2-Hop cover and yet has query processing speed comparable to those chain/tree covers. We conduct extensive experiments to illustrate the effectiveness of our approach relative to other state-of-the-art methods.

Directed st-connectivity is the problem of deciding whether or not there exists a path from a distinguished node s to a distinguished node t in a directed graph. We prove a time--space lower bound on the probabilistic NNJAG model of Poon [ Proc. 34th Annual Symposium on Foundations of Computer Science, Palo Alto, CA, 1993, pp. 218--227]. Let n be the number of nodes in the input graph and S and T be the space and time used by the NNJAG, respectively. We show that, for any $\delta > 0$, if an NNJAG uses space $S \in O(n^{1-\delta})$, then $T \in 2^{ \Omega(\log^2 (n/S)) }$; otherwise $T \in 2^{ \Omega( \log^2({n\log n \over S}) / \log\log n )} \times (nS / \log n)^{1/2}$. (In a preliminary version of this paper by Edmonds and Poon [Proc. 27th Annual ACM Symposium on Theory of Computing, Las Vegas, NV, 1995, pp. 147--156.], a lower bound of $T \in 2^{ \Omega( \log^2({n\log n \over S}) / \log\log n )} \times (nS/\log n)^{1/2}$ was proved.) Our result greatly improves the previous lower bound of $ST \in \Omega(n^2/\log n)$ on the JAG model by Barnes and Edmonds [ Proc. 34th Annual Symposium on Foundations of Computer Science, Palo Alto, CA, 1993, pp. 228--237] and that of $S^{1/3}T \in \Omega(n^{4/3})$ on the NNJAG model by Edmonds [ Time-Space Lower Bounds for Undirected and Directed ST-Connectivity on JAG Models, Ph.D. thesis, University of Toronto, Toronto, ON, Canada, 1993]. Our lower bound is tight for $S \in O(n^{1-\delta})$, for any $\delta > 0$, matching the upper bound of Barnes \etal [ Proc. 7th Annual IEEE Conference on Structure in Complexity Theory, Boston, MA, 1992, pp. 27--33]. As a corollary of this improved lower bound, we obtain the first tight space lower bound of $\Omega( \log^2 n )$ on the NNJAG model. No tight space lower bound was previously known even for the more restricted JAG model.

Article Free Access Share on A polynomial time solution for labeling a rectilinear map Authors: Chung Keung Poon Dept. of Computer Science, City University of Hong Kong Dept. of Computer Science, City University of Hong KongView Profile , Binhai Zhu Dept. of Computer Science, City University of Hong Kong Dept. of Computer Science, City University of Hong KongView Profile , Franis Chin Dept. of Computer Science, University of Hong Kong Dept. of Computer Science, University of Hong KongView Profile Authors Info & Claims SCG '97: Proceedings of the thirteenth annual symposium on Computational geometryAugust 1997Pages 451–453https://doi.org/10.1145/262839.263079Published:01 August 1997Publication History 9citation277DownloadsMetricsTotal Citations9Total Downloads277Last 12 Months25Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Publisher SiteeReaderPDF

Article A nearly optimal time-space lower bound for directed st-connectivity on the NNJAG model Share on Authors: Jeff Edmonds International Computer Science Institute, Berkeley, California International Computer Science Institute, Berkeley, CaliforniaView Profile , Chung-Keung Poon Department of Computer Science, University of Toronto, Toronto, Ontario M5S 1A4 Department of Computer Science, University of Toronto, Toronto, Ontario M5S 1A4View Profile Authors Info & Claims STOC '95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computingMay 1995 Pages 147–156https://doi.org/10.1145/225058.225103Online:29 May 1995Publication History 6citation270DownloadsMetricsTotal Citations6Total Downloads270Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We study the problem of running full binary tree based algorithms on a hypercube with faulty nodes. The key to this problem is to devise a method for embedding a full binary tree into the faulty hypercube. Based on a novel embedding strategy, we present two results for embedding an (n-1) tree fa full binary tree with 2/sup n-1/ nodes) into an n-cube (a hypercube with 2/sup n/ nodes) with unit dilation and load. For the problem where the root of the tree must be mapped to a specified hypercube node (specified root embedding problem), we show that up to n-2 (node or edge) faults can be tolerated. This result is optimal in the following sense: 1) it is time-optimal, 2) (n-1)-tree is the largest fall binary tree that can be embedded in an n-cube, and 3) n-2 faults Is the maximum number of worst-case faults that can be tolerated in the specified root problem. Furthermore, we also show that any algorithm for this problem cannot be totally recursive in nature. For the problem where the root can be mapped to any nonfaulty hypercube node (variable root embedding problem), we show that up to 2n-3-[log n] faults can be tolerated. Thus we have improved upon the previous result of n-1-[log n]. In addition, we show that the algorithm for the variable root embedding problem is optimal within a class of algorithms called recursive embedding algorithms as far as the number of tolerable faults is concerned. Finally, we show that when an O(1spl radic/n) fraction of nodes in the hypercube are faulty, it is not always possible to have an O(1)-load variable root embedding no matter how large the dilation is.>

Two new models, NO-JAG and NN-JAG in order of increasing computation power, are introduced as extensions to the conventional JAG model. A space lower bound of /spl Omega/(log/sup 2/ n/log log n) is proved for the problem of directed st-connectivity on a probabilistic NN-JAG and a space upper bound of O(log n) is proved for the problem of directed st-nonconnectivity on a nondeterministic NO-JAG. It is also shown that a nondeterministic NO-JAG is nearly as powerful as a nondeterministic Turing machine.>