Convolution is the most time consuming computation kernel in Convolutional Neural Network (CNN) applications and the majority of Graph Neural Network (GNN) applications. To achieve good convolution performance, current NN libraries such as cuDNN usually transform the naive convolution problem into either the matrix vector multiplication form, called the im2col+MM approach, or into the Fourier domain representation, namely the FFT approach. Both approaches either introduce significant amount of data redundancy to reduce the number of data passes and to leverage highly tuned linear algebra libraries, or avoid data redundancy but require multiple passes on input. Therefore, no implementation of convolution can outperform others in all cases. In this paper, we introduce a novel transformation that reinterprete the convolution in NN as a polynomial multiplication problem. By carefully constructing a number of conceptual polynomials, NN’s convolution essentially becomes a well-known problem of calculating the coefficients in the product of two polynomials. We evaluate our approach in multiple ways: at the API level comparing it with one of the most widely used NN libraries cuDNN, as well as implementing it in PyTorch and comparing the performance with benchmark networks. On three NVIDIA GPUs 3090Ti, V100 and A10G, our approach outperforms cuDNN over a broad range of parameters with the max speedups of 34.6%, 43.1% and 33.6% on these GPUs, respectively.

A key challenge of real-world image super-resolution (SR) is to recover the missing details in low-resolution (LR) images with complex unknown degradations (\eg, downsampling, noise and compression). Most previous works restore such missing details in the image space. To cope with the high diversity of natural images, they either rely on the unstable GANs that are difficult to train and prone to artifacts, or resort to explicit references from high-resolution (HR) images that are usually unavailable. In this work, we propose Feature Matching SR (FeMaSR), which restores realistic HR images in a much more compact feature space. Unlike image-space methods, our FeMaSR restores HR images by matching distorted LR image features to their distortion-free HR counterparts in our pretrained HR priors, and decoding the matched features to obtain realistic HR images. Specifically, our HR priors contain a discrete feature codebook and its associated decoder, which are pretrained on HR images with a Vector Quantized Generative Adversarial Network (VQGAN). Notably, we incorporate a novel semantic regularization in VQGAN to improve the quality of reconstructed images. For the feature matching, we first extract LR features with an LR encoder consisting of several Swin Transformer blocks and then follow a simple nearest neighbour strategy to match them with the pretrained codebook. In particular, we equip the LR encoder with residual shortcut connections to the decoder, which is critical to the optimization of feature matching loss and also helps to complement the possible feature matching errors.Experimental results show that our approach produces more realistic HR images than previous methods. Code will be made publicly available.

The Sketch is a compact data structure useful for network measurements. However, to cope with the high speeds of the current data plane, it needs to be held in the small on-chip memory (SRAM). Therefore, the product of the counter size and the number of counters must be below a certain limit. With small counters, some will overflow. With large counters, the total number of counters will be small, but each counter will be shared by more flows, leading to poor accuracy. To address this issue, we propose a generic technique:self-adaptive counters (SEAD Counter). When the value of the counter is small, it works as a standard counter. When the value of the counter is large however, we increment it using a predefined probability, so as to represent this large value. Moreover, in the SEAD Counter, the probability decreases when the value increases. We show that this technique can significantly improve the accuracy of counters. This technique can be adapted to different circumstances. We theoretically analyze the improvements achieved by the SEAD Counter. We further show that our SEAD Counter can be extended to three typical sketches and Bloom filters. We conduct extensive experiments on three real datasets and one synthetic dataset. The experimental results show that, compared with the state-of-the-art, sketches using the SEAD Counter improve the accuracy by up to 13.6 times, while the Bloom filters using SEAD Counter can reduce the false positive rate by more than one order of magnitude.

The 360-degree video streaming system delivers a monocular panoramic video surrounding the user, and the user can change the viewing direction of mobile devices to see different parts of the video through the “viewport”. Due to the limited network bandwidth, playbacks of high-resolution 360-degree videos often suffer from rebuffering, while too much bandwidth is wasted in delivering those out-of-viewport parts that the user never watches. In this article, we present an Ensemble Prediction and Allocation based Streaming System, named as EPASS360, for delivering high Quality of Experience (QoE) 360-degree videos. The prediction model takes advantages of ensemble learning, providing high accuracy on the prediction of viewports. The allocation model divides a video into tiles, and allocates high resolution to tiles where a user's viewpoint may appear in the future by solving the QoE-aware optimization problem. Trace-driven emulation on real-world datasets shows that EPASS360 enhances the QoE in various scenarios compared to state-of-the-art streaming approaches. Experiments on the head-mounted device and the hand-held device over real-world Internet confirm the high user experience of EPASS360.

User profiles are not always visible in E-commerce scenarios, in which case the recommender systems can only summarize users' preferences through sessions of historical records. However, the items in a session might be irrelevant to users' preferences or become the disturbances for modelling the users' portraits, and thus degrade the performance of the recommender systems. In this paper, we propose the preference-aware mask to capture user preferences over the items within the sessions, which adapts to the preference-irrelevant items within the sessions and provides explainable evidence for the recommendation. Evaluation over three real-world datasets verifies that MBTREC performs well on the new-item recommendation task, and outperforms several state-of-the-art recommender systems on the general metrics.

Edge devices with sensing, storage, and communication resources (e.g., smartphones, tablets, connected vehicles, and IoT nodes) are increasingly penetrating our daily lives. Many novel applications can be created through sharing data among nearby peer edge devices. In such applications, caching data at some edge devices can greatly improve data availability, retrieval robustness, and delivery latency. In this paper, we study the unique problem of caching fairness in edge computing environments. Due to the heterogeneity of peer edge devices, load balance is a critical issue that affects the fairness in caching. We propose fairness metrics to characterize this issue and formulate the caching fairness problem as an integer linear programming problem, which is shown as the summation of multiple Connected Facility Location (ConFL) problems. We provide an approximation algorithm by leveraging an existing ConFL approximation algorithm, and prove that it preserves a 6.55 approximation ratio. We further develop a distributed algorithm where devices exchange data reachability information and identify popular candidates as caching nodes. Finally, we update the fairness metric and apply it to algorithms for making continuous caching decisions overtime. Our extensive evaluation results show that compared with existing caching algorithms for wireless networks, our proposed algorithms significantly improve the data caching fairness while keeping the contention induced latency comparable to the best existing algorithms.

Nowadays, an explosive increase of the size of Forwarding Information Base (FIB) in backbone router makes IP lookup a challenging issue. An effective solution is to use Bloom filter. Because of its false positive, to boost longest prefix matching (LPM), sophisticated Bloom filter-based algorithms were proposed, which makes FIB updating extremely difficult. To address this issue, in this paper, we propose a novel IP lookup algorithm which prunes unneeded prefix probes incurred by false positive and supports FIB updating. Experimental results show that our algorithm can save approximately 7~24% on-chip memory space than the well-known PBF (longest Prefix matching using Bloom Filters) while keeping the same average number of probes of 1.003 per IP lookup. In other words, given a limited on-chip memory budget, our proposed algorithm can handle FIB 7~24% bigger than PBF. The source code can be found in [1].

Finding top-k frequent items has been a hot issue in databases. Finding top-k persistent items is a new issue, and has attracted increasing attention in recent years. In practice, users often want to know which items are significant, i.e., not only frequent but also persistent. No prior art can address both of the above two issues at the same time. Also, for high-speed data streams, they cannot achieve high accuracy when the memory is tight. In this paper, we define a new issue, named finding top-k significant items, and propose a novel algorithm namely LTC to address this issue. It includes two key techniques: Long-tail Replacement and a modified CLOCK algorithm. We theoretically prove there is no overestimation error and derive the correct rate and error bound. We conduct extensive experiments on three real datasets. Our experimental results show that LTC achieves 300~10^8 and in average 10^5 times higher accuracy than other related algorithms.

Multi-set query is a fundamental issue in data science. When the sizes of multi-sets are large, exact matching methods like hash tables need too much memory, and they cannot achieve high query speed. Bloom filters are recently used to handle big data query, but they cannot achieve high accuracy when the memory space is tight. In this paper, we propose a new data structure named coloring embedder, which is fast, accurate as well as memory efficient. The insight is to first map elements to a high dimensional space to almost eliminate hashing collisions, and then use a dimensional reduction representation, which is similar to coloring a graph, to save memory. Theoretical proofs and experimental results show that compared to the state-of-the[1]art, the error rate of the coloring embedder is thousands of times smaller even with much less memory usage, and the query speed of the coloring embedder is about 2 times faster. The source code of coloring embedder is released on Github.

Sketch is a compact data structure for network measurements. To achieve fast speed, it needs to be held in the on-chip memory (SRAM), which is very small. To enable the sketch fit into the on-chip memory, the product of counter size and number of counters must be below a certain limit. If we use small counters, e.g., 8 bits, some counters will overflow. If we use large counters, e.g., 16 bits per counter, the total number of counters will be small, each counter will be shared by more flows, leading to poor accuracy. To address this issue, we propose a generic technique: self-adaptive counters (SA Counter). When the value of the counter is small, it works as a normal counter. When the value of the counter is large, we increment it using a predefined probability, so as to represent a large value. Moreover, in SA Counter, the probability decreases when the value increases. This technique can significantly improve the accuracy of sketches. To verify the effectiveness of SA Counter, we apply SA Counter to three typical sketches, and conduct extensive experiments on one real dataset and one synthetic dataset. Experimental results show that, compared with the state-of-the-art, sketches using SA Counter improve the accuracy by up to 13.6 times.

360-degree videos have gained more popularity in recent years, owing to the great advance of panoramic cameras and head-mounted devices. However, as 360-degree videos are usually in high resolution, transmitting the content requires extremely high bandwidth. To protect the Quality of Experience (QoE) of users, researchers have proposed tile-based 360-degree video streaming systems that allocate high/low bit rates to selected tiles of video frames for streaming over the limited bandwidth. It is challenging to determine which tiles should be allocated with a high/low rate, because (1) the video playbacks include too many features that dynamically change over time when making the rate allocation; (2) most of the state-of-the-art systems focus on a fixed set of heuristics to optimize a specific QoE objective, while users may have various QoE objectives that need to be optimized in different ways. This paper presents a Deep Reinforcement Learning (DRL) based framework for 360-degree video streaming, named DRL360. The DRL360 framework helps improve the system performance by jointly optimizing multiple QoE objectives across a broad set of dynamic features. The DRL-based model adaptively allocates rates for the tiles of the future video frames based on the observations collected by client video players. We compare the proposed DRL360 to the existing systems by trace-driven evaluations as well as conducting a realworld experiment over a wide variety of network conditions. Evaluation results reveal that DRL360 can adapt to all considered scenarios, and outperform the state-of-the-art approaches by 20%-30% on average given different QoE objectives.

Finding top-k elephant flows is a critical task in network traffic measurement, with many applications in congestion control, anomaly detection and traffic engineering. As the line rates keep increasing in today's networks, designing accurate and fast algorithms for online identification of elephant flows becomes more and more challenging. The prior algorithms are seriously limited in achieving accuracy under the constraints of heavy traffic and small on-chip memory in use. We observe that the basic strategies adopted by these algorithms either require significant space overhead to measure the sizes of all flows or incur significant inaccuracy when deciding which flows to keep track of. In this paper, we adopt a new strategy, called count-with-exponential-decay, to achieve space-accuracy balance by actively removing small flows through decaying, while minimizing the impact on large flows, so as to achieve high precision in finding top-k elephant flows. Moreover, the proposed algorithm called HeavyKeeper incurs small, constant processing overhead per packet and thus supports high line rates. Experimental results show that HeavyKeeper algorithm achieves 99.99% precision with a small memory size, and reduces the error by around 3 orders of magnitude on average compared to the state-of-the-art.

When network is undergoing problems such as congestion, scan attack, DDoS attack, etc, measurements are much more important than usual. In this case, traffic characteristics including available bandwidth, packet rate, and flow size distribution vary drastically, significantly degrading the performance of measurements. To address this issue, we propose the Elastic sketch. It is adaptive to currently traffic characteristics. Besides, it is generic to measurement tasks and platforms. We implement the Elastic sketch on six platforms: P4, FPGA, GPU, CPU, multi-core CPU, and OVS, to process six typical measurement tasks. Experimental results and theoretical analysis show that the Elastic sketch can adapt well to traffic characteristics. Compared to the state-of-the-art, the Elastic sketch achieves 44.6 ~ 45.2 times faster speed and 2.0 ~ 273.7 smaller error rate.

Per-flow measurement is a critical issue in computer networks, and one of its key tasks is to count the number of packets in each flow (for big streaming data). The literature has demonstrated that sketch is the most memory-efficient data structure for the counting task, and is widely used in distributed systems. Existing sketches often use many counters that are of the same size to record the number of packets in a flow, thus the counters are forced to be large enough to accommodate the size of the largest flow. Unfortunately, as most flows are small (i.e., mice flows) and only a very few flows are large (i.e., elephant flows), many counters represent very small values, which is a waste of memory. Sketches are often stored in fast but expensive memory (e.g., SRAM), thus it is critical to achieve high memory efficiency. To address this issue, we propose a novel sketch, namely the Diamond sketch. The Diamond sketch is composed of atom sketches, and each atom sketch uses small counters. The key idea of Diamond is to dynamically assign an appropriate number of atom sketches to each flow on demand, thus optimizing memory efficiency. Experimental results show that the Diamond sketch outperforms the best of the five typical sketches by up to 508.3 times in terms of relative error while keeping comparable speed. We made the source code of all the six sketches available on GitHub [1] .

Recent advance in Internet-of-Things (IoT) brings consumer- level smart mobile robot to our life. Indoor navigation is one of the most critical challenges for mobile robots. Existing approaches using wireless signal fingerprinting (e.g., WiFi fingerprint), computer vision techniques, require extensive war-driving of the indoor environment to collect sufficient environmental data. In this paper, we present SIGN, a lightweight, visual-tag based, indoor navigation approach that is free of indoor war-driving. The approach deploys a set of coded visual tags in the environment, and allows the robot to autonomously decide the moving direction by recognizing nearby tags and leveraging the geometry information. The proposed approach is robust to the change of the environment such as unexpected obstacles. Experiments in two indoor spaces under various scenarios show that SIGN helps the mobile robot using the off-the- shelf camera to self-navigate in indoor environment with the deployment of coded visual tags.

The problem of multi-set membership query plays a significant role in many network applications, including routers and firewalls. Answering multi-set membership query means telling whether an element belongs to the multi-set, and if yes, which particular set it belongs to. Most traditional solutions for multi-set membership query are based on Bloom filters. However, these solutions cannot achieve high accuracy and high speed at the same time when the memory is tight. To address this issue, this paper presents the ID Bloom Filter (IBF) and ID Bloom Filter with ones' Complement (IBFC). The key technique in IBF is mapping each element to k positions in a filter and directly recording its set ID at these positions. It has a small memory usage as well as a high processing speed. To achieve higher accuracy, we propose IBFC that records the set ID and its ones' complement together. The experimental results show that our IBF and IBFC are faster than the state-of-the-art while achieving a high accuracy.

Machine reading comprehension has gained attention from both industry and academia. It is a very challenging task that involves various domains such as language comprehension, knowledge inference, summarization, etc. Previous studies mainly focus on reading comprehension on short paragraphs, and these approaches fail to perform well on the documents. In this paper, we propose a hierarchical match attention model to instruct the machine to extract answers from a specific short span of passages for the long document reading comprehension (LDRC) task. The model takes advantages from hierarchical-LSTM to learn the paragraph-level representation, and implements the match mechanism (i.e., quantifying the relationship between two contexts) to find the most appropriate paragraph that includes the hint of answers. Then the task can be decoupled into reading comprehension task for short paragraph, such that the answer can be produced. Experiments on the modified SQuAD dataset show that our proposed model outperforms existing reading comprehension models by at least 20% regarding exact match (EM), F1 and the proportion of identified paragraphs which are exactly the short paragraphs where the original answers locate.

Software-Defined Networking (SDN), which separates the control plane and data plane, is a promising new network architecture for the Future Internet. OpenFlow is the de facto standard which defines the communication protocol between the controller and switches. The most challenging issue in OpenFlow switches is the lookup of multiple OpenFlow tables. The lookup of OpenFlow tables is so complicated that the state-of-the-art research are still focusing on the design of lookup pipeline architecture, and there is no specific algorithm for the lookup of OpenFlow tables. In this paper, we revise the long-pipeline architecture of OpenFlow 1.4 to a 5-stage pipeline architecture to make a trade-off between flexibility and implementability, and decompose the lookup of OpenFlow tables into three kinds of lookup: longest prefix matching (IP lookup), multi-field matching (packet classification), and exact matching. Then we design new algorithms for packet classification, because the state-of-the-art solutions for them seldom support fast update which is highly demanding for OpenFlow. The other two kinds of lookups can be well handled by state-of-the-art. Experimental results show that our proposed algorithms work excellently, and outperform state-of-the-art solutions.

Decentralizing content delivery to edge devices has become a popular solution for saving the bandwidth consumption of CDN when the CDN bandwidth is expensive. One successful realization is the hybrid CDN-P2P VoD system, where a client is allowed to request video content from a number of seeds (seed clients) in the P2P network. However, the seed scarcity problem may arise for a video resource when there are an insufficient number of seeds to satisfy requests to the video. To alleviate this problem, many commercial VoD systems have employed a video push mechanism that directly sends the recent scarce video resources to randomly-chosen seeds to serve more requests. However, the current video push mechanism fails to consider which videos will become scarce in the future, or differentiate the uploading capability of different seeds. In this paper, we propose Proactive-Push, a video push mechanism that lowers the bandwidth consumption of CDN by predicting future scarce videos and proactively sending them to competent seeds with strong uploading capabilities. Proactive-Push trains neural network models to correctly predict 80% of future scarce video resources, and identify over 90% of competent seeds. We evaluate Proactive-Push using a trace-driven emulation and a real-world pilot deployment over a commercial VoD system. Results show that Proactive-Push can further reduce the proportion of direct download from CDN by 21%, and save the CDN bandwidth cost at peak time by 18%.

Data stream processing is a fundamental issue in many fields, such as data mining, databases, network traffic measurement. There are five typical tasks in data stream processing: frequency estimation, heavy hitter detection, heavy change detection, frequency distribution estimation, and entropy estimation. Different algorithms are proposed for different tasks, but they seldom achieve high accuracy and high speed at the same time. To address this issue, we propose a novel data structure named HeavyGuardian. The key idea is to intelligently separate and guard the information of hot items while approximately record the frequencies of cold items. We deploy HeavyGuardian on the above five typical tasks. Extensive experimental results show that HeavyGuardian achieves both much higher accuracy and higher speed than the state-of-the-art solutions for each of the five typical tasks. The source codes of HeavyGuardian and other related algorithms are available at GitHub.

When network is undergoing problems such as congestion, scan attack, DDoS attack, etc., measurements are much more important than usual. In this case, traffic characteristics including available bandwidth, packet rate, and flow size distribution vary drastically, significantly degrading the performance of measurements. To address this issue, we propose the Elastic sketch. It is adaptive to currently traffic characteristics. Besides, it is generic to measurement tasks and platforms. We implement the Elastic sketch on six platforms: P4, FPGA, GPU, CPU, multi-core CPU, and OVS, to process six typical measurement tasks. Experimental results and theoretical analysis show that the Elastic sketch can adapt well to traffic characteristics. Compared to the state-of-the-art, the Elastic sketch achieves 44.6 ∼ 45.2 times faster speed and 2.0 ∼ 273.7 smaller error rate.

Approximate stream processing algorithms, such as Count-Min sketch, Space-Saving, etc., support numerous applications in databases, storage systems, networking, and other domains. However, the unbalanced distribution in real data streams poses great challenges to existing algorithms. To enhance these algorithms, we propose a meta-framework, called Cold Filter (CF), that enables faster and more accurate stream processing.

With the explosive increase of images and videos, visual analysis has become an essential technique in dealing with the big visual data, which utilizes the visual feature descriptors to search or recognize the images or frames with target objects or events. Subject to the constraints of resources (e.g., memory, bandwidth, storage, etc.), interest point selection is crucial to generate robust compact descriptors for high-efficiency visual analysis by selecting and aggregating the most discriminative local feature descriptors, which has been demonstrated in the state-of-the-art low bit rate visual search works. In this paper, we propose a data-driven lightweight interest point selection approach to significantly improve the performance of visual search, while ameliorating the efficiency of extracting feature descriptors. Comprehensive experimental results over benchmarks have shown that the proposed interest point selection algorithm has significantly improved image matching and retrieval performance in the completed MPEG Compact Descriptors for Visual Search (CDVS) standard as well as the emerging MPEG Compact Descriptors for Video Analytics (CDVA) standard, say 20% mAP gain by data-driven selection against random selection of interest points. In particular, the presented data-driven interest point selection has been adopted by MPEG-CDVS and MPEG-CDVA as a normative technique to improve the aggregation of handcrafted features, which has contributed to the combination of handcrafted features and deep learning (CNN) features as well.

Unmanned aerial vehicle (UAV) has been recognized as a promising way to assist future wireless communications due to its high flexibility of deployment and scheduling. In this paper, we focus on temporarily deployed UAVs that provide downlink data offloading in some regions under a macro base station (MBS). Since the manager of the MBS and the operators of the UAVs could be of different interest groups, we formulate the corresponding spectrum trading problem by means of contract theory, where the manager of the MBS has to design an optimal contract to maximize its own revenue. Such contract comprises a set of bandwidth options and corresponding prices, and each UAV operator only chooses the most profitable one from all the options in the whole contract. We analytically derive the optimal pricing strategy based on fixed bandwidth assignment, and then propose a dynamic programming algorithm to calculate the optimal bandwidth assignment in polynomial time. By simulations, we compare the outcome of the MBS optimal contract with that of a socially optimal one and find that a selfish MBS manager sells less bandwidth to the UAV operators.

Sketch is a data structure used to record frequencies of items in a multiset, which is widely used in data streams, data graph, distributed datasets processing, etc. It works with small memory usage and a high speed at the cost of a slight inaccuracy. In practice, frequencies of items in many datasets are non-uniformly distributed. Unfortunately, existing sketches can hardly work well on non-uniform datasets. To address this issue, we propose a new sketch framework, namely ABC framework, which can be applied to most existing sketches and can significantly improve the accuracy on non-uniform datasets. The key idea behind our framework is that when a counter overflows, it makes use of the space from the adjacent counters by operations of bits-borrowing and combination. Extensive experimental results show that our ABC framework improves the accuracy by 4.10 times and 4.49 times in average, respectively. A demo and all the related source codes are available on our homepage [1].

Hash table, a widely used data structure, can achieve an O(1) average lookup speed at the cost of large memory usage. Unfortunately, hash tables suffer from collisions and the rate of collisions is largely determined by the load factor. Broadly speaking, existing research has taken two approaches to improve the performance of hash tables. The first approach trades-off collision rate with memory usage, but only works well under low load. The second approach pursues high load and no hash collisions, but comes with update failures. The goal of this paper is to design a practical and efficient hash table that achieves high load factor, low hash collision rate, fast lookup speed, fast update speed, and zero update failures. To achieve this goal, we take a three-step approach. First, we propose a set of hashing techniques that leverage Bloom filters to significantly reduce hash collision rates. Second, we introduce a novel kick mechanism to achieve a high load factor. Last, we develop bitmaps to significantly accelerate the kick mechanism. Theoretical analysis and experimental results show that our hashing schemes significantly outperform the state-of-the-art Our hash table achieves a high load factor (greater than 95%), a low collision rate (less than 0.56%), and the number of hash buckets almost equals to the number of key-value pairs. Given n key-value pairs, the collision rate is reduced to 0 by either using 1.18 ×n buckets or allowing up to 5 blind kicks. We have released the source code of the implementations of our hash table and of 6 prior hash tables at Github [1].

Recent years have witnessed the proliferation of Massive Open Online Courses (MOOCs).With massive learners being offered MOOCs, there is a demand that the forum contents within MOOCs need to be classified in order to facilitate both learners and instructors.Therefore we investigate a significant application, which is to associate forum threads to subtitles of video clips.This task can be regarded as a document ranking problem, and the key is how to learn a distinguishable text representation from word sequences and learners' behavior sequences.In this paper, we propose a novel cascade model, which can capture both the latent semantics and latent similarity by modeling MOOC data.Experimental results on two real-world datasets demonstrate that our textual representation outperforms state-of-the-art unsupervised counterparts for the application.

The state of art protocols in neighbor discovery in wireless sensor networks can be divided into two categories: the quorum based, and the co-primality based protocols, which are confirmed by simulations to have a small "theoretical" latency according to their wake-up schedule designs. However, these works fail to consider the collision of neighbor discovery beacons, when multiple pairs of nodes search for discovery simultaneously, which could lead to a greater "practical" latency. In this paper, we seek to reduce such practical latency in neighbor discovery protocols caused by the collision of neighbor discovery beacons by a dynamic slot-length control mechanism that allows each node to autonomously vary its slot length based on the detection of beacon collisions. We develop a real-world testbed of neighbor discovery on Android smartphones by implementing a few classic neighbor discovery protocols in literature, and evaluate their performance with and without the proposed slot-length control. Experimental results show that the slot-length control can help reduce the practical latency of neighbor discovery by more than 15% under both types of neighbor discovery protocols.

Sketch is a probabilistic data structure widely used for per-flow measurement in the real network. The key metrics of sketches for per-flow measurement are their memory usage, accuracy, and speed. There are a variety of sketches, but they cannot achieve both high accuracy and high speed at the same time given a fixed memory size. To address this issue, we propose a new sketch, namely the OM (One Memory) sketch. It achieves much higher accuracy than the state-of-the-art, and achieves close to one memory access and one hash computation for each insertion or query. The key methodology of our OM sketch is to leverage word constraint and fingerprint techniques based on a hierarchical structure. Extensive experiments based on real IP traces show that the accuracy is improved up to 10.64 times while the speed is improved up to 2.50 times, compared with the well-known CM sketch [1]. All the related source code has been released at GitHub [2].

Given v sets and an incoming item e, multi-set membership query is to report which set contains item e. Multi-set membership query is a fundamental problem in computer systems and applications. All existing data structures cannot achieve small memory usage, fast query speed and high accuracy at the same time. In this paper, we propose a novel probabilistic data structure named Difference Bloom Filter (DBF) for fast multi-set membership query, which not only is more accurate than the state-of-the-art, but has a faster query speed. There are two key design principles for DBF. The first one is to make the representation of the membership of elements exclusive by writing different number of 1s and 0s in the same filter, and the second one is to use the slow but cheap DRAM memory to improve the accuracy of the filter on the fast but expensive SRAM memory. Experimental results show that in terms of accuracy, DBF has a great advantage compared to state-of-the-art, being hundreds of times more accurate than the state-of-the-art vBF and ShBF. Furthermore, we have made the source code of our DBF available at our homepage [1] and GitHub [2].

Edge devices (e.g., smartphones, tablets, connected vehicles, IoT nodes) with sensing, storage and communication resources are increasingly penetrating our environments. Many novel applications can be created when nearby peer edge devices share data. Caching can greatly improve the data availability, retrieval robustness and latency. In this paper, we study the unique issue of caching fairness in edge environment. Due to distinct ownership of peer devices, caching load balance is critical. We consider fairness metrics and formulate an integer linear programming problem, which is shown as summation of multiple Connected Facility Location (ConFL) problems. We propose an approximation algorithm leveraging an existing ConFL approximation algorithm, and prove that it preserves a 6.55 approximation ratio. We further develop a distributed algorithm where devices exchange data reachability and identify popular candidates as caching nodes. Extensive evaluation shows that compared with existing wireless network caching algorithms, our algorithms significantly improve data caching fairness, while keeping the contention induced latency similar to the best existing algorithms.

The proliferation and daily congregation of modern mobile devices have created abundant opportunities for peer edge devices to share valuable data with each other. The short contact durations, relatively small sharing sizes, and uncertain data availability, demand agile, light weight peer based data sharing. In this paper, we propose Peer Data Sharing (PDS) that enables edge devices to discover which data exist in nearby peers, and retrieve interested data robustly and efficiently. PDS uses novel lingering queries, mixedcast and en-route message rewriting techniques to minimize redundant transmissions and maximize opportunistic overhearing thus caching in data discovery and retrieval. Extensive evaluations based on an Android prototype show that PDS discovers and retrieves almost 100% data in tens of seconds, and remains robust despite wireless contention, simultaneous consumer requests and user mobility.

A sketch is a probabilistic data structure that is used to record frequencies of items in a multi-set. Sketches have been applied in a variety of fields, such as data stream processing, natural language processing, distributed data sets etc. In this paper, we propose a new sketch, called Slim-Fat (SF) sketch, which has a much smaller memory footprint for query while supporting updates. The key idea behind our proposed SF-sketch is to maintain two separate sketches: a small sketch called Slimsubsketch and a large sketch called Fat-subsketch. The Slimsubsketch enables fast and accurate querying. The Fat-subsketch is used to assist the insertion and deletion from Slim-subsketch. We implemented and evaluated SF-sketch along with several prior sketches and compared them side by side. Our experimental results show that SF-sketch significantly outperforms the most commonly used CM-sketch in terms of accuracy. The full version is provided at arXiv.org [12].

Sketch is a probabilistic data structure, and is used to store and query the frequency of any item in a given multiset. Due to its high memory efficiency, it has been applied to various fields in computer science, such as stream database, network traffic measurement, etc. The key metrics of sketches for data streams are accuracy, speed, and memory usage. Various sketches have been proposed, but they cannot achieve both high accuracy and high speed using limited memory, especially for skewed datasets. To address this issue, we propose a sketch framework, the Pyramid sketch, which can significantly improve accuracy as well as update and query speed. To verify the effectiveness and efficiency of our framework, we applied our framework to four typical sketches. Extensive experimental results show that the accuracy is improved up to 3.50 times, while the speed is improved up to 2.10 times. We have released our source codes at Github [1].

Many web applications provide secondary authentication methods, i.e., secret questions (or password recovery questions), to reset the account password when a user's login fails. However, the answers to many such secret questions can be easily guessed by an acquaintance or exposed to a stranger that has access to public online tools (e.g., online social networks); moreover, a user may forget her/his answers long after creating the secret questions. Today's prevalence of smartphones has granted us new opportunities to observe and understand how the personal data collected by smartphone sensors and apps can help create personalized secret questions without violating the users’ privacy concerns. In this paper, we present aSecret-Question based Authenticationsystem, called “Secret-QA”, that creates a set of secret questions on basic of people's smartphone usage. We develop a prototype on Android smartphones, and evaluate the security of the secret questions by asking the acquaintance/stranger who participates in our user study to guess the answers with and without the help of online tools; meanwhile, we observe the questions’ reliability by asking participants to answer their own questions. Our experimental results reveal that the secret questions related to motion sensors, calendar, app installment, and part of legacy app usage history (e.g., phone calls) have the best memorability for users as well as the highest robustness to attacks.

Set queries are fundamental operations in computer networks. This paper addresses the fundamental problem of designing a probabilistic data structure that can quickly process set queries using a small amount of memory. We propose a shifting bloom filter (ShBF) framework for representing and querying sets. We demonstrate the effectiveness of ShBF using three types of popular set queries: membership, association, and multiplicity queries. The key novelty of ShBF is on encoding the auxiliary information of a set element in a location offset. In contrast, prior BF-based set data structures allocate additional memory to store auxiliary information. We further extend our shifting framework from BF-based data structures to sketch-based data structures, which are widely used to store multiplicities of items. We conducted experiments using real-world network traces, and results show that ShBF significantly advances the state-of-the-art on all three types of set queries.

Recent improvements in vehicular ad hoc networks are accelerating the realization of intelligent transportation system (ITS), which not only provides road safety and driving efficiency, but also enables infotainment services. Since data dissemination plays an important part in ITS, recent studies have found caching as a promising way to promote the efficiency of data dissemination against rapid variation of network topology. In this paper, we focus on the scenario of roadside unit (RSU) caching, where multiple content providers (CPs) aim to improve the data dissemination of their own contents by utilizing the storages of RSUs. To deal with the competition among multiple CPs for limited caching facilities, we propose a multi-object auction-based solution, which is sub-optimal and efficient to be carried out. A caching-specific handoff decision mechanism is also adopted to take advantages of the overlap of RSUs. Simulation results show that our solution leads to a satisfactory outcome.

Network embedding is a classical task which aims to map the nodes of a network to low-dimensional vectors. Most of the previous network embedding methods are trained in an unsupervised scheme. Then the learned node embeddings can be used as inputs of many machine learning tasks such as node classification, attribute inference. However, the discrimination validity of the node embeddings maybe improved by considering the node label information and the node attribute information. Inspired by traditional semi-supervised learning techniques, we explore to train the node embeddings and the node classifiers simultaneously with the text attributes information in a flexible framework. We present NLSTNE (Non-Linear Smoothed Transductive Network Embedding), a transductive network embedding method, whose embeddings are enhanced by modeling the non-linear pairwise similarity between the nodes and the non-linear relationship between the nodes and the text attributes. We use the node classification task to evaluate the quality of node embeddings learned by different models on four real-world network datasets . The experimental results demonstrate that our model outperforms several state-of-the-art network embedding methods.

Despite significant research efforts and great advances on Mobile CrowdSensing (MCS), building MCS applications remains difficult. In this paper, we develop and run Dining Halls on Live (DHOL), a campus dining population density monitoring system over several months. We make a holistic reality examination, discover key technical and practical difficulties, develop effective solutions and share our experiences and insights. We find two main obstacles on data fusion and incentive design: insufficient data quantity/quality and ``irrational'' user behavior. We develop effective methods by combining historical and real time data, and allocating a given budget among users to address them. We also conduct a detailed user survey to identify reasons behind interesting discoveries, important practical difficulties in acquiring sufficient users and location data, and share our experiences dealing with them. Our main insight is that insufficient data quantity/quality and ``irrational'' user behavior demand practical yet effective data fusion and incentive mechanisms, and one must provide values to users to acquire and retain a large user base.

Many online social networks have provided a messenger app (e.g., facebook messenger, direct message on Twitter) to facilitate communication between strong- tied friends. Meanwhile, some messenger apps (WeChat) also start to offer social-networking services ("WeChat Moments" (WM), a.k.a. friend circle) that allow users to post pictures, texts, links of webpages, on their walls, which is called the messenger-based social network (Msg-SN). In online social networks, Key Opinion Leaders (KOLs) with millions of followers are easy to identify for helping viral marketing/advertising. However, most users of a messenger app have a small number of friends (e.g., hundreds of friends), which makes it challenging to detect a KOL in Msg-SN by only counting the number of his/her friends. In this paper, we study the influence maximization problem in the Msg-SN of finding the set of most influential KOL nodes that maximize the spread of information. We develop a novel efficient approximation algorithm that calculates the influence by looking at the user's local contribution to the information diffusion process, which scales to large datasets with provable near-optimal performance. Experiment results using the real-world WeChat Moments data (on January 14th, 2016, 100 thousand users) show that our algorithms can identify the set of KOL nodes with a low time complexity.

Fitting large and ever increasing routing tables in small on-chip memory is just like fitting an elephant in a box, which has been considered as impossible. In this paper, we propose the data structure of two-Dimensional Division Bloom Filter (D2BF) that can compactly encode almost all the needed information for performing IP lookup from a FIB in small on-chip memory. With pipelining, we further achieve the throughput of one packet per on-chip memory access.

Most applications in urban Vehicular Ad hoc NETworks (VANETs) rely on information sharing, such as real-time traffic information queries, advertisements, etc. However, existing data dissemination techniques cannot guarantee satisfactory performance when a lot of information requests come from all around the network. Because these pieces of information are useful for multiple users located in various positions, it is beneficial to spread the cached copies around. Existing work proposed caching mechanisms and conducted simulations for validation, but there is a lack of theoretical analysis on the explicit caching effects. In this paper, we present the cache coverage ratio as the metric to quantify the caching effects, and theoretical analysis is given based on reasonable assumptions for urban VANETs, through which we find the affecting factors include vehicle density, transmission range, ratio of caching vehicles, etc. We deduce the quantitative relationship among them, which have similar forms as the cumulative density function of an exponential distribution. We conduct intensive simulations, which verify the theoretical analysis results match quite well with the simulated reality under different scenarios.

Set queries are fundamental operations in computer systems and applications. This paper addresses the fundamental problem of designing a probabilistic data structure that can quickly process set queries using a small amount of memory. We propose a Shifting Bloom Filter (ShBF) framework for representing and querying sets. We demonstrate the effectiveness of ShBF using three types of popular set queries: membership, association, and multiplicity queries. The key novelty of ShBF is on encoding the auxiliary information of a set element in a location offset. In contrast, prior BF based set data structures allocate additional memory to store auxiliary information. We conducted experiments using real-world network traces, and results show that ShBF significantly advances the state-of-the-art on all three types of set queries.

We present in this article an automated framework that extracts product adopter information from online reviews and incorporates the extracted information into feature-based matrix factorization for more effective product recommendation. In specific, we propose a bootstrapping approach for the extraction of product adopters from review text and categorize them into a number of different demographic categories. The aggregated demographic information of many product adopters can be used to characterize both products and users in the form of distributions over different demographic categories. We further propose a graph-based method to iteratively update user- and product-related distributions more reliably in a heterogeneous user--product graph and incorporate them as features into the matrix factorization approach for product recommendation. Our experimental results on a large dataset crawled from J ing D ong , the largest B2C e-commerce website in China, show that our proposed framework outperforms a number of competitive baselines for product recommendation.

In recent years, the boundaries between e-commerce and social networking have become increasingly blurred. Many e-commerce Web sites support the mechanism of social login where users can sign on the Web sites using their social network identities such as their Facebook or Twitter accounts. Users can also post their newly purchased products on microblogs with links to the e-commerce product Web pages. In this paper, we propose a novel solution for cross-site cold-start product recommendation, which aims to recommend products from e-commerce Web sites to users at social networking sites in “cold-start” situations, a problem which has rarely been explored before. A major challenge is how to leverage knowledge extracted from social networking sites for cross-site cold-start product recommendation. We propose to use the linked users across social networking sites and e-commerce Web sites (users who have social networking accounts and have made purchases on e-commerce Web sites) as a bridge to map users' social networking features to another feature representation for product recommendation. In specific, we propose learning both users' and products' feature representations (called user embeddings and product embeddings, respectively) from data collected from e-commerce Web sites using recurrent neural networks and then apply a modified gradient boosting trees method to transform users' social networking features into user embeddings. We then develop a feature-based matrix factorization approach which can leverage the learnt user embeddings for cold-start product recommendation. Experimental results on a large dataset constructed from the largest Chinese microblogging service Sina Weibo and the largest Chinese B2C e-commerce website JingDong have shown the effectiveness of our proposed framework.

Mainstream indoor localization technologies rely on RF signatures that require extensive human efforts to measure and periodically recalibrate signatures. The progress to ubiquitous localization remains slow. In this study, we explore Sextant, an alternative approach that leverages environmental reference objects such as store logos. A user uses a smartphone to obtain relative position measurements to such static reference objects for the system to triangulate the user location. Sextant leverages image matching algorithms to automatically identify the chosen reference objects by photo-taking, and we propose two methods to systematically address image matching mistakes that cause large localization errors. We formulate the benchmark image selection problem, prove its NP-completeness, and propose a heuristic algorithm to solve it. We also propose a couple of geographical constraints to further infer unknown reference objects. To enable fast deployment, we propose a lightweight site survey method for service providers to quickly estimate the coordinates of reference objects. Extensive experiments have shown that Sextant prototype achieves 2-5 m accuracy at 80-percentile, comparable to the industry state-of-the-art, while covering a 150 x 75 m mall and 300 x 200m train station requires a one time investment of only 2-3 man-hours from service providers.

The lack of floor plans is a critical reason behind the current sporadic availability of indoor localization service. Service providers have to go through effort-intensive and time-consuming business negotiations with building operators, or hire dedicated personnel to gather such data. In this paper, we propose Jigsaw, a floor plan reconstruction system that leverages crowdsensed data from mobile users. It extracts the position, size, and orientation information of individual landmark objects from images taken by users. It also obtains the spatial relation between adjacent landmark objects from inertial sensor data, then computes the coordinates and orientations of these objects on an initial floor plan. By combining user mobility traces and locations where images are taken, it produces complete floor plans with hallway connectivity, room sizes, and shapes. It also identifies different types of connection areas (e.g., escalators and stairs) between stories, and employs a refinement algorithm to correct detection errors. Our experiments on three stories of two large shopping malls show that the 90-percentile errors of positions and orientations of landmark objects are about 1~2m and 5~9°, while the hallway connectivity and connection areas between stories are 100 percent correct.

Wireless network virtualization has been well recognized as a way to improve the flexibility of wireless networks by decoupling the functionality of the system and implementing infrastructure and spectrum as services. Recent studies have shown that caching provides a better performance to serve the content requests from mobile users. In this paper, we propose that caching can be applied as a service in mobile networks, i.e., different service providers (SPs) cache their contents in the storage of wireless facilities that are owned by mobile network operators. Specifically, we focus on the scenario of small-cell networks, where cache-enabled small-cell base stations are the facilities to cache contents. To deal with the competition for storage among multiple SPs, we design a mechanism based on multi-object auctions, where the time-dependent feature of system parameters and the frequency of content replacement are both taken into account. Simulation results show that our solution leads to a satisfactory outcome.

Abstract Most applications in urban vehicular ad hoc networks (VANETs) rely on information sharing, such as real‐time traffic information queries, and advertisements. However, existing data dissemination techniques cannot guarantee satisfactory performance when amounts of information requests come from all around the network. Because these pieces of information are useful for multiple users located in various positions, it is beneficial to spread the cached copies around. Existing work proposed caching mechanisms and conducted simulations for validation, but there is a lack of theoretical analysis on the explicit caching effects. Because of the complex urban environment and high mobility of vehicles, quantifying the caching effects on the VANET performance is quite challenging. We present the cache coverage ratio as the metric to measure the caching effects, and theoretical analysis is given based on reasonable assumptions for urban VANETs, through which we find the affecting factors include vehicle density, transmission range, and ratio of caching vehicles. We deduce the quantitative relationship among them, which have similar forms as the cumulative density function of an exponential distribution. We also consider the impact of vehicle mobility to predict the future cache effect on surrounding roads of the caching area. We conduct intensive simulations, which verify that the theoretical analysis results match quite well with the simulated reality under different scenarios. Copyright © 2015 John Wiley & Sons, Ltd.

In this paper, we propose to study the problem of identifying and classifying tweets into intent categories. For example, a tweet “I wanna buy a new car” indicates the user’s intent for buying a car. Identifying such intent tweets will have great commercial value among others. In particular, it is important that we can distinguish different types of intent tweets. We propose to classify intent tweets into six categories, namely Food & Drink, Travel, Career & Education, Goods & Services, Event and Activities and Trifle. We propose a semisupervised learning approach to categorizing intent tweets into the six categories.We construct a test collection by using a bootstrap method. Our experimental results show that our approach is effective in inferring intent categories for tweets.

In this paper, we present TapLock as a smartphone password system that exploits the finger tap events on capacitive touch screens for increasing the password's resilience to shoulder-surfing attacks (where the password input by a user can be easily observed by a bystander over the user's shoulder). TapLock captures the size and the axis length of the finger touch area on the phone screen for creating a password, which cannot be easily observed by a shoulder surfer. Our user study shows that TapLock has several advantages over existing smartphone password systems, including its strong attack resilience, small authentication delay, and haptic input feedback that improves the usability.

Neighbor discovery plays a crucial role in the formation of wireless sensor networks and mobile networks where the power of sensors (or mobile devices) is constrained. Due to the difficulty of clock synchronization, many asynchronous protocols based on wake-up scheduling have been developed over the years in order to enable timely neighbor discovery between neighboring sensors while saving energy. However, existing protocols are not fine-grained enough to support all heterogeneous battery duty cycles, which can lead to a more rapid deterioration of long-term battery health for those without support. Existing research can be broadly divided into two categories according to their neighbor-discovery techniques — the quorum based protocols and the co-primality based protocols. In this paper, we propose two neighbor discovery protocols, called Hedis and Todis, that optimize the duty cycle granularity of quorum and co-primality based protocols respectively, by enabling the finest-grained control of heterogeneous duty cycles. We compare the two optimal protocols via analytical and simulation results, which show that although the optimal co-primality based protocol (Todis) is simpler in its design, the optimal quorum based protocol (Hedis) has a better performance since it has a lower relative error rate and smaller discovery delay, while still allowing the sensor nodes to wake up at a more infrequent rate.

Named Data Networking (NDN) is a data-centric architecture designed for the future Internet. Existing works show that NDN brings significant performance improvement for typical content-centric applications, and can also fit the mobile environment well. However, directly applying NDN to Vehicular Ad hoc NETworks (VANETs) is confronted with great challenges due to the high mobility of vehicles. Most applications in VANETs are relied on data dissemination mechanisms. Therefore, we aim to improve the performance of NDN packet forwarding for the efficient content delivery in urban VANET scenarios. Specifically, we introduce the geo-location information to the NDN forwarding plane, and propose a geo-based forwarding strategy to make NDN fit the urban VANETs. Simulation results show our strategy can achieve 27% ~ 75% higher request success ratio, and 40% ~ 80% lower delay compared with the default NDN strategy in urban scenarios with different vehicle densities.

Abstract Multi‐interface multi‐channel can be used to reduce the channel interference and improve the network capacity for multi‐hop wireless ad‐hoc networks, but using multi‐channel will impact the network connectivity, which is an important quality of service factor in VANET. The basic multi‐channel assignment scheme in our paper keeps the network connectivity resilient to the mobility. On the basis of this method, we design a dynamic channel assignment algorithm that can dynamically switch the channels to the less busy ones by monitoring the channel usages. In order to survive the highly mobile scenarios in VANET, the algorithm is designed in a fully distributed way with low overhead. Simulations show that our method can notably improve the throughput of VANETs. And the performance keeps steady with various network configurations. Copyright © 2014 John Wiley & Sons, Ltd.

In this paper, we explore the idea of social role theory (SRT) and propose a novel regularized topic model which incorporates SRT into the generative process of social media content. We assume that a user can play multiple social roles, and each social role serves to fulfil different duties and is associated with a role-driven distribution over latent topics. In particular, we focus on social roles corresponding to the most common social activities on social networks. Our model is instantiated on microblogs, i.e., Twitter and community question-answering (cQA), i.e., Yahoo!Answers, where social roles on Twitter include “originators” and “propagators”, and roles on cQA are “askers” and “answerers”. Both explicit and implicit interactions between users are taken into account and modeled as regularization factors. To evaluate the performance of our proposed method, we have conducted extensive experiments on two Twitter datasets and two cQA datasets. Furthermore, we also consider multi-role modeling for scientific papers where an author's research expertise area is considered as a social role. A novel application of detecting users' research interests through topical keyword labeling based on the results of our multi-role model has been presented. The evaluation results have shown the feasibility and effectiveness of our model.

Mainstream indoor localization technologies rely on RF signatures that require extensive human efforts to measure and periodically re-calibrate. Although recent crowdsourcing based work has started to address the issue, incentives are still lacking for wide user adoption. Thus the progress to ubiquitous localization remains slow. In this paper, we explore an alternative approach that leverages environmental physical features such as store logos or wall posters. A user uses a smartphone to obtain relative position measurements to such static reference points for the system to triangulate the user location. We study the principle of such localization, determine the suitable sensor, and devise guidelines for the user to choose reference points for better accuracy. To enable fast deployment, we propose a lightweight site survey method for service providers to quickly estimate the coordinates of reference points. We incorporate and enhance image matching algorithms with a heuristic technique to automatically identify chosen reference points at high accuracy. Extensive experiments have shown that the prototype achieves 4-5m accuracy at 80-percentile, comparable to the industry state-of-the-art, while covering a 150×75m mall and 300×200m train station requires a one time investment of only 2-3 man-hours from service providers.

Product recommender systems are often deployed by e-commerce websites to improve user experience and increase sales. However, recommendation is limited by the product information hosted in those e-commerce sites and is only triggered when users are performing e-commerce activities. In this paper, we develop a novel product recommender system called METIS, a MErchanT Intelligence recommender System, which detects users' purchase intents from their microblogs in near real-time and makes product recommendation based on matching the users' demographic information extracted from their public profiles with product demographics learned from microblogs and online reviews. METIS distinguishes itself from traditional product recommender systems in the following aspects: 1) METIS was developed based on a microblogging service platform. As such, it is not limited by the information available in any specific e-commerce website. In addition, METIS is able to track users' purchase intents in near real-time and make recommendations accordingly. 2) In METIS, product recommendation is framed as a learning to rank problem. Users' characteristics extracted from their public profiles in microblogs and products' demographics learned from both online product reviews and microblogs are fed into learning to rank algorithms for product recommendation. We have evaluated our system in a large dataset crawled from Sina Weibo. The experimental results have verified the feasibility and effectiveness of our system. We have also made a demo version of our system publicly available and have implemented a live system which allows registered users to receive recommendations in real time.

The lack of floor plans is a critical reason behind the current sporadic availability of indoor localization service. Service providers have to go through effort-intensive and time-consuming business negotiations with building operators, or hire dedicated personnel to gather such data. In this paper, we propose Jigsaw, a floor plan reconstruction system that leverages crowdsensed data from mobile users. It extracts the position, size and orientation information of individual landmark objects from images taken by users. It also obtains the spatial relation between adjacent landmark objects from inertial sensor data, then computes the coordinates and orientations of these objects on an initial floor plan. By combining user mobility traces and locations where images are taken, it produces complete floor plans with hallway connectivity, room sizes and shapes. Our experiments on 3 stories of 2 large shopping malls show that the 90-percentile errors of positions and orientations of landmark objects are about 1~2m and 5~9°, while the hallway connectivity is 100% correct.

In cognitive radio (CR) networks, a pair of CR nodes have to ``rendezvous'' on a common channel for link establishment. Channel hopping (CH) protocols have been proposed for creating rendezvous over multiple channels to reduce the possibility of rendezvous failures caused by the detection of primary user signals. Rendezvous within a minimal bounded time over multiple channels is a challenging problem in heterogeneous CR networks where two CR nodes may have asynchronous clocks, different sensing capabilities, no common universal channel set, and heterogeneous channel index systems. In this paper, we present a systematic approach using group theory for designing CH protocols that guarantee the maximum number of rendezvous channels and the minimal time-to-rendezvous (TTR) in heterogeneous environments. We derive the minimum upper bound of TTR, and propose two types of rendezvous protocols that are independent of environmental heterogeneity. Analytical and simulation results show that these protocols are resistant to rendezvous failures under various network conditions.

Learning user interests from online social networks helps to better understand user behaviors and provides useful guidance to design user-centric applications. Apart from analyzing users' online content, it is also important to consider users' social connections in the social Web. Graph regularization methods have been widely used in various text mining tasks, which can leverage the graph structure information extracted from data. Previously, graph regularization methods operate under the cluster assumption that nearby nodes are more similar and nodes on the same structure (typically referred to as a cluster or a manifold) are likely to be similar. We argue that learning user interests from complex, sparse, and dynamic social networks should be based on the link structure assumption under which node similarities are evaluated based on the local link structures instead of explicit links between two nodes. We propose a regularization framework based on the relation bipartite graph, which can be constructed from any type of relations. Using Twitter as our case study, we evaluate our proposed framework from social networks built from retweet relations. Both quantitative and qualitative experiments show that our proposed method outperforms a few competitive baselines in learning user interests over a set of predefined topics. It also gives superior results compared to the baselines on retweet prediction and topical authority identification.

Cardiovascular disease (CVD) is a major issue to public health. It contributes 41% to the Chinese death rate each year. This huge loss encouraged us to develop a Wearable Efficient teleCARdiology systEm (WE-CARE) for early warning and prevention of CVD risks in real time. WE-CARE is expected to work 24/7 online for mobile health (mHealth) applications. Unfortunately, this purpose is often disrupted in system experiments and clinical trials, even if related enabling technologies work properly. This phenomenon is rooted in the overload issue of complex Electrocardiogram (ECG) data in terms of system integration. In this study, our main objective is to get a system light-loading technology to enable mHealth with a benchmarked ECG anomaly recognition rate. To achieve this objective, we propose an approach to purify clinical features from ECG raw data based on manifold learning, called the Manifold-based ECG-feature Purification algorithm. Our clinical trials verify that our proposal can detect anomalies with a recognition rate of up to 94% which is highly valuable in daily public health-risk alert applications based on clinical criteria. Most importantly, the experiment results demonstrate that the WE-CARE system enabled by our proposal can enhance system reliability by at least two times and reduce false negative rates to 0.76%, and extend the battery life by 40.54%, in the system integration level.

A large number of studies have been devoted to modeling the contents and interactions between users on Twitter. In this paper, we propose a method inspired from Social Role Theory (SRT), which assumes that a user behaves differently with different roles in the generation process of Twitter content. We consider the two most distinctive social roles on Twitter: originator and propagator, who respectively posts original messages and retweets or forwards the messages from others. In addition, we also consider role-specific social interactions, especially implicit interactions between users who share some common interests. All the above elements are integrated into a novel regularized topic model. We evaluate the proposed method on real Twitter data. The results show that our method is more effective than the existing ones which do not distinguish social roles.

Hot trends are likely to bring new business opportunities.For example, "Air Pollution" might lead to a significant increase of the sales of related products, e.g., mouth mask.For ecommerce companies, it is very important to make rapid and correct response to these hot trends in order to improve product sales.In this paper, we take the initiative to study the task of how to identify trend related products.The major novelty of our work is that we automatically learn commercial intents revealed from microblogs.We carefully construct a data collection for this task and present quite a few insightful findings.In order to solve this problem, we further propose a graph based method, which jointly models relevance and associativity.We perform extensive experiments and the results showed that our methods are very effective.

Timeline generation is an important research task which can help users to have a quick understanding of the overall evolution of any given topic. It thus attracts much attention from research communities in recent years. Nevertheless, existing work on timeline generation often ignores an important factor, the attention attracted to topics of interest (hereafter termed "social attention"). Without taking into consideration social attention, the generated timelines may not reflect users' collective interests. In this paper, we study how to incorporate social attention in the generation of timeline summaries. In particular, for a given topic, we capture social attention by learning users' collective interests in the form of word distributions from Twitter, which are subsequently incorporated into a unified framework for timeline summary generation. We construct four evaluation sets over six diverse topics. We demonstrate that our proposed approach is able to generate both informative and interesting timelines. Our work sheds light on the feasibility of incorporating social attention into traditional text mining tasks.

This paper proposes a dynamic physical-virtual NIC switching. A virtual machine directly accessing the physical NIC can switch to use the virtual NIC if it is to be migrated. This solution is implemented in network configuration level in Guest OS drivers, so it can be used in different VMMs and with different NICs. The experiments illustrate that our solution does not interrupt the network connections from clients' perspective. After the virtual machine switches to use the virtual NIC, it can be migrated and the switching will not affect the migration performance, including the downtime during the migration.

Lots of document collections are well organized in hierarchical structure, and such structure can help users browse and understand these collections. Meanwhile, there are a large number of plain document collections loosely organized, and it is difficult for users to understand them effectively. In this paper we study how to automatically integrate latent topics in a plain collection with the topics in a hierarchical structured collection. We propose to use semi-supervised topic modeling to solve the problem in a principled way. The experiments show that the proposed method can generate both meaningful latent topics and expand high quality hierarchical topic structures.

Recently, statistical topic modeling has been widely applied in text mining and knowledge management due to its powerful ability. A topic, as a probability distribution over words, is usually difficult to be understood. A common, major challenge in applying such topic models to other knowledge management problem is to accurately interpret the meaning of each topic. Topic labeling, as a major interpreting method, has attracted significant attention recently. However, previous works simply treat topics individually without considering the hierarchical relation among topics, and less attention has been paid to creating a good hierarchical topic descriptors for a hierarchy of topics. In this paper, we propose two effective algorithms that automatically assign concise labels to each topic in a hierarchy by exploiting sibling and parent-child relations among topics. The experimental results show that the inter-topic relation is effective in boosting topic labeling accuracy and the proposed algorithms can generate meaningful topic labels that are useful for interpreting the hierarchical topics.

We present a novel graph-based framework for timeline summarization, the task of creating different summaries for different timestamps but for the same topic. Our work extends timeline summarization to a multimodal setting and creates timelines that are both textual and visual. Our approach exploits the fact that news documents are often accompanied by pictures and the two share some common content. Our model optimizes local summary creation and global timeline generation jointly following an iterative approach based on mutual reinforcement and co-ranking. In our algorithm, individual summaries are generated by taking into account the mutual dependencies between sentences and images, and are iteratively refined by considering how they contribute to the global timeline and its coherence. Experiments on real-world datasets show that the timelines produced by our model outperform several competitive baselines both in terms of ROUGE and when assessed by human evaluators.

As the study of large graphs over hundreds of gigabytes becomes increasingly popular for various data-intensive applications in cloud computing, developing large graph processing systems has become a hot and fruitful research area. Many of those existing systems support a vertex-oriented execution model and allow users to develop custom logics on vertices. However, the inherently random access pattern on the vertex-oriented computation generates a significant amount of network traffic. While graph partitioning is known to be effective to reduce network traffic in graph processing, there is little attention given to how graph partitioning can be effectively integrated into large graph processing in the cloud environment. In this paper, we develop a novel graph partitioning framework to improve the network performance of graph partitioning itself, partitioned graph storage and vertex-oriented graph processing. All optimizations are specifically designed for the cloud network environment. In experiments, we develop a system prototype following Pregel (the latest vertex-oriented graph engine by Google), and extend it with our graph partitioning framework. We conduct the experiments with a real-world social network and synthetic graphs over 100GB each in a local cluster and on Amazon EC2. Our experimental results demonstrate the efficiency of our graph partitioning framework, and the effectiveness of network performance aware optimizations on the large graph processing engine.

In this paper, we present an efficient routing protocol for Mobile Hybrid Wireless Networks (MHWNs), which consists of an infrastructure wireless network and a few mobile ad hoc networks. MHWNs have several advantages over traditional wireless networks (such as cellular networks and WLANs). For example, MHWNs can achieve higher throughput, larger coverage, and better load balancing cross cells. In this paper, we present an efficient routing protocol for MHWNs. The protocol utilizes node location information, moving speed, and remaining battery life for routing decision. The protocol is energy efficient (for mobile nodes) and can find robust routing path. We evaluate its performance by NS-2 simulations. Our results show that the protocol significantly reduces the routing overhead, and the routing path is relatively stable.

We present EventSearch, a system for event extraction and retrieval on four types of news-related historical data, i.e., Web news articles, newspapers, TV news program, and micro-blog short messages. The system incorporates over 11 million web pages extracted from "Web InfoMall", the Chinese Web Archive since 2001. The newspaper and TV news video clips also span from 2001 to 2011. The system, upon a user query, returns a list of event snippets from multiple data sources. A novel burst model is used to discover events from time-stamped texts. In addition to offline event extraction, our system also provides online event extraction to further meet the user needs. EventSearch provides meaningful analytics that synthesize an accurate description of events. Users interact with the system by ranking the identified events using different criteria (scale, recency and relevance) and submitting their own information needs in different input fields.

Cache sharing among multiple computing units on chip is common in today's multi-core processors, and a lot of research has focused on the effective management of shared cache. A software management method called page coloring is commonly used to divide the cache among different applications competing for the same cache entries. Both static and dynamic cache partition mechanism have been implemented in operating system or user-space level. However, few efforts have been made under virtualization environments. Our previous work has provided a static cache partition method based on page coloring in Xen, following that, a dynamic cache partition mechanism called Colored Page Migration (CoPaM) is presented in this paper.

Large web search engines are facing formidable performance challenges because they have to process thousands of queries per second on tens of billions of documents, within interactive response time. Among many others, Top-k query processing (also called early termination or dynamic pruning) is an important class of optimization techniques that can improve the search efficiency and achieve faster query processing by avoiding the scoring of documents that are unlikely to be in the top results. One recent technique is using Block-Max index. In the Block-Max index, the posting lists are organized as blocks and the maximum score for each block is stored to improve the query efficiency. Although query processing speedup is achieved with Block-Max index, the ranking function for the Top-k results is the term-based approach. It is well known that documents' static scores are also important for a good ranking function. In this paper, we show that the performance of the state-of-the-art algorithms with the Block-Max index is degraded when the static score is added in the ranking function. Then we study efficient techniques for Top-k query processing in the case where a page's static score is given, such as PageRank, in addition to the term-based approach. In particular, we propose a set of new algorithms based on the WAND and MaxScore with Block-Max index using local score, which outperform the existing ones. Then we propose new techniques to estimate a better score upper bound for each block. We also study the search efficiency on different index structures where the document identifiers are assigned by URL sorting or by static document scores. Experiments on TREC GOV2 and ClueWeb09B show that considerable performance gains are achieved.

Data dissemination is an important technology for most VANET applications. Due to the physical factors like traffic lights, the density of vehicles is usually uneven. Areas near intersections often have a high node density while areas near the center of streets can have a very low node density. The uneven distribution of nodes and the movement pattern of vehicles cause intermittent connections and redundant transmissions, which we call MIRT (Mobility Induced Redundant Transmission). Existing data dissemination algorithms did not pay enough attention to MIRT and the intermittent connections of the network, which makes them unsuitable for realistic VANET scenarios. In this paper, we propose the Bloom Filter based Buffering Data Dissemination (BFBD) algorithm. BFBD copes with MIRT by using decayed bloom filter as the structure to record the data dissemination history and handles the intermittent connectivity by a carefully designed buffering mechanism. Extensive simulations show the performance of BFBD is superior over contrastive algorithms in terms of reliability, dissemination efficiency and delay.

A large proportion of search engine queries contain phrases,namely a sequence of adjacent words. In this paper, we propose to use flat position index (a.k.a schema-independent index) for phrase query evaluation. In the flat position index, the entire document collection is viewed as a huge sequence of tokens. Each token is represented by one flat position, which is a unique position offset from the beginning of the collection. Each indexed term is associated with a list of the flat positions about that term in the sequence. To recover DocID from flat positions efficiently, we propose a novel cache sensitive look-up table (CSLT), which is much faster than existing search algorithms. Experiments on TREC GOV2 data collection show that flat position index can reduce the index size and speed up phrase querying substantially, compared with traditional word-level index.

In most of the cases, scientists depend on previous literature which is relevant to their research fields for developing new ideas. However, it is not wise, nor possible, to track all existed publications because the volume of literature collection grows extremely fast. Therefore, researchers generally follow, or cite merely a small proportion of publications which they are interested in. For such a large collection, it is rather interesting to forecast which kind of literature is more likely to attract scientists' response. In this paper, we use the citations as a measurement for the popularity among researchers and study the interesting problem of Citation Count Prediction (CCP) to examine the characteristics for popularity. Estimation of possible popularity is of great significance and is quite challenging. We have utilized several features of fundamental characteristics for those papers that are highly cited and have predicted the popularity degree of each literature in the future. We have implemented a system which takes a series of features of a particular publication as input and produces as output the estimated citation counts of that article after a given time period. We consider several regression models to formulate the learning process and evaluate their performance based on the coefficient of determination (R-square). Experimental results on a real-large data set show that the best predictive model achieves a mean average predictive performance of 0.740 measured in R-square, which significantly outperforms several alternative algorithms.

We present a link capacity estimation model and a hybrid routing scheme for wireless mesh networks which aims at improving throughput. The multi-source interference between links and frame capture behaviors of nodes are analyzed. Our model provides estimated values which can indicate the relative quality of wireless links. And we present a routing metric which combines multiple factors based on the estimated values. The proposed routing scheme which is independent of special routing protocols adopts different strategies for the traffic of accessing the Internet and the end-to-end traffic. Besides, we introduce a new gateway-assisted routing technique to further improve the performance. Simulation results show that the estimation model provides accurate estimated values enough for route selection, and the routing scheme improves end-to-end throughput by 185% compared with legacy AODV[14] protocol.

The heterogeneous nature of Peer-to-Peer (P2P) networks can be exploited to optimize a wide range of applications. But this requires an accurate characterization of peer heterogeneity, which is difficult due to huge population and disparate properties of individuals. To overcome this barrier, we conduct a thorough inspection of peer heterogeneity in terms of individual churn and resource capacity. We make a first attempt to (i) experimentally reduce heterogeneous churn and resource dynamics to simple distributions with individual-specific parameters, and to (ii) provide an empirical support for the heterogeneous Markov model of churn. We further demonstrate how our characterization can be leveraged to optimize practical systems, through two case studies: fast backup in online storage and fault-tolerance in cycle-sharing systems. Both applications gain remarkable performance improvement by incorporating our model of peer heterogeneity.

Various click models have been recently proposed as a principled approach to infer the relevance of documents from the clickthrough data. The inferred document relevance is potentially useful in evaluating the Web retrieval systems. In practice, it generally requires to acquire the accurate evaluation results within minimal users' query submissions. This problem is important for speeding up search engine development and evaluation cycle and acquiring reliable evaluation results on tail queries. In this paper, we propose a reordering framework for efficient evaluation problem in the context of clickthrough based Web retrieval evaluation. The main idea is to move up the documents that contribute more for the evaluation task. In this framework, we propose four intuitions and formulate them as an optimization problem. Both user study and TREC data based experiments validate that the reordering framework results in much fewer query submissions to get accurate evaluation results with only a little harm to the users' utility.

Classic news summarization plays an important role with the exponential document growth on the Web. Many approaches are proposed to generate summaries but seldom simultaneously consider evolutionary characteristics of news plus to traditional summary elements. Therefore, we present a novel framework for the web mining problem named Evolutionary Timeline Summarization (ETS). Given the massive collection of time-stamped web documents related to a general news query, ETS aims to return the evolution trajectory along the timeline, consisting of individual but correlated summaries of each date, emphasizing relevance, coverage, coherence and cross-date diversity. ETS greatly facilitates fast news browsing and knowledge comprehension and hence is a necessity. We formally formulate the task as an optimization problem via iterative substitution from a set of sentences to a subset of sentences that satisfies the above requirements, balancing coherence/diversity measurement and local/global summary quality. The optimized substitution is iteratively conducted by incorporating several constraints until convergence. We develop experimental systems to evaluate on 6 instinctively different datasets which amount to 10251 documents. Performance comparisons between different system-generated timelines and manually created ones by human editors demonstrate the effectiveness of our proposed framework in terms of ROUGE metrics.

As virtualization becomes a key technique for supporting cloud computing, much effort has been made to reduce virtualization overhead, so a virtualized system can match its native performance. One major overhead is due to memory or page table virtualization. Conventional virtual machines rely on a shadow mechanism to manage page tables, where a shadow page table maintained by the VMM (Virtual Machine Monitor) maps virtual addresses to machine addresses while a guest maintains its own virtual to physical page table. This shadow mechanism will result in expensive VM exits whenever there is a page fault that requires synchronization between the two page tables. To avoid this cost, both Intel and AMD provide hardware assists, EPT (extended page table) and NPT (nested page table), to facilitate address translation. With the hardware assists, the MMU (Memory Management Unit) maintains an ordinary guest page table that translates virtual addresses to guest physical addresses. In addition, the extended page table as provided by EPT translates from guest physical addresses to host physical or machine addresses. NPT works in a similar style. With EPT or NPT, a guest page fault can be handled by the guest itself without triggering VM exits. However, the hardware assists do have their disadvantage compared to the conventional shadow mechanism -- the page walk yields more memory accesses and thus longer latency. Our experimental results show that neither hardware-assisted paging (HAP) nor shadow paging (SP) can be a definite winner. Despite the fact that in over half of the cases, there is no noticeable gap between the two mechanisms, an up to 34% performance gap exists for a few benchmarks. We propose a dynamic switching mechanism that monitors TLB misses and guest page faults on the fly, and dynam-ically switches between the two paging modes. Our experiments show that this new mechanism can match and, sometimes, even beat the better performance of HAP and SP.

Hypervisor-based fault tolerance (HBFT), which synchronizes the state between the primary VM and the backup VM at a high frequency of tens to hundreds of milliseconds, is an emerging approach to sustaining mission-critical applications. Based on virtualization technology, HBFT provides an economic and transparent fault tolerant solution. However, the advantages currently come at the cost of substantial performance overhead during failure-free, especially for memory intensive applications. This paper presents an in-depth examination of HBFT and options to improve its performance. Based on the behavior of memory accesses among checkpointing epochs, we introduce two optimizations, read-fault reduction and write-fault prediction, for the memory tracking mechanism. These two optimizations improve the performance by 31 percent and 21 percent, respectively, for some applications. Then, we present software superpage which efficiently maps large memory regions between virtual machines (VM). Our optimization improves the performance of HBFT by a factor of 1.4 to 2.2 and achieves about 60 percent of that of the native VM.

Bursty features in text streams are very useful in many text mining applications. Most existing studies detect bursty features based purely on term frequency changes without taking into account the semantic contexts of terms, and as a result the detected bursty features may not always be interesting or easy to interpret. In this paper we propose to model the contexts of bursty features using a language modeling approach. We then propose a novel topic diversity-based metric using the context models to find newsworthy bursty features. We also propose to use the context models to automatically assign meaningful tags to bursty features. Using a large corpus of a stream of news articles, we quantitatively show that the proposed context language models for bursty features can effectively help rank bursty features based on their newsworthiness and to assign meaningful tags to annotate bursty features.

The Cranfield evaluation method has some disadvantages, including its high cost in labor and inadequacy for evaluating interactive retrieval techniques. As a very promising alternative, automatic comparison of retrieval systems based on observed clicking behavior of users has recently been studied. Several methods have been proposed, but there has so far been no systematic way to assess which strategy is better, making it difficult to choose a good method for real applications. In this paper, we propose a general way to evaluate these relative comparison methods with two measures: utility to users(UtU) and effectiveness of differentiation(EoD). We evaluate two state of the art methods by systematically simulating different retrieval scenarios. Inspired by the weakness of these methods revealed through our evaluation, we further propose a novel method by considering the positions of clicked documents. Experiment results show that our new method performs better than the existing methods.

Virtual Machine (VM) cloning is to create a replica of a source virtual machine (parent virtual machine); the replica, also called child virtual machine, owns exactly the same executing status as parent virtual machine. Fast live cloning guarantees that, during the period of cloning, the services running on the parent virtual machine observe no performance degradation. There are three important goals for fast live cloning: reducing the total cloning time, minimizing the suspension time of the parent virtual machine, and maximizing resource sharing between the parent virtual machine and the child virtual machine. This paper exploits Copy-on-Write (CoW) mechanism fully to minimize the time of duplicating active main memory and secondary storage of the parent virtual machine. As a result, out experiments show that the total cloning time of a virtual machine on Xen virtual machine monitor can be confined within several hundred milliseconds and the downtime of parent virtual machine is limited to tens of milliseconds, close to VMM’s scheduling interval. Experiments also show that the parent virtual machine highly shares memory with the child virtual machine as long as both virtual machines continue executing the same applications.

In virtual machine (VM) systems, with the increase in the number of VMs and the demands of applications, the main memory is becoming a bottleneck of application performance. To improve paging performance for memory-intensive or I/O-intensive workloads, we propose the hypervisor REMOte disk CAche (REMOCA), which allows a virtual machine to use the memory resources on other physical machines as its cache between its virtual memory and virtual disk devices. The goal of REMOCA is to reduce disk accesses, which is much slower than transferring memory pages over modern interconnect networks. As a result, the average disk I/O latency can be improved. REMOCA is implemented within the hypervisor, by intercepting guest events such as page evictions and disk accesses. This design is transparent to the applications, and is compatible with existing techniques like ballooning and ghost buffer. Moreover, a combination of them can provide a more flexible resource management policy. Our experimental results show that REMOCA can efficiently alleviate the impact of thrashing behavior, and also significantly improve the performance for real-world I/O intensive applications.

Virtualization is often used in systems for the purpose of offering isolation among applications running in separate virtual machines (VM). Current virtual machine monitors (VMMs) have done a decent job in resource isolation in memory, CPU and I/O devices. However, when looking further into the usage of lower-level shared cache, we notice that one virtual machine’s cache behavior may interfere with another’s due to the uncontrolled cache sharing. In this situation, performance isolation cannot be guaranteed. This paper presents a cache partitioning approach which can be implemented in the VMM. We have implemented this mechanism in Xen VMM using the page coloring technique traditionally applied to the OS. Our VMM-based implementation is fully transparent to the guest OSes. It thus shows the advantages of simplicity and flexibility. Our evaluation shows that our cache partitioning method can work efficiently and improve the performance of co-scheduled applications running within different VMs. In the concurrent workloads selected from the SPEC CPU 2006 benchmarks, our technique achieves a performance improvement by up to 19% for the most sensitive workloads

Abstract To achieve high data availability or reliability in an efficient manner, distributed storage systems must detect whether an observed node failure is permanent or transient, and if necessary, generate replicas to restore the desired level of replication. Given the unpredictability of network dynamics, however, distinguishing permanent and transient failures is extremely difficult. Though timeout‐based detectors can be used to avoid mistaking transient failures as permanent failures, it is unknown how the timeout values should be selected to achieve a better tradeoff between detection latency and accuracy. In this paper, we address this fundamental tradeoff from several perspectives. First, we explore the impact of different timeout values on maintenance cost by examining the probability of their false positives and false negatives. Second, we propose a self‐configurable failure detector called the Neutralizer based on the idea of counteracting false positives with false negatives. The Neutralizer could enable the system to maintain a desired replication level on average with the least amount of bandwidth. We conduct extensive simulations using real trace data from a widely deployed peer‐to‐peer system and synthetic traces based on PlanetLab and Microsoft PCs, showing a significant reduction in aggregate bandwidth usage after applying the Neutralizer (especially in an environment with a low average node availability). Overall, we demonstrate that the Neutralizer closely approximates the performance of a perfect ‘oracle’ detector in many cases. Copyright © 2008 John Wiley & Sons, Ltd.

To find near-duplicate documents, fingerprint-based paradigms such as Broder's shingling and Charikar's simhash algorithms have been recognized as effective approaches and are considered the state-of-the-art. Nevertheless, we see two aspects of these approaches which may be improved. First, high score under these algorithms' similarity measurement implies high probability of similarity between documents, which is different from high similarity of the documents. But how similar two documents are is what we really need to know. Second, there has to be a tradeoff between hash-code length and hash-code multiplicity in fingerprint paradigms, which makes it hard to maintain a satisfactory recall level while improving precision.

As opposed to representing a document as a "bag of words" in most information retrieval applications, we propose a model of representing a web page as sets of named entities of multiple types. Specifically, four types of named entities are extracted, namely person, geographic location, organization, and time. Moreover, the relations among these entities are also extracted, weighted, classified and marked by labels. On top of this model, some interesting applications are demonstrated. In particular, we introduce a notion of person-activity, which contains four different elements: person, location, time and activity. With this notion and based on a reasonably large set of web pages, we are able to show how one person's activities can be attributed by time and location, which gives a good idea of the mobility of the person under question.

In this paper, we describe an experimental search engine on our Chinese web archive since 2001. The original data set contains nearly 3 billion Chinese web pages crawled from past 5 years. From the collection, 430 million "article-like" pages are selected and then partitioned into 68 million sets of similar pages. The titles and publication dates are determined for the pages. An index is built. When searching, the system returns related pages in a chronological order. This way, if a user is interested in news reports or commentaries for certain previously happened event, he/she will be able to find a quite rich set of highly related pages in a convenient way.

Popular entities often have thousands of instances on the Web. In this paper, we focus on the case where they are presented in table-like format, namely appearing with their attribute names. It is observed that, on one hand, for the same entity, different web pages often incorporate different attributes; on the other, for the same attribute, different web pages often use different attribute names (labels). Therefore, it is imaginably difficult to produce a global attribute schema for all the web entities of a given entity type based on their web instances, although the global attribute schema is usually highly desired in web entity instances integration and web object extraction. To this end, we propose a novel framework of automatically learning a global attribute schema for all web entities of one specific entity type. Under this framework, an iterative instances extraction procedure is first employed to extract sufficient web entity instances to discover enough attribute labels. Next, based on the labels, entity instances, and related web pages, a maximum entropy-based schema discovery approach is adopted to learn the global attribute schema for the target entity type. Experimental results on the Chinese Web achieve weighted average Fscores of 0.7122 and 0.7123 on two global attribute schemas for person-type and movie-type web entities, respectively. These results show that our framework is general, efficient and effective.

The shape of the Web in terms of its graphical structure has been a widely interested topic. Two graphs, Bow Tie and Daisy, have stood out from previous research. In this work, we take a different approach, by viewing the Web as a hierarchy of three levels, namely page level, host level, and domain level. Such structures are analyzed and compared with a snapshot of Chinese Web in early 2006, involving 830 million pages, 17 million hosts, and 0.8 million domains. Some interesting results have emerged. For example, the Chinese Web appears more like a teapot (with a large size of SCC, a medium size of IN and a small size of OUT) at page level than the classic bow tie or daisy shape. Some challenging phenomena are also observed. For example, the INs become much smaller than OUTs at host and domain levels. Future work will tackle these puzzles.

Abstract Much work has been done to address the need for incentive models in real deployed peer‐to‐peer networks. In this paper, we discuss problems found with the incentive model in a large, deployed peer‐to‐peer network, Maze. We evaluate several alternatives, and propose an incentive system that generates preferences for well‐behaved nodes while correctly punishing colluders. We discuss our proposal as a hybrid between Tit‐for‐Tat and EigenTrust, and show its effectiveness through simulation of real traces of the Maze system. Copyright © 2007 John Wiley & Sons, Ltd.

Graphs have been widely used to model relationships among data. For large graphs, excessive edge crossings make the display visually cluttered and thus difficult to explore. In this paper, we propose a novel geometry-based edge-clustering framework that can group edges into bundles to reduce the overall edge crossings. Our method uses a control mesh to guide the edge-clustering process; edge bundles can be formed by forcing all edges to pass through some control points on the mesh. The control mesh can be generated at different levels of detail either manually or automatically based on underlying graph patterns. Users can further interact with the edge-clustering results through several advanced visualization techniques such as color and opacity enhancement. Compared with other edge-clustering methods, our approach is intuitive, flexible, and efficient. The experiments on some large graphs demonstrate the effectiveness of our method.

Peer-to-peer networks often use incentive policies to encourage cooperation between nodes. Such systems are generally susceptible to collusion by groups of users in order to gain unfair advantages over others. While techniques have been proposed to combat Web spam collusion, there are few measurements of real collusion in deployed systems. In this paper, we report analysis and measurement results of user collusion in Maze, a large-scale peer-to-peer file sharing system with a non-net-zero point-based incentive policy. We search for colluding behavior by examining complete user logs, and incrementally refine a set of collusion detectors to identify common collusion patterns. We find collusion patterns similar to those found in Web spamming. We evaluate how proposed reputation systems would perform on the Maze system. Our results can help guide the design of more robust incentive schemes.

The architecture of P2P file-sharing applications has been developing to meet the needs of large scale demands. The structured overlay network, also known as DHT, has been used in these applications to improve the scalability, robustness of the system, and to make it free from single-point failure. We believe that the measurement study of the overlay network used in the real file-sharing P2P systems can provide guidance for the designing of such systems, and improve the performance of the system. In this paper, we perform the measurement in two different aspects. First, the modified client provides view to the overlay network from a single user vision. Second, the instances of crawler programs deployed in many nodes managed to crawl the user information of the overlay network as much as possible. We find vulnerability in the overlay network, combined with the character of the DNS service; a more serious DDos attack can be launched

In this paper, we propose a novel approach to emulate an arbitrary wireless multi-hop network scenario in a fixed wireless testbed, in which every node is equipped with a variable attenuator. We formulate the core problem of wireless multi-hop network scenario emulation as a constrained optimization problem and propose an optimum algorithm

Abstract The CSFS (cryptographic storage file system) is a network file storage system that is suitable for a small‐to‐medium sized networks such as a campus network. In a CSFS, a lot of distributed file servers are organized in a star‐liked architecture. File names are stored in a name server and file data are stored in distributed file servers. A CSFS has good scalability and is able to accommodate hundreds of file servers. We implemented a CSFS in pure Java and tested the system with a benchmark. The test results show that CSFS delivers acceptable performance for general file operations. Its performance of file upload and download is as efficient as FTP. It can support more than 450 concurrent online users. Copyright © 2005 John Wiley & Sons, Ltd.

This paper presents an architectural design and evaluation result of an efficient Web-crawling system. The design involves a fully distributed architecture, a URL allocating algorithm, and a method to assure system scalability and dynamic reconfigurability. Simulation experiment shows that load balance, scalability and efficiency can be achieved in the system. Currently this distributed Web-crawling subsystem has been successfully integrated with WebGather, a well-known Chinese and English Web search engine, aimed at collecting all the Web pages in China and keeping pace with the rapid growth of Chinese Web information. In addition, we believe that the design can also be useful in other context such as digital library, etc. 2002 Elsevier Science Inc. All rights reserved.

Abstract A well‐known model for network reliability studies consists of an undirected graph with perfectly reliable nodes and equal and independent edge failure probabilities. The measure of reliability is then defined to be the probability that the graph is connected. A well‐defined synthesis problem is to find the graph that minimizes the failure probability given the number of nodes n, the number of edges e, and the edge failure rate ρ. In this work, we consider the possibility of the existence of a fixed graph that is optimal for all possible ρ. It is simple to verify that such graphs exist when e = n − 1, or n. Herein, we show that they also exist when e = n + 1 and n + 2.