Approximate K-Median of Location Streams with Redundancy and Inconsistency
    Download PDF
Zhihong Chong,Weiwei Ni,Lizhen Xu,Zhuoming Xu,Hu Shu,Jinwang Zheng. Approximate K-Median of Location Streams with Redundancy and Inconsistency. International Journal of Software and Informatics, 2010,4(2):165~182
Hits: 3418
Download times: 2327
Fund:This work is sponsored by the National Natural Science Foundation of China (Grant No. 60973023),the Natural Science Foundation of Jiangsu Province of China (Grant No. BK2008354).
Abstract:Data streams produced by positioning systems such as Global Positioning System (GPS) or RFID readers can be considered as location streams[12]. Location streams are usually generated in a distributed fashion by a large scale distributed system covering a wide range of areas. Computing on distributed location streams is both practically useful and theoretically challenging. The results of computation could be used to schedule the traffic in a metropolis to avoid traffic jam, dispatch taxis to serve the passengers more quickly and display the current position of goods in supply chain management, etc. Since location streams are usually generated with very high rate in uncertain ways over hostile environments, the collected updates of location are probably redundant and inconsistent in a wide positioning system. To process distributed location streams with redundancy and inconsistency, this paper proposes a novel method based on min-wise hash. With this method, redundant updates of distributed location streams can be effiectively filtered out, while the true location could be derived from inconsistent ones. Consequently, globally uniform samples can be obtained. Based on the uniform samples, an algorithm for computing the approximate k-median of huge number of moving objects is presented in this paper. Furthermore, it is demonstrated that sketch-based methods are not necessarily effiective in processing location streams with redundancy and inconsistency. In addition to theoretical analysis, some extensive experiments are conducted to validate the efficiency and effiectiveness of the proposed approach.
keywords:data streams  k-median  approximate algorithm
View Full Text  View/Add Comment  Download reader



Top Paper  |  FAQ  |  Guest Editors  |  Email Alert  |  Links  |  Copyright  |  Contact Us

© Copyright by Institute of Software, the Chinese Academy of Sciences

京公网安备 11040202500065号