Efficient clustering of uncertain data streams

Clustering uncertain data streams has recently become one of the most challenging tasks in data management because of the strict space and time requirements of processing tuples arriving at high speed and the difficulty that arises from handling uncertain data. The prior work on clustering data streams focuses on devising complicated synopsis data structures to summarize data streams into a small number of micro-clusters so that important statistics can be computed conveniently, such as Clustering Feature (CF) (Zhang et al. in Proceedings of ACM SIGMOD, pp 103–114, 1996) for deterministic data and Error-based Clustering Feature (ECF) (Aggarwal and Yu in Proceedings of ICDE, 2008) for uncertain data. However, ECF can only handle attribute-level uncertainty, while existential uncertainty, the other kind of uncertainty, has not been addressed yet. In this paper, we propose a novel data structure, Uncertain Feature (UF), to summarize data streams with both kinds of uncertainties: UF is space-efficient, has additive and subtractive properties, and can compute complicated statistics easily. Our first attempt aims at enhancing the previous streaming approaches to handle the sliding-window model by using UF instead of old synopses, inclusive of CluStream (Aggarwal et al. in Proceedings of VLDB, 2003) and UMicro (Aggarwal and Yu in Proceedings of ICDE, 2008). We show that such methods cannot achieve high efficiency. Our second attempt aims at devising a novel algorithm, cluUS , to handle the sliding-window model by using UF structure. Detailed analysis and thorough experimental reports on synthetic and real data sets confirm the advantages of our proposed method.     

On measuring network robustness for weighted networks

Knowledge and Information Systems - Network robustness measures how well network structure is strong and healthy when it is under attack, such as vertices joining and leaving. It has been widely...     

A framework for cloned vehicle detection

Rampant cloned vehicle offenses have caused great damage to transportation management as well as public safety and even the world economy. It necessitates an efficient detection mechanism to identify the vehicles with fake license plates accurately, and further explore the motives through discerning the behaviors of cloned vehicles. The ubiquitous inspection spots that deployed in the city have been collecting moving information of passing vehicles, which opens up a new opportunity for cloned vehicle detection. Existing detection methods cannot detect the cloned vehicle effectively due to that they use the fixed speed threshold. In this paper, we propose a two-phase framework, called CVDF, to detect cloned vehicles and discriminate behavior patterns of vehicles that use the same plate number. In the detection phase, cloned vehicles are identified based on speed thresholds extracted from historical trajectory and behavior abnormality analysis within the local neighborhood. In the behavior analysis phase, consider the traces of vehicles that uses the same license plate will be mixed together, we aim to differentiate the trajectories through matching degreebased clustering and then extract frequent temporal behavior patterns. The experimental results on the real-world data show that CVDF framework has high detection precision and could reveal cloned vehicles’ behavior effectively. Our proposal provides a scientific basis for traffic management authority to solve the crime of cloned vehicle.     

Popular route planning with travel cost estimation from trajectories

With the increasing number of GPS-equipped vehicles,more and more trajectories are generated continuously,based on which some urban applications become feasible,such as route planning.In general,popular route that has been travelled frequently is a good choice,especially for people who are not familiar with the road networks.Moreover,accurate estimation of the travel cost(such as travel time,travel fee and fuel consumption)will benefit a wellscheduled trip plan.In this paper,we address this issue by finding the popular route with travel cost estimation.To this end,we design a system consists of three main components.First,we propose a novel structure,called popular traverse graph where each node is a popular location and each edge is a popular route between locations,to summarize historical trajectories without road network information.Second,we propose a self-adaptive method to model the travel cost on each popular route at different time interval,so that each time interval has a stable travel cost.Finally,based on the graph,given a query consists of source,destination and leaving time,we devise an efficient route planning algorithmwhich considers optimal route concatenation to search the popular route from source to destination at the leaving time with accurate travel cost estimation.Moreover,we conduct comprehensive experiments and implement our system by a mobile App,the results show that our method is both effective and efficient.     

面向不确定图的k最近邻查询

生物网络、社会网络、交际网络等复杂的网络被广泛的研究,由于数据抽出时引入的噪声和错误使这些数据具有不确定性,因此可以对这些应用使用不确定图模型建模,k最近邻查询问题是查询一个图上的距离某个特定点最近的k个邻居节点的问题,它是不确定图上的一个基础问题.设计了一个解决不确定图上最近邻问题的框架,首先定义了一种新颖的不确定图上的k最近邻查询,然后提出了针对该查询的一般处理算法,同时对该算法进行了优化,使算法效率得到极大提高.理论分析和实验结果表明提出的算法能够高效地处理不确定图上的k最近邻查询.     

Making filters smart in distributed data stream environments

Monitoring aggregate queries in real-time over distributed streaming environments appears to be a great challenge not only because of the huge data volume and high rate, but also because of the limitation of the network transmission bandwidth. Consequently, ensuring qualified approximate results with economical network consumption becomes one of the most important goals in such scenarios. In this paper, we study how to monitor aggregate queries continuously over distributed environments efficiently by disposing numerous filters at remote sites, in order to transmit only a small part of incoming data to the query site and therefore save the network resource significantly. We also show how to adjust the parameters of a filter continuously when the incoming data distribution at the corresponding remote site changes. Analysis and extensive experimental results demonstrate that our approach outperforms the existing work.     

面向不确定数据流的近似ER-Topk查询处理

随着移动互联网的快速发展以及信息技术的普遍应用,在许多应用中都产生了海量、不确定性数据,包括金融、军事、位置服务、医疗以及气象等。然而,传统的确定性数据管理方法很难管理不确定数据,亟需开发新型数据管理方法。可能世界模型被广泛用于为不确定数据建模,通过该模型可以衍生出诸多确定性的可能世界实例。不确定性数据流是指高速到达的海量不确定元组序列,因而不确定数据流管理比不确定性静态数据管理更具挑战性。面向于不确定数据流的ER-Topk查询是一个典型问题,但是处理复杂度高。提出一种近似算法来处理该查询,具有较小的空间复杂度;同时,还通过搜索策略优化来进一步提升查询处理效率。实验结果验证了所提方法的有效性和高效性。     

基于手机轨迹数据的人口流动分析

随着通信技术的发展和智能手机的普及,运营商基站所采集的大规模手机轨迹数据在城市规划、人口迁移等领域中发挥了重要价值。针对城市人口流动问题,提出一种利用手机轨迹数据的基于轨迹行为特征的人口流动判定(MF-JUPF)算法。首先,可对手机轨迹数据进行数据预处理,以提取用户活动轨迹;然后根据进出城市的行为模式提取重要特征,再根据真实标注数据集合利用多种分类模型进行参数训练;最后,根据模型训练结果判定用户轨迹是否为进出城市行为。所提系统使用MapReduce框架进行数据分析,以提高性能和可扩展性。基于真实数据集合的实验结果表明,对于进出城市的判定,该方法的准确率和召回率可达80%以上,与基于信号消失时长的人口流动判定(SD-JUPF)算法相比,在判定进入城市的准确率上提高了19.0%,召回率提高了13.9%;在判定离开城市的准确率上提高了17.3%,召回率提高了6.1%。相比非过滤算法,根据手机轨迹数据特点进行的数据过滤算法可减少处理时间36.1%以上。理论分析和实验结果表明MF-JUPF方法精度高,可扩展性好,因此对城市规划等领域有重要应用价值。     

Benchmarking in-memory database

We have witnessed exciting development of RAM technology in the past decade. The memory size grows rapidly and the price continues to decrease, so that it is feasible to deploy large amounts of RAM in a computer system. Several companies and research institutions have devoted a lot of resources to develop in-memory databases (IMDB) that implement queries after loading data into (virtual) memory in advance. The bloom of various in-memory databases pursues us to test and evaluate their performance objectively and fairly. Although the existing database benchmarks like Wisconsin benchmark and TPC-X series have achieved great success, they cannot suit for in-memory databases due to the lack of consideration of unique characteristics of an IMDB. In this study, we propose MemTest, a novel benchmark that concerns some major characteristics of an in-memory database. This benchmark constructs particular metrics, which cover processing time, compression ratio, minimal memory space and column strength of an in-memory database. We design a data model based on inter-bank transaction applications, and a data generator to support uniform and skew data distributions. The MemTest workload includes a set of queries and transactions against the metrics and data model. Finally, we illustrate the efficacy of MemTest through the implementations on two different in-memory databases.     

Sliding-window top-k queries on uncertain streams

Recently, due to the imprecise nature of the data generated from a variety of streaming applications, such as sensor networks, query processing on uncertain data streams has become an important problem. However, all the existing works on uncertain data streams study unbounded streams. In this paper, we take the first step towards the important and challenging problem of answering sliding-window queries on uncertain data streams, with a focus on one of the most important types of queries—top-k queries. It is nontrivial to find an efficient solution for answering sliding-window top-k queries on uncertain data streams, because challenges not only stem from the strict space and time requirements of processing both arriving and expiring tuples in high-speed streams, but also rise from the exponential blowup in the number of possible worlds induced by the uncertain data model. In this paper, we design a unified framework for processing sliding-window top-k queries on uncertain streams. We show that all the existing top-k definitions in the literature can be plugged into our framework, resulting in several succinct synopses that use space much smaller than the window size, while they are also highly efficient in terms of processing time. We also extend our framework to answering multiple top-k queries. In addition to the theoretical space and time bounds that we prove for these synopses, we present a thorough experimental report to verify their practical efficiency on both synthetic and real data.