| 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: 3992 |
| Download times: 2934 |
|
| 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 |
|
|
|
