A Geometric Approach to Approximate Continuous k-Median Query
We revisit the classic k-median problem in continuous distributed model. The rapid advance in electronic miniaturization, wireless communication and position technologies makes a significant contribution to pervasive applications of continuous distributed model. Data sets acquired in continuous distributed model are automatically and continuously updated, or even distributed over a wide area in typical cases. The sequence of A-median at each time stamp in the continuous distributed model forms a Amedian series, which is called continuous k-median. Our main idea is to transform continuous appmedian problem to continuous A-median query, which applies a selection operation on continuous A-median. Because the result of this selection is a subset of A-median series, time and communication efficiency in the continuous distributed model can be achieved. The continuous A-median query provides an insightful structure of data sets along time dimension and widely applied in various cases such as locationbased services, sensor network monitor, and etc. In this paper, the time-efficiency of continuous kmedian query in a central paradigm is first studied where an efficient indicator function is designed to suppress unnecessary re-evaluations. Then, communication-efficiency of continuous kmedian query is addressed in a distributed paradigm where a geometric approach is applied to suppress unnecessary communications between nodes. Our approach to continuous A-median query distinguishes itself in two aspects. First, the indicator function is built on the aggregation distribution of data sets instead of prevailing safe region of individuals and timeefficiency can therefore be achieved. Second, a geometric approach is explored so that a single local node can trigger a re-valuation and therefore communication-efficiency can be obtained. Experiments are done to empirically demonstrate the time and communication efficiency of our approach on various data sets.
Zhihong Chong Jiajia Bao Weiwei Ni Aibo Song Yinghao Xie Jinwang Zheng
School of Computer Science and Engineering Southeast University, China, Nanjing 210096 School of Computer Science and Engineering Southeast University, China, anjing 210096
国际会议
2010 4th International Universal Communication Symposium(第四届国际普遍交流学术研讨会 IUCS 2010)
北京
英文
24-31
2010-10-18（万方平台首次上网日期，不代表论文的发表时间）